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 |
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)