Страницы справочника OS X

Эта страница руководства для  версии 10.9 Mac OS X

Читать страницы руководства

pt::peg_language(n)                             Parser Tools                             pt::peg_language(n)



____________________________________________________________________________________________________________

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 over-view overview
       view provided by the Introduction to Parser Tools. This document is the entrypoint to the whole  sys-tem system
       tem the current package is a part of.

       Welcome to the tutorial / introduction for the PEG Specification Language.  If you are already famil-iar familiar
       iar 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  lan-guage. language.
       guage.  It  was defined to make writing the specification of a grammar easy, something the other for-mats formats
       mats 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 termina-
       tor, 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  speci-fied specified
       fied 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  addi-tionally additionally
       tionally 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 dou-ble-apostroph, double-apostroph,
       ble-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 prede-fined predefined
       fined 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 com-ments. comments.
       ments. 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  lan-guage. language.
       guage.  It  was defined to make writing the specification of a grammar easy, something the other for-mats formats
       mats 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 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"   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:   END             <- "END"   WHITESPACE ;
       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 <- '(' Expression ')' / (Factor (MulOp Factor)*)  ;
           MulOp      <- '*' / '/'                       ;
           Factor     <- Term (AddOp Term)*                   ;
           AddOp      <- '+'/'-'                         ;
           Term       <- 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   SF  Trackers  [http://source -
       forge.net/tracker/? group_id=12883].  Please also report any ideas for enhancements you may  have  for
       either package and/or documentation.

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 pars-ing parsing
       ing languages, transducer

CATEGORY
       Parsing and Grammars

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




pt                                                    1                                  pt::peg_language(n)