Shift Reduce Parsing
By Sam Becht
Reading: Shift reduce section of Bottom-up parsing Wikipedia page, http://lambda.uta.edu/cse5317/notes/node18.html and lecture notes from: http://www.d.umn.edu/~rmaclin/cs5641/Notes/Lecture8.pdf
Reading Questions:
Wikipedia and UTA reading questions:
1. What is the action table and how could it be represented in Python?
2. What is the general algorithm for shift-reduce parsing
3. Go through the example and make sure it makes sense. Then draw the parse tree for the example input string “the dog jumps”
4. How fast is the shift reduce algorithm?
UMN Lecture notes questions:
1. What are shift-reduce and reduce-reduce conflicts and how can they be avoided?
2. Create a grammar that has a reduce-reduce conflict.
Lecture notes:
Types of parser
Parsers can be broken up into top-down and bottom-up categories. Top-down parsers start at the beginning of the parse tree and work down according to the grammar rules and bottom-up goes up the parse tree from the input string. Bottom-up parsers are used more often in programming languages because often top-down parsers need to backtrack because they chose the wrong production rule.
Shift reduce algorithm
1. Take in the input string to be parsed
2. Until you reach the start symbol or can no longer continue:
1. Shift the leftmost input symbol(s) onto the stack until you have something on the stack that corresponds to the right-hand side of a production rule
2. Reduce by replacing the right-hand side symbols with the left-hand side variable that fulfills the production rule
3. If end with the start symbol, accept
4. Otherwise reject
Conflicts
Shift-reduce conflicts occur when it is possible to both shift and reduce. This can happen for ambiguous grammars such as:
S à T + S | T
T à a * T | a
With the input string: a * a + a, the first reduction results in rejecting the string because there are no production rules that create T * a. However, the input string can be parsed as seen in the second parsing.
In-class activity: Brainstorm ways compilers can avoid shift-reduce conflicts.
Compiler compilers such as YACC and Bison avoid shift-reduce conflicts by preferring shift over reduce. Some parsers also use operator precedence rules that prefer certain mathematical operators, typically using PEMDAS rules.
In-class activity: Try to create a grammar that could have a reduce-reduce conflict.
Example solution:
S à Tb | cR
T à a
R à a
If this grammar is given a string ‘ca’, the a can be reduced to either T or R.
Compilers that use this kind of parsing avoid reduce-reduce conflicts by preferring the first rule in the grammar that has the symbol on the right-hand side. For the example above, the a would be reduced to T’s, so the parser would not accept the string even though it can be derived from the start variable. Therefore, it is important to either understand the parsing precedence of the compiler, or unambiguate the grammar.
Lookaheads
In more complex shift reduce parsers such as LR parsers, a lookahead is used to avoid reduce-reduce conflicts. For example, given the grammar rules (from Parser Wikipedia page):
1. E à E + E
2. E à E * E
3. E à integer
4. * has precedence over +
And input string 1 + 2 * 3, without a lookahead, the grammar will return 9 instead of 7. Without the lookahead, the parser would reduce the sum first and then multiply because it would not know when to use rule 4 since it cannot see the next symbols in the input. Many parsers used in compilers have one lookahead, meaning it can read the following symbol in the input string. More lookaheads can be used, but that quickly slows down the parser and does not provide much additional power.
Quiz Questions:
1. Given the following grammar, draw the bottom-up parse tree and fill out the table for input string “the girl walks”
Sentence à NounPhrase VerbPhrase
NounPhrase à Article Noun | Noun
VerbPhrase à Verb | Adverb Verb
Article à the
Noun à boy | girl | dog | cat
Verb à walks | talks | sits | barks
Adverb à quickly | softly
2. How can a compiler avoid shift-reduce and reduce-reduce conflicts?
3. What is the benefit of a lookahead?
Homework Exercise:
Create a shift reduce parser that parses the following grammar:
S à R
R à Rb | a
You can test your parser with the attached testing suite.
Stack
Input String
Action