'\" '\" Generated from file 'pt_peg_language\&.man' by tcllib/doctools with format 'nroff' '\" Copyright (c) 2009 Andreas Kupries '\" .TH "pt::peg_language" 3tcl 1 tcllib "Parser Tools" .\" 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 pt::peg_language \- PEG Language Tutorial .SH SYNOPSIS package require \fBTcl 8\&.5\fR .sp .BE .SH DESCRIPTION .PP Are you lost ? Do you have trouble understanding this document ? In that case please read the overview provided by the \fIIntroduction to Parser Tools\fR\&. This document is the entrypoint to the whole system the current package is a part of\&. .PP Welcome to the tutorial / introduction for the \fBPEG Specification Language\fR\&. 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\&. .SH "WHAT IS IT?" \fBpeg\fR, 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\&. .SH "THE ELEMENTS OF THE LANGUAGE" .SS "BASIC STRUCTURE" The general outline of a textual PEG is .CS PEG <> (<>) <> END; .CE \fINote\fR: We are using text in double angle-brackets as place-holders for things not yet explained\&. .SS 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 \&. The exception to that is the name given after the keyword \fBPEG\fR (see previous section), which is the name of the whole grammar itself\&. .PP The structure of a name is simple: .IP [1] It begins with a letter, underscore, or colon, followed by .IP [2] zero or more letters, digits, underscores, or colons\&. .PP Or, in formal textual notation: .CS ([_:] / ) ([_:] / )* .CE Examples of names: .CS Hello ::world _:submarine55_ .CE Examples of text which are \fInot\fR names: .CS 12 \&.bogus 0wrong @location .CE .SS 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 .CS <> <- <> ; .CE The specifies the nonterminal symbol to be defined, the after the arrow (<-) then declares its structure\&. .PP Note that each rule ends in a single semicolon, even the last\&. I\&.e\&. the semicolon is a rule \fIterminator\fR, not a separator\&. .PP 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\&. .SS EXPRESSIONS The \fIparsing\fR expressions are the meat of any specification\&. They declare the structure of the whole document (<>), and of all nonterminal symbols\&. .PP All expressions are made up out of \fIatomic expressions\fR and \fIoperators\fR 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 \fIconcatenation\fR) of parts however\&. This is specified by simply placing the parts adjacent to each other\&. .PP Here are the operators, from highest to lowest priority (i\&.e\&. strength of binding): .CS # Binary operators\&. <> <> # sequence\&. parse 1, then 2\&. <> / <> # alternative\&. try to parse 1, and parse 2 if 1 failed to parse\&. # Prefix operators\&. Lookahead constraints\&. Same priority\&. & <> # Parse expression, ok on successful parse\&. ! <> # Ditto, except ok on failure to parse\&. # Suffix operators\&. Repetition\&. Same priority\&. <> ? # Parse expression none, or once (repeat 0 or 1)\&. <> * # Parse expression zero or more times\&. <> + # Parse expression one or more times\&. # Expression nesting ( <> ) # Put an expression in parens to change its priority\&. .CE With this we can now deconstruct the formal expression for names given in section \fBNames\fR: .CS ([_:] / ) ([_:] / )* .CE It is a sequence of two parts, .CS [_:] / .CE and .CS ([_:] / )* .CE 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 .CS [_:] .CE And \fIatomic expressions\fR are our next topic\&. They fall into three classes: .IP [1] names, i\&.e\&. nonterminal symbols, .IP [2] string literals, and .IP [3] character classes\&. .PP Names we know about already, or see section \fBNames\fR for a refresher\&. .PP 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 .CS '' "" 'hello' "umbra" "'" '"' .CE The last two examples show how to place any of the delimiters into a string\&. .PP 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: .CS # Any unicode alphabet or digit character (string is alnum)\&. # Any unicode alphabet character (string is alpha)\&. # Any unicode character below codepoint 0x80 (string is ascii)\&. # Any unicode control character (string is control)\&. # The digit characters [0-9]\&. # Any unicode digit character (string is digit)\&. # Any unicode printing character, except space (string is graph)\&. # Any unicode lower-case alphabet character (string is lower)\&. # Any unicode printing character, incl\&. space (string is print)\&. # Any unicode punctuation character (string is punct)\&. # Any unicode space character (string is space)\&. # Any unicode upper-case alphabet character (string is upper)\&. # Any unicode word character (string is wordchar)\&. # The hexadecimal digit characters [0-9a-fA-F]\&. \&. # Any character, except end of input\&. .CE And the syntax of custom-defined character classes is .CS [ <>* ] .CE where each range is either a single character, or of the form .CS <> - > .CE Examples for character classes we have seen already in the course of this introduction are .CS [_:] [0-9] [0-9a-fA-F] .CE We are nearly done with expressions\&. The only piece left is to tell how the characters in character classes and string literals are specified\&. .PP 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\&. .PP 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: .CS \\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 .CE .SS "WHITESPACE AND COMMENTS" One issue not touched upon so far is whitespace and comments\&. .PP Whitespace is any unicode space character, i\&.e\&. anything in the character class , and comments\&. The latter are sequences of characters starting with a '#' (hash, unicode codepoint 0x23) and ending at the next end-of-line\&. .PP 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\&. .SS "NONTERMINAL ATTRIBUTES" Lastly, a more advanced topic\&. In the section \fBRules\fR we gave the structure of a rule as .CS <> <- <> ; .CE 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 .CS <> : <> <- <> ; .CE is also allowed\&. This mode is optional\&. The known modes and their meanings are: .TP \fBvalue\fR 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\&. .TP \fBleaf\fR 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\&. .TP \fBvoid\fR The nonterminal has no semantic value\&. Any ASTs generated by the symbol's right hand side are discarded (as well)\&. .PP Of these three modes only \fBleaf\fR and \fBvoid\fR can be specified directly\&. \fBvalue\fR is implicitly specified by the absence of a mode before the nonterminal\&. .PP 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\&. .SH "PEG SPECIFICATION LANGUAGE" \fBpeg\fR, 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\&. .PP It is formally specified by the grammar shown below, written in itself\&. For a tutorial / introduction to the language please go and read the \fIPEG Language Tutorial\fR\&. .PP .CS 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 <- ([_:] / ) ([_:] / )* ; 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: 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 <- "" WHITESPACE ; leaf: ALPHA <- "" WHITESPACE ; leaf: ASCII <- "" WHITESPACE ; leaf: CONTROL <- "" WHITESPACE ; leaf: DDIGIT <- "" WHITESPACE ; leaf: DIGIT <- "" WHITESPACE ; leaf: GRAPH <- "" WHITESPACE ; leaf: LOWER <- "" WHITESPACE ; leaf: PRINTABLE <- "" WHITESPACE ; leaf: PUNCT <- "" WHITESPACE ; leaf: SPACE <- "" WHITESPACE ; leaf: UPPER <- "" WHITESPACE ; leaf: WORDCHAR <- "" WHITESPACE ; leaf: XDIGIT <- "" WHITESPACE ; void: WHITESPACE <- (" " / "\\t" / EOL / COMMENT)* ; void: COMMENT <- '#' (!EOL \&.)* EOL ; void: EOL <- "\\n\\r" / "\\n" / "\\r" ; void: EOF <- !\&. ; # -------------------------------------------------------------------- END; .CE .SS EXAMPLE Our example specifies the grammar for a basic 4-operation calculator\&. .PP .CS 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; .CE .PP Using higher-level features of the notation, i\&.e\&. the character classes (predefined and custom), this example can be rewritten as .PP .CS PEG calculator (Expression) Sign <- [-+] ; Number <- Sign? + ; Expression <- '(' Expression ')' / (Factor (MulOp Factor)*) ; MulOp <- [*/] ; Factor <- Term (AddOp Term)* ; AddOp <- [-+] ; Term <- Number ; END; .CE .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 \fIpt\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 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 .SH CATEGORY Parsing and Grammars .SH COPYRIGHT .nf Copyright (c) 2009 Andreas Kupries .fi