Generalized left corner parsing

Brosgol [Br] formalizes the notion that parsing methods can be classified by the positions at which production rules are recognized. In an LL parser, each rule is recognized at the left end, before the rule's yield has been read; in an LR parser, a rule is recognized at its right end, after its yield has been read; and in an LC parser a rule is recognized after the yield of its "left corner" has been read. We generalize on these techniques by allowing the user to specify arbitrarily for each production rule the position at which that rule is to be recognized. The resulting GLC or generalized left corner technique includes the LR, LL, LC, and ELC methods as special cases. It also allows for less conventional parsing strategies, such as grammar splitting [K] with certain component grammars parsed top-down and the others parsed bottom-up, as suggested in [AU].This paper is organized as follows. In Section 2 we give some necessary background and notation. Section 3 defines GLC parsing. A canonical GLC(k) parsing technique can be defined analogous to the LR(k) technique. However, the resulting parsers tend to be unacceptably large. We therefore restrict our attention to the SGLC(k), or simple generalized left corner parsing technique, which is analogous to the SLR(k) technique of DeRemer [D]. We give an algorithm for the construction of SGLC(k) parsing tables and prove that the resulting parser is correct.In Section 4 we develop some potentially useful properties of SGLC(1) parsers. We show that there is a well-defined leftmost position at which each production rule can be recognized, and that a minimal left corner parser can be constructed which recognizes each rule as early as possible. We derive a simple expression relating the size (number of states) of an SGLC(1) parser to the size of the corresponding SLR(1) parser. If G is not left-recursive, then the minimal left-corner parser is the smallest parser for G in this class, while the SLR(1) parser is the largest.In Section 5 we extend the techniques 5 of [HSU] to give an O(n²) algorithm to test whether a grammar with no left recursion is SGLC(1), and if so to compute its minimal left corners.