CS606 - Compiler Construction - Lecture Handout 28

User Rating:  / 0
PoorBest 

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

LR(1) Skeleton Parser

stack.push(dummy); stack.push(0);
done = false; token = scanner.next();
while (!done) {
s = stack.top();
if( Action[s,token] == “reduce A→β”) {
stack.pop(2×|β|);
s = stack.top();
stack.push(A);
stack.push(Goto[s,A]);
}
else if( Action[s,token] == “shift i”){
stack.push(token); stack.push(i);
token = scanner.next();
}
else if(Action[s,token] == “accept”
&& token == “$” )
done = true;
else
report error and recover;
}
report success;

Shift/Reduce Conflicts

If a DFA states contains both [X → α•aβ, b] and [Y → γ•, a]
Then on input “a” we could either shift into state [X → αa•β,b], or reduce with Y → γ.
This is called a shift-reduce conflict. Typically, this is due to ambiguities in the grammar.
The classic example of a shift-reduce conflict is the dangling else. Consider the grammar

stmt → if E then stmt
| if E then stmt else stmt

We will have DFA state containing

[stmt → if E then stmt•, else]
[stmt → if E then stmt •else stmt, x]

If else follows, we can shift

[stmt → if E then stmt else • stmt, x]

or reduce

[stmt → if E then stmt•, else]

Typical action is shift so that else matches with most recent if.