How To Generate Minimal Grammars From Parse Trees

XT -- A Bundle of Program Transformation Tools

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


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.


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 # sdf2text -a -i -o L.sub.def

See Also

SdfToTable, sglrSGLR, asfix2sdfGT, sdfdenormalizeGT, HowToPrettyPrintAGrammar.