A parsing method on l-1 bounded context parsing

ABSTRACT

Bounded context parsing was first introduced by Floyd and Graham in which they used a precedence parsing method. However, precedence parsing has some drawbacks such as the parser is often very large and not all languages are precedence parsable.Another technique for generating a Bounded Context Parser was developed by Mickunas at Purdue University. This technique, which is often referred to as Bounded Context Acceptor (BCA) or Extended Bounded Context Acceptor (EBCA), can generate a more compact parser.This paper introduces a new parsing method which is derived from EBCA. The parse table generated by this method is much smaller than those generated by EBCA. The parsing technique yields similiar or improved efficiency when compared to EBCA.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: Robert W. Floyd, Bounded context syntactic analysis, Communications of the ACM, v.7 n.2, p.62-67, Feb. 1964 [doi>10.1145/363921.363927]
• 3: Graham, S. L. "On Bounded Right Context Languages and Grammars," SIAM J. Comput. 3(1974), 224-254.
• 4: Graham, R. M. "Bounded Context Translation," AFIPS. Vol 25, p.p. 17-29, 1964.
• 5: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 6: M. D. Mickunas , V. B. Schneider, A parser-generating system for constructing compressed compilers, Communications of the ACM, v.16 n.11, p.669-676, Nov. 1973 [doi>10.1145/355611.362536]
• 7: M. D. Mickunas , R. L. Lancaster , V. B. Schneider, Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars, Journal of the ACM (JACM), v.23 n.3, p.511-533, July 1976 [doi>10.1145/321958.321972]
• 8: Philip M. Lewis, 2nd , Daniel J. Rosenkrantz , Richard E. Stearns, Compiler Design Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1976
• 9: Schell, R. M. "A Method for Constructing Compressed Parsers for a Parser Generating System," Master's Thesis, University of Illinois, 1976.

INDEX TERMS

Keywords:
Bounded Context Acceptor, Bounded right context, Context free grammar, Extended Bounded Context Acceptor, Normal form grammar, Parsing, pushdown automaton