On the Parsing of Deterministic Languages

ABSTRACT

A parsing method for strict deterministic grammars is presented and a technique for using it to parse any deterministic language is indicated. An important characterization of the trees of strict deterministic grammars is established. This is used to prove iteration theorems for (strict) deterministic languages, and hence proving that certain sets are not in these families becomes comparatively straightforward. It is shown that every strict deterministic grammar is LR(0) and that any strict deterministic grammar is equivalent to a bounded right context (1, 0) grammar. Thus rigorous proofs that the families of deterministic, LR (k), and bounded right context languages are coextensive are presented for the first time.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: A. V. Aho , P. J. Denning , J. D. Ullman, Weak and Mixed Strategy Precedence Parsing, Journal of the ACM (JACM), v.19 n.2, p.225-243, April 1972 [doi>10.1145/321694.321697]
• 3: Franklin L. DeRemer, Simple LR(k) grammars, Communications of the ACM, v.14 n.7, p.453-460, July 1971 [doi>10.1145/362619.362625]
• 4: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 5: 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]
• 6: Matthew M. Geller , Michael A. Harrison, Strict deterministic versus LR(0) parsing, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.22-32, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512929]
• 7: GELLER, M. M., AND HARRISON, M.A. Characterizations of LR(0) languages. Conf. Rec. of the 14th Annual Symp. on Switching and Automata Theory, 73CH0-786-4-C, 1973, pp. 103-108.
• 8: Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
• 9: GINSBURG, S., AND GREIBACR, S.A. Deterministic context-free languages. Inform. and Contr. 9 (1966), 602-648.
• 10: Susan Lois Graham, Precedence languages and bounded right context languages, 1971
• 11: GaARAM, S.L. On bounded right context languages and grammars. SIAM J. of Computing (to appear).
• 12: James N. Gray , Michael A. Harrison, On the Covering and Reduction Problems for Context-Free Grammars, Journal of the ACM (JACM), v.19 n.4, p.675-698, Oct. 1972 [doi>10.1145/321724.321732]
• 13: James N. Gray , Michael A. Harrison, Canonical Precedence Schemes, Journal of the ACM (JACM), v.20 n.2, p.214-234, April 1973 [doi>10.1145/321752.321755]
• 14: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 15: HAINES, L.H. Generation and recognition of formal languages. Ph.D. Thesis, M.I.T., 1965.
• 16: HARRISON, M.A. On the relation between grammars add automata. InAdvances of lnformation Sciences 4, J. T. Tou, Ed., Plenum Press, New York, 1972, pp. 39-92.
• 17: HARRISON, M. A., AND HAVEL, I .M . Strict deterministic grammars. J. Comput. and Syst. Sci. 7 (1973), 237-277.
• 18: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 19: KNUTH, D.E. On the translation of languages from left to right. Inform. and Contr. 8 (1965), 607-639.
• 20: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 21: A. J. Korenjak, A practical method for constructing LR (k) processors, Communications of the ACM, v.12 n.11, p.613-623, Nov. 1969 [doi>10.1145/363269.363281]
• 22: LEMANN, D. LR(k) grammars and deterministic languages. Israel J. of Math. 10 (1971), 526-530.
• 23: OGDEN, W.F. Intercalation theorems for pushdown store and stack languages. Ph.D. Thesis, Stanford U., 1968.
• 24: Arto Salomaa, Formal languages, Academic Press Professional, Inc., San Diego, CA, 1987
• 25: ULLMAN, J. D. Applications of language theory to compiler design. In Theoretical Computer Science, A. V. Aho, Ed., Prentice-Hall, Englewood Cliffs, N. J., 1972.
• 26: VALIANT, L.G. General context-free recognition in less than cubic time. Tech. Rep., Dep. of Computer Science, Carnegie-Mellon U., Pittsburgh, Pa., Jan. 1974.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

General Terms:
Algorithms, Languages, Performance, Theory, Verification