Maximizing Top-down Constraints for Unification-based Systems

Maximizing Top-down Constraints for Unification-based Systems Noriko Tomuro School of Computer Science, Telecommunications and Information Systems DePaul University Chicago, IL 60604 cphdnt@ted.cs.depaul.edu Abstract A left-corner parsing algorithm with top- down filtering has been reported to show very efficient performance for unification- based systems. However, due to the non- termination of parsing with left-recursive grammars, top-down constraints must be weakened. In this paper, a general method of maximizing top-down constraints is pro- posed. The method provides a procedure to dynamically compute *restrictor., a minimum set of features involved in an in- finite loop for every propagation path; thus top-down constraints are maximally prop- agated. 1 Introduction A left-corner parsing algorithm with top-down filter- ing has been reported to show very efficient perfor- mance for unification-based systems (Carroll, 1994). In particular, top-down filtering seems to be very ef- fective in increasing parse efficiency (Shann, 1991). Ideally all top-down expectation should be propa- gated down to the input word so that unsuccess- ful rule applications are pruned at the earliest time. However, in the context of unification-based parsing, left-recursive grammars have the formal power of a Turing machine, therefore detection of all infinite loops due to left-recursion is impossible (Shieber, 1992). So, top-down constraints must be weakened in order for parsing to be guaranteed to terminate. In order to solve the nontermination problem, Shieber (1985) proposes restrictor, a statically pre- defined set of features to consider in propagation, and restriction, a filtering function which removes the features not in restrictor from top-down expec- tation. However, not only does this approach fail to provide a method to automatically generate the re- strictor set, it may weaken the predicative power of top-down expectation more than necessary: a glob- ally defined restrictor can only specify the least com- mon features for all propagation paths. In this paper, a general method of maximizing top-down constraints is proposed. The method provides a procedure to dynamically compute *restrictor*, a minimum set of features involved in an infinite loop, for every propagation path. Fea- tures in this set are selected by the detection func- tion, and will be ignored in top-down propagation. Using .vestrictor., only the relevant features par- ticular to the propagation path are ignored, thus top-down constraints are maximally propagated. 2 Notation We use notation from the PATR-II formalism (Shieber, 1986) and (Shieber, 1992). Directed aeyclie graphs (dags) are adopted as the representa- tion model. The symbol -" is used to represent the equality relation in the unification equations, and the symbol • used in the form of pl • p2 represents the path concatenation of pl and p2. The subsumption relation is defined as "Dag D subsumes dag D ~ if D is more general than D'." The unification of D and D ~ is notated by D tJ D ~. The extraction function D/pl extracts the subdag under path pl for a given D, and the embedding function D \ pl injects D into the enclosing dag D' such that D'/pl = D. The filtering function …

Content truncated to 500 words