This package provides a container class for parsingexpressiongrammars (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 are grammar::mengine and
grammar::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&CONCEPTS
PEGs 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 section
PARSINGEXPRESSIONGRAMMARS.
In short, we have terminalsymbols, which are the most basic building blocks for sentences, and
nonterminalsymbols with associated parsingexpressions, 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 of symbols.
Here the set of terminalsymbols is 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 of nonterminal and parsingexpression is also called a grammaticalrule, or rule for 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).
The startexpression of a grammar is a parsing expression from which all the sentences contained in the
language specified by the grammar are derived. 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 a sentence. The set of all sentences which can
be derived from the start expression is the language of the grammar.
Some definitions for nonterminals and expressions:
[1] A nonterminal A is called reachable if it is possible to derive a parsing expression from the
start expression which contains A.
[2] A nonterminal A is called useful if it is possible to derive a sentence from it.
[3] A nonterminal A is called recursive if it is possible to derive a parsing expression from it which
contains A, again.
[4] The FIRSTset of 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 called left-recursive.
[5] The LASTset of 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 called right-recursive.
[6] The FOLLOWset of 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 called nullable if the empty sentence can be derived from
it.
And based on the above definitions for grammars:
[1] A grammar G is recursive if and only if it contains a nonterminal A which is recursive. The terms
left- and right-recursive, and useful are analogously defined.
[2] A grammar is minimal if it contains only reachable and useful nonterminals.
[3] A grammar is wellformed if it is not left-recursive. Such grammars are also complete, 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 call invalid. We cannot use the term incomplete as this term is
already taken, see the last item.
CONTAINERCLASSAPI
The 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 section CONTAINEROBJECTAPI. 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 no src is specified. Otherwise it will contain a
copy of the grammar contained in the src. The src has to be a container object reference for all
operators except deserialize. The deserialize operator requires src to 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 is valid, but not useful.
CONTAINEROBJECTAPI
All grammar container objects provide the following methods for the manipulation of their contents:
pegNamedestroy
Destroys the grammar, including its storage space and associated command.
pegNameclear
Clears out the definition of the grammar contained in pegName, but does not destroy the object.
pegName=srcPEG
Assigns the contents of the grammar contained in srcPEG to pegName, overwriting any existing
definition. This is the assignment operator for grammars. It copies the grammar contained in the
grammar object srcPEG over the grammar definition in pegName. The old contents of pegName are
deleted by this operation.
This operation is in effect equivalent to
pegNamedeserialize [srcPEGserialize]
pegName-->dstPEG
This is the reverse assignment operator for grammars. It copies the automation contained in the
object pegName over the grammar definition in the object dstPEG. The old contents of dstPEG are
deleted by this operation.
This operation is in effect equivalent to
dstPEGdeserialize [pegNameserialize]
pegNameserialize
This method serializes the grammar stored in pegName. In other words it returns a tcl value
completely 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 the
grammar::peg interface. 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 string grammar::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, the startexpression of 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.
pegNamedeserializeserialization
This is the complement to serialize. It replaces the grammar definition in pegName with the
grammar described by the serialization value. The old contents of pegName are deleted by this
operation.
pegNameisvalid
A predicate. It tests whether the PEG in pegName is valid. See section TERMS&CONCEPTS for the
definition of this grammar property. The result is a boolean value. It will be set to true if the
PEG has the tested property, and false otherwise.
pegNamestart ?pe?
This method defines the startexpression of the grammar. It replaces the previously defined start
expression with the parsing expression pe. The method fails and throws an error if pe does not
contain a valid parsing expression as specified in the section PARSINGEXPRESSIONS. 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.
pegNamenonterminals
Returns the set of all nonterminal symbols known to the grammar.
pegNamenonterminaladdntpe
This method adds the nonterminal nt and its associated parsing expression pe to the set of
nonterminal symbols and rules of the PEG contained in the object pegName. The method fails and
throws an error if either the string nt is already known as a symbol of the grammar, or if pe does
not contain a valid parsing expression as specified in the section PARSINGEXPRESSIONS. 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 symbols nt1, nt2 from the set of nonterminal symbols of the PEG
contained in the object pegName. 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.
pegNamenonterminalexistsnt
A predicate. It tests whether the nonterminal symbol nt is known to the PEG in pegName. The
result is a boolean value. It will be set to true if the symbol nt is known, and false otherwise.
pegNamenonterminalrenamentntnew
This method renames the nonterminal symbol nt to ntnew. The method fails and throws an error if
either nt is not known as a nonterminal, or if ntnew is 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 symbol nt. If no mode
is specified the current mode of the nonterminal is returned. Otherwise the current mode is set to
mode. The method fails and throws an error if nt is not known as a nonterminal. The grammar
interpreter implemented by the package grammar::peg::interpreter recognizes 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).
pegNamenonterminalrulent
This method returns the parsing expression associated with the nonterminal nt. The method fails
and throws an error if nt is not known as a nonterminal.
pegNameunknownnonterminals
This 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.
PARSINGEXPRESSIONS
Various 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 string epsilon is an atomic parsing expression. It matches the empty string.
[2] The string alnum is an atomic parsing expression. It matches any alphanumeric character.
[3] The string alpha is an atomic parsing expression. It matches any alphabetical character.
[4] The string dot is an atomic parsing expression. It matches any character.
[5] The expression [list t x] is an atomic parsing expression. It matches the terminal string x.
[6] The expression [list n A] is an atomic parsing expression. It matches the nonterminal A.
[7] For parsing expressions e1, e2, ... the result of [list / e1e2 ... ] is a parsing expression as
well. This is the orderedchoice, aka prioritizedchoice.
[8] For parsing expressions e1, e2, ... the result of [list x e1e2 ... ] is a parsing expression as
well. This is the sequence.
[9] For a parsing expression e the result of [list * e] is a parsing expression as well. This is the
kleeneclosure, describing zero or more repetitions.
[10] For a parsing expression e the result of [list + e] is a parsing expression as well. This is the
positivekleeneclosure, describing one or more repetitions.
[11] For a parsing expression e the result of [list & e] is a parsing expression as well. This is the
andlookaheadpredicate.
[12] For a parsing expression e the result of [list ! e] is a parsing expression as well. This is the
notlookaheadpredicate.
[13] For a parsing expression e the result of [list ? e] is a parsing expression as well. This is the
optionalinput.
Examples of parsing expressions where already shown, in the description of the method serialize.
Install Now
PNG Icons