Department of Computer and Information Science
National Chiao-Tung University
Hsinchu, Taiwan 300, R.O.C.
We propose a lattice framework for analyzing context-free grammars and context-free languages. This framework is motivated by a technique for simplifying parsers with information derived from the associated scanners. We define the lattice framework and demonstrate it using additional applications, including data-flow analysis. Soundness and other properties of the lattice framework are also discussed.
Keywords: compiler, context-free grammar, finite-state machine, lattice, Mealy machine, parser, regular expression, scanner
Retrieve PDF document (199903_06.pdf : 117,757 bytes)
Received April 29, 1997; accepted September 15, 1997
Communicated by Jang-Ping Sheu.
1 This work was supported in part by the National Science Council, Taiwan, R.O.C., under grant NSC 85-2213-E-009-051.