'\"
'\" Generated from file 'peg\&.man' by tcllib/doctools with format 'nroff'
'\" Copyright (c) 2005 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>
'\"
.TH "grammar::peg" n 0\&.1 tcllib "Grammar operations and usage"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,
.\"	and indent is equivalent to second arg of .IP (shouldn't ever be
.\"	needed;  use .AS below instead)
.\"
.\" .AS ?type? ?name?
.\"	Give maximum sizes of arguments for setting tab stops.  Type and
.\"	name are examples of largest possible arguments that will be passed
.\"	to .AP later.  If args are omitted, default tab stops are used.
.\"
.\" .BS
.\"	Start box enclosure.  From here until next .BE, everything will be
.\"	enclosed in one large box.
.\"
.\" .BE
.\"	End of box enclosure.
.\"
.\" .CS
.\"	Begin code excerpt.
.\"
.\" .CE
.\"	End code excerpt.
.\"
.\" .VS ?version? ?br?
.\"	Begin vertical sidebar, for use in marking newly-changed parts
.\"	of man pages.  The first argument is ignored and used for recording
.\"	the version when the .VS was added, so that the sidebars can be
.\"	found and removed when they reach a certain age.  If another argument
.\"	is present, then a line break is forced before starting the sidebar.
.\"
.\" .VE
.\"	End of vertical sidebar.
.\"
.\" .DS
.\"	Begin an indented unfilled display.
.\"
.\" .DE
.\"	End of indented unfilled display.
.\"
.\" .SO ?manpage?
.\"	Start of list of standard options for a Tk widget. The manpage
.\"	argument defines where to look up the standard options; if
.\"	omitted, defaults to "options". The options follow on successive
.\"	lines, in three columns separated by tabs.
.\"
.\" .SE
.\"	End of list of standard options for a Tk widget.
.\"
.\" .OP cmdName dbName dbClass
.\"	Start of description of a specific option.  cmdName gives the
.\"	option's name as specified in the class command, dbName gives
.\"	the option's name in the option database, and dbClass gives
.\"	the option's class in the option database.
.\"
.\" .UL arg1 arg2
.\"	Print arg1 underlined, then print arg2 normally.
.\"
.\" .QW arg1 ?arg2?
.\"	Print arg1 in quotes, then arg2 normally (for trailing punctuation).
.\"
.\" .PQ arg1 ?arg2?
.\"	Print an open parenthesis, arg1 in quotes, then arg2 normally
.\"	(for trailing punctuation) and then a closing parenthesis.
.\"
.\"	# Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
.if t .wh -1.3i ^B
.nr ^l \n(.l
.ad b
.\"	# Start an argument description
.de AP
.ie !"\\$4"" .TP \\$4
.el \{\
.   ie !"\\$2"" .TP \\n()Cu
.   el          .TP 15
.\}
.ta \\n()Au \\n()Bu
.ie !"\\$3"" \{\
\&\\$1 \\fI\\$2\\fP (\\$3)
.\".b
.\}
.el \{\
.br
.ie !"\\$2"" \{\
\&\\$1	\\fI\\$2\\fP
.\}
.el \{\
\&\\fI\\$1\\fP
.\}
.\}
..
.\"	# define tabbing values for .AP
.de AS
.nr )A 10n
.if !"\\$1"" .nr )A \\w'\\$1'u+3n
.nr )B \\n()Au+15n
.\"
.if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
.nr )C \\n()Bu+\\w'(in/out)'u+2n
..
.AS Tcl_Interp Tcl_CreateInterp in/out
.\"	# BS - start boxed text
.\"	# ^y = starting y location
.\"	# ^b = 1
.de BS
.br
.mk ^y
.nr ^b 1u
.if n .nf
.if n .ti 0
.if n \l'\\n(.lu\(ul'
.if n .fi
..
.\"	# BE - end boxed text (draw box now)
.de BE
.nf
.ti 0
.mk ^t
.ie n \l'\\n(^lu\(ul'
.el \{\
.\"	Draw four-sided box normally, but don't draw top of
.\"	box if the box started on an earlier page.
.ie !\\n(^b-1 \{\
\h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.el \}\
\h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.\}
.fi
.br
.nr ^b 0
..
.\"	# VS - start vertical sidebar
.\"	# ^Y = starting y location
.\"	# ^v = 1 (for troff;  for nroff this doesn't matter)
.de VS
.if !"\\$2"" .br
.mk ^Y
.ie n 'mc \s12\(br\s0
.el .nr ^v 1u
..
.\"	# VE - end of vertical sidebar
.de VE
.ie n 'mc
.el \{\
.ev 2
.nf
.ti 0
.mk ^t
\h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
.sp -1
.fi
.ev
.\}
.nr ^v 0
..
.\"	# Special macro to handle page bottom:  finish off current
.\"	# box/sidebar if in box/sidebar mode, then invoked standard
.\"	# page bottom macro.
.de ^B
.ev 2
'ti 0
'nf
.mk ^t
.if \\n(^b \{\
.\"	Draw three-sided box if this is the box's first page,
.\"	draw two sides but no top otherwise.
.ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.\}
.if \\n(^v \{\
.nr ^x \\n(^tu+1v-\\n(^Yu
\kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
.\}
.bp
'fi
.ev
.if \\n(^b \{\
.mk ^y
.nr ^b 2
.\}
.if \\n(^v \{\
.mk ^Y
.\}
..
.\"	# DS - begin display
.de DS
.RS
.nf
.sp
..
.\"	# DE - end display
.de DE
.fi
.RE
.sp
..
.\"	# SO - start of list of standard options
.de SO
'ie '\\$1'' .ds So \\fBoptions\\fR
'el .ds So \\fB\\$1\\fR
.SH "STANDARD OPTIONS"
.LP
.nf
.ta 5.5c 11c
.ft B
..
.\"	# SE - end of list of standard options
.de SE
.fi
.ft R
.LP
See the \\*(So manual entry for details on the standard options.
..
.\"	# OP - start of full description for a single option
.de OP
.LP
.nf
.ta 4c
Command-Line Name:	\\fB\\$1\\fR
Database Name:	\\fB\\$2\\fR
Database Class:	\\fB\\$3\\fR
.fi
.IP
..
.\"	# CS - begin code excerpt
.de CS
.RS
.nf
.ta .25i .5i .75i 1i
..
.\"	# CE - end code excerpt
.de CE
.fi
.RE
..
.\"	# UL - underline word
.de UL
\\$1\l'|0\(ul'\\$2
..
.\"	# QW - apply quotation marks to word
.de QW
.ie '\\*(lq'"' ``\\$1''\\$2
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\$2
..
.\"	# PQ - apply parens and quotation marks to word
.de PQ
.ie '\\*(lq'"' (``\\$1''\\$2)\\$3
.\"" fix emacs highlighting
.el (\\*(lq\\$1\\*(rq\\$2)\\$3
..
.\"	# QR - quoted range
.de QR
.ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
..
.\"	# MT - "empty" string
.de MT
.QW ""
..
.BS
.SH NAME
grammar::peg \- Create and manipulate parsing expression grammars
.SH SYNOPSIS
package require \fBTcl  8\&.4\fR
.sp
package require \fBsnit \fR
.sp
package require \fBgrammar::peg  ?0\&.1?\fR
.sp
\fB::grammar::peg\fR \fIpegName\fR ?\fB=\fR|\fB:=\fR|\fB<--\fR|\fBas\fR|\fBdeserialize\fR \fIsrc\fR?
.sp
\fIpegName\fR \fBdestroy\fR
.sp
\fIpegName\fR \fBclear\fR
.sp
\fIpegName\fR \fB=\fR \fIsrcPEG\fR
.sp
\fIpegName\fR \fB-->\fR \fIdstPEG\fR
.sp
\fIpegName\fR \fBserialize\fR
.sp
\fIpegName\fR \fBdeserialize\fR \fIserialization\fR
.sp
\fIpegName\fR \fBis valid\fR
.sp
\fIpegName\fR \fBstart\fR ?\fIpe\fR?
.sp
\fIpegName\fR \fBnonterminals\fR
.sp
\fIpegName\fR \fBnonterminal add\fR \fInt\fR \fIpe\fR
.sp
\fIpegName\fR \fBnonterminal delete\fR \fInt1\fR ?\fInt2\fR \&.\&.\&.?
.sp
\fIpegName\fR \fBnonterminal exists\fR \fInt\fR
.sp
\fIpegName\fR \fBnonterminal rename\fR \fInt\fR \fIntnew\fR
.sp
\fIpegName\fR \fBnonterminal mode\fR \fInt\fR ?\fImode\fR?
.sp
\fIpegName\fR \fBnonterminal rule\fR \fInt\fR
.sp
\fIpegName\fR \fBunknown nonterminals\fR
.sp
.BE
.SH DESCRIPTION
.PP
This package provides a container class for
\fIparsing expression grammars\fR (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 \fBgrammar::mengine\fR and
\fBgrammar::peg::interpreter\fR\&. 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\&.
.SS "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
\fBPARSING EXPRESSION GRAMMARS\fR\&.
.PP
In short, we have \fIterminal symbols\fR, which are the most basic
building blocks for \fIsentences\fR, and \fInonterminal symbols\fR
with associated \fIparsing expressions\fR, 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 \fIsymbols\fR\&.
.PP
Here the set of \fIterminal symbols\fR 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\&.
.PP
A pair of \fInonterminal\fR and \fIparsing expression\fR is also
called a \fIgrammatical rule\fR, or \fIrule\fR 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)\&.
.PP
The \fIstart expression\fR of a grammar is a parsing expression
from which all the sentences contained in the language specified by
the grammar are \fIderived\fR\&.
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
.PP
.CS


    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

.CE
.PP
A derived expression containing only terminal symbols is a
\fIsentence\fR\&. The set of all sentences which can be derived from
the start expression is the \fIlanguage\fR of the grammar\&.
.PP
Some definitions for nonterminals and expressions:
.IP [1]
A nonterminal A is called \fIreachable\fR if it is possible to derive
a parsing expression from the start expression which contains A\&.
.IP [2]
A nonterminal A is called \fIuseful\fR if it is possible to derive a
sentence from it\&.
.IP [3]
A nonterminal A is called \fIrecursive\fR if it is possible to derive
a parsing expression from it which contains A, again\&.
.IP [4]
The \fIFIRST set\fR 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
\fIleft-recursive\fR\&.
.IP [5]
The \fILAST set\fR 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
\fIright-recursive\fR\&.
.IP [6]
The \fIFOLLOW set\fR of a nonterminal A contains all the symbols which
can occur after A in a parsing expression derived from the start
expression\&.
.IP [7]
A nonterminal (or parsing expression) is called \fInullable\fR if the
empty sentence can be derived from it\&.
.PP
.PP
And based on the above definitions for grammars:
.IP [1]
A grammar G is \fIrecursive\fR if and only if it contains a nonterminal
A which is recursive\&. The terms \fIleft-\fR and \fIright-recursive\fR,
and \fIuseful\fR are analogously defined\&.
.IP [2]
A grammar is \fIminimal\fR if it contains only \fIreachable\fR and
\fIuseful\fR nonterminals\&.
.IP [3]
A grammar is \fIwellformed\fR if it is not left-recursive\&. Such
grammars are also \fIcomplete\fR, 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\&.
.IP [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 \fIinvalid\fR\&.
We cannot use the term \fIincomplete\fR as this term is already
taken, see the last item\&.
.PP
.PP
.SS "CONTAINER CLASS API"
The package exports the API described here\&.
.TP
\fB::grammar::peg\fR \fIpegName\fR ?\fB=\fR|\fB:=\fR|\fB<--\fR|\fBas\fR|\fBdeserialize\fR \fIsrc\fR?
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 \fBCONTAINER OBJECT API\fR\&. It may be used to invoke
various operations on the container and the grammar within\&.
.sp
The new container, i\&.e\&. grammar will be empty if no \fIsrc\fR is
specified\&. Otherwise it will contain a copy of the grammar contained
in the \fIsrc\fR\&.
The \fIsrc\fR has to be a container object reference for all operators
except \fBdeserialize\fR\&.
The \fBdeserialize\fR operator requires \fIsrc\fR to be the
serialization of a parsing expression grammar instead\&.
.sp
An empty grammar has no nonterminal symbols, and the start expression
is the empty expression, i\&.e\&. epsilon\&. It is \fIvalid\fR, but not
\fIuseful\fR\&.
.PP
.SS "CONTAINER OBJECT API"
.PP
All grammar container objects provide the following methods for the
manipulation of their contents:
.TP
\fIpegName\fR \fBdestroy\fR
Destroys the grammar, including its storage space and associated
command\&.
.TP
\fIpegName\fR \fBclear\fR
Clears out the definition of the grammar contained in \fIpegName\fR,
but does \fInot\fR destroy the object\&.
.TP
\fIpegName\fR \fB=\fR \fIsrcPEG\fR
Assigns the contents of the grammar contained in \fIsrcPEG\fR to
\fIpegName\fR, overwriting any existing definition\&.
This is the assignment operator for grammars\&. It copies the grammar
contained in the grammar object \fIsrcPEG\fR over the grammar
definition in \fIpegName\fR\&. The old contents of \fIpegName\fR are
deleted by this operation\&.
.sp
This operation is in effect equivalent to
.sp
.CS


    \fIpegName\fR \fBdeserialize\fR [\fIsrcPEG\fR \fBserialize\fR]

.CE
.TP
\fIpegName\fR \fB-->\fR \fIdstPEG\fR
This is the reverse assignment operator for grammars\&. It copies the
automation contained in the object \fIpegName\fR over the grammar
definition in the object \fIdstPEG\fR\&.
The old contents of \fIdstPEG\fR are deleted by this operation\&.
.sp
This operation is in effect equivalent to
.sp
.CS


    \fIdstPEG\fR \fBdeserialize\fR [\fIpegName\fR \fBserialize\fR]

.CE
.TP
\fIpegName\fR \fBserialize\fR
This method serializes the grammar stored in \fIpegName\fR\&. In other
words it returns a tcl \fIvalue\fR 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\&.
.sp
The result of this method has to be semantically identical over all
implementations of the \fBgrammar::peg\fR interface\&. This is what
will enable us to copy grammars between different implementations of
the same interface\&.
.sp
The result is a list of four elements with the following structure:
.RS
.IP [1]
The constant string \fBgrammar::peg\fR\&.
.IP [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\&.
.IP [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\&.
.IP [4]
The last item is a parsing expression, the \fIstart expression\fR
of the grammar\&.
.RE
.sp
Assuming the following PEG for simple mathematical expressions
.sp
.CS


    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

.CE
.sp
a possible serialization is
.sp
.CS


    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

.CE
.sp
A possible one, because the order of the nonterminals in the
dictionary is not relevant\&.
.TP
\fIpegName\fR \fBdeserialize\fR \fIserialization\fR
This is the complement to \fBserialize\fR\&. It replaces the grammar
definition in \fIpegName\fR with the grammar described by the
\fIserialization\fR value\&. The old contents of \fIpegName\fR are
deleted by this operation\&.
.TP
\fIpegName\fR \fBis valid\fR
A predicate\&. It tests whether the PEG in \fIpegName\fR is \fIvalid\fR\&.
See section \fBTERMS & CONCEPTS\fR for the definition of this
grammar property\&.
The result is a boolean value\&. It will be set to \fBtrue\fR if
the PEG has the tested property, and \fBfalse\fR otherwise\&.
.TP
\fIpegName\fR \fBstart\fR ?\fIpe\fR?
This method defines the \fIstart expression\fR of the grammar\&. It
replaces the previously defined start expression with the parsing
expression \fIpe\fR\&.
The method fails and throws an error if \fIpe\fR does not contain a
valid parsing expression as specified in the section
\fBPARSING EXPRESSIONS\fR\&. In that case the existing start
expression is not changed\&.
The method returns the empty string as its result\&.
.sp
If the method is called without an argument it will return the currently
defined start expression\&.
.TP
\fIpegName\fR \fBnonterminals\fR
Returns the set of all nonterminal symbols known to the grammar\&.
.TP
\fIpegName\fR \fBnonterminal add\fR \fInt\fR \fIpe\fR
This method adds the nonterminal \fInt\fR and its associated parsing
expression \fIpe\fR to the set of nonterminal symbols and rules of the
PEG contained in the object \fIpegName\fR\&.
The method fails and throws an error if either the string \fInt\fR is
already known as a symbol of the grammar, or if \fIpe\fR does not
contain a valid parsing expression as specified in the section
\fBPARSING EXPRESSIONS\fR\&. In that case the current set of
nonterminal symbols and rules is not changed\&.
The method returns the empty string as its result\&.
.TP
\fIpegName\fR \fBnonterminal delete\fR \fInt1\fR ?\fInt2\fR \&.\&.\&.?
This method removes the named symbols \fInt1\fR, \fInt2\fR from the
set of nonterminal symbols of the PEG contained in the object
\fIpegName\fR\&.
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\&.
.sp
The stored grammar becomes invalid if the deleted nonterminals are
referenced by the RHS of still-known rules\&.
.TP
\fIpegName\fR \fBnonterminal exists\fR \fInt\fR
A predicate\&. It tests whether the nonterminal symbol \fInt\fR is known
to the PEG in \fIpegName\fR\&.
The result is a boolean value\&. It will be set to \fBtrue\fR if the
symbol \fInt\fR is known, and \fBfalse\fR otherwise\&.
.TP
\fIpegName\fR \fBnonterminal rename\fR \fInt\fR \fIntnew\fR
This method renames the nonterminal symbol \fInt\fR to \fIntnew\fR\&.
The method fails and throws an error if either \fInt\fR is not known
as a nonterminal, or if \fIntnew\fR is a known symbol\&.
The method returns the empty string as its result\&.
.TP
\fIpegName\fR \fBnonterminal mode\fR \fInt\fR ?\fImode\fR?
This mode returns or sets the semantic mode associated with the
nonterminal symbol \fInt\fR\&. If no \fImode\fR is specified the
current mode of the nonterminal is returned\&. Otherwise the current
mode is set to \fImode\fR\&.
The method fails and throws an error if \fInt\fR is not known as a
nonterminal\&.
The grammar interpreter implemented by the package
\fBgrammar::peg::interpreter\fR recognizes the
following modes:
.RS
.TP
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\&.
.TP
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\&.
.TP
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\&.
.TP
discard
The nonterminal has no semantic value\&. The ASTs generated by the RHS
are discarded (as well)\&.
.RE
.TP
\fIpegName\fR \fBnonterminal rule\fR \fInt\fR
This method returns the parsing expression associated with the
nonterminal \fInt\fR\&.
The method fails and throws an error if \fInt\fR is not known as a
nonterminal\&.
.TP
\fIpegName\fR \fBunknown nonterminals\fR
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\&.
.PP
.PP
.SS "PARSING EXPRESSIONS"
.PP
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\&.
.PP
.IP [1]
The string \fBepsilon\fR is an atomic parsing expression\&. It matches
the empty string\&.
.IP [2]
The string \fBalnum\fR is an atomic parsing expression\&. It matches
any alphanumeric character\&.
.IP [3]
The string \fBalpha\fR is an atomic parsing expression\&. It matches
any alphabetical character\&.
.IP [4]
The string \fBdot\fR is an atomic parsing expression\&. It matches
any character\&.
.IP [5]
The expression
[list t \fBx\fR]
is an atomic parsing expression\&. It matches the terminal string \fBx\fR\&.
.IP [6]
The expression
[list n \fBA\fR]
is an atomic parsing expression\&. It matches the nonterminal \fBA\fR\&.
.IP [7]
For parsing expressions \fBe1\fR, \fBe2\fR, \&.\&.\&. the result of
[list / \fBe1\fR \fBe2\fR \&.\&.\&. ]
is a parsing expression as well\&.
This is the \fIordered choice\fR, aka \fIprioritized choice\fR\&.
.IP [8]
For parsing expressions \fBe1\fR, \fBe2\fR, \&.\&.\&. the result of
[list x \fBe1\fR \fBe2\fR \&.\&.\&. ]
is a parsing expression as well\&.
This is the \fIsequence\fR\&.
.IP [9]
For a parsing expression \fBe\fR the result of
[list * \fBe\fR]
is a parsing expression as well\&.
This is the \fIkleene closure\fR, describing zero or more
repetitions\&.
.IP [10]
For a parsing expression \fBe\fR the result of
[list + \fBe\fR]
is a parsing expression as well\&.
This is the \fIpositive kleene closure\fR, describing one or more
repetitions\&.
.IP [11]
For a parsing expression \fBe\fR the result of
[list & \fBe\fR]
is a parsing expression as well\&.
This is the \fIand lookahead predicate\fR\&.
.IP [12]
For a parsing expression \fBe\fR the result of
[list ! \fBe\fR]
is a parsing expression as well\&.
This is the \fInot lookahead predicate\fR\&.
.IP [13]
For a parsing expression \fBe\fR the result of
[list ? \fBe\fR]
is a parsing expression as well\&.
This is the \fIoptional input\fR\&.
.PP
.PP
Examples of parsing expressions where already shown, in the
description of the method \fBserialize\fR\&.
.SH "PARSING EXPRESSION GRAMMARS"
.PP
For the mathematically inclined, a PEG is a 4-tuple (VN,VT,R,eS) where
.IP \(bu
VN is a set of \fInonterminal symbols\fR,
.IP \(bu
VT is a set of \fIterminal symbols\fR,
.IP \(bu
R is a finite set of rules, where each rule is a pair (A,e), A in VN,
and \fIe\fR a \fIparsing expression\fR\&.
.IP \(bu
eS is a parsing expression, the \fIstart expression\fR\&.
.PP
.PP
Further constraints are
.IP \(bu
The intersection of VN and VT is empty\&.
.IP \(bu
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\&.
.PP
.PP
Parsing expression are inductively defined via
.IP \(bu
The empty string (epsilon) is a parsing expression\&.
.IP \(bu
A terminal symbol \fIa\fR is a parsing expression\&.
.IP \(bu
A nonterminal symbol \fIA\fR is a parsing expression\&.
.IP \(bu
\fIe1\fR\fIe2\fR is a parsing expression for parsing expressions
\fIe1\fR and \fI2\fR\&. This is called \fIsequence\fR\&.
.IP \(bu
\fIe1\fR/\fIe2\fR is a parsing expression for parsing expressions
\fIe1\fR and \fI2\fR\&. This is called \fIordered choice\fR\&.
.IP \(bu
\fIe\fR* is a parsing expression for parsing expression
\fIe\fR\&. This is called \fIzero-or-more repetitions\fR, also known
as \fIkleene closure\fR\&.
.IP \(bu
\fIe\fR+ is a parsing expression for parsing expression
\fIe\fR\&. This is called \fIone-or-more repetitions\fR, also known
as \fIpositive kleene closure\fR\&.
.IP \(bu
!\fIe\fR is a parsing expression for parsing expression
\fIe1\fR\&. This is called a \fInot lookahead predicate\fR\&.
.IP \(bu
&\fIe\fR is a parsing expression for parsing expression
\fIe1\fR\&. This is called an \fIand lookahead predicate\fR\&.
.PP
.PP
.PP
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)\&.
.PP
They can be easily implemented by recursive descent parsers with
backtracking\&. This makes them relatives of LL(k) Context-Free
Grammars\&.
.SH REFERENCES
.IP [1]
\fIThe Packrat Parsing and Parsing Expression Grammars Page\fR [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\&.
.IP [2]
\fIParsing Techniques - A Practical Guide \fR [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\&.
.IP [3]
\fICompilers and Compiler Generators\fR [http://scifac\&.ru\&.ac\&.za/compilers/], an online book using
CoCo/R, a generator for recursive descent parsers\&.
.PP
.SH "BUGS, IDEAS, FEEDBACK"
This document, and the package it describes, will undoubtedly contain
bugs and other problems\&.
Please report such in the category \fIgrammar_peg\fR of the
\fITcllib Trackers\fR [http://core\&.tcl\&.tk/tcllib/reportlist]\&.
Please also report any ideas for enhancements you may have for either
package and/or documentation\&.
.PP
When proposing code changes, please provide \fIunified diffs\fR,
i\&.e the output of \fBdiff -u\fR\&.
.PP
Note further that \fIattachments\fR are strongly preferred over
inlined patches\&. Attachments can be made by going to the \fBEdit\fR
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar\&.
.SH 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
.SH CATEGORY
Grammars and finite automata
.SH COPYRIGHT
.nf
Copyright (c) 2005 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>

.fi