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

NAME

       pt::peg_language - PEG Language Tutorial

SYNOPSIS

       package require Tcl  8.5

_________________________________________________________________________________________________

DESCRIPTION

       Are  you  lost  ?   Do you have trouble understanding this document ?  In that case please
       read the overview provided by the Introduction to  Parser  Tools.  This  document  is  the
       entrypoint to the whole system the current package is a part of.

       Welcome  to  the  tutorial  / introduction for the PEG Specification Language.  If you are
       already familiar with the language we are about to discuss, and only wish to refresh  your
       memory you can, of course, skip ahead to the aforementioned section and just read the full
       formal specification.

WHAT IS IT?

       peg, a language for the specification of parsing expression grammars is meant to be  human
       readable, and writable as well, yet strict enough to allow its processing by machine. Like
       any computer language. It was defined to make writing the specification of a grammar easy,
       something the other formats found in the Parser Tools do not lend themselves too.

THE ELEMENTS OF THE LANGUAGE

   BASIC STRUCTURE
       The general outline of a textual PEG is

              PEG <<name>> (<<start-expression>>)
                 <<rules>>
              END;

       Note:  We  are  using  text  in  double angle-brackets as place-holders for things not yet
       explained.

   NAMES
       Names are mostly used to identify the nonterminal symbols of the grammar, i.e. that  which
       occurs  on  the left-hand side of a <rule>.  The exception to that is the name given after
       the keyword PEG (see previous section), which is the name of the whole grammar itself.

       The structure of a name is simple:

       [1]    It begins with a letter, underscore, or colon, followed by

       [2]    zero or more letters, digits, underscores, or colons.

       Or, in formal textual notation:

                  ([_:] / <alpha>) ([_:] / <alnum>)*

       Examples of names:

                  Hello
                  ::world
                  _:submarine55_

       Examples of text which are not names:

                  12
                  .bogus
                  0wrong
                  @location

   RULES
       The main body of the text of a grammar specification is taken up by the rules.  Each  rule
       defines the sentence structure of one nonterminal symbol. Their basic structure is

                   <<name>>  <-  <<expression>> ;

       The  <name>  specifies  the  nonterminal  symbol to be defined, the <expression> after the
       arrow (<-) then declares its structure.

       Note that each rule ends in a single semicolon, even the last.  I.e. the  semicolon  is  a
       rule terminator, not a separator.

       We can have as many rules as we like, as long as we define each nonterminal symbol at most
       once, and have at least  one  rule  for  each  nonterminal  symbol  which  occured  in  an
       expression, i.e. in either the start expression of the grammar, or the right-hande side of
       a rule.

   EXPRESSIONS
       The parsing expressions are the meat of any specification. They declare the  structure  of
       the whole document (<<start-expression>>), and of all nonterminal symbols.

       All  expressions  are  made  up out of atomic expressions and operators combining them. We
       have operators for choosing between alternatives, repetition of parts, and for  look-ahead
       constraints.   There   is   no  explicit  operator  for  the  sequencing  (also  known  as
       concatenation) of parts however. This is specified by simply placing the parts adjacent to
       each other.

       Here are the operators, from highest to lowest priority (i.e. strength of binding):

                  # Binary operators.

                  <<expression-1>>     <<expression-2>>  # sequence. parse 1, then 2.
                  <<expression-1>>  /  <<expression-2>>  # alternative. try to parse 1, and parse 2 if 1 failed to parse.

                  # Prefix operators. Lookahead constraints. Same priority.

                  & <<expression>>  # Parse expression, ok on successful parse.
                  ! <<expression>>  # Ditto, except ok on failure to parse.

                  # Suffix operators. Repetition. Same priority.

                  <<expression>> ?  # Parse expression none, or once (repeat 0 or 1).
                  <<expression>> *  # Parse expression zero or more times.
                  <<expression>> +  # Parse expression one or more times.

                  # Expression nesting

                  ( <<expression>> ) # Put an expression in parens to change its priority.

       With this we can now deconstruct the formal expression for names given in section Names:

                  ([_:] / <alpha>) ([_:] / <alnum>)*

       It is a sequence of two parts,

                  [_:] / <alpha>
       and

                  ([_:] / <alnum>)*
       The  parentheses around the parts kept their inner alternatives bound together against the
       normally higher priority of the sequence. Each of the two parts is  an  alternative,  with
       the second part additionally repeated zero or more times, leaving us with the three atomic
       expressions

                  [_:]
                  <alpha>
                  <alnum>

       And atomic expressions are our next topic. They fall into three classes:

       [1]    names, i.e. nonterminal symbols,

       [2]    string literals, and

       [3]    character classes.

       Names we know about already, or see section Names for a refresher.

       String literals are simple. They are delimited by (i.e.  start  and  end  with)  either  a
       single  or  double-apostroph,  and in between the delimiters we can have any character but
       the delimiter itself. They can be empty as well. Examples of strings are

                  ''
                  ""
                  'hello'
                  "umbra"
                  "'"
                  '"'

       The last two examples show how to place any of the delimiters into a string.

       For the last, but not least of our atomic expressions, character classes, we have a number
       of  predefined  classes,  shown below, and the ability to construct or own. The predefined
       classes are:

                  <alnum>    # Any unicode alphabet or digit character (string is alnum).
                  <alpha>    # Any unicode alphabet character (string is alpha).
                  <ascii>    # Any unicode character below codepoint 0x80 (string is ascii).
                  <control>  # Any unicode control character (string is control).
                  <ddigit>   # The digit characters [0-9].
                  <digit>    # Any unicode digit character (string is digit).
                  <graph>    # Any unicode printing character, except space (string is graph).
                  <lower>    # Any unicode lower-case alphabet character (string is lower).
                  <print>    # Any unicode printing character, incl. space (string is print).
                  <punct>    # Any unicode punctuation character (string is punct).
                  <space>    # Any unicode space character (string is space).
                  <upper>    # Any unicode upper-case alphabet character (string is upper).
                  <wordchar> # Any unicode word character (string is wordchar).
                  <xdigit>   # The hexadecimal digit characters [0-9a-fA-F].
                  .          # Any character, except end of input.

       And the syntax of custom-defined character classes is

                  [ <<range>>* ]

       where each range is either a single character, or of the form

                 <<character>> - <character>>

       Examples for character classes we have seen already in the course of this introduction are

                  [_:]
                  [0-9]
                  [0-9a-fA-F]

       We are nearly done with expressions. The only piece left is to tell how the characters  in
       character classes and string literals are specified.

       Basically characters in the input stand for themselves, and in addition to that we several
       types of escape syntax to to repesent control characters, or  characters  outside  of  the
       encoding the text is in.

       All  the  escaped  forms  are  started  with a backslash character ('\', unicode codepoint
       0x5C). This is then followed by a series of octal digits, or 'u' and  hexedecimal  digits,
       or a regular character from a fixed set for various control characters. Some examples:

                  \n \r \t \' \" \[ \] \\ #
                  \000 up to \277         # octal escape, all ascii character, leading 0's can be removed.
                  \u2CA7                  # hexadecimal escape, all unicode characters.
                  #                       # Here 2ca7 <=> Koptic Small Letter Tau

   WHITESPACE AND COMMENTS
       One issue not touched upon so far is whitespace and comments.

       Whitespace  is  any unicode space character, i.e. anything in the character class <space>,
       and comments. The latter are sequences of characters starting with a  '#'  (hash,  unicode
       codepoint 0x23) and ending at the next end-of-line.

       Whitespace can be freely used between all syntactical elements of a grammar specification.
       It cannot be used inside of syntactical elements, like names, string literals,  predefined
       character classes, etc.

   NONTERMINAL ATTRIBUTES
       Lastly, a more advanced topic. In the section Rules we gave the structure of a rule as

                   <<name>>  <-  <<expression>> ;

       This  is  not quite true. It is possible to associate a semantic mode with the nonterminal
       in the rule, by writing it before the name, separated from it by a colon, i.e. writing

                  <<mode>> : <<name>>  <-  <<expression>> ;

       is also allowed. This mode is optional. The known modes and their meanings are:

       value  The semantic value of the nonterminal symbol is an abstract syntax tree  consisting
              of  a  single  node  node  for  the  nonterminal  itself, which has the ASTs of the
              symbol's right hand side as its children.

       leaf   The semantic value of the nonterminal symbol is an abstract syntax tree  consisting
              of a single node node for the nonterminal, without any children. Any ASTs generated
              by the symbol's right hand side are discarded.

       void   The nonterminal has no semantic value. Any ASTs generated  by  the  symbol's  right
              hand side are discarded (as well).

       Of  these  three  modes  only leaf and void can be specified directly. value is implicitly
       specified by the absence of a mode before the nonterminal.

       Now, with all the above under our belt it  should  be  possible  to  not  only  read,  but
       understand  the formal specification of the text representation shown in the next section,
       written in itself.

