Re: shift/reduce problem

[Roger Keays <s354157@student.uq.edu.au>]

yuntao,

Your grammar is ambiguous. i.e. a string in the language could be parsed
two different ways.

Take for example the string

  if (x) then if (y) then (echo "Hello") else (echo "Goodbye);

does this mean a)

  if (x) then
	if (y) then
		(echo "Hello")
	else
		(echo "Goodbye")

or does it mean b)

  if (x) then
	if (y) then
		(echo "Hello")
  else
	(echo "Goodbye)

To disambiguate, you need to force all if statements before an else to be
distinguishable from those after an else.

  statement =
	{a} matched |
	{b} unmatched;

  matched =
	{if} if general_expression then matched else [true]:matched |
	{other} ident; /* other statement types here */

  unmatched =
	{if} if general_expression then statement |
	{if_else} if general_expression then matched else unmatched;

Here is what our string is parsed to now (semantics of (a) above ):

  >- ABStatement
     `- AIfUnmatched
        |- if
        |- AGeneralExpression
        |  `- x
        |- then
        `- AAStatement
           `- AIfMatched
              |- if
              |- AGeneralExpression
              |  `- y
              |- then
              |- AOtherMatched
              |  `- echohello
              |- else
              `- AOtherMatched
                 `- echogoodbye

This is straight from a textbook (Compiler Construction - by Kenneth C
Louden)... I agree, it's not exactly straight forward. We should add (some
sort of) shift/reduce conflict resolution into SableCC 3.0

Good luck!

Roger



On Mon, 1 Oct 2001, yuntao wrote:

> Hi,
>
> I am using sablecc to parse some if statements, the grammar is as follows:
>
>   if_statement =
>    {if} if general_expression then [true]:statement |
>    {if_else} if general_expression then [true]:statement else statement;
>
> After run SableCC, I got the following error message:
>
>      [exec] shift/reduce conflict in state [stack: TIf PGeneralExpression TThen
> PStatement *] on TElse in {
>      [exec]     [ PIfStatement = TIf PGeneralExpression TThen PStatement * TElse
>  PStatement ] (shift),
>      [exec]     [ PIfStatement = TIf PGeneralExpression TThen PStatement * ] fol
> lowed by TElse (reduce)
>      [exec]
>
> The message basically says that there is a reduce/shift conflict after
> it sees the keyword "else". I would like the code behaving do shift
> first. Any suggestion?
>
> Also I look at simplecc.sablecc sample, it looks like they have
> similar grammar to define the "if" statements, just wondering how they
> can avoid the problem.
>
> Thanks a lot.
>
> Yuntao Cui
>
>
>
>
>
>