compileShortPT {xegaBNF}R Documentation

Produces a production table with non-recursive productions only.

Description

compileShortPT() produces a “short” production table from a context-free grammar. The short production table does not contain recursive production rules. Warning: No error checking implemented.

Usage

compileShortPT(G)

Arguments

G

A grammar with symbol table ST, production table PT, and start symbol Start.

Details

compileShortPT() starts with production rules whose right-hand side contains only terminals. It incrementally builds up the new PT until in the new PT at least one production rule exists for each non-terminal which replaces the non-terminal symbol by a list of terminal symbols.

The short production rule table provides for each non-terminal symbol a minimal finite derivation into terminals. It contains a finite subset of the context-free language as defined by the grammar G. Instead of the full production table, it is used for generating depth-bounded derivation trees. The first idea of defining such a finite part of the language is due to M. P. Schützenberger (1966).

Value

A (short) production table is a named list with 2 columns. The first column (the left-hand side LHS) is a vector of non-terminal identifiers. The second column (the right-hand side RHS) is a vector of vectors of numerical identifiers. LHS[i] derives into RHS[i].

References

Schützenberger, M. P. (1966): Classification of Chomsky Languages. In: Steel, T. B. Jr. (Ed.) Formal Language Description Languages for Computer Programming. Proceedings of the IFIP Workshop on Formal Language Description Languages. North-Holland, Amsterdam, 100 -104.

See Also

Other Compiler Steps: makeProductionTable(), makeStartSymbol(), makeSymbolTable()

Examples

g<-compileBNF(booleanGrammar())
compileShortPT(g)


[Package xegaBNF version 1.0.0.5 Index]