A Modular Architecture for Constraint-Based Parsing

A MODULAR ARCHITECTURE FOR CONSTRAINT-BASED PARSING Francois Barthdlemy ~" Fran(;ois Rouaix 0 0 INRIA Roequeneourt, BP 105, 78153 Le Chesnay cedex, France & Universidade Nova de Lisboa, 2825 Monte de Caparica, Portugal ABSTRACT This paper presents a framework and a system for implementing, comparing and analyzing parsers for some classes of Constraint-Based Grammars. The framework consists in a uniform theoretic description of parsing algorithms, and provides the structure for decomposing the system into logical components, with possibly several inter- changeable implementations. Many parsing al- gorithms can be obtained by compositi(m of the modules of our system. Modularity is also ,~ way of achieving code sharing for the common parts of these various algorithms. Furthermore, tile de- sign lielpi~ reusing the existing modules when im- plementing other algorithms. The system uses the flexible modularity provided by the program- mifig languages hleool-90, 1)ased on a type system that ensures the safety of module composition. 1 INTRODUCTION We designed a system to study parsing. Our aim was not to implement only one parsing algorithm, but as many as possible, in such a way that we could compare their performances. We wanted to study parsers' behavior rather than using them to exploit their parses. Furthermore, we wanted a system opened to new developments, impossibh~ to predict at the time we began our project. We achieved these aims by detining a mo(lular architecture that gives us in addition code sharing between alternative implementations. Onr system, called APOC-II, implements more than 60 ditferent parsing algorithms for Context- Free Grammars, Tree-Adjoining Grammars, and Definite-Clause Grammars. The different gener- ated parsers are comparable, because they are im- plemented in the same way, with common data structures. Experimental comparison can involve more than 20 parsers for a given grammar and give results independent from the implementa- tion. Fnrthermore, adding new modules multiplies the mHnber of parsing Mgorithm. APOC-II is open to new parsing techniques to such an ex- tent that it can be seen as a library of tools for parsing, including constraint solvers, look-ahead, parsing strategies and control strategies. These tools make prototyping of parshlg algorithms eas- ier an(l qui(:ker. The system is I)ase(1 on a general framework that divides parsing matters in three different tasks. First, tl,e compili~tion that translates a grammar into a push-down automaton (tescrib- ing how a parse-tree is built. The automaton can be non-determinlstic if several trees have to be eonsidere(l when parsing a string. Second, the interl)retation of the push-down ~mtomaton that has to deal with non-determinism. Third, the constraint solving, used by 1)oth eomi)ilation and interpretation to perform operations related to constraints. Several algorithms can perform each of these three tasks: the compiler can generate either top- down or bottom-up automata, the interl)reter can make use of backtracldng or of tal)ulation and the solver has to deal with different kinds of con- straints (first-order terms, features, ... ). Our architecture allows different combinations of three components (one for each basic task) re- sulting into a specific parsing system. We use the …

Content truncated to 500 words