Mihai Ciocoiu, Ştefan Bruda * GULiveR: Generalized Unification Based LR Parser for Natural Languages

The unification is a very important process in any parser. Even if we used in our application one of the most efficient algorithms, we are currently testing another dag representation which uses binary trees and lazy evaluation [17] (the dags in that representation also shares structures and allow an efficient duplication). This representation does not use an environment structure and therefore may be more appropriate to our application. Anyway, no comparisons are yet available.

The initial project included a minimal interface because a parser cannot be a stand alone program (it can be used either for natural language understanding or machine translation). We included later a graphical interface (Macintosh) for didactic purposes (because PAIL is first of all a didactic system). This interface offers possibilities to view the parse forest (figure 5), to trace the execution (figure 3) and to view the parse table (figure 1). The application offers an exhaustive base for compositional semantic analysis by the parse forest produced, and is fast enough to be useful on such a small platform as the Mac.

We tested the parser using a small grammar which models the enunciative English phrases. We intend to use the application for a complete Romanian grammar.

Acknowledgments. Special thanks to Dr. Dan Tufi who helped us to bring up to life this project. Without his comments and advice this paper would not have been the same.

References

1. R. KAPLAN, J. BRESNAN, Lexical-Functional Grammar, a Formal System for Grammatical Representation, in J. Bresnan (ed.) The Mental Representation of Grammatical Relations, The MIT Press, Cambridge, MA, 1982.
   
   
2. M. KAY, Unification in Grammar, in V. Dahl, P. Saint-Dizier (eds.) Natural Language Understanding and Logic Programming, North Holland, Amsterdam, 1985.
   
   
3. M. KAY, Parsing in Functional-Unification Grammar, in D. R. Dorothy, L. Karttunen, A. M. Zwicky (eds.) Natural Language Processing, Cambridge Univ. Press, 1985.
   
   
4. G. GAZDAR, E. KLEIN, G. PULLUM, I. SAG, Generalized Phrase Structure Grammar, Blackwell, Oxford, 1985.
   
   
5. H. USZKOREIT, Categorial Unification Grammar, in COLING-86.
   
   
6. C. POLLARD, I. SAG, Information Based Syntax and Semantics, vol. 1, CSLI Lecture Notes, Chicago Univ. Press, Chicago, 1987.
   
   
7. S. SHEIBER, An Introduction to Unification-Based Approaches to Grammar, CSLI Lecture Notes, Chicago Univ. Press, Chicago, 1986.
   
   
8. A.V. AHO, J.D. ULLMAN, The Theory of Parsing, Translation and Compiling, Prentice Hall, 1972.
   
   
9. J. EARLY, An Efficient Context-Free Parsing Algorithm, CACM 13/2 (1970).
   
   
10. M. TOMITA, S.K. NG, The Generalized LR Parsing Algorithm, Kluwer Academic Publishers, 1991.
    
    
11. J.R. KIPPS, GRL Parsing in Time O(n3), in M. Tomita (Ed.) Generalized LR Parsing Algorithm, Kluwer Academic Publishers, 1991.
    
    
12. F. PERREIRA, D. WARREN, Definite Clause Grammars for Language Analysis - A Survey of the Formalism and a Comparison with Augmented Transition Networks, Artificial Intelligence, 13, 231-278, (1980).
    
    
13. F. PEREIRA, A Structured Sharing Representation for Unification Based Grammar Formalisms, SRI International, 1985.
    
    
14. T. NAKAZAWA, An Extended LR Parser Algorithm for Grammars using Feature-Based Syntactic Categories, Proceedings of the 5th EACL Conference, Berlin 1991.
    
    
15. O. POPESCU, D. TUFIª, V. MIHALACHE, A. BOANGIU, Modelare cognitiva a limbajelor naturale, ICI, 1993.
    
    
16. M. ROSNER, P. CATTANEO, D. TUFIª, On-Line Summer School on AI Technology Ongoing Swiss-Romanian Cooperation, in ELSNews, January 1995.
    
    
17. L. KARTTUNEN, M. KAY, Structure Sharing with Binary Trees, in More Notes from the Unification Underground - A Second Compilation of Papers on Unification-Based Grammar Formalisms, SRI International, 1985.

104