Provided by: tcllib_1.21+dfsg-1_all bug

NAME

       grammar::peg - Create and manipulate parsing expression grammars

SYNOPSIS

       package require Tcl  8.4

       package require snit

       package require grammar::peg  ?0.1?

       ::grammar::peg pegName ?=|:=|<--|as|deserialize src?

       pegName destroy

       pegName clear

       pegName = srcPEG

       pegName --> dstPEG

       pegName serialize

       pegName deserialize serialization

       pegName is valid

       pegName start ?pe?

       pegName nonterminals

       pegName nonterminal add nt pe

       pegName nonterminal delete nt1 ?nt2 ...?

       pegName nonterminal exists nt

       pegName nonterminal rename nt ntnew

       pegName nonterminal mode nt ?mode?

       pegName nonterminal rule nt

       pegName unknown nonterminals

_________________________________________________________________________________________________

DESCRIPTION

       This  package provides a container class for parsing expression grammars (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 PARSING EXPRESSION GRAMMARS.

       In short, we have  terminal  symbols,  which  are  the  most  basic  building  blocks  for
       sentences,  and  nonterminal  symbols  with  associated  parsing expressions, 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 terminal symbols 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 parsing expression is also called a grammatical  rule,  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 start expression 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 FIRST set 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 LAST set 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 FOLLOW set 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.

   CONTAINER CLASS API
       The package exports the API described here.

       ::grammar::peg pegName ?=|:=|<--|as|deserialize src?
              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 CONTAINER OBJECT API. 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.

   CONTAINER OBJECT API
       All  grammar container objects provide the following methods for the manipulation of their
       contents:

       pegName destroy
              Destroys the grammar, including its storage space and associated command.

       pegName clear
              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

                  pegName deserialize [srcPEG serialize]

       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

                  dstPEG deserialize [pegName serialize]

       pegName serialize
              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 start expression 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.

       pegName deserialize serialization
              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.

       pegName is valid
              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.

       pegName start ?pe?
              This method defines the start expression 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 PARSING EXPRESSIONS. 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.

       pegName nonterminals
              Returns the set of all nonterminal symbols known to the grammar.

       pegName nonterminal add nt pe
              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  PARSING  EXPRESSIONS.  In that case the current set of
              nonterminal symbols and rules is not changed.  The method returns the empty  string
              as its result.

       pegName nonterminal delete nt1 ?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.

       pegName nonterminal exists nt
              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.

       pegName nonterminal rename nt ntnew
              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.

       pegName nonterminal mode nt ?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).

       pegName nonterminal rule nt
              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.

       pegName unknown nonterminals
              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.

   PARSING EXPRESSIONS
       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 / e1 e2 ... ] is a parsing
              expression as well.  This is the ordered choice, aka prioritized choice.

       [8]    For parsing expressions e1, e2, ... the result of [list x e1 e2 ... ] 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 kleene closure, 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 positive kleene closure, 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 and lookahead predicate.

       [12]   For a parsing expression e the result of [list ! e]  is  a  parsing  expression  as
              well.  This is the not lookahead predicate.

       [13]   For  a  parsing  expression  e  the result of [list ? e] is a parsing expression as
              well.  This is the optional input.

       Examples of parsing expressions where already shown, in  the  description  of  the  method
       serialize.

PARSING EXPRESSION GRAMMARS

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

       [3]    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  grammar_peg  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

       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>