# CS计算机代考程序代写 7. Transition-based parsing of CFGs

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