Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.15 No.2, pp.287-306 (March 1999)
A Lattice Framework for Analyzing Context-Free Languages With Applications in Paper Simplification and Data-Flow Analysis1

Wuu Yang
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

Full Text () 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.