Fernando C. N. Pereira
David H. D. Warren
ABSTRACT
By exploring the relationship between parsing and deduction, a new and more general view of chart parsing is obtained, which encompasses parsing for grammar formalisms based on unification, and is the basis of the Earley Deduction proof procedure for definite clauses. The efficiency of this approach for an interesting class of grammars is discussed.
- A. V. Aho and J. D. Ullman. The Theory of Parsing, Translation and Compiling (Prentice-Hall, Englewood Cliffs, New Jersey, 1972). Google Scholar
Digital Library
- R. S. Boyer and J S. Moore, "The Sharing of Structure in Theorem-Proving Programs," in Machine Intelligence 7, B. Meltzer and D. Michie, eds., pp. 101--116 (John Wiley & Sons, New York, New York, 1972).Google Scholar
- J. Bresnan and R. Kaplan. "Lexical-Functional Grammar: A Formal System for Grammatical Representation," in The Mental Representation of Grammatical Relations, J. Bresnan, ed., pp. 173--281 (MIT Press, Cambridge, Massachusetts, 1982).Google Scholar
- A. Colmerauer, "Metamorphosis Grammars," in Natural Language Communication with Computers, L. Bolc, ed. (Springer-Verlag, Berlin, 1978). First appeared as 'Les Grammaires de Metamorphose', Groupe d'Intelligence Artificielle, Université de Marseille II, November 1975. Google ScholarDigital Library
- J. Earley, "An Efficient Context-Free Parsing Algorithm," Communications of the ACM, Vol. 13, No. 2, pp. 94--102 (February 1970). Google ScholarDigital Library
- G. Gazdar and G. Pullum, Generalized Phrase Structure Grammar: A Theoretical Synopsis (Indiana University Linguistics Club, Bloomington, Indiana, 1982).Google Scholar
- S. L. Graham, M. A. Harrison and W. L. Ruzzo, "An Improved Context-Free Recognizer," ACM Transactions on Programming Languages and Systems, Vol. 2, No. 3, pp. 415--462 (July 1980). Google ScholarDigital Library
- M. Kay, "Functional Grammar," Proc. of the Fifth Annual Meeting of the Berkeley Linguistic Society, pp. 142--158. Berkeley Linguistic Society, Berkeley, California (February 17--19 1979).Google Scholar
- M. Kay. "Algorithm Schemata and Data Structures in Syntactic Processing," Technical Report, XEROX Palo Alto Research Center, Palo Alto, California (1980). A version will appear in the proceedings of the Nobel Symposium on Text Processing, Gothenburg, 1980.Google Scholar
- R. A. Kowalski, Logic for Problem Solving (North Holland, New York, New York, 1980). Google ScholarDigital Library
- M. C. McCord, "Slot Grammars," American Journal of Computational Linguistics, Vol. 6. No. 1. pp. 255--286 (January-March 1980). Google ScholarDigital Library
- F. C. N. Pereira. "Extraposition Grammars," American Journal of Computational Linguistics, Vol. 7. No. 4. pp. 243--256 (October-December 1981). Google ScholarDigital Library
- F. C. N. Pereira. Logic for Natural Language Analysis, Ph.D. thesis. University of Edinburgh. Scotland. 1982.Google Scholar
- F. C. N. Pereira and D. H. D. Warren. "Definite Clause Grammars for Language Analysis - a Survey of the Formalism and a Comparison with Augmented Transition Networks." Artificial Intelligence, Vol. 13. pp. 231--278 (1980).Google ScholarCross Ref
- F. C. N. Pereira and D. H. D. Warren, "Parsing as Deduction," Forthcoming technical note, Artificial Intelligence Center, SRI International, Menlo Park, California (1983).Google Scholar
- J. A. Robinson, "A Machine-Oriented Logic Based on the Resolution Principle," Journal of the ACM, Vol. 12, pp. 23--44 (January 1965). Google ScholarDigital Library
- P. Roussel, "Prolog: Manuel de Référence et Utilisation," Technical Report, Groupe d'Intelligence Artificielle, Université d'Aix-Marseille II, Marseille, France (1975).Google Scholar
- S. Shieber, Personal communication, 1983.Google Scholar
- H. Thompson, "Chart Parsing and Rule Schemata in GPSG," Proc. of the 19th Annual Meeting of the Association for Computational Linguistics, pp. 167--172, Association for Computational Linguistics, Stanford University, Stanford, California (June 29-July 1 1981). Google ScholarDigital Library
- M. H. van Emden and R. A. Kowalski, "The Semantics of Predicate Logic as a Programming Language," Journal of the ACM, Vol. 23, No. 4, pp. 733--742 (October 1976). Google ScholarDigital Library
- D. H. D. Warren, Earley Deducation. Unpublished note, 1975.Google Scholar
- D. H. D. Warren and F. C. N. Pereira, An Efficient Easily Adaptable System for Interpreting Natural Language Queries. To appear in the American Journal of Computational Linguistics., 1983. Google ScholarDigital Library
- Parsing as deduction
Recommendations
Parsing as natural deduction
ACL '89: Proceedings of the 27th annual meeting on Association for Computational LinguisticsThe logic behind parsers for categorial grammars can be formalized in several different ways. Lambek Calculus (LC) constitutes an example for a natural deduction1 style parsing method.In natural language processing, the task of a parser usually consists ...
LLLR parsing
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied ComputingThe idea of an LLLR parsing is presented. An LLLR(k) parser can be constructed for any LR(k) grammar but it produces the left parse of the input string in linear time (in respect to the length of the derivation) without backtracking. If used as a basis ...
Comments