1grammar::peg(n) Grammar operations and usage grammar::peg(n)
2______________________________________________________________________________
6
8 grammar::peg - Create and manipulate parsing expression grammars
9
11 package require Tcl 8.4
12 package require snit
14 package require grammar::peg ?0.1?
16 ::grammar::peg pegName ?=|:=|<--|as|deserialize src?
18 pegName destroy
20 pegName clear
22 pegName = srcPEG
24 pegName --> dstPEG
26 pegName serialize
28 pegName deserialize serialization
30 pegName is valid
32 pegName start ?pe?
34 pegName nonterminals
36 pegName nonterminal add nt pe
38 pegName nonterminal delete nt1 ?nt2 ...?
40 pegName nonterminal exists nt
42 pegName nonterminal rename nt ntnew
44 pegName nonterminal mode nt ?mode?
46 pegName nonterminal rule nt
48 pegName unknown nonterminals
50______________________________________________________________________________
52
54 This package provides a container class for parsing expression grammars
55 (Short: PEG). It allows the incremental definition of the grammar, its
56 manipulation and querying of the definition. The package neither pro‐
57 vides complex operations on the grammar, nor has it the ability to exe‐
58 cute a grammar definition for a stream of symbols. Two packages
59 related to this one are grammar::mengine and grammar::peg::interpreter.
60 The first of them defines a general virtual machine for the matching of
61 a character stream, and the second implements an interpreter for pars‐
62 ing expression grammars on top of that virtual machine.
63 TERMS & CONCEPTS
65 PEGs are similar to context-free grammars, but not equivalent; in some
66 cases PEGs are strictly more powerful than context-free grammars (there
67 exist PEGs for some non-context-free languages). The formal mathemati‐
68 cal definition of parsing expressions and parsing expression grammars
69 can be found in section PARSING EXPRESSION GRAMMARS.
70 In short, we have terminal symbols, which are the most basic building
72 blocks for sentences, and nonterminal symbols with associated parsing
73 expressions, defining the grammatical structure of the sentences. The
74 two sets of symbols are distinctive, and do not overlap. When speaking
75 about symbols the word "symbol" is often left out. The union of the
76 sets of terminal and nonterminal symbols is called the set of symbols.
77 Here the set of terminal symbols is not explicitly managed, but implic‐
79 itly defined as the set of all characters. Note that this means that we
80 inherit from Tcl the ability to handle all of Unicode.
81 A pair of nonterminal and parsing expression is also called a grammati‐
83 cal rule, or rule for short. In the context of a rule the nonterminal
84 is often called the left-hand-side (LHS), and the parsing expression
85 the right-hand-side (RHS).
86 The start expression of a grammar is a parsing expression from which
88 all the sentences contained in the language specified by the grammar
89 are derived. To make the understanding of this term easier let us
90 assume for a moment that the RHS of each rule, and the start expres‐
91 sion, is either a sequence of symbols, or a series of alternate parsing
92 expressions. In the latter case the rule can be seen as a set of
93 rules, each providing one alternative for the nonterminal. A parsing
94 expression A' is now a derivation of a parsing expression A if we pick
95 one of the nonterminals N in the expression, and one of the alternative
96 rules R for N, and then replace the nonterminal in A with the RHS of
97 the chosen rule. Here we can see why the terminal symbols are called
98 such. They cannot be expanded any further, thus terminate the process
99 of deriving new expressions. An example
100 Rules
102 (1) A <- a B c
103 (2a) B <- d B
104 (2b) B <- e
105 Some derivations, using starting expression A.
107 A -/1/-> a B c -/2a/-> a d B c -/2b/-> a d e c
109 A derived expression containing only terminal symbols is a sentence.
112 The set of all sentences which can be derived from the start expression
113 is the language of the grammar.
114 Some definitions for nonterminals and expressions:
116 [1] A nonterminal A is called reachable if it is possible to derive
118 a parsing expression from the start expression which contains A.
119 [2] A nonterminal A is called useful if it is possible to derive a
121 sentence from it.
122 [3] A nonterminal A is called recursive if it is possible to derive
124 a parsing expression from it which contains A, again.
125 [4] The FIRST set of a nonterminal A contains all the symbols which
127 can occur of as the leftmost symbol in a parsing expression
128 derived from A. If the FIRST set contains A itself then that
129 nonterminal is called left-recursive.
130 [5] The LAST set of a nonterminal A contains all the symbols which
132 can occur of as the rightmost symbol in a parsing expression
133 derived from A. If the LAST set contains A itself then that non‐
134 terminal is called right-recursive.
135 [6] The FOLLOW set of a nonterminal A contains all the symbols which
137 can occur after A in a parsing expression derived from the start
138 expression.
139 [7] A nonterminal (or parsing expression) is called nullable if the
141 empty sentence can be derived from it.
142 And based on the above definitions for grammars:
144 [1] A grammar G is recursive if and only if it contains a nontermi‐
146 nal A which is recursive. The terms left- and right-recursive,
147 and useful are analogously defined.
148 [2] A grammar is minimal if it contains only reachable and useful
150 nonterminals.
151 [3] A grammar is wellformed if it is not left-recursive. Such gram‐
153 mars are also complete, which means that they always succeed or
154 fail on all input sentences. For an incomplete grammar on the
155 other hand input sentences exist for which an attempt to match
156 them against the grammar will not terminate.
157 [4] As we wish to allow ourselves to build a grammar incrementally
159 in a container object we will encounter stages where the RHS of
160 one or more rules reference symbols which are not yet known to
161 the container. Such a grammar we call invalid. We cannot use
162 the term incomplete as this term is already taken, see the last
163 item.
164 CONTAINER CLASS API
166 The package exports the API described here.
167 ::grammar::peg pegName ?=|:=|<--|as|deserialize src?
169 The command creates a new container object for a parsing expres‐
170 sion grammar and returns the fully qualified name of the object
171 command as its result. The API the returned command is following
172 is described in the section CONTAINER OBJECT API. It may be used
173 to invoke various operations on the container and the grammar
174 within.
175 The new container, i.e. grammar will be empty if no src is spec‐
177 ified. Otherwise it will contain a copy of the grammar contained
178 in the src. The src has to be a container object reference for
179 all operators except deserialize. The deserialize operator
180 requires src to be the serialization of a parsing expression
181 grammar instead.
182 An empty grammar has no nonterminal symbols, and the start
184 expression is the empty expression, i.e. epsilon. It is valid,
185 but not useful.
186 CONTAINER OBJECT API
188 All grammar container objects provide the following methods for the
189 manipulation of their contents:
190 pegName destroy
192 Destroys the grammar, including its storage space and associated
193 command.
194 pegName clear
196 Clears out the definition of the grammar contained in pegName,
197 but does not destroy the object.
198 pegName = srcPEG
200 Assigns the contents of the grammar contained in srcPEG to peg‐
201 Name, overwriting any existing definition. This is the assign‐
202 ment operator for grammars. It copies the grammar contained in
203 the grammar object srcPEG over the grammar definition in peg‐
204 Name. The old contents of pegName are deleted by this operation.
205 This operation is in effect equivalent to
207 pegName deserialize [srcPEG serialize]
211 pegName --> dstPEG
214 This is the reverse assignment operator for grammars. It copies
215 the automation contained in the object pegName over the grammar
216 definition in the object dstPEG. The old contents of dstPEG are
217 deleted by this operation.
218 This operation is in effect equivalent to
220 dstPEG deserialize [pegName serialize]
224 pegName serialize
227 This method serializes the grammar stored in pegName. In other
228 words it returns a tcl value completely describing that grammar.
229 This allows, for example, the transfer of grammars over arbi‐
230 trary channels, persistence, etc. This method is also the basis
231 for both the copy constructor and the assignment operator.
232 The result of this method has to be semantically identical over
234 all implementations of the grammar::peg interface. This is what
235 will enable us to copy grammars between different implementa‐
236 tions of the same interface.
237 The result is a list of four elements with the following struc‐
239 ture:
240 [1] The constant string grammar::peg.
242 [2] A dictionary. Its keys are the names of all known nonter‐
244 minal symbols, and their associated values are the pars‐
245 ing expressions describing their sentennial structure.
246 [3] A dictionary. Its keys are the names of all known nonter‐
248 minal symbols, and their associated values hints to a
249 matcher regarding the semantic values produced by the
250 symbol.
251 [4] The last item is a parsing expression, the start expres‐
253 sion of the grammar.
254 Assuming the following PEG for simple mathematical expressions
256 Digit <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9'
260 Sign <- '+' / '-'
261 Number <- Sign? Digit+
262 Expression <- '(' Expression ')' / (Factor (MulOp Factor)*)
263 MulOp <- '*' / '/'
264 Factor <- Term (AddOp Term)*
265 AddOp <- '+'/'-'
266 Term <- Number
267 a possible serialization is
270 grammar::peg \\
274 {Expression {/ {x ( Expression )} {x Factor {* {x MulOp Factor}}}} \\
275 Factor {x Term {* {x AddOp Term}}} \\
276 Term Number \\
277 MulOp {/ * /} \\
278 AddOp {/ + -} \\
279 Number {x {? Sign} {+ Digit}} \\
280 Sign {/ + -} \\
281 Digit {/ 0 1 2 3 4 5 6 7 8 9} \\
282 } \\
283 {Expression value Factor value \\
284 Term value MulOp value \\
285 AddOp value Number value \\
286 Sign value Digit value \\
287 }
288 Expression
289 A possible one, because the order of the nonterminals in the dictionary
292 is not relevant.
293 pegName deserialize serialization
295 This is the complement to serialize. It replaces the grammar
296 definition in pegName with the grammar described by the serial‐
297 ization value. The old contents of pegName are deleted by this
298 operation.
299 pegName is valid
301 A predicate. It tests whether the PEG in pegName is valid. See
302 section TERMS & CONCEPTS for the definition of this grammar
303 property. The result is a boolean value. It will be set to true
304 if the PEG has the tested property, and false otherwise.
305 pegName start ?pe?
307 This method defines the start expression of the grammar. It
308 replaces the previously defined start expression with the pars‐
309 ing expression pe. The method fails and throws an error if pe
310 does not contain a valid parsing expression as specified in the
311 section PARSING EXPRESSIONS. In that case the existing start
312 expression is not changed. The method returns the empty string
313 as its result.
314 If the method is called without an argument it will return the
316 currently defined start expression.
317 pegName nonterminals
319 Returns the set of all nonterminal symbols known to the grammar.
320 pegName nonterminal add nt pe
322 This method adds the nonterminal nt and its associated parsing
323 expression pe to the set of nonterminal symbols and rules of the
324 PEG contained in the object pegName. The method fails and
325 throws an error if either the string nt is already known as a
326 symbol of the grammar, or if pe does not contain a valid parsing
327 expression as specified in the section PARSING EXPRESSIONS. In
328 that case the current set of nonterminal symbols and rules is
329 not changed. The method returns the empty string as its result.
330 pegName nonterminal delete nt1 ?nt2 ...?
332 This method removes the named symbols nt1, nt2 from the set of
333 nonterminal symbols of the PEG contained in the object pegName.
334 The method fails and throws an error if any of the strings is
335 not known as a nonterminal symbol. In that case the current set
336 of nonterminal symbols is not changed. The method returns the
337 empty string as its result.
338 The stored grammar becomes invalid if the deleted nonterminals
340 are referenced by the RHS of still-known rules.
341 pegName nonterminal exists nt
343 A predicate. It tests whether the nonterminal symbol nt is known
344 to the PEG in pegName. The result is a boolean value. It will
345 be set to true if the symbol nt is known, and false otherwise.
346 pegName nonterminal rename nt ntnew
348 This method renames the nonterminal symbol nt to ntnew. The
349 method fails and throws an error if either nt is not known as a
350 nonterminal, or if ntnew is a known symbol. The method returns
351 the empty string as its result.
352 pegName nonterminal mode nt ?mode?
354 This mode returns or sets the semantic mode associated with the
355 nonterminal symbol nt. If no mode is specified the current mode
356 of the nonterminal is returned. Otherwise the current mode is
357 set to mode. The method fails and throws an error if nt is not
358 known as a nonterminal. The grammar interpreter implemented by
359 the package grammar::peg::interpreter recognizes the following
360 modes:
361 value The semantic value of the nonterminal is the abstract
363 syntax tree created from the AST's of the RHS and a node
364 for the nonterminal itself.
365 match The semantic value of the nonterminal is an the abstract
367 syntax tree consisting of single a node for the string
368 matched by the RHS. The ASTs generated by the RHS are
369 discarded.
370 leaf The semantic value of the nonterminal is an the abstract
372 syntax tree consisting of single a node for the nontermi‐
373 nal itself. The ASTs generated by the RHS are discarded.
374 discard
376 The nonterminal has no semantic value. The ASTs generated
377 by the RHS are discarded (as well).
378 pegName nonterminal rule nt
380 This method returns the parsing expression associated with the
381 nonterminal nt. The method fails and throws an error if nt is
382 not known as a nonterminal.
383 pegName unknown nonterminals
385 This method returns a list containing the names of all nontermi‐
386 nal symbols which are referenced on the RHS of a grammatical
387 rule, but have no rule definining their structure. In other
388 words, a list of the nonterminal symbols which make the grammar
389 invalid. The grammar is valid if this list is empty.
390 PARSING EXPRESSIONS
392 Various methods of PEG container objects expect a parsing expression as
393 their argument, or will return such. This section specifies the format
394 such parsing expressions are in.
395 [1] The string epsilon is an atomic parsing expression. It matches
397 the empty string.
398 [2] The string alnum is an atomic parsing expression. It matches any
400 alphanumeric character.
401 [3] The string alpha is an atomic parsing expression. It matches any
403 alphabetical character.
404 [4] The string dot is an atomic parsing expression. It matches any
406 character.
407 [5] The expression [list t x] is an atomic parsing expression. It
409 matches the terminal string x.
410 [6] The expression [list n A] is an atomic parsing expression. It
412 matches the nonterminal A.
413 [7] For parsing expressions e1, e2, ... the result of [list / e1 e2
415 ... ] is a parsing expression as well. This is the ordered
416 choice, aka prioritized choice.
417 [8] For parsing expressions e1, e2, ... the result of [list x e1 e2
419 ... ] is a parsing expression as well. This is the sequence.
420 [9] For a parsing expression e the result of [list * e] is a parsing
422 expression as well. This is the kleene closure, describing zero
423 or more repetitions.
424 [10] For a parsing expression e the result of [list + e] is a parsing
426 expression as well. This is the positive kleene closure,
427 describing one or more repetitions.
428 [11] For a parsing expression e the result of [list & e] is a parsing
430 expression as well. This is the and lookahead predicate.
431 [12] For a parsing expression e the result of [list ! e] is a parsing
433 expression as well. This is the not lookahead predicate.
434 [13] For a parsing expression e the result of [list ? e] is a parsing
436 expression as well. This is the optional input.
437 Examples of parsing expressions where already shown, in the description
439 of the method serialize.
440
442 For the mathematically inclined, a PEG is a 4-tuple (VN,VT,R,eS) where
443 · VN is a set of nonterminal symbols,
445 · VT is a set of terminal symbols,
447 · R is a finite set of rules, where each rule is a pair (A,e), A
449 in VN, and e a parsing expression.
450 · eS is a parsing expression, the start expression.
452 Further constraints are
454 · The intersection of VN and VT is empty.
456 · For all A in VT exists exactly one pair (A,e) in R. In other
458 words, R is a function from nonterminal symbols to parsing
459 expressions.
460 Parsing expression are inductively defined via
462 · The empty string (epsilon) is a parsing expression.
464 · A terminal symbol a is a parsing expression.
466 · A nonterminal symbol A is a parsing expression.
468 · e1e2 is a parsing expression for parsing expressions e1 and 2.
470 This is called sequence.
471 · e1/e2 is a parsing expression for parsing expressions e1 and 2.
473 This is called ordered choice.
474 · e* is a parsing expression for parsing expression e. This is
476 called zero-or-more repetitions, also known as kleene closure.
477 · e+ is a parsing expression for parsing expression e. This is
479 called one-or-more repetitions, also known as positive kleene
480 closure.
481 · !e is a parsing expression for parsing expression e1. This is
483 called a not lookahead predicate.
484 · &e is a parsing expression for parsing expression e1. This is
486 called an and lookahead predicate.
487 PEGs are used to define a grammatical structure for streams of symbols
489 over VT. They are a modern phrasing of older formalisms invented by
490 Alexander Birham. These formalisms were called TS (TMG recognition
491 scheme), and gTS (generalized TS). Later they were renamed to TPDL
492 (Top-Down Parsing Languages) and gTPDL (generalized TPDL).
493 They can be easily implemented by recursive descent parsers with back‐
495 tracking. This makes them relatives of LL(k) Context-Free Grammars.
496
498 [1] The Packrat Parsing and Parsing Expression Grammars Page
499 [http://www.pdos.lcs.mit.edu/~baford/packrat/], by Bryan Ford,
500 Massachusetts Institute of Technology. This is the main entry
501 page to PEGs, and their realization through Packrat Parsers.
502 [2] Parsing Techniques - A Practical Guide
504 [http://www.cs.vu.nl/~dick/PTAPG.html], an online book offering
505 a clear, accessible, and thorough discussion of many different
506 parsing techniques with their interrelations and applicabili‐
507 ties, including error recovery techniques.
508 [3] Compilers and Compiler Generators [http://scifac.ru.ac.za/com‐
510 pilers/], an online book using CoCo/R, a generator for recursive
511 descent parsers.
512
514 This document, and the package it describes, will undoubtedly contain
515 bugs and other problems. Please report such in the category gram‐
516 mar_peg of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
517 Please also report any ideas for enhancements you may have for either
518 package and/or documentation.
519 When proposing code changes, please provide unified diffs, i.e the out‐
521 put of diff -u.
522 Note further that attachments are strongly preferred over inlined
524 patches. Attachments can be made by going to the Edit form of the
525 ticket immediately after its creation, and then using the left-most
526 button in the secondary navigation bar.
527
529 LL(k), TDPL, context-free languages, expression, grammar, parsing,
530 parsing expression, parsing expression grammar, push down automaton,
531 recursive descent, state, top-down parsing languages, transducer
532
534 Grammars and finite automata
535
537 Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>
538tcllib 0.1 grammar::peg(n)