One-Pass, Optimal Tree Parsing – With Or Without Trees

This paper describes the theory behind and implementation of wburg, a code-generator generator that accepts tree grammars as input and produces a code generator that emits an optimal parse of an IR tree in just a single bottom-up pass. Furthermore, wburg eliminates the need for an explicit IR tree altogether. The grammars that wburg-generated parsers can parse are a proper subset of those that two-pass systems can handle. However, analysis indicates that wburg can optimally handle grammars for most instruction sets (e.g., SPARC, MIPS R3000, and x86).