Re: Shift/reduce conflict in Yacc C grammar

Akos Hajnal asked:
...
> The above grammar contains a shift/reduce conflict at
> the definitions if-then, if-then-else.
> For this reason I can not put actions within these rules,
> i.e. for example after parsing the condition part.


Yes, you can. You just have to be devious about it, which is the
point of this response. See below.


> My question is that, there is available a C grammar in lex/yacc
> that does not contain any shift/reduce conflict?
> Can such grammar exsist?


To which our moderator replied:
-- [I doubt you'll find any if-then-else constructs where yacc will let you
-- embed actions in any grammar. -John]


Or to specifically answer the question, there cannot be a grammar
without a shift-reduce conflict (it is present in the language,
i.e. you must know whether you have a lookahead of ELSE to decide
whether to shift to the if-then-else alternative or reduce the if-then
alternative), but as I will show below that does not prevent adding
action code to the grammar.


As a response Scott Stanchfield suggested a precedence trick which
directs yacc how to resolve the shift-reduce conflict (by using, as
our moderator pointed out, one token of lookahead) that provides a
nice grammar for me to cut and paste a solution in.


%nonassoc ELSE
%nonassoc LOWER_THEN_ELSE


...


ifStatement
    : IF expr THEN statement %prec LOWER_THAN_ELSE
    | IF expr THEN statement ELSE statement
    ;


Given Scott's grammar, I presume what you would like to write is this:


ifStatement
    : IF expr { actions for the if clause } THEN statement
{ actions for the then clause }
    | IF expr { actions for the if clause } THEN statement
{ actions for the then clause }
                                                            ELSE statement
    ;


The solution is to embedding actions in rules with shift-reduce (or
even reduce-reduce conflicts) conflicts is to introduce empty
non-terminals to hang the actions on. When you embed actions in
rules, yacc introduces empty non-terminals for you, but most versions
aren't smart enough to reuse the same non-terminal if the action code
is repeated. However, you can do it by hand. (Note Yacc++ handles
shift action code without introducing the dummy empty non-terminal
because the model calls out action code explicitly and it also
recognizes when you repeat the same action code in more than one place
and reuses it. For those reasons, Yacc++ would except the definition
above.)


Thus, the solution for the grammar Scott presented is:


ifStatement
    : IF expr afterIfExpression THEN statement afterThenStatement
    | IF expr afterIfExpression THEN statement afterThenStatement
                                                            ELSE statement
    ;


afterIfExpression: /* empty */ ; { actions for the if clause }


afterThenStatement: /* empty */ ; { actions for the then clause }


The only point is that the same non-terminal must be added to each
rule in the conflict. That means the action must be the same for each
conflicting rule. That means, you are out of luck if you want to do
something "different" immediately after the if-expression of an
if-then and an if-then-else. You must wait until your lexer has given
the parser the ELSE token to distinguish the two cases. That is the
following will not work (it will give you reduce-reduce conflicts):


ifStatement
    : IF expr afterIfExpression THEN statement afterThenStatement
    ;


ifElseStatement
    : IF expr afterIfElseExpression THEN statement afterThenELseStatement
                                                            ELSE statement
    ;


afterIfExpression: /* empty */ ;
{ actions for the if clause of an if-then }


afterIfELseExpression: /* empty */ ;
{ actions for the if clause of an if-then-else }


afterThenStatement: /* empty */ ;
{ actions for the then clause of an if-then }


afterThenElseStatement: /* empty */ ;
{ actions for the then clause of an if-then-else }


By the way, Yacc++ handles to one token of lookahead case implicitly.
Thus, if you need only one token of lookahead to decide which action
to apply, Yacc++ will read the lookahead token before applying the
action code. That means you could have different actions for the then
clause since the ELSE token will be the next read, but not for the if
clause.


This example is okay:


ifStatement
    : IF expr { actions for the if clause } THEN statement
{ actions for the then clause of an if-then }
    | IF expr { actions for the if clause } THEN statement
{ actions for the then clause of an if-then-else }
                                                            ELSE statement
    ;


This example will cause a "shift action code conflict":


ifStatement
    : IF expr { actions for the if clause of an if-then } THEN statement
{ actions for the then clause of an if-then }
    | IF expr { actions for the if clause of an if-then-else } THEN statement
{ actions for the then clause of an if-then-else }
                                                            ELSE statement
    ;


The equivalent restriction applies for the dummy empty non-terminals
in yacc. You cannot have a distinct afterIfElseExpression, but you
can have a distinct afterThenElseStatement. I'll leave that example
as an exercise for the reader.


There is one last caveat. You cannot use the distinct
afterThenStatement and afterThenElseStatements for controlling the
lexer state if that change of lexer state can effect the parsing of
the ELSE token. The reason is that parser must wait for the presence
or absence of the ELSE token to decide which action to apply. Thus,
the parser will not have told the lexer to change state until after
that token is seen (and its pretty hard for the lexer to change the
state before recognizing the token if the command to do so does not
come until after the token is recognized).


By the way, you can use Scott's precedence "trick" with any of the
above grammars to resolve the shift-reduce conflict without warning.
It's not really a trick, because that is exactly how the precedence
declaration was defined in yacc, and part of why it is defined the way
that it is. Just note that, as our moderator points out, that
precedence declarations are very powerful and can hide other
legitimate conflicts in the grammar, misleading you to believe you
have a correct grammar when it is actually ambiguous. One good way of
doing this is to write the grammar without any precedence declarations
and get it debugged (excluding the precedence of the expression
operators) and then add the precedence operators making certain you do
not change the semantics of the resulting tables.


-Chris Clark
************************************************************************
Compiler Resources, Inc. email: compres@world.std.com
3 Proctor St. http://world.std.com/~compres
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847
[I need to write up something on grammar flattening, it's a fundamental
technique in writing yacc grammars, and it's not obvious until you see
it a few times. We touch on it in L&Y but not at length. -John]




--

Return to the comp.compilers page.
Search the comp.compilers archives again.