Bottom-up (Shift-reduce) parsing

Bottom-up parsing, also called shift-reduce parsing, starts with the individual words of a sentence and combines them into larger constituents until the whole sentence collapses into the start symbol.

It works against a grammar, so read Context-free Grammar (CFG) first. The direction is the opposite of top-down parsing, which starts at S and tries to expand down to the words.

There are many parsing families (CCG, chart, top-down recursive descent, hybrid constituency, data-oriented, tree-adjoining, parse reranking). Shift-reduce is the one in scope.

The 4 parts

Part	What it does
Stack and Input	a stack holds grammar symbols (terminals and non-terminals), an input buffer holds the rest of the string, marked at the end with a dollar sign $
Shift	move the next token from the input buffer onto the stack
Reduce	if the symbols on top of the stack match the right-hand side (RHS) of a rule, replace them with the left-hand side (LHS) non-terminal
Parsing Actions	keep shifting and reducing until the parser reaches Accept or Error

The parser only ever ends in 1 of 2 states:

• Accept: the stack holds only the start symbol and the input buffer is empty
• Error: neither a shift nor a reduce is possible, which means a syntax error

Direction of the two operations

Shift moves symbols into the stack from the buffer. Reduce replaces symbols inside the stack using a grammar rule. Every row of a trace table is one of these two, and nothing else.

Worked example 1

Grammar:

S --> S + S
S --> S * S
S --> id

Input string: id + id + id

Stack	Input Buffer	Parsing Action
$	id+id+id$	Shift
$id	+id+id$	Reduce S->id
$S	+id+id$	Shift
$S+	id+id$	Shift
$S+id	+id$	Reduce S->id
$S+S	+id$	Reduce S->S+S
$S	+id$	Shift
$S+	id$	Shift
$S+id	$	Reduce S->id
$S+S	$	Reduce S->S+S
$S	$	Accept

• the $ on the left of the stack is the bottom of stack marker, and the $ on the right of the buffer is the end of input marker
• the operator + is a terminal, so it is shifted onto the stack like any other token

Worked example 2

Grammar:

E --> 2E2
E --> 3E3
E --> 4

Input string: 32423

Stack	Input Buffer	Parsing Action
$	32423$	Shift
$3	2423$	Shift
$32	423$	Shift
$324	23$	Reduce by E --> 4
$32E	23$	Shift
$32E2	3$	Reduce by E --> 2E2
$3E	3$	Shift
$3E3	$	Reduce by E --> 3E3
$E	$	Accept

• the parser shifts 3 times before the first reduce becomes possible, because no shorter stack top matches any RHS
• a reduce can shrink the stack by several symbols at once, since 2E2 is 3 symbols replaced by 1

Advantages and Limitations

Advantages	Limitations
Used widely in syntax analysis, since parsing is driven directly by grammar rules	Limited lookahead, so it can miss syntax errors that need a larger lookahead
Stack-based analysis is easy, being only push and pop	Difficulty in parsing ambiguous grammars
Handles both left-recursive and right-recursive grammars	May generate false positive shift-reduce conflicts
Parse table is small, so it is efficient in memory	The generated parse tree might be quite complex

Shift-reduce parsing in NLTK

from nltk.parse import ShiftReduceParser
 
bottom_up_parser = ShiftReduceParser(grammar)
trees = [(list(bottom_up_parser.parse(sentence.split())), sentence) for sentence in sentences]
print("Bottom-Up Parsing:")
for tree, sent in trees:
    print("sentence:", sent)
    if tree:
        for t in tree:
            t.pretty_print()
    else:
        print("No parse tree found")
        print()

Warning: VP -> V NP will never be used
Bottom-Up Parsing:
sentence: the dog chased the cat
No parse tree found

sentence: the cat slept
          S
      ___|____
     NP       VP
   __|__      |
 Det    N     V
  |     |     |
 the   cat  slept

sentence: the dog ate a cookie
No parse tree found

NLTK's ShiftReduceParser is greedy

It commits to the first reduce it can make and never backtracks, so it returns at most 1 parse tree and fails on 2 of the 3 sentences. The warning VP -> V NP will never be used appears because the parser always reduces V to VP before it ever sees the following NP.

Other parsers for comparison

Technique	NLTK class	Direction
Bottom-up (shift-reduce)	ShiftReduceParser	words upward to S
Top-down (recursive descent)	RecursiveDescentParser	S downward to words
Constituency (chart)	ChartParser	stores partial parses, finds all trees

• ChartParser prints the bracketed constituency tree, for example (S (NP (Det the) (N dog)) (VP (V chased) (NP (Det the) (N cat))))
• the CYK algorithm and Chomsky Normal Form are related ideas, mentioned only as optional background