Direct non-binary constituency parsing must identify an ordered sequence of children at each phrase-level reduction. We extend our earlier delimiter-guided bottom-up construction to a common calculus for top-down, in-order, and bottom-up parsing. At reduction, the rightmost delimiter marks the left boundary, the nonterminal marker supplies the mother label, and the completed items in the delimited segment determine the children and arity. We use a stack invariant to prove soundness and completeness and derive the exact length of the static oracle's action sequence. A projection-and-lifting theorem shows that each delimiter-guided system and its canonical counterpart generate the same set of trees under both the structural and grammar-licensed transition relations. In controlled experiments on PTB and CTB, the delimiter-guided parsers achieve similar labeled accuracy to their canonical counterparts across all traversal orders. For bottom-up parsing, delimiter guidance reduces the number of action classes and increases the number of supervised decisions per tree.
Figures & tables
PTB
CTB
System
evalb
jp-evalb
evalb
jp-evalb
Previously reported canonical non-binary systems
Top-down ( Dyer et al., 2016 )
92.40
—
82.70
—
In-order ( Liu and Zhang, 2017a )
91.80
—
86.10
—
Bottom-up ( Fernández-González and Gómez-Rodríguez, 2019 )
91.70
—
86.80
—
Canonical non-binary systems, reimplemented
Table 1: Labeled test F1 on PTB and CTB. The published evalb scores come from a generative top-down parser, a greedy in-order parser trained with a static oracle, and a greedy bottom-up parser trained with a dynamic oracle. These scores reflect the training and evaluation settings of the original studies. All six systems in this study use a shared static-oracle training protocol and greedy decoding. Their scores are means with sample standard deviations across three seeds. Dashes indicate unreported jp-evalb scores.
PTB
CTB
Order
Classes
Actions
MACs (M)
Classes
Actions
MACs (M)
Canonical
Top-down
79
110.04
17.21
65
122.15
18.67
In-order
79
110.04
17.21
65
122.15
18.67
Bottom-up
251
67.25
13.48
227
73.08
14.20
Delimiter-guided
Table 2: Action classes observed during training and mean scoring workload per gold test sentence. Actions count oracle decisions. MACs are millions of multiply–accumulate operations in the two affine layers of the action scorer.
PTB
CTB
Order
Canonical
Delimiter-guided
Canonical
Delimiter-guided
Top-down
0.92±0.04
0.90±0.03
1.61±0.01
1.49±0.04
In-order
0.92±0.10
0.93±0.09
1.58±0.05
1.54±0.06
Bottom-up
1.00±0.06
0.91±0.06
1.83±0.05
1.55±0.03
Table 3: Single-core greedy decoding throughput on the length-balanced test samples, in sentences per second. For each checkpoint, throughput is the number of timed sentences divided by their total elapsed parsing time. Entries give the mean and sample standard deviation across the three seeds.
Figure 1: Single-core decoding time by sentence length. We average the wall-clock time over the same 20 sentences per band for each checkpoint. Points show the means across seeds and error bars show one sample standard deviation. The two corpus rows have separate vertical scales.
System
1
2
3
4
≥5
PTB
Gold count
8,879
23,840
7,381
2,317
1,859
C Top-down
93.48±0.07
92.88±0.11
88.46±0.29
81.29±0.59
81.28±0.62
C In-order
93.65±0.13
93.10±0.06
88.57±0.16
81.42±0.12
81.64±0.43
C Bottom-up
93.53±0.04
92.93±0.12
88.43±0.21
81.82±0.54
81.77±0.13
D Top-down
93.49±0.07
92.86±0.14
88.50±0.38
81.11±0.27
82.05±0.58
Table 4: Exact-arity labeled test F1 by immediate child count. Gold counts give the number of reference phrasal occurrences in each group. Results are means ± sample standard deviations across three seeds. C denotes canonical and D delimiter-guided.
System
1–10
11–20
21–30
31–40
≥41
PTB
Sentences
270
764
778
433
171
C Top-down
95.65±0.19
95.21±0.20
94.32±0.12
93.39±0.14
92.41±0.43
C In-order
95.99±0.29
95.17±0.09
94.49±0.12
93.53±0.14
92.28±0.12
C Bottom-up
95.53±0.47
95.06±0.12
94.60±0.06
93.19±0.16
92.34±0.39
D Top-down
96.05±0.09
95.16±0.07
94.21±0.15
93.43±0.23
92.46±0.06
Table 5: Labeled bracket F1 by test sentence length in tokens. Counts give the number of test sentences in each group. Results are means ± sample standard deviations across three seeds. C denotes canonical and D delimiter-guided.
PTB
CTB
Order
Same
D higher
C higher
Same
D higher
C higher
Top-down
64.67±2.06
16.90±1.52
16.63±0.93
52.78±1.30
22.70±1.00
23.08±0.88
In-order
62.16±1.27
17.40±0.87
18.50±1.51
53.16±2.87
20.31±2.88
24.81±3.02
Bottom-up
60.00±1.53
18.65±0.56
19.23±1.02
50.86±1.99
24.04±2.91
23.85±3.89
Table 6: Sentence-level agreement and relative accuracy for matched seed pairs (%, mean ± sample standard deviation). Same requires identical labeled bracket multisets. D higher and C higher count sentences with higher bracket F1 for the delimiter-guided and canonical predictions, respectively.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Step
Top-down
In-order
Bottom-up
1
Nt (TOP)
d-Shift (Ms.)
d-Shift (Ms.)
2
Nt (S)
Nt (NNP)
Nt (NNP)
3
Nt (NP 1 )
u-Reduce
u-Reduce
4
Nt (NNP)
Nt (NP 1 )
Shift (Haag)
5
Shift (Ms.)
Shift (Haag)
Nt (NNP)
6
u-Reduce
Nt (NNP)
u-Reduce
Appendix
Table 7: Delimiter-guided static-oracle sequences for the tree in Figure 2 . Tokens shown with Shift and d-Shift identify the consumed input token; they are not action parameters. The reduction actions have neither label nor arity parameters.
Non-binary bottom-up constituency parsing is usually taken to require arity actions: reductions such as \textscReduce−X#k specify both the mother label and the number of children to be composed. We show that this arity parameter is not a necessary transition primitive. Our parser introduces constituent labels separately and recovers reduction spans from delimiter-bounded stack configurations. In a well-formed reduction configuration, arity is uniquely determined by the active delimiter and the label marker, making it a derived property of parser state rather than an action label. This factorization removes label--arity-specific reduce actions while preserving direct construction of original non-binary trees. Experiments on PTB and CTB show that the delimiter-guided parser remains competitive with an arity-specific bottom-up baseline under the same implementation framework, with substantially smaller action inventories. Analyses further show that its predicted arity profile remains close to the gold treebanks and that high-arity constituents do not collapse when arity actions are removed.
Jungyeul Park, Eunkyul Leah Jo, Zihao Huang
Korea Advanced Institute of Science & Technology, Daejeon, South Korea · The University of British Columbia, Vancouver, Canada
We revisit punctuation-aware tree binarization for constituency parsing and ask whether dependency-induced headedness improves binary parser supervision. Although learned heads substantially outperform rule-based heads in intrinsic head prediction, they do not yield consistent parsing gains after debinarization. In particular, punctuation-conditioned evaluation shows that learned headedness underperforms rule-based binarization in macro-average punctuation-sensitive F1, despite a small overall gain on CTB. Similar instability appears under cross-treebank transfer. These results suggest that \ycc{linguistically grounded} headedness is not necessarily parser-optimal when used as a binarization control signal. The paper presents a negative result: better head prediction does not imply better punctuation-sensitive constituency parsing.
Zeyao Qi, Yige Chen, Eitan Klinger +2
The Chinese University of Hong Kong, Ma Liu Shui, Hong Kong · The University of British Columbia, Vancouver, Canada · Korea Advanced Institute of Science & Technology, Daejeon, South Korea
This paper presents Dependency-Phrase Hierarchy Parser (DPH Parser), a grammar-driven bottom-up unsupervized parsing framework inspired by Generalized Phrase Structure Grammar (GPSG) and Head-driven Phrase Structure Grammar (HPSG). The parser incrementally constructs constituency structures using a compact inventory of feature-based syntactic rules while deriving dependency relations through explicit head annotations. The system combines probabilistic POS tagging, recursive phrase projection, and weighted parse hypotheses to process realistic and partially noisy text input. Unlike purely neural and data-driven parsers, the resulting syntactic derivations remain explicitly interpretable. We evaluated parser performance on English corpora from the Universal Dependencies (UD) project using Unlabeled Attachment Score (UAS) as the main parsing metric, comparing the outcomes against Stanza and spaCy parsers. For a small inventory of syntactic rules, DPH parser achieved UAS values of 53.32% & 52.58% (UD Devset/Testset respectively). For the same data, Stanza achieved 89.12% & 88.67% while spaCy achieved 56.91% and 58.59%. Although the current system does not yet approach the accuracy of modern neural parsers, the results demonstrate the feasibility of applying transparent rule-based bottom-up parsing to realistic treebank data while jointly producing constituency and dependency structures.