Properties of deterministic top down grammars

ABSTRACT

The class of context free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. These grammars, called LL(k) grammars where k is the amount of look-ahead are first defined and a procedure is given for determining if a context free grammar is LL(k) for a given value of k. It is shown that &egr;-rules can be eliminated from an LL(k) grammar, at the cost of increasing the value of k by one, and a description is given of a canonical pushdown machine for recognizing LL(k) languages. It is shown that for each value of k there are LL(k+l) languages that are not LL(k) languages. It is shown that the equivalence problem is decidable for LL(k) grammars. Additional properties are also given.

REFERENCES

• 1: Davis, M., Computability and Unsolvability, McGraw-Hill, New York, 1958.
• 2: Ginsburg, S. and Greibach, S., "Deterministic Context-Free Languages," Information & Control, 9,6 (December 1966) 620-648.
• 3: Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965 [doi>10.1145/321250.321254]
• 4: Korenjak, A.J., and Hopcroft, J.E., "Simple Deterministic Languages," IEEE Conference Record of Seventh Annual Symposium on Switching and Automata Theory, IEEE Pub. No. 16-C-40, Oct. 1966, pp. 36-46.
• 5: Knuth, D.E., "On the Translation Of Languages from Left to Right," Information & Control, 8,6 (December 1965) 607-639.
• 6: P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
• 7: Oettinger, A. Automatic Syntactic Analysis and the Pushdown Store, Jacobson, R. (Ed.), Structure of Language and Its Mathematical Concepts, Proc. 12th Symposium in Appl. Math., Amer. Math. Soc., Providence, R. I., 1961, pp. 104-129.
• 8: Paull, M.C., and Unger, S.H., "Structural Equivalence of LL-k Grammars," IEEE Conference Record of Ninth Annual Symposium on Switching and Automata Theory, IEEE Pub. No. 68-C-50-C, Oct. 1968, pp. 176-186.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

General Terms:
Theory