Non-binary bottom-up constituency parsing without arity actions

Park, Jungyeul; Jo, Eunkyul Leah; Huang, Zihao

doi:10.18653/2026.findings-emnlp.611

A delimiter-guided transition system for non-binary constituency parsing that derives reduction arity from the stack configuration

Findings of EMNLP 2026

Jungyeul Park^1,*, Eunkyul Leah Jo², Zihao Huang²

¹Korea Advanced Institute of Science & Technology (KAIST), Daejeon, South Korea ²The University of British Columbia, Vancouver, Canada

^*Corresponding author

Abstract

Non-binary bottom-up constituency parsing commonly uses arity-specific reductions such as Reduce-X#k, which jointly specify the mother label and number of children. We show that arity need not be a primitive transition parameter. The proposed parser predicts the mother label separately and identifies the ordered child sequence from a delimiter-bounded stack configuration. In every well-formed reducible configuration, the active delimiter, label marker, and intervening completed items uniquely determine the reduction domain and hence its arity. This factorization removes label–arity-specific reduction actions while preserving direct construction of the original non-binary trees. Controlled experiments on PTB and CTB show that the delimiter-guided parser closely tracks an arity-specific baseline while using a substantially smaller action inventory. Its predicted trees retain the gold branching profile without systematic collapse at higher arities. The smaller inventory is obtained at the cost of longer derivations and boundary-sensitive errors involving delimiter insertion, preservation, and consumption.

Keywords Constituency parsing Transition-based parsing Shift-reduce parsing Phrase-structure parsing Syntactic parsing Penn Treebank (PTB) Chinese Treebank (CTB) Binarization EVALB / JP-EVALB

Method

Definitions of the seven delimiter-guided bottom-up transitions (Shift, D-Shift, Nt(X), U-Reduce, Reduce, D-Reduce, Finish) as rewrites of the parser configuration consisting of stack, input index and completion flag.

Figure 1. Delimiter-guided bottom-up transitions. U-Reduce constructs a preterminal; Reduce and D-Reduce compose the delimiter-bounded child sequence, respectively consuming and preserving the delimiter D. None of the reduction actions carries a label or an arity parameter.

A bottom-up parser introduces a constituent's label only after its children are built, so the label cannot mark where the children begin. Existing non-binary bottom-up parsers (Fernández-González and Gómez-Rodríguez, 2019) therefore use actions Reduce-X#k that pop exactly $k$ items and label them $X$ , so every observed label–arity pair becomes a separate classifier target. The delimiter-guided parser splits this decision in two. A parser configuration is $(\sigma, i, f)$ (stack, next input index, completion flag), starting from $(\epsilon, 0, \mathsf{false})$ , and the parser proceeds as follows.

Mark left boundaries while shifting. Shift pushes the next word; D-Shift first pushes a delimiter $D$ (the empty label marker Nt()) and then the word, marking the leftmost word of a new phrase-level reduction domain: $\text{D-Shift}:\ (\sigma, i, \mathsf{false}) \Rightarrow (\sigma \mid D \mid w_i,\ i+1,\ \mathsf{false}).$ The static oracle inserts a delimiter at $w_i$ if $i=0$ , or if the phrase-level projection (grandparent) of $w_i$ differs from that of $w_{i-1}$ and $w_i$ is at least as deep in the gold tree.
Predict the label separately. Nt( $X$ ) pushes the label marker $X$ after the children have been shifted or built. For a part-of-speech tag, U-Reduce turns $\sigma \mid w \mid X$ into $\sigma \mid X(w)$ .
Recover the reduction domain from the stack. The nearest active delimiter and the topmost label marker enclose a unique configuration $\sigma \mid D \mid s_1 \mid \cdots \mid s_k \mid X,$ and both phrase-level reductions build $X(s_1, \ldots, s_k)$ . The arity $k$ is simply the number of completed subtrees between $D$ and $X$ ; a smaller value would omit a child and a larger one would cross the left boundary, so no arity parameter is needed.
Consume or keep the delimiter. Reduce consumes $D$ when the built constituent is the one the delimiter was assigned to; D-Reduce leaves $D$ on the stack when a higher constituent shares the same left boundary. Finish ends the derivation once the input is consumed and a single root remains.

