How To Generate Minimal Grammars From Parse Trees

Given a grammar and a parse tree obtained by parsing a term over this grammar, construct a subgrammar that still parses the same term.

Description

Given a grammar G and a term t over that grammar, a subgrammar that still parses t can be obtained in the following steps.

1. Parse t over G, using SdfToTable and sglrSGLR, to obtain a parse tree t.asfix.
2. Run the parse tree trough asfix2sdfGT, to obtain your subgrammar, in normalized Sdf form.
3. Run the normalized subgrammar through sdfdenormalizeGT, to transfer the subgrammar into ordinary Sdf.
4. Pretty-print the subgrammar.

Examples

Assume that L.def is an Sdf grammar for language L, and t is a term over L.

# sdf2table -i L.def -o L.tbl # sglr -p L.tbl -i t -o t.asfix # asfix2sdf -i t.asfix | sdf-de-normalize -o L.sub.def.af # sdf2text -a -i L.sub.def.af -o L.sub.def

See Also

SdfToTable, sglrSGLR, asfix2sdfGT, sdfdenormalizeGT, HowToPrettyPrintAGrammar.