Tcl Library Source Code

Documentation
Login


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

grammar::peg - Create and manipulate parsing expression grammars

Table Of Contents

SYNOPSIS

package require Tcl 8.5 9
package require snit
package require grammar::peg ?0.3?

::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.

CONTAINER OBJECT API

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

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

Further constraints are

Parsing expression are inductively defined via

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, 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 , 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, 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. 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 © 2005 Andreas Kupries