Previous    Next


Cattell [1980] expressed machine instructions as tree patterns, invented the maximal munch algorithm for instruction selection, and built a code-generator generator to produce an instruction selection function from a tree-pattern description of an instruction set. Glanville and Graham [1978] expressed the tree patterns as productions in LR(1) grammars, which allows the maximal munch algorithm to use multiple nonterminal symbols to represent different classes of registers and addressing modes. But grammars describing instruction sets are inherently ambiguous, leading to problems with the LR(1) approach; Aho et al. [1989] use dynamic coding to parse the tree grammars, which solves the ambiguity problem, and describe the Twig automatic code-generator generator. The dynamic coding can be done at compiler-construction time instead of code-generation time [Pelegri-Llopart and Graham 1988]; using this technique, the BURG tool [Fraser et al. 1992] has an interface similar to Twig's but generates code much faster.

JaVaScreenshot Previous    Next