Provided by: tcllib_1.14-dfsg-1_all

**NAME**

grammar::peg - Create and manipulate parsing expression grammars

**SYNOPSIS**

package requireTcl8.4package requiresnitpackage requiregrammar::peg?0.1?::grammar::pegpegName?=|:=|<--|as|deserializesrc?pegNamedestroypegNameclearpegName=srcPEGpegName-->dstPEGpegNameserializepegNamedeserializeserializationpegNameisvalidpegNamestart?pe?pegNamenonterminalspegNamenonterminaladdntpepegNamenonterminaldeletent1?nt2...?pegNamenonterminalexistsntpegNamenonterminalrenamentntnewpegNamenonterminalmodent?mode?pegNamenonterminalrulentpegNameunknownnonterminals_________________________________________________________________

**DESCRIPTION**

This package provides a container class forparsingexpressiongrammars(Short: PEG). It allows the incremental definition of the grammar, its manipulation and querying of the definition. The package neither provides complex operations on the grammar, nor has it the ability to execute a grammar definition for a stream of symbols. Two packages related to this one aregrammar::mengineandgrammar::peg::interpreter. The first of them defines a general virtual machine for the matching of a character stream, and the second implements an interpreter for parsing expression grammars on top of that virtual machine.TERMS&CONCEPTSPEGs are similar to context-free grammars, but not equivalent; in some cases PEGs are strictly more powerful than context-free grammars (there exist PEGs for some non-context- free languages). The formal mathematical definition of parsing expressions and parsing expression grammars can be found in sectionPARSINGEXPRESSIONGRAMMARS. In short, we haveterminalsymbols, which are the most basic building blocks forsentences, andnonterminalsymbolswith associatedparsingexpressions, defining the grammatical structure of the sentences. The two sets of symbols are distinctive, and do not overlap. When speaking about symbols the word "symbol" is often left out. The union of the sets of terminal and nonterminal symbols is called the set ofsymbols. Here the set ofterminalsymbolsis not explicitly managed, but implicitly defined as the set of all characters. Note that this means that we inherit from Tcl the ability to handle all of Unicode. A pair ofnonterminalandparsingexpressionis also called agrammaticalrule, orrulefor short. In the context of a rule the nonterminal is often called the left-hand-side (LHS), and the parsing expression the right-hand-side (RHS). Thestartexpressionof a grammar is a parsing expression from which all the sentences contained in the language specified by the grammar arederived. To make the understanding of this term easier let us assume for a moment that the RHS of each rule, and the start expression, is either a sequence of symbols, or a series of alternate parsing expressions. In the latter case the rule can be seen as a set of rules, each providing one alternative for the nonterminal. A parsing expression A' is now a derivation of a parsing expression A if we pick one of the nonterminals N in the expression, and one of the alternative rules R for N, and then replace the nonterminal in A with the RHS of the chosen rule. Here we can see why the terminal symbols are called such. They cannot be expanded any further, thus terminate the process of deriving new expressions. An example Rules (1) A <- a B c (2a) B <- d B (2b) B <- e Some derivations, using starting expression A. A -/1/-> a B c -/2a/-> a d B c -/2b/-> a d e c A derived expression containing only terminal symbols is asentence. The set of all sentences which can be derived from the start expression is thelanguageof the grammar. Some definitions for nonterminals and expressions: [1] A nonterminal A is calledreachableif it is possible to derive a parsing expression from the start expression which contains A. [2] A nonterminal A is calledusefulif it is possible to derive a sentence from it. [3] A nonterminal A is calledrecursiveif it is possible to derive a parsing expression from it which contains A, again. [4] TheFIRSTsetof a nonterminal A contains all the symbols which can occur of as the leftmost symbol in a parsing expression derived from A. If the FIRST set contains A itself then that nonterminal is calledleft-recursive. [5] TheLASTsetof a nonterminal A contains all the symbols which can occur of as the rightmost symbol in a parsing expression derived from A. If the LAST set contains A itself then that nonterminal is calledright-recursive. [6] TheFOLLOWsetof a nonterminal A contains all the symbols which can occur after A in a parsing expression derived from the start expression. [7] A nonterminal (or parsing expression) is callednullableif the empty sentence can be derived from it. And based on the above definitions for grammars: [1] A grammar G isrecursiveif and only if it contains a nonterminal A which is recursive. The termsleft-andright-recursive, andusefulare analogously defined. [2] A grammar isminimalif it contains onlyreachableandusefulnonterminals. [3] A grammar iswellformedif it is not left-recursive. Such grammars are alsocomplete, which means that they always succeed or fail on all input sentences. For an incomplete grammar on the other hand input sentences exist for which an attempt to match them against the grammar will not terminate. [4] As we wish to allow ourselves to build a grammar incrementally in a container object we will encounter stages where the RHS of one or more rules reference symbols which are not yet known to the container. Such a grammar we callinvalid. We cannot use the termincompleteas this term is already taken, see the last item.CONTAINERCLASSAPIThe package exports the API described here.::grammar::pegpegName?=|:=|<--|as|deserializesrc? The command creates a new container object for a parsing expression grammar and returns the fully qualified name of the object command as its result. The API the returned command is following is described in the sectionCONTAINEROBJECTAPI. It may be used to invoke various operations on the container and the grammar within. The new container, i.e. grammar will be empty if nosrcis specified. Otherwise it will contain a copy of the grammar contained in thesrc. Thesrchas to be a container object reference for all operators exceptdeserialize. Thedeserializeoperator requiressrcto be the serialization of a parsing expression grammar instead. An empty grammar has no nonterminal symbols, and the start expression is the empty expression, i.e. epsilon. It isvalid, but notuseful.CONTAINEROBJECTAPIAll grammar container objects provide the following methods for the manipulation of their contents:pegNamedestroyDestroys the grammar, including its storage space and associated command.pegNameclearClears out the definition of the grammar contained inpegName, but doesnotdestroy the object.pegName=srcPEGAssigns the contents of the grammar contained insrcPEGtopegName, overwriting any existing definition. This is the assignment operator for grammars. It copies the grammar contained in the grammar objectsrcPEGover the grammar definition inpegName. The old contents ofpegNameare deleted by this operation. This operation is in effect equivalent topegNamedeserialize[srcPEGserialize]pegName-->dstPEGThis is the reverse assignment operator for grammars. It copies the automation contained in the objectpegNameover the grammar definition in the objectdstPEG. The old contents ofdstPEGare deleted by this operation. This operation is in effect equivalent todstPEGdeserialize[pegNameserialize]pegNameserializeThis method serializes the grammar stored inpegName. In other words it returns a tclvaluecompletely describing that grammar. This allows, for example, the transfer of grammars over arbitrary channels, persistence, etc. This method is also the basis for both the copy constructor and the assignment operator. The result of this method has to be semantically identical over all implementations of thegrammar::peginterface. This is what will enable us to copy grammars between different implementations of the same interface. The result is a list of four elements with the following structure: [1] The constant stringgrammar::peg. [2] A dictionary. Its keys are the names of all known nonterminal symbols, and their associated values are the parsing expressions describing their sentennial structure. [3] A dictionary. Its keys are the names of all known nonterminal symbols, and their associated values hints to a matcher regarding the semantic values produced by the symbol. [4] The last item is a parsing expression, thestartexpressionof the grammar. Assuming the following PEG for simple mathematical expressions Digit <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9' Sign <- '+' / '-' Number <- Sign? Digit+ Expression <- '(' Expression ')' / (Factor (MulOp Factor)*) MulOp <- '*' / '/' Factor <- Term (AddOp Term)* AddOp <- '+'/'-' Term <- Number a possible serialization is grammar::peg \\ {Expression {/ {x ( Expression )} {x Factor {* {x MulOp Factor}}}} \\ Factor {x Term {* {x AddOp Term}}} \\ Term Number \\ MulOp {/ * /} \\ AddOp {/ + -} \\ Number {x {? Sign} {+ Digit}} \\ Sign {/ + -} \\ Digit {/ 0 1 2 3 4 5 6 7 8 9} \\ } \\ {Expression value Factor value \\ Term value MulOp value \\ AddOp value Number value \\ Sign value Digit value \\ } Expression A possible one, because the order of the nonterminals in the dictionary is not relevant.pegNamedeserializeserializationThis is the complement toserialize. It replaces the grammar definition inpegNamewith the grammar described by theserializationvalue. The old contents ofpegNameare deleted by this operation.pegNameisvalidA predicate. It tests whether the PEG inpegNameisvalid. See sectionTERMS&CONCEPTSfor the definition of this grammar property. The result is a boolean value. It will be set totrueif the PEG has the tested property, andfalseotherwise.pegNamestart?pe? This method defines thestartexpressionof the grammar. It replaces the previously defined start expression with the parsing expressionpe. The method fails and throws an error ifpedoes not contain a valid parsing expression as specified in the sectionPARSINGEXPRESSIONS. In that case the existing start expression is not changed. The method returns the empty string as its result. If the method is called without an argument it will return the currently defined start expression.pegNamenonterminalsReturns the set of all nonterminal symbols known to the grammar.pegNamenonterminaladdntpeThis method adds the nonterminalntand its associated parsing expressionpeto the set of nonterminal symbols and rules of the PEG contained in the objectpegName. The method fails and throws an error if either the stringntis already known as a symbol of the grammar, or ifpedoes not contain a valid parsing expression as specified in the sectionPARSINGEXPRESSIONS. In that case the current set of nonterminal symbols and rules is not changed. The method returns the empty string as its result.pegNamenonterminaldeletent1?nt2...? This method removes the named symbolsnt1,nt2from the set of nonterminal symbols of the PEG contained in the objectpegName. The method fails and throws an error if any of the strings is not known as a nonterminal symbol. In that case the current set of nonterminal symbols is not changed. The method returns the empty string as its result. The stored grammar becomes invalid if the deleted nonterminals are referenced by the RHS of still-known rules.pegNamenonterminalexistsntA predicate. It tests whether the nonterminal symbolntis known to the PEG inpegName. The result is a boolean value. It will be set totrueif the symbolntis known, andfalseotherwise.pegNamenonterminalrenamentntnewThis method renames the nonterminal symbolnttontnew. The method fails and throws an error if eitherntis not known as a nonterminal, or ifntnewis a known symbol. The method returns the empty string as its result.pegNamenonterminalmodent?mode? This mode returns or sets the semantic mode associated with the nonterminal symbolnt. If nomodeis specified the current mode of the nonterminal is returned. Otherwise the current mode is set tomode. The method fails and throws an error ifntis not known as a nonterminal. The grammar interpreter implemented by the packagegrammar::peg::interpreterrecognizes the following modes: value The semantic value of the nonterminal is the abstract syntax tree created from the AST's of the RHS and a node for the nonterminal itself. match The semantic value of the nonterminal is an the abstract syntax tree consisting of single a node for the string matched by the RHS. The ASTs generated by the RHS are discarded. leaf The semantic value of the nonterminal is an the abstract syntax tree consisting of single a node for the nonterminal itself. The ASTs generated by the RHS are discarded. discard The nonterminal has no semantic value. The ASTs generated by the RHS are discarded (as well).pegNamenonterminalrulentThis method returns the parsing expression associated with the nonterminalnt. The method fails and throws an error ifntis not known as a nonterminal.pegNameunknownnonterminalsThis method returns a list containing the names of all nonterminal symbols which are referenced on the RHS of a grammatical rule, but have no rule definining their structure. In other words, a list of the nonterminal symbols which make the grammar invalid. The grammar is valid if this list is empty.PARSINGEXPRESSIONSVarious methods of PEG container objects expect a parsing expression as their argument, or will return such. This section specifies the format such parsing expressions are in. [1] The stringepsilonis an atomic parsing expression. It matches the empty string. [2] The stringalnumis an atomic parsing expression. It matches any alphanumeric character. [3] The stringalphais an atomic parsing expression. It matches any alphabetical character. [4] The stringdotis an atomic parsing expression. It matches any character. [5] The expression [list tx] is an atomic parsing expression. It matches the terminal stringx. [6] The expression [list nA] is an atomic parsing expression. It matches the nonterminalA. [7] For parsing expressionse1,e2, ... the result of [list /e1e2... ] is a parsing expression as well. This is theorderedchoice, akaprioritizedchoice. [8] For parsing expressionse1,e2, ... the result of [list xe1e2... ] is a parsing expression as well. This is thesequence. [9] For a parsing expressionethe result of [list *e] is a parsing expression as well. This is thekleeneclosure, describing zero or more repetitions. [10] For a parsing expressionethe result of [list +e] is a parsing expression as well. This is thepositivekleeneclosure, describing one or more repetitions. [11] For a parsing expressionethe result of [list &e] is a parsing expression as well. This is theandlookaheadpredicate. [12] For a parsing expressionethe result of [list !e] is a parsing expression as well. This is thenotlookaheadpredicate. [13] For a parsing expressionethe result of [list ?e] is a parsing expression as well. This is theoptionalinput. Examples of parsing expressions where already shown, in the description of the methodserialize.

**PARSING** **EXPRESSION** **GRAMMARS**

For the mathematically inclined, a PEG 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 expression 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]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. [3]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 categorygrammar_pegof 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**

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

**CATEGORY**

Grammars and finite automata

**COPYRIGHT**

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