An Earley-style Predictive Chart Parsing Method for Lambek Grammars

An Earley-style Predictive Chart Parsing Method for Lambek Grammars Mark Hepple Department of Computer Science, University of Sheffield, Regent Court, 211 Portobello Street, Sheffield S1 4DP, UK [heppleOdcs .shef .ac.uk] Abstract We present a new chart parsing method for Lambek grammars, inspired by a method for D- Tree grammar parsing. The formulae of a Lam- bek sequent are firstly converted into rules of an indexed grammar formalism, which are used in an Earley-style predictive chart algorithm. The method is non-polynomial, but performs well for practical purposes -- much better than previous chart methods for Lambek grammars. 1 Introduction We present a new chart parsing method for Lambek grammars. The starting point for this work is the observation, in (Hepple, 1998), of certain similarities between categorial gram- mars and the D-Tree grammar (DTG) formal- ism of Rambow et al. (1995a). On this basis, we have explored adapting the DTG parsing ap- proach of Rambow et al. (1995b) for use with the Lambek calculus. The resulting method is one in which the formulae of a Lambek sequent that is to be proven are first converted to pro- duce rules of a formalism which combines ideas from the multiset-valued linear indexed gram- mar formalism of Rainbow (1994), with the Lambek calculus span labelling scheme of Mor- rill (1995), and with the first-order compilation method for categorial parsing of Hepple (1996). The resulting 'grammar' is then parsed using an Earley-style predictive chart algorithm which is adapted from Rambow et al. (1995b). 2 The Lambek Calculus We are concerned with the implicational (or 'product-free') fragment of the associative Lam- bek calculus (Lambek, 1958). A natural deduc- tion formulation is provided by the following rules of elimination and introduction, which cor- respond to steps of functional application and abstraction, respectively (as the term labelling reveals). The rules are sensitive to the order of assumptions. In the [/I] (resp. [\I]) rule, [B] in- dicates a discharged or withdrawn assumption, which is required to be the rightmost (resp. left- most) of the proof. A/B :a B :b /E B:b B\A a A: (ab) A: (ab) • ....[B: v] [B: v].:. A:a A:a /I \I A/B : Av.a B\A : Av.a \E (which) (mary) (ate) rel/(s/np) np (np\s)/np [np] /E np\s \E S rel The above proof illustrates 'hypothetical reasoning', i.e. the presence of additional as- sumptions ('hypotheticals') in proofs that are subsequently discharged. It is because of this phenomenon that standard chart methods are inadequate for the Lambek calculus -- hypo- theticals don't belong at any position on the single ordering over lexical categories by which standard charts are organised. 1 The previ- ous chart methods for the Lambek calculus deal with this problem in different ways. The method of K6nig (1990, 1994) places hypothet- icals on separate 'minicharts' which can attach into other (mini)charts where combinations are 1In effect, hypotheticals belong on additional subor- derings, which can connect into the main ordering of the chart at various positions, generating a branching, multi-dimensional ordering scheme. 465 possible. The …

Content truncated to 500 words