7. Transition-based parsing of CFGs
1 Embedding and acceptability patterns
The following collection of sentences provides a motivating “test set” for basic theories of human sentence processing.
(1)
(2)
(3)
Here’s
S
S NP NP VP PP SRC ORC
Left-branching structures
a. Mary won
b. Mary ’s baby won
c. Mary ’s boss ’s baby won
Right-branching structures
a. John met the boy
b. John met the boy that saw the actor
c. John met the boy that saw the actor that won the award
Center-embedding structures
a. the actor won
b. the actor the boy met won
c. the actor the boy the baby saw met won
a CFG generating all the sentences in (1), (2) and (3):
→ NP VP
→ WHILE S S
→ NP POSS N
→ (D) N (PP) (SRC) (ORC) → V (NP) (PP)
→ P NP
→ THAT VP
→ NP V
N → baby, boy, actor, wife, boss NP → Mary, John
V → met, saw, won D → the
P → on, in, with
THAT → that POSS → ’s
WHILE → while
S
Left-branching structure:
NP
VP
NP POSS N V Mary ’s baby won
Ling185A, Winter 2021 — Tim Hunter, UCLA
Right-branching structure:
S
NP John
VP
V NP met
DN SRC the boy
THAT that
S
VP
V NP saw
Center-embedding structure:
DN the actor
VP D N ORC V
NP
the actor
won
NP V met
DN the boy
2 Transition-based parsing
A parsing schema defines, for any given grammar, a method for parsing/recognizing symbol-sequences.
A transition-based parsing schema of the sort we will look at here has these components:
• a specification of what a configuration is;
• a specification of what a starting configuration is, for a given grammar and a given symbol- sequence;
• a specification of what a goal configuration is, for a given grammar;
• a specification of a transition relation on configurations (which I’ll write as ≡).
To give you a sense of what this means, let’s start with the boringly-simple case of finite-state automata.
Parsing with an FSA
Starting configuration: (A, x1 . . . xn)
where A is a start state and x1 …xn is the input
consume step: (A,xixi+1 …xn) ≡ (B,xi+1 …xn) where there is an arrow from A to B labeled with xi
Goal configuration: (A, ε) where A is a final state
Ling185A, Winter 2021 — Tim Hunter, UCLA
3 CFG parsing schemas
In all of the following: A, B, etc. are placeholders for a nonterminal; x1, x2, etc. are placeholders for a terminal symbol; and Φ is a placeholder for a sequence of nonterminals (in the form of a “stack”).
We assume that the right-hand side of each CFG rule has either a single terminal symbol or a sequence of one-or-more nonterminal symbols.
3.1 Bottom-up
Bottom-up parsing schema
Starting configuration: (ε, x1 . . . xn) where x1 …xn is the input
shift step: (Φ,xixi+1 …xn) ≡ (ΦA,xi+1 …xn) where there is a rule A → xi in the grammar
reduce step: (ΦB1 …Bm,xi …xn) ≡ (ΦA,xi …xn) where there is a rule A → B1 …Bm in the grammar
Goal configuration: (A, ε)
where A is one of the grammar’s start symbols
Example:
Type of transition
0 —
1 shift
2 shift
3 reduce
4 shift
5 shift
6 shift
7 reduce
8 reduce
9 reduce
Rule used —
D→the N→baby NP→DN V→saw D→the N→boy NP→DN VP→VNP S→NPVP
Configuration
(ε, the baby saw the boy) (D, baby saw the boy) (D N, saw the boy)
(NP, saw the boy)
(NP V, the boy) (NP V D, boy) (NP V D N, ε) (NP V NP, ε) (NP VP, ε)
(S, ε)
Ling185A, Winter 2021 — Tim Hunter, UCLA
3.2 Top-down
Top-down parsing schema
Starting configuration: (A, x1 . . . xn)
where A is one of the grammar’s start symbols and x1 . . . xn is the input
predict step: (AΦ,xi …xn) ≡ (B1 …BmΦ,xi …xn) where there is a rule A → B1 …Bm in the grammar
match step: (AΦ,xixi+1 …xn) ≡ (Φ,xi+1 …xn) where there is a rule A → xi in the grammar
Goal configuration: (ε, ε) Example:
Type of transition
0 —
1 predict
2 predict
3 match
4 match
5 predict
6 match
7 predict
8 match
9 match
Rule used —
S→NPVP NP→DN D→the N→baby VP→VNP V→saw NP→DN D→the N→boy
Configuration
(S, the baby saw the boy)
(NP VP, the baby saw the boy) (D N VP, the baby saw the boy) (N VP, baby saw the boy)
(VP, saw the boy)
(V NP, saw the boy)
(NP, the boy)
(D N, the boy)
(N, boy)
(ε, ε)
Ling185A, Winter 2021 — Tim Hunter, UCLA
3.3 Left-corner
Left-corner parsing schema
Starting configuration: (A, x1 . . . xn)
where A is one of the grammar’s start symbols and x1 . . . xn is the input
shift step: (Φ,xixi+1 …xn) ≡ (AΦ,xi+1 …xn) where there is a rule A → xi in the grammar
match step: (AΦ,xixi+1 …xn) ≡ (Φ,xi+1 …xn) where there is a rule A → xi in the grammar
lc-predict step: (B1Φ,xi …xn) ≡ (B2 …BmAΦ,xi …xn) where there is a rule A → B1 …Bm in the grammar
lc-connect step: (B1AΦ,xi …xn) ≡ (B2 …BmΦ,xi …xn) where there is a rule A → B1 …Bm in the grammar
Goal configuration: (ε, ε) Example:
Type of transition
0 —
1 shift
2 lc-predict
3 match
4 lc-connect
5 shift
6 lc-connect
7 shift
8 lc-connect
9 match
Rule used —
D → the
NP → D N N → baby
S → NP VP V→saw VP→V NP D→the NP→D N N→boy
Configuration
(S, the baby saw the boy) (D S, baby saw the boy)
(N NP S, baby saw the boy) (NP S, saw the boy)
(VP, saw the boy) (V VP, the boy) (NP, the boy)
(D NP, boy)
(N, boy) (ε, ε)
Ling185A, Winter 2021 — Tim Hunter, UCLA