Mihai Ciocoiu, Štefan Bruda *
GULiveR: Generalized Unification Based LR Parser for Natural Languages
For a faster production retrieval
in grammar and also for a better efficiency of any unification,
structured categories are implicitly indexed by "cat"
attribute: any unification (or dag retrieval which is basically
a set of unifications) verifies first the equality of the value
of that attribute in the two dags; if the two values do not match
then the unification fails immediately.
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
- 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.
- M. KAY, Unification in Grammar, in V. Dahl, P. Saint-Dizier
(eds.) Natural Language Understanding and Logic Programming, North
Holland, Amsterdam, 1985.
- M. KAY, Parsing in Functional-Unification Grammar,
in D. R. Dorothy, L. Karttunen, A. M. Zwicky (eds.) Natural Language
Processing, Cambridge Univ. Press, 1985.
- G. GAZDAR, E. KLEIN, G. PULLUM, I. SAG, Generalized Phrase
Structure Grammar, Blackwell, Oxford, 1985.
- H. USZKOREIT, Categorial Unification Grammar, in COLING-86.
- C. POLLARD, I. SAG, Information Based Syntax and Semantics,
vol. 1, CSLI Lecture Notes, Chicago Univ. Press, Chicago, 1987.
- S. SHEIBER, An Introduction to Unification-Based Approaches
to Grammar, CSLI Lecture Notes, Chicago Univ. Press, Chicago,
1986.
- A.V. AHO, J.D. ULLMAN, The Theory of Parsing, Translation
and Compiling, Prentice Hall, 1972.
- J. EARLY, An Efficient Context-Free Parsing Algorithm,
CACM 13/2 (1970).
- M. TOMITA, S.K. NG, The Generalized LR Parsing Algorithm,
Kluwer Academic Publishers, 1991.
- J.R. KIPPS, GRL Parsing in Time O(n3), in M. Tomita
(Ed.) Generalized LR Parsing Algorithm, Kluwer Academic Publishers,
1991.
- 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).
- F. PEREIRA, A Structured Sharing Representation for Unification
Based Grammar Formalisms, SRI International, 1985.
- T. NAKAZAWA, An Extended LR Parser Algorithm for Grammars
using Feature-Based Syntactic Categories, Proceedings of the
5th EACL Conference, Berlin 1991.
- O. POPESCU, D. TUFIª, V. MIHALACHE, A. BOANGIU, Modelare
cognitiva a limbajelor naturale, ICI, 1993.
- M. ROSNER, P. CATTANEO, D. TUFIª, On-Line Summer School
on AI Technology Ongoing Swiss-Romanian Cooperation, in ELSNews,
January 1995.
- 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