SI413 Lab 6: LR parser conflicts

A grammar with a problem

We're going to consider a grammar for the language we use to define ... grammars. We have rules with symbols and arrows and bars for "or". These descriptions must themselves obey a grammar. Consider the file ex1.ypp below:

/* This file is ex1.ypp */
%%

%token ARROW OR SYM ;

s: s rule | rule
rule: SYM ARROW rlist
rlist: rlist OR rhs | rhs
rhs: rhs SYM | SYM

%%

Run it through bison and you should see an error/warning message. 1 What is it? Run as bison -v ex1.ypp and the file ex1.output is produced. It lists the states of the parser's CFSM along with the actions for each state, and if there are conflicts it should appear as multiple actions from the same state & lookahead. 2 Which states have conflicts? Explain the conflicts for each such state, i.e. why is there ambiguity about which action to take? 3 Would more than one lookahead symbol help? Explain!

What I'd recommend you do is to consider the following valid input:

X -> a b   Y -> c d

where X,Y,a,b,c,d are all SYM tokens and -> is an ARROW token. Trace through the parse modelling the stack (which remember contains states as well as grammar symbols) at each step. Determine where you first run into a conflict, and try to figure out why it really happens.

Fix the grammar with a problem

You should be able to convince yourself that two symbols of lookahead is really required here, and refactoring the grammar isn't going to fix that. 4 How could we change the language (not just the grammar, but actually the language) to fix the above problem? Explain! Make your fix to the code and verify that bison compiles without errors/warnings. HINT: Think about what C++ and Java do to separate statements. 5 Include the modified grammar in your lab solution.

Another grammar with a problem

Consider the following grammar, which is supposed to be the basis for parsing expressions like: 3*(2 - 7)^3 + 2^3/19;

/* This file is ex2.ypp */
%token NUM
%token OPA OPM LP RP STOP EXP

%%
run: res run | res

res: exp STOP     

exp: exp OPA term 
| term            

term: term OPM factor
| sfactor            

sfactor: OPA factor  
| factor             

factor: NUM          
| LP exp RP          
| factor EXP factor

%%

Run bison -v ex2.ypp 6 Choose one state with a conflict and explain why that conflict arises. 7 What, in general, is the problem with this grammar?

Fix the ex2.ypp grammar

Fix the ex2.ypp grammar so that the ambiguity goes away. Modify the file and rerun bison to verify that you've fixed it. 8 Explain the fix! I.e. tell me what you did and why! Include the modified grammar.