PEG SPECIFICATION LANGUAGE

       peg, a language for the specification of parsing expression grammars is meant to be  human
       readable, and writable as well, yet strict enough to allow its processing by machine. Like
       any computer language. It was defined to make writing the specification of a grammar easy,
       something the other formats found in the Parser Tools do not lend themselves too.

       It  is  formally specified by the grammar shown below, written in itself. For a tutorial /
       introduction to the language please go and read the PEG Language Tutorial.

              PEG pe-grammar-for-peg (Grammar)

                # --------------------------------------------------------------------
                      # Syntactical constructs

                      Grammar         <- WHITESPACE Header Definition* Final EOF ;

                      Header          <- PEG Identifier StartExpr ;
                      Definition      <- Attribute? Identifier IS Expression SEMICOLON ;
                      Attribute       <- (VOID / LEAF) COLON ;
                      Expression      <- Sequence (SLASH Sequence)* ;
                      Sequence        <- Prefix+ ;
                      Prefix          <- (AND / NOT)? Suffix ;
                      Suffix          <- Primary (QUESTION / STAR / PLUS)? ;
                      Primary         <- ALNUM / ALPHA / ASCII / CONTROL / DDIGIT / DIGIT
                                      /  GRAPH / LOWER / PRINTABLE / PUNCT / SPACE / UPPER
                                      /  WORDCHAR / XDIGIT
                                      / Identifier
                                      /  OPEN Expression CLOSE
                                      /  Literal
                                      /  Class
                                      /  DOT
                                      ;
                      Literal         <- APOSTROPH  (!APOSTROPH  Char)* APOSTROPH  WHITESPACE
                                      /  DAPOSTROPH (!DAPOSTROPH Char)* DAPOSTROPH WHITESPACE ;
                      Class           <- OPENB (!CLOSEB Range)* CLOSEB WHITESPACE ;
                      Range           <- Char TO Char / Char ;

                      StartExpr       <- OPEN Expression CLOSE ;
              void:   Final           <- "END" WHITESPACE SEMICOLON WHITESPACE ;

                      # --------------------------------------------------------------------
                      # Lexing constructs

                      Identifier      <- Ident WHITESPACE ;
              leaf:   Ident           <- ([_:] / <alpha>) ([_:] / <alnum>)* ;
                      Char            <- CharSpecial / CharOctalFull / CharOctalPart
                                      /  CharUnicode / CharUnescaped
                                      ;

              leaf:   CharSpecial     <- "\\" [nrt'"\[\]\\] ;
              leaf:   CharOctalFull   <- "\\" [0-2][0-7][0-7] ;
              leaf:   CharOctalPart   <- "\\" [0-7][0-7]? ;
              leaf:   CharUnicode     <- "\\" 'u' HexDigit (HexDigit (HexDigit HexDigit?)?)? ;
              leaf:   CharUnescaped   <- !"\\" . ;

              void:   HexDigit        <- [0-9a-fA-F] ;

              void:   TO              <- '-'           ;
              void:   OPENB           <- "["           ;
              void:   CLOSEB          <- "]"           ;
              void:   APOSTROPH       <- "'"           ;
              void:   DAPOSTROPH      <- '"'           ;
              void:   PEG             <- "PEG" !([_:] / <alnum>) WHITESPACE ;
              void:   IS              <- "<-"    WHITESPACE ;
              leaf:   VOID            <- "void"  WHITESPACE ; # Implies that definition has no semantic value.
              leaf:   LEAF            <- "leaf"  WHITESPACE ; # Implies that definition has no terminals.
              void:   SEMICOLON       <- ";"     WHITESPACE ;
              void:   COLON           <- ":"     WHITESPACE ;
              void:   SLASH           <- "/"     WHITESPACE ;
              leaf:   AND             <- "&"     WHITESPACE ;
              leaf:   NOT             <- "!"     WHITESPACE ;
              leaf:   QUESTION        <- "?"     WHITESPACE ;
              leaf:   STAR            <- "*"     WHITESPACE ;
              leaf:   PLUS            <- "+"     WHITESPACE ;
              void:   OPEN            <- "("     WHITESPACE ;
              void:   CLOSE           <- ")"     WHITESPACE ;
              leaf:   DOT             <- "."     WHITESPACE ;

              leaf:   ALNUM           <- "<alnum>"    WHITESPACE ;
              leaf:   ALPHA           <- "<alpha>"    WHITESPACE ;
              leaf:   ASCII           <- "<ascii>"    WHITESPACE ;
              leaf:   CONTROL         <- "<control>"  WHITESPACE ;
              leaf:   DDIGIT          <- "<ddigit>"   WHITESPACE ;
              leaf:   DIGIT           <- "<digit>"    WHITESPACE ;
              leaf:   GRAPH           <- "<graph>"    WHITESPACE ;
              leaf:   LOWER           <- "<lower>"    WHITESPACE ;
              leaf:   PRINTABLE       <- "<print>"    WHITESPACE ;
              leaf:   PUNCT           <- "<punct>"    WHITESPACE ;
              leaf:   SPACE           <- "<space>"    WHITESPACE ;
              leaf:   UPPER           <- "<upper>"    WHITESPACE ;
              leaf:   WORDCHAR        <- "<wordchar>" WHITESPACE ;
              leaf:   XDIGIT          <- "<xdigit>"   WHITESPACE ;

              void:   WHITESPACE      <- (" " / "\t" / EOL / COMMENT)* ;
              void:   COMMENT         <- '#' (!EOL .)* EOL ;
              void:   EOL             <- "\n\r" / "\n" / "\r" ;
              void:   EOF             <- !. ;

                      # --------------------------------------------------------------------
              END;

   EXAMPLE
       Our example specifies the grammar for a basic 4-operation calculator.

              PEG calculator (Expression)
                  Digit      <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9'       ;
                  Sign       <- '-' / '+'                                     ;
                  Number     <- Sign? Digit+                                  ;
                  Expression <- Term (AddOp Term)*                            ;
                  MulOp      <- '*' / '/'                                     ;
                  Term       <- Factor (MulOp Factor)*                        ;
                  AddOp      <- '+'/'-'                                       ;
                  Factor     <- '(' Expression ')' / Number                   ;
              END;

       Using higher-level features of the notation, i.e. the character  classes  (predefined  and
       custom), this example can be rewritten as

              PEG calculator (Expression)
                  Sign       <- [-+] ;
                  Number     <- Sign? <ddigit>+;
                  Expression <- '(' Expression ')' / (Factor (MulOp Factor)*);
                  MulOp      <- [*/];
                  Factor     <- Term (AddOp Term)*;
                  AddOp      <- [-+];
                  Term       <- Number;
              END;

BUGS, IDEAS, FEEDBACK

       This  document,  and  the  package  it  describes, will undoubtedly contain bugs and other
       problems.   Please  report  such   in   the   category   pt   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

       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>