A General, Sound and Efficient Natural Language Parsing Algorithm based on Syntactic Constraints Propagation

A General, Sound and Efficient Natural Language Parsing Algorithm based on Syntactic Constraints Propagation∗ Jos´e F. Quesada CICA (Centro de Inform´atica Cient´ıfica de Andaluc´ıa) Sevilla, Spain e-mail: [email protected] Abstract This paper presents a new context-free parsing algorithm based on a bidirectional strictly horizontal strategy which incorporates strong top–down predictions (derivations and adjacencies). From a functional point of view, the parser is able to propagate syntactic constraints reducing parsing ambiguity. From a computational perspective, the algorithm includes different techniques aimed at the improvement of the manipulation and representation of the structures used. 1 Parsing Ambiguity and Parsing Efficiency In Formal Language Theory [Aho & Ullman 1972, Drobot 1989] a language is a set, and in Set Theory an element belongs or not to a set. That is to say, a set (and therefore a language) is an unambiguous structure. A grammar may be considered as an intensive definition of a language. Thus, the notion of grammaticality corresponds to the relation of membership over a language (set). But a grammar incorporates more information than the simple report of the elements of the language (the extensive specification). A grammar defines a structure: the parse tree or forest. The distance between grammaticality and grammatical structure is a first level of ambiguity: grammatical ambiguity. The next notion to take into account is the process of analysis of a string of words with a grammar, that is, the parser [Kay 1980, Bolc 1987, Sikkel & Nijholt 1997]. A parser must be able to determine the relation of grammaticality and to obtain the grammatical structure, by mean of a set of operations, that we will call the parsing structure. The distance between the grammatical structure and the parsing structure defines a second level of ambiguity: parsing ambiguity, usually referred as temporal ambiguity. Parsing ambiguity depends on two factors: the grammar and the parsing strategy. A very important design requirement of natural language parsers is to eliminate parsing ∗Jose F. Quesada: A General, Sound and Efficient Natural Language Parsing Algorithm based on Syntactic Constraints Propagation. Proceedings of CAEPIA’97, M/’alaga, Spain. 775–786 ambiguity, that is, to reduce the work done by the parser to the amount of grammatical structures allowed by the grammar. The work presented here is a step more in this direction [Earley 1970, Kay 1980, Tomita 1987, Tomita 1991, Dowding et al. 1994, ?]. The second goal of this paper is to present a computational model aimed at the improvement of the efficiency of the algorithm [Carroll 1994, Quesada & Amores Forthcoming]. In this sense, our proposal may be understood as the incorporation of strong top–down predictions (partial derivations and adjacencies) over a bottom–up framework. And the two strategies (bottom–up and top–down) are mixed by a mechanism able to propagate syntactic constraints over a bidirectional model based on a strictly horizontal strategy [Quesada 1996]. Section 2 presents an informal introduction to the problem of parsing ambiguity with chart parsing [Kay 1980], but similar situations may be described for other strategies like Earley’s algorithm [Earley 1970], DCG [Pereira & Warren 1980], GLR [Chapman 1987, Tomita 1991], etc. Section 3 defines formally the relations that support the mechanism of bottom–up bidirectional analysis, top–down predictions and constraints propagation. Section 4 presents in detail the parsing algorithm and finally Section 5 shows some experimental results. 2 An Informal Introduction Let us consider the following grammar: S -> A1 b S -> A2 c A1 -> a A1 -> a A1 A2 -> a A2 -> a A2 and the string of words a a a b. Figure 1 shows the arcs genereted by a bidirectional chart parser in a first stage where we have created only the arcs with at least one pre– terminal symbol. Each arc has been identified by a number, and indicates the symbol that the arc will generate and the expected symbol (only for active arcs). 1 A1 A1 A1 3 4 A2 A2 2 A2 a0 A2 A1 a A2 A2 A1 A1 A2 A2 A1 A1 a A1 A2 b1 2 3 4 5 6 7 8 9 10 11 12 S A1 13 Figure 1 Let us consider what happens at position 3 . There exists an obvious relation between arcs 13 and 9, but arcs 10,11 and 12 don’t have a correspondent link at this position. Figure 2 shows the parsing state once we have deleted these three arcs. 1 A1 A1 A1 3 4 A2 A2 2 A2 a0 A1 a A2 A2 A1 A1 a A1 A2 b1 2 3 4 5 6 7 8 9 S A1 13 Figure 2 At position 2 there exists a relation between arcs 7and 9, and arcs 5,6and 8may be deleted. Once we have deleted these three arcs, if we analyze position 1 we can delete now arcs 1,2and 4obtaining Figure 3. A1 A1 3 a0 A1 a A1 A1 a b1 2 3 4 7 9 S A1 13 Figure 3 Therefore, our next goal will be to define formally the relations between arcs that guarantee their success during parsing. 3 The Mathematical Kernel 3.1 Bottom-Up Derivation Given a context-free grammar G=< GT, GN, GP, GR>where we have distinguished their set of productions GP, roots GR, terminal symbols GT, non-terminal symbols GN and vocabulary GV=GT∪GN, we will define the bottom-up derivation as follows. Let be δ∈GVand ∆,Γ,Ω∈G∗ V. The direct bottom–up derivation in G,−→G, is defined as: Γ∆Ω −→GΓδΩ iff δ−→ ∆∈GP The bottom–up derivation in G, =⇒G, will be defined as the reflexive and transitive closure of the direct bottom–up derivation: Γ =⇒GΩ iff ∃∆1,...,∆n∈G∗ Vsuch that ∀i(1≤i<n)∆i−→G∆i+1 where ∆1≡Γ and ∆n≡Ω 3.2 Partial Derivability and Adjacency Root Symbols. αis a root symbol: R(α) iff α∈GR Epsilon Symbols. αis an epsilon symbol: E(α) iff ε=⇒Gα1 1εis the empty string. String of Epsilon Symbols. ∆ is a string of epsilon symbols: E(∆) iff ∀δ∈ ∆(E(δ)) Left Partial Derivability. βis a left partial derivation of α: α7−→∗ lβiff ∃Γ,∆,Ω∈G∗ Vsuch that (Γα∆ =⇒GΓβΩ). We define LPD(α) = {β∈GV:α7−→∗ lβ} ∪ {α}2 Right Partial Derivability. βis a right partial derivation of α: α7−→∗ rβiff ∃Γ,∆,Ω∈G∗ Vsuch that (Γα∆ =⇒GΩβ∆) We define RPD(α) = {β∈GV:α7−→∗ rβ} ∪ {α}3 Primary Adjacency. βis a primary adjacent of α: α⇑βiff ∃δ∈GVand ∃Γ,Ω,∆∈G∗ Vsuch that (δ−→ Γα∆βΩ∈GP∧E(∆)) Left Adjacency. βis a left adjacent of α: α⇑∗ lβiff ∃γ∈LPD(α) and ∃δ∈RPD(β) such that (δ⇑γ) We define LA(α) = {β∈GV:α⇑∗ lβ}. Right Adjacency. βis a right adjacent of α: α⇑∗ rβiff ∃γ∈RPD(α) and ∃δ∈LPD(β) such that (γ⇑δ) We define RA(α) = {β∈GV:α⇑∗ rβ}. Left–Most Symbol. αis a left–most symbol: LM(α) iff ∃δ∈GVsuch that (α7−→∗ lδ∧R(δ)) Right–Most Symbol. αis a right–most symbol: RM(α) iff ∃δ∈GVsuch that (α7−→∗ rδ∧R(δ)) 3.3 Coverage Tables Finally we present the formal definition of the coverage tables which are in charge of triggering the events of the bidirectional parser. For each symbol of a grammar, α∈GV, their left, LC1(α) and LC2(α), medium, MC(α), and right, RC(α), coverages are defined as sets of productions in the following way: LC1(α) = {(δ−→ α∈GP) : δ∈GN} LC2(α) = {(δ−→ αΩ∈GP) : δ∈GN∧Ω∈G∗ V∧ ¬E(Ω)} MC(α) = {(δ−→ ∆αΩ∈GP) : δ∈GN∧Ω,∆∈G∗ V∧ ¬E(∆) ∧ ¬E(Ω)} RC(α) = {(δ−→ ∆α∈GP) : δ∈GN∧∆∈G∗ V∧ ¬E(∆)} 2We will consider that a symbol is a left partial derivation of itself. 3We will consider that a symbol is a right partial derivation of itself. 4 The Parsing Algorithm 4.1 Parsing Input. The main task of the lexical analyzer is to separate the input string in a set of items, each one associated with one or more (lexical ambiguity) pre-terminal symbols (syntactic categories). Our parsing algorithm is also able to deal with “multi-word expressions” and “multi-expression words”4. In any case, the parsing input will be a list of breaking points and a set of preterminal symbols, each one associated with a lexical unit (a portion of the input string) and two breaking points. For instance, we can consider the input string a a a b. This string will be lexically analyzed obtaining 5 breaking points and 4 pre-terminal symbols: 0a1a2a3b4 4.2 Step 1: CaD creation. For each breaking point we will generate a CaD (collection and diffusion of information) structure, which has 6 fields: the first four fields are lists of Events and the two last ones are lists of Nodes:tole (events arriving at the CaD from the right side), frle (events going to the left from the CaD), tori (events arriving at the CaD from the left side), frri (events going to the right from the CaD), ndle (nodes at the left of the CaD) and ndri (nodes at the right of the CaD). If the lexical analyzer has obtained nbreaking points, then we will store the CaD structures as a matrix of npointers to CaD structures. We will call this matrix CaDroot. 4.3 Step 2: Node creation. For each element <lexical_unit,pre-terminal_symbol,fbp5,lbp6>we will generate a Node structure, which has the following fields: grsymbol (grammar symbol) and cmanalysis (complex analysis, a list of Analysis structures). The new node newNode will be associated with the corresponding CaD structures: CaDroot[fbp]->ndri =AddNode(newNode) CaDroot[lbp]->ndle =AddNode(newNode) 4.4 Step 3: Event creation. For each node created at step 2, we will generate their correspondent events using the coverage tables. An Event has the following fields: grprod (production or grammar rule), leftdot (left dot), rightdot (right dot), leftlinks (list of Link structures associated with the left extreme), rightlinks (list of Link structures associated with the right extreme) and status (logical status). Let us suppose that the node created (newNode) has been associated with the grammar symbol α. Then: For each production p∈LC1(α) we will create the appropriate new event (newEvent) and: 4Words that contain more than one lexical unit, such as clitics in Spanish or compounds in German. 5The first or left breaking point of the lexical unit. 6The last or right breaking point of the lexical unit. CaDroot[fbp]->frri =AddEvent(newEvent) CaDroot[lbp]->frle =AddEvent(newEvent) For each production p∈LC2(α) we will create the appropriate new event (newEvent) and: CaDroot[fbp]->frri =AddEvent(newEvent) CaDroot[lbp]->tole =AddEvent(newEvent) For each production p∈MC(α) we will create the appropriate new event (newEvent) and: CaDroot[fbp]->tori =AddEvent(newEvent) CaDroot[lbp]->tole =AddEvent(newEvent) For each production p∈RC(α) we will create the appropriate new event (newEvent) and: CaDroot[fbp]->tori =AddEvent(newEvent) CaDroot[lbp]->frle =AddEvent(newEvent) 4.5 Step 4: Link creation. For each event created we have to analyze their possible links with other events. This operation is internal to the CaD structure according to the following criteria: tole frle frri tori ADJACENCY FUSION DERIVATION Figure 4. Links inside a CaD structure. 4.5.1 Analyses of Partial Derivations These analyses are applied over the open extremes of an event. Basically, we have to check if the symbol needed is partially derivable from the real symbol. We will distinguish two types of analyses of derivations depending on the direction of the open extreme of the event. Left–Derivation Analysis: T OLE −F RRI.Let us suppose that an event evtole is applying the production δ−→ δ1. . . δnover the surface Γδh. . . δiγ1. . . γjΩ where 1 ≤h≤i < n and 1 ≤j≤m. In fact, this event is making a prediction of the (required) symbol δi+1 over the (real) symbol γ1. The right extreme of this event will be associated with the component tole of a CaD structure. In this case, we have to check if there exists a second event, evfrri, which left extreme belongs to the frri field of the same CaD, such that δi+1 ∈LP D(γ), where γis the left-hand side of the production associated with evfrri:γ−→ γ1. . . γm. Right–Derivation Analysis: T ORI −F RLE.Let us suppose that an event evtori is applying the production δ−→ δ1. . . δnover the surface Γγj. . . γmδh. . . δiΩ where 1 < h ≤i≤nand 1 ≤j≤m. In fact, this event is making a prediction of the (required) symbol δh−1over the (real) symbol γm. The left extreme of this event will be associated with the component tori of a CaD structure. In this case, we have to check if there exists a second event, evfrle, which right extreme belongs to the frle field of the same CaD, such that δh−1∈RPD(γ), where γis the left-hand side of the production associated with evfrle:γ−→ γ1. . . γm. 4.5.2 Analyses of Adjacencies These analyses are applied over the closed extremes of an event. Basically, we have to check the adjacency relation between the symbol that the event will generate (the left– hand side of the production) and the symbol that appears next to the closed extreme of the event. We will distinguish two types of analyses of adjacencies depending on the direction of the closed extreme of the event. Left–Adjacency Analysis: F RRI −F RLE.Let us suppose that an event evfrri is applying the production δ−→ δ1. . . δnover the surface Γγj. . . γmδ1. . . δiΩ where 1 ≤i≤nand 1 ≤j≤m. The left extreme of this event belongs to the frri field of a CaD structure. Then we have to analyze if there exists an evfrle event which right extreme belongs to the frle field of the same CaD such that γ∈LA(δ), where γis the lhs of the production of evfrle:γ−→ γ1. . . γm. If Γγj. . . γmis empty, that is, the CaD associated with the left extreme of evfrri is the first one, then we have to check if LM(δ). Right–Adjacency Analysis: F RLE −F RRI.Let us suppose that an event evfrle is applying the production δ−→ δ1. . . δnover the surface Γδi. . . δnγ1. . . γj∆ where 1 ≤i≤nand 1 ≤j≤m. The right extreme of this event belongs to the frle field of a CaD structure. Then we have to analyze if there exists an evfrri event which left extreme belongs to the frri field of the same CaD such that γ∈RA(δ), where γ is the lhs of the production of evfrri:γ−→ γ1. . . γm. If γ1. . . γj∆ is empty, that is, the CaD associated with the left extreme of evfrle is the last one, then we have to check if RM(δ). 4.5.3 Analyses of Fusions Left–Fusion Analysis: T ORI −T OLE.Let us suppose that an event evtori is applying the production δ−→ δ1. . . δnover the surface Γγδi. . . δj∆ where 1 < i ≤j≤ n. The left extreme of this event belongs to the tori field of a CaD structure. Then we have to analyze if there exists an evtole event in the tole field of the same CaD such that evtole is applying the same production that evtori over the surface δh. . . δi−1 where 1 ≤h. Right–Fusion Analysis: T OLE −T ORI.Let us suppose that an event evtole is applying the production δ−→ δ1. . . δnover the surface Γδi. . . δjγ∆ where 1 ≤i≤ j < n. The right extreme of this event belongs to the tole field of a CaD structure. Then we have to analyze if there exists an evtori event in the tori field of the same CaD such that evtori is applying the same production that evtole over the surface δj+1 . . . δkwhere k≤n. Link creation. Each time an analysis is successfull, we will generate a Link structure between the two events involved. For LM and RM analysis the Link will have only one event. 4.6 Step 5: Event’s Logical Status. Each time a Link is created we have to study the logical status of the events involved. Also, at the end of the analysis of the links of an event (step 4) we will analyze its logical status. Let be ean event applying the production δ−→ δ1. . . δi−1•δi. . . δj•δj+1 . . . δn 4.6.1 Closed-Closed events (F RRI +F RLE): i= 1 and j=n. if ((!e->leftlinks) || (!e->rightlinks)) nstatus = DELETE else nstatus = RUN 4.6.2 Closed-Open events (F RRI +T ORI): i= 1 and j < n. if (!e->leftlinks) nstatus = DELETE else if (e->rightlinks) nstatus = DERIVATION else if (E(δj+1)) nstatus = EPSILON else nstatus = DELETE 4.6.3 Open-Closed events (T OLE +F RLE): i > 1and j=n. if (!e->rightlinks) nstatus = DELETE else if (e->leftlinks) nstatus = DERIVATION else if (E(δi−1)) nstatus = EPSILON else nstatus = DELETE 4.6.4 Open-Open events (T OLE +T ORI): i > 1and j < n. if ((e->leftlinks) && (e->rightlinks)) nstatus = DERIVATION else if ((e->leftlinks) && (E(δj+1))) nstatus = EPSILON else if ((e->rightlinks) && (E(δi−1))) nstatus = EPSILON else nstatus = DELETE If nstatus is different that e->status we will change the logical status of the event. To improve the efficiency it is possible to maintain four lists of events (DERIVATION, RUN, DELETE and EPSILON). To change the status of an event implies to move the event from one list to another, but this may be done in constant time. 4.6.5 Step 6: Parsing Cycle. This is the kernel of the algorithm: cycle = 1 while (cycle) cycle = 0 if (event = GetEpsilonEvent()) cycle = 1 EpsilonExpansion(event) else if (event = GetDeleteEvent()) cycle = 1 DeleteEvent(event) else if (event = GetRunEvent()) cycle = 1 RunEvent(event) else if (link = GetFusionLink()) cycle = 1 FusionLink(link) The functions Get* return the first element of the correspondent list and change the head of the list to the following element, which are constant operations. 6.1.- Epsilon Expansion. This operation moves the left dot one position to the left or the right dot one position to the right, depending on the open extreme marked as EPSILON. 6.2.- Delete Event. To delete an event implies to delete it and their links. 6.3.- Run Event. To run a closed-closed event involves the application of a grammar rule, incorporating a new node (step 2). But if this node has been previously created between the same CaD structures, we can obtain a representation model based on subtree-sharing and local ambiguity packing, associating the analysis correspondent to the last one with the previously created node. This way, a node will have a list of Analysis structures, and this structure is defined as a list of Node structures. The result of this mechanism is a representation based on virtual relations between the skeleton of the parse forest and the nodes included in it. 6.4.- Fusion Events. Let us consider the production δ−→ δ1. . . δh. . . δiδi+1 . . . δj. . . δn and two events e1:δ−→ δ1...•δh. . . δi•δi+1 . . . δnand e2:δ−→ δ1. . . δi•δi+1 . . . δj• . . . δn.