Provided by: tcllib_1.14-dfsg-1_all

**NAME**

pt::pegrammar - Introduction to Parsing Expression Grammars

**SYNOPSIS**

package requireTcl8.5_________________________________________________________________

**DESCRIPTION**

Are you lost ? Do you have trouble understanding this document ? In that case please read the overview provided by theIntroductiontoParserTools. This document is the entrypoint to the whole system the current package is a part of. Welcome to the introduction toParsingExpressionGrammars (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-FreeGrammars(short:CFG),languages, and associated terms likeLL(k),LR(k),terminalandnonterminalsymbols, etc. We do not intend to recapitulate such basic definitions or terms likeuseful,reachable, (left/right)recursive,nullable, first/last/follow sets, etc. Please see theReferencesat 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!) ofchoiceoperators. Where CFGs use anunorderedchoiceto represent alternatives PEGs useprioritizedchoice. 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 choicedeterministicwith a boundedlookaheadof k terminal symbols, where LL is in essencetopdownakarecursivedescentparsing, and LRbottomupakashiftreduceparsing. On the PEG side we can parse input with recursive descent andbacktrackingof 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 behindpackratparsers. A limitation pure PEGs share with LL(k) CFGs is thatleft-recursivegrammars 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 thekleeneclosureandpositivekleeneclosure. 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 viastringis. 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 ofnonterminalsymbols, · VT is a set ofterminalsymbols, · R is a finite set of rules, where each rule is a pair (A,e), A in VN, andeaparsingexpression. · eS is a parsing expression, thestartexpression. 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 symbolais a parsing expression. · A nonterminal symbolAis a parsing expression. ·e1e2is a parsing expression for parsing expressionse1and2. This is calledsequence. ·e1/e2is a parsing expression for parsing expressionse1and2. This is calledorderedchoice. ·e* is a parsing expression for parsing expressione. This is calledzero-or-morerepetitions, also known askleeneclosure. ·e+ is a parsing expression for parsing expressione. This is calledone-or-morerepetitions, also known aspositivekleeneclosure. · !eis a parsing expression for parsing expressione1. This is called anotlookaheadpredicate. · &eis a parsing expression for parsing expressione1. This is called anandlookaheadpredicate. 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]ThePackratParsingandParsingExpressionGrammarsPage[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_grammarWikipedia's entry about Parsing Expression Grammars. [3]ParsingTechniques-APracticalGuide[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]CompilersandCompilerGenerators[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 categoryptof theTcllibSFTrackers[http://sourceforge.net/tracker/?group_id=12883]. Please also report any ideas for enhancements you may have for either package and/or documentation.

**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>