For the tree in Figure 2, the oracle runs D-Shift(Ms.), Nt(NNP), U-Reduce, Shift(Haag), Nt(NNP), U-Reduce, Nt(NP), D-Reduce, D-Shift(plays), Nt(VBZ), U-Reduce, D-Shift(Elianti), Nt(NNP), U-Reduce, Nt(NP), Reduce, Nt(VP), Reduce, Shift(.), Nt(.), U-Reduce, Nt(S), D-Reduce, Nt(TOP), Reduce, Finish. Unary, binary and ternary constituents all use the same reduction schema. After auxiliary delimiters are disregarded, each delimiter-guided reduction builds exactly the same local tree as the corresponding Reduce-X#k action.

In the experiments, the delimiter-guided parser (D) is compared with a reimplementation of the arity-specific parser (A) and a binary bottom-up parser trained on binarized trees (B). All three share the same Stanza-based neural architecture, optimization, greedy decoding and evaluation, and differ only in transition inventory, applicability conditions and static oracle. Data: the Wall Street Journal portion of the Penn Treebank (PTB; train 02–21, dev 22, test 23) and Chinese Treebank 5.1 (CTB).

Main Results

Much smaller action inventory. Removing Reduce-X#k shrinks the non-binary inventory from 202 to 78 actions on PTB and from 190 to 64 on CTB (binary parser: 126 and 148).
Accuracy close to the arity-specific parser. On the PTB test set the delimiter-guided parser obtains 92.90 EVALB / 92.33 JP-EVALB F1 versus 92.45 / 91.89 for the arity-specific parser; on CTB it obtains 90.90 / 89.13 versus 91.02 / 89.27. On the development sets the two differ by at most 0.08 points on PTB and are 0.68 / 0.57 points lower on CTB. The binary parser scores higher (PTB 94.11 EVALB), but it is trained on binarized trees.
No collapse at high arity. Predicted constituents with five or more children closely follow the gold counts (PTB: gold 1,859, D 1,897, A 1,950; CTB: gold 235, D 238, A 222). Labeled F1 on k≥5 constituents is 83.33 vs. 83.01 (A) on PTB and 72.73 vs. 74.84 on CTB.
Cost: longer derivations. The average transition sequence per sentence is 56.76 on PTB and 77.56 on CTB, compared with 43.47 and 59.45 for the arity-specific parser.
Errors move to boundary control. Delimiter-persistence errors outnumber insertion errors: premature Reduce 455 (PTB) / 142 (CTB) and spurious D-Reduce 443 / 96, versus missing D-Shift 369 / 102 and spurious D-Shift 293 / 77.

**Table 1.** Test-set labeled F1 on PTB and CTB with EVALB (punctuation excluded) and JP-EVALB (punctuation retained). Published results are external reference points with different architectures and preprocessing; the current-work rows compare the three systems under the same implementation framework. The paper does not bold any entry. (Table 3 in the paper.)
System	Type	PTB		CTB
System	Type	EVALB	JP-EVALB	EVALB	JP-EVALB
Watanabe and Sumita (2015)	Binary bottom-up	90.68	–	84.33	–
Liu and Zhang (2017b)	Binary bottom-up	91.70	–	85.50	–
Dyer et al. (2016)	Non-binary top-down	92.40	–	82.70	–
Liu and Zhang (2017a)	Non-binary in-order	91.80	–	86.10	–
Fernández-González and Gómez-Rodríguez (2019)	Non-binary arity-specific bottom-up	91.70	–	86.80	–
Current work B	Binary bottom-up	94.11	93.64	92.81	91.08
Current work A	Non-binary arity-specific bottom-up	92.45	91.89	91.02	89.27
Current work D (ours)	Non-binary delimiter-guided bottom-up	92.90	92.33	90.90	89.13

**Table 2.** Action-inventory sizes of the three bottom-up systems (Table 4 in the paper).
System	PTB	CTB
B: binary	126	148
A: arity-specific non-binary	202	190
D: delimiter-guided non-binary (ours)	78	64

@inproceedings{park-etal-2026-non, title = "Non-binary bottom-up constituency parsing without arity actions", author = "Park, Jungyeul and Jo, Eunkyul Leah and Huang, Zihao", editor = "Lee, Hung-Yi and Dev, Sunipa and Li, Jessy and Elliott, Desmond", booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {EMNLP} 2026", month = oct, year = "2026", address = "Budapest, Hungary", publisher = "Association for Computational Linguistics", url = "https://aclanthology.org/2026.findings-emnlp.611/", doi = "10.18653/2026.findings-emnlp.611", pages = "12869--12879", ISBN = "979-8-89176-462-0" }

Non-binary bottom-up constituency parsing without arity actions

Abstract

Method

Main Results

BibTeX