5.2 Simulating split-bilexical grammars with a left-corner strategy
5.2.3 Algorithm
Figures 5.2 and 5.3 describe the algorithm that parses SBGs with the left-corner parsing strategy.
Each inference rule can be basically mapped to a particular action of the transition, though the mapping is sometimes not one-to-one. For example SHIFTaction is divided into two cases, LEFT
and RIGHT, for achieving head-splitting. Some actions, e.g., INSERT(INSERT-LEFTand INSERT -RIGHT) and LEFTCOMP(LEFTCOMP-L-* and LEFTCOMP-R-*) are further divided into two cases depending on tree structure of a stack element, i.e., whether a predicted node (a dummy) is a head of the stack element or some right dependent.
Each chart item preserves the current stack depthd. The algorithm only accepts an item span-ning the whole sentence (including the dummy root symbol$at the end of the sentence) with the stack depth one and this condition certifies that the derivation can be converted to a valid sequence of transitions. When our interest is to eliminate derivations that contain the specific depth of center-embedding, it can be achieved by assigning zero weight to every chart cell in which the depth exceeds the threshold.
See LEFTCOMP-L-1 and LEFTCOMP-L-2 (LEFTCOMP-R-* is described later); these are the points where deeper stack depth might be detected. These two rules are the result of decomposing a single LEFTCOMPaction in the transition system into theleft phase, which collects only left half constituent given a headh, andright phase, which collects the remaining. Figure 5.4 describes how
SHIFT-LEFT: q∈final(Lh)
1≤h≤n q :d
h h
FINISH-LEFT: q:d
i h q ∈init(Lh) I :d i h
SHIFT-RIGHT: q∈init(Rh)
1≤h≤n q:d
h h
FINISH-RIGHT: q :d
h i q∈final(Rh) F :d
h i
INSERT-LEFT: q:d
i p−1 p q∈init(Lp) I :d
i p INSERT-RIGHT: r:d
q
h p−1 p q∈init(Lp) r:d
h p LEFTPRED:
:d i h j
r∈final(Lp) r7−→h q∈Lp
q:d
i j p
RIGHTPRED: r:d
h i
q∈final(Lp) r7−→p r′ ∈Rh r′ :d
q
h i p
COMBINE: I :d i h
F :d h j :d
i h j
ACCEPT: I : 1 1 n+ 1
accept
Figure 5.2: An algorithm for parsing SBGs with a left-corner strategy inO(n4)given a sentence of lengthn, except the composition rules which are summarized in Figure 5.3. Then+ 1-th token is a dummy root token$, which only has one left dependent (sentence root). i, j, h, pare indices of tokens. The index of a head which is still collecting its dependents is decorated with a state (e.g., q). Lh andRhare left and right FSAs of SBGs given a head indexh, respectively; we reverse the proces ofLhto start withq ∈final(Lh)and finish withq∈init(Lh)(see the body). Each item is also decorated with depthdthat corresponds to the stack depth incurred when building the corresponding tree with left-corner parsing. Since an item with larger depth is only required for composition rules, the depth is unchanged with the rules above, except SHIFT-*, which corresponds to SHIFTtransition and can be instantiated with arbitrary depth. Note that ACCEPTis only applicable for an item with depth 1, which guarantees that the successful parsing process remains a single tree on the stack.
Each item as well as a statement about a state (e.g.,r∈final(Lp)) has a weight and the weight of a consequence item is obtained by the product of the weights of its antecedent items.
LEFTCOMP-L-1:
q :d
i j p
I :d j+ 1 h
b=
1 ifh−(j+ 1)≥1 0 otherwise.
b
q:d
i h p
LEFTCOMP-L-2:
b
q :d
i h p
F :d′
h j q 7−→h q′ ∈Lp
d′ =
d+ 1 if b= 1 or(j−h)≥1 d otherwise.
q′ :d
i j p
LEFTCOMP-R-1:
r :d
q
i j p
I :d j+ 1 h
b=
1 ifh−(j+ 1)≥1 0 otherwise.
q r :d b
i h p
LEFTCOMP-R-2:
q r :d b
i h p
F :d′
h j q 7−→h q′ ∈Lp
d′ =
d+ 1 if b= 1 or(j−h)≥1 d otherwise.
r:d
q′
i j p
RIGHTCOMP: r :d
q i h−1 h
q′ :d′ h j
q ∈init(Lh)
q′ 7−→p q′′∈final(Rh) s∈final(Lp)
d′ =
d+ 1 if (j−h)≥1 d otherwise.
r:d
s
i j p
Figure 5.3: The composition rules that are not listed in Figure 5.2. LEFTCOMPis devided into two cases, LEFTCOMP-L-* and LEFTCOMP-R-* depending on the position of the dummy (predicted) node on the left antecedent item (corresponding to the second top element on the stack). They are further divided into two processes, 1 and 2 for achieving head-splitting.bis an additional annotation on an intermediate item for correct depth computation in LEFTCOMP.
Stack:
x a
x b
d c e
1 2 3 Buffer:
f · · ·
(a) A configuration of the transition system.
Stack:
x a
x b
d c
d e
1 2 3 Buffer:
f · · ·
(b) After head splitting.
Stack:
x a
x b d
c
d e
1 2 3 Buffer:
f · · ·
(c) After LEFTCOMP-L-1 on (b).
Stack:
x a
x b d
c e
1 2 Buffer:
f · · ·
(d) After LEFTCOMP-L-2 on (c).
Figure 5.4: We decompose the LEFTCOMPaction defined for the transition system into two phases, LEFTCOMP-L-1 and LEFTCOMP-L-2, each of which collects only left or right half constituent of a subtree on the top of the stack. A number above each stack element is the stack depth decorated on the corresponding chart item.
this decomposition looks like in the transition system. As shown in Figure 5.4(b), we imagine that the top subtree on the stack is divided into a left and right constituents.2 In Figure 5.4 we number each subtree on the stack from left to right. Note that then the number of the rightmost (top) element on the stack corresponds to the stack depth of the configuration. This value corresponds to the depth annotated on each item in the algorithm, such asd′in
F :d′
appeared as the right antecedent item of LEFTCOMP-L-2 in Figure 5.3. Then, since the left antecedent item of the same rule, i.e., , corresponds to the second top element on the stack, its depthd is generally smaller by one, i.e., d=d′−1.
One complicated point with this depth calculation is that larger stack depth should not always be detected during this computation. Recall the discussion in Section 4.3.4 that there are two kinds of stack depth that we called depthre and depthsh, in which only depthre correctly captures the center-embeddedness of a construction. Depthshis the depth of a configuration after a shift action, on which the top element iscomplete, i.e., contains no dummy (predicted) node. Note that the depth annotated on each subtree in Figure 5.3 is in fact depthsh, as the right antecedent item of each rule (corresponds to the top element on the stack) does not contain a predicted node. Since our goal is to capture the center-embeddedness during parsing, we fix this discrepancy with a small trick, which is described as the side condition of LEFTCOMP-L-1 and LEFTCOMP-L-2 in Figure 5.3. The point at which only depthshincreases by 1 is when a shifted token is immediately reduced with a following composition rule. We treat this process as a special case and do not increase the stack depth when the span length of the subtree that is reduced with a composition rule (right antecedent) is 1.
2This assumption does not change the incurred stack depth at each step since in the left-corner transition system, right half dependents of a head are collected only after its left half construction is finished. Splitting a head as in Figure 5.4(b) means that we treat these left and right parsing processes independently.
The remained problem is that because we split each constituent into left and right constituents, we cannot calculate the size of the reduced constituent immediately. The additional variablebin Figure 5.3 is introduced for checking this condition.bis set to 1 if the left part, i.e., LEFTCOMP-L-1 collects a constituent with span length greater than one (h=j+ 1indicates one word constituent).
Ifb = 1, regardless of the size of remaining right constituent, the second phase, or the right part LEFTCOMP-L-2 always increases the stack depth (i.e., d′ = d+ 1). b= 0means the size of left constituent is zero; in this case, the stack depth is increased when the size of the right constituent is greater than one. In summary, the stack depth of the right antecedent item is increasedunlessthree indices,j+ 1andhin LEFTCOMP-L-1 andjin LEFTCOMP-L-2 are identical, which occurs when the reduced constituent is a single shifted token.
Finally, we note that we do not modify the depth of the right antecedent item of LEFTCOMP -L-1. This is correct since the consequent item of this rule , which waits for a right half constituent ofh, can only be used as an antecedent of the following LEFTCOMP-L-2 rule. The role of LEFTCOMP-L-1 is just to annotate the head of the reduced constituent and the span length. Then LEFTCOMP-L-2 checks the depth condition and calculates the weight associated with LEFTCOMP
action (i.e.,q7−→h q′ ∈Lp).
The other part of the algorithm can be understood as follows:
• LEFTCOMP-R-* is almost the same as LEFTCOMP-L-*. The difference is in the tree shape of the left antecedent item; in the R case, it is a right half constituent with a predicted node , which corresponds to a subtree in which the predicted node is not the head but the tail of the right spine. We distinguish these two trees in the algorithm since they often behave very differently as shown in Figure 5.2. Note that has two FSA states since it contains two head tokens collecting its dependents (i.e., the head of the tree and the predicted token).
• Differently from LEFTCOMP, RIGHTCOMPis summarized as a single rule while it seems a bit complicated. In the algorithm, RIGHTCOMPcan only be performed when the predicted token of finishes collecting its left dependents (indicated as the consecutive indices ofh−1 andh). See Section 5.2.4 for the reason of this restriction. Another condition for applying this rule is that the right state q′ of head h must be a final state after applying transition q′ 7−→p q′′, which collects new rightmost dependent ofh, i.e.,p. Under these conditions, the rule performs the following parser actions: 1) attachpas a right dependent ofh; 2) finishes the right FSA ofh; and 3) start collecting left dependents ofpby setting the final state to the left state of it.
• Some rules such as FINISH-* and COMBINEdo not exist in the original transition system.
We introduce these to represent the generative process of SBGs in the left-corner algorithm.
• We do not annotate a state on a triangle :d
. This is because it can only be deduced by COMBINE, which combines two finished constituents with the same head.
• A parse always finishes with a consecutive application of LEFTPRED, INSERT-LEFT, and ACCEPT after a parse spanning the sentence 1 n is recognized. LEFTPREDpredicts
the arc between the dummy root token$at n+ 1-th position and this parse tree, and then INSERT-LEFTremoves this predicted arc. Note that to get a correct parse the left FSA for$ should be modified appropriately for not collecting more than one dependent (the common parameterization of DMV automatically achieve this).