Scroll to navigation

pt::pegrammar(3tcl) Parser Tools pt::pegrammar(3tcl) 





NAME


pt::pegrammar - Introduction to Parsing Expression Grammars






SYNOPSIS


package require Tcl 8.5 9










DESCRIPTION


Are you lost ? Do you have trouble understanding this document ?
    In that case please read the overview provided by the Introduction to
    Parser Tools. This document is the entrypoint to the whole system the
    current package is a part of.


Welcome to the introduction to Parsing Expression Grammars
    (short: PEG), the formalism used by the Parser Tools. It is assumed
    that the reader has a basic knowledge of parsing theory, i.e.
    Context-Free Grammars (short: CFG), languages, and
    associated terms like LL(k), LR(k), terminal and
    nonterminal symbols, etc. We do not intend to recapitulate
    such basic definitions or terms like useful, reachable,
    (left/right) recursive, nullable, first/last/follow sets, etc.
    Please see the References at the end instead if you are in need of
    places and books which provide such background information.


PEGs are formally very similar to CFGs, with terminal and
    nonterminal symbols, start symbol, and rules defining the structure of each
    nonterminal symbol. The main difference lies in the choice(sic!) of
    choice operators. Where CFGs use an unordered choice to
    represent alternatives PEGs use prioritized choice. Which is fancy
    way of saying that a parser has to try the first alternative first and can
    try the other alternatives if only if it fails for the first, and so on.


On the CFG side this gives rise to LL(k) and LR(k) for making the
    choice deterministic with a bounded lookahead of k terminal
    symbols, where LL is in essence topdown aka recursive descent
    parsing, and LR bottomup aka shift reduce parsing.


On the PEG side we can parse input with recursive descent and
    backtracking of failed choices, the latter of which amounts to
    unlimited lookahead. By additionally recording the success or failure of
    nonterminals at the specific locations they were tried at and reusing this
    information after backtracking we can avoid the exponential blowup of
    running time usually associated with backtracking and keep the parsing
    linear. The memory requirements are of course higher due to this cache, as
    we are trading space for time.


This is the basic concept behind packrat parsers.


A limitation pure PEGs share with LL(k) CFGs is that
    left-recursive grammars cannot be parsed, with the associated
    recursive descent parser entering an infinite recursion. This limitation is
    usually overcome by extending pure PEGs with explicit operators to specify
    repetition, zero or more, and one or more, or, formally spoken, for the
    kleene closure and positive kleene closure. This is what the
    Parser Tools are doing.


Another extension, specific to Parser Tools, is a set of operators
    which map more or less directly to various character classes built into Tcl,
    i.e. the classes reachable via string is.


The remainder of this document consists of the formal definition
    of PEGs for the mathematically inclined, and an appendix listing references
    to places with more information on PEGs specifically, and parsing in
    general.






FORMAL DEFINITION


For the mathematically inclined, a Parsing Expression Grammar is a
    4-tuple (VN,VT,R,eS) where


    
  
  • VN is a set of nonterminal symbols,
    • 
  
  • VT is a set of terminal symbols,
    • 
  
  • R is a finite set of rules, where each rule is a pair (A,e), A in VN, and
      e a parsing expression.
    • 
  
  • eS is a parsing expression, the start expression.
    • 



Further constraints are


    
  
  • The intersection of VN and VT is empty.
    • 
  
  • For all A in VT exists exactly one pair (A,e) in R. In other words, R is a
      function from nonterminal symbols to parsing expressions.
    • 



Parsing expressions are inductively defined via


    
  
  • The empty string (epsilon) is a parsing expression.
    • 
  
  • A terminal symbol a is a parsing expression.
    • 
  
  • A nonterminal symbol A is a parsing expression.
    • 
  
  • e1e2 is a parsing expression for parsing expressions
      e1 and 2. This is called sequence.
    • 
  
  • e1/e2 is a parsing expression for parsing expressions
      e1 and 2. This is called ordered choice.
    • 
  
  • e* is a parsing expression for parsing expression e. This is
      called zero-or-more repetitions, also known as kleene
      closure.
    • 
  
  • e+ is a parsing expression for parsing expression e. This is
      called one-or-more repetitions, also known as positive kleene
      closure.
    • 
  
  • !e is a parsing expression for parsing expression e1. This
      is called a not lookahead predicate.
    • 
  
  • &e is a parsing expression for parsing expression e1.
      This is called an and lookahead predicate.
    • 



PEGs are used to define a grammatical structure for streams of
    symbols over VT. They are a modern phrasing of older formalisms invented by
    Alexander Birham. These formalisms were called TS (TMG recognition scheme),
    and gTS (generalized TS). Later they were renamed to TPDL (Top-Down Parsing
    Languages) and gTPDL (generalized TPDL).


They can be easily implemented by recursive descent parsers with
    backtracking. This makes them relatives of LL(k) Context-Free Grammars.






REFERENCES



  
[1]

  
The Packrat Parsing and Parsing Expression Grammars Page
      [http://www.pdos.lcs.mit.edu/~baford/packrat/], by Bryan Ford,
      Massachusetts Institute of Technology. This is the main entry page to
      PEGs, and their realization through Packrat Parsers.

  
[2]

  
http://en.wikipedia.org/wiki/Parsing_expression_grammar Wikipedia's
      entry about Parsing Expression Grammars.

  
[3]

  
Parsing Techniques - A Practical Guide 
      [http://www.cs.vu.nl/~dick/PTAPG.html], an online book offering a clear,
      accessible, and thorough discussion of many different parsing techniques
      with their interrelations and applicabilities, including error recovery
      techniques.

  
[4]

  
Compilers and Compiler Generators
      [http://scifac.ru.ac.za/compilers/], an online book using CoCo/R, a
      generator for recursive descent parsers.








BUGS, IDEAS, FEEDBACK


This document, and the package it describes, will undoubtedly
    contain bugs and other problems. Please report such in the category
    pt of the Tcllib Trackers
    [http://core.tcl.tk/tcllib/reportlist]. Please also report any ideas for
    enhancements you may have for either package and/or documentation.


When proposing code changes, please provide unified diffs,
    i.e the output of diff -u.


Note further that attachments are strongly preferred over
    inlined patches. Attachments can be made by going to the Edit form of
    the ticket immediately after its creation, and then using the left-most
    button in the secondary navigation bar.






KEYWORDS


EBNF, LL(k), PEG, TDPL, context-free languages, expression,
    grammar, matching, parser, parsing expression, parsing expression grammar,
    push down automaton, recursive descent, state, top-down parsing languages,
    transducer






CATEGORY


Parsing and Grammars






COPYRIGHT


Copyright (c) 2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>








  

    1.1
    tcllib