Formal parsing systems

ABSTRACT

Automatic syntactic analysis has recently become important for both natural language data processing and syntax-directed compilers. A formal parsing system G = (V, &mgr;, T, R) consists of two finite disjoint vocabularies, V and T, a many-many map, &mgr;, from V onto T, and a recursive set R of strings in T called syntactic sentence classes. Every program for automatic syntactic analysis determines a formal parsing system. A directed production analyzer (I, T, X, &rgr;) is a nondeterministic pushdown-store machine with internal vocabulary I, input vocabulary T, and all productions of &rgr; in the form: (Z, a) → aY1 ··· Ym, Z, Yi &egr; I, a &egr; T. Every context-free language can be analyzed by a directed production analyzer.

REFERENCES

• 1: BAR-HILLEL, Y., PERLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Zeit. Phonet. Spraehwiss. Kommunik. Forsch. 15, 2 (1961), 143-72.
• 2: CHOMSKY, N. Formal properties of grammars. In Handbook of Mathematical Psychology, Vol. II. Luce, R. D., Bush, R. R., and Galantes, E. (EDs.), John Wiley, New York, 1963, 323-418.
• 3: EVEY, J. The Theory and Applications of Pushdown Store Machines. Doct. Thesis, Div. Eng. Appl. Phys., Harvard U., Cambridge, Mass., June 1963.
• 4: GREIBACH, S. Inverses of Phrase Structure Generators. Doer. Thesis, Div. Eng. Appl. Phys., Harvard U., Cambridge, Mass., June 1963.
• 5: The undecidability of the ambiguity problem for minimal linear grammars. Inform. Contr. 6, 2 (June 1963), 119-25.
• 6: HARTMANIS, J., AND STEARNS, R. E. On the computational complexity of algorithms. Rep. No. 63-RL-3292E, General Electric Res. Lab., Schenectady, N. Y., April 1963.
• 7: KUNO, S., AND OETTINGER, A. G. Syntactic structure and ambiguity of English. Proc. 1963 Fall Joint Comput. Conf., Spartan Books, Inc., Baltimore, 1963.
• 8: MATTHEWS, G. H. Analysis by synthesis of natural languages. Proc. 1961 Int. Conf. on Machine Translation of Languages and Applied Language Analysis, Vol. II. Her Majesty's Stationery Off., London, 1962.
• 9: OETTINGER, A. G. Automatic syntactic analysis and the pushdown store. Proc. of Symposia in Applied Mathematics, Vol. 72. Amer. Math. Soc., Providence, R. I., 1961.
• 10: PARIKH, R. J. Language generating devices. Quart. Prog. Rep. No. 60, Res. Lab. of Electronics, MIT, Cambridge, Mass., Jan. 1961, 199-212.
• 11: ROBINSON, J. Preliminary codes and rules for the automatic parsing of English. Memo. RM-3339-PR, The RAND Corp., Santa Monica, Calif., Dec. 1962.
• 12: SCHUTZENBERGER, M. P. On context-free languages and pushdown automata. Inform. Contr. 6, 3 (Sept. 1963), 246-264.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

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

General Terms:
Design, Languages, Theory