Re: Resolving of a reduce/reduce conflict generally requiring custom tokenizer

[keeskwekkeboom]

I think this is a grammar issue, and you should try to adjust this. Or use AntLR, which can do backtracking

 

Op dinsdag 4 september 2012 01:48:04 UTC+2 schreef Aleksander Heintz het volgende:

I have a fairly troublesome reduce/reduce conflict that I'm trying to solve. The problem can basically be simplified to this:

! Welcome to GOLD Parser Builder 5.2

"Start Symbol" = <Program>

               

Identifier = [a]

<Program> ::= <Expression>

           

<Expression> ::= '(' <Expression> ')'

               | <Lambda Expression>

               | <Variable>

               

<Variable> ::= Identifier

            

<Parameter> ::= Identifier

               

<Lambda Expression> ::= '(' <Parameter> ')' '=>' '{' <Expression> '}'

As you can probably read, both "(i)" and "(i) => { i }" should be valid inputs here, but instead I get a reduce/reduce conflict cause it doesn't know whether to reduce to <Variable> or <Parameter>. The "normal" way to solve this problem (or rather, the way I've found, used in for instance mono's C# compiler) is to have the tokenizer generate different open_paren tokens based on the next tokens (specifically, it looks ahead for the arrow (=>) token and generates lambda_open_paren instead of just open_paren in the case that it is found. Now, my question is, how can I solve this problem in GOLD, or do I need to use some other parser-generator?

[Arsène von Wyss]

This is a problem related to how a LALR(1) parser works. It is not specific to GOLD, but other parsing algorithms such as the one used by ANTLR may be able to deal with this. There usually is a solution though...

Have you tried moving the lambda expression into the expression rule?

<Expression> ::= '(' <Expression> ')'

               | '(' <Parameter> ')' '=>' '{' <Expression> '}'

               | <Variable>

This probably works (maybe you also need to replace the variable and parameter with Identifier though) - not tested... ;)

Cheers, Arsène

[Arsène von Wyss]

Okay, so I played around with it, the suggested removal of the <Lambda Expression> doesn't cut it (well, obviously *g*).

No Reduce-Reduce or Shift-Reduce problems when the <Variable> is replaced with a plain Identifier. That's the way I'd go when using my bsn Engine because I could bind the rule "<Expression> ::= Identifier" to a "Variable" token instance when the semantic AST is created.

Good luck, Arsène

[Aleksander Heintz]

Thanks. I actually had more problems, and needed more custom control with regards to tokens missing etc, so I wrote my own recursive decent parser and custom tokenizer. Was a great learning experience :-)