Page 16      All Pages  All Books
1
.
X
+
Y
*
z
shift
2
X
.
+
Y
*
z
reduce(r3)
3
E
.
+
Y
*
z
shift
4
E
+
.
Y
*
z
shift
5
E
+
Y
.
*
z
reduce(r3)
6
E
+
E
.
*
z
shift
7
E
+
E
*
.
z
shift
8
E
+
E
*
z
.
reduce(r3)
9
E
+
E
*
E
.
reduce(r2)
emit multiply
10
E
+
E
.
reduce(rl)
emit add
11
E
.
accept
Terms to the left of the dot are on the stack, while remaining input is to the right of the dot. We start by shifting tokens onto the stack. When the top of the stack matches the rhs of a production, we replace the matched tokens on the stack with the lhs of the production. Conceptually, the matched tokens of the rhs are popped off the stack, and the lhs of the production is pushed on the stack. The matched tokens are known as a handle, and we are reducing the handle to the lhs of the production. This process continues until we have shifted all input to the stack, and only the starting nonterminal remains on the stack. In step 1 we shift the x to the stack. Step 2 applies rule r3 to the stack, changing x to E. We continue shifting and reducing, until a single nonterminal, the start symbol, remains in the stack. In step 9, when we reduce rule r2, we emit the multiply instruction. Similarly, the add instruction is emitted in step 10. Thus, multiply has a higher precedence than addition.
Consider, however, the shift at step 6. Instead of shifting, we could have reduced, applying rule r1. This would result in addition having a higher precedence than multiplication. This is known as a shift-reduce conflict. Our grammar is ambiguous, as there is more than one possible derivation that will yield the expression. In this case, operator precedence is affected. As another example, associativity in the rule
E -> E + E
is ambiguous, for we may recurse on the left or the right. To remedy the situation, we could rewrite the grammar, or supply yacc with directives that indicate which operator has precedence. The latter method is simpler, and will be demonstrated in the practice section.
The following grammar has a reduce-reduce conflict. With an id on the stack, we may reduce to T, or reduce to E.
E -> T E -> id T -> id
Yacc takes a default action when there is a conflict. For shift-reduce conflicts, yacc will shift. For reduce-reduce conflicts, it will use the first rule in the listing. It also issues a warning message whenever a conflict exists. The warnings may be suppressed by making
13
Page 16      All Pages  All Books