Resolving conflict

[Javier Abdul Córdoba Gándara]

Hi all! I'm writing a grammar for the CoolC language used by Alex Aiken on its Coursera MOOC (https://www.coursera.org/course/compilers).

I've implemented it before in flex+cup, but SableCC make things cleaner so I'm rewriting my work. For the lexer I went for a weird subclassing to the Lexer class and overriding of the filter() method to implement a state machine over what SableCC detects and get some of the required features (error detection).

Now with the parser I get this conflict that (I guess) is very basic, but I can't think of a way to overcome it.

t = 

{mult} t mult f

| {other} f

;

f =

{bool} int_const

| {let} let t

        ;

I'm oversimplifying it a lot but you get the idea, the "let" structure is more complex but it has to end with t (in the full grammar it is all the tree of expressions). This is an obvious shift/reduce as with:

let 5 | * let 6

The grammar is not specifying whether to reduce on "let 5" or shift the operator to continue parsing. I'm basically looking for a pattern to give shift a precedence. In cup you have an explicit operator to do that, but is there a way to rewrite this grammar to do the same? I also know that modifying the let to have a terminator would do the trick, but I don't want to modify the syntax.

Thank you!

Abdul

[Niklas Matthies]

Hi,

On Mon 2013-01-28 at 15:10h, you wrote:
:

> t =
> {mult} t mult f
> | {other} f
> ;
>
> f =
> {bool} int_const
> | {let} let t
> ;

:

> let 5 | * let 6
>
> The grammar is not specifying whether to reduce on "let 5" or shift
> the operator to continue parsing. I'm basically looking for a
> pattern to give shift a precedence.

Shift having precedence means that the left operand of "mult" (and of
any other operator with a left-hand operand) cannot be a "let"
expression. So you need to change the grammar to reflect exactly that.

For example like this (I hope I got it right):

t =
{let} l |
{not_let} not_let ;

not_let =
{mult} not_let mult f |
{atom} atom ;

f =
{let} l |
{atom} atom ;

l =
{let} let t ;

atom =
{bool} int_const ;

Cheers,
Niklas

[Javier Abdul Córdoba Gándara]

The conflict is appearing again due to 

T         -> not_let

not_let -> not_let mult f

on some state after not_let is recognized, it again goes on a shift/reduce conflict.

I'm working with the idea, it makes sense. It resembled me the dangling else problem. Thank you! 

Abdul