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

Skip to first unread message


Sep 5, 2012, 4:05:11 AM9/5/12
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

Sep 5, 2012, 6:51:04 PM9/5/12
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

Sep 5, 2012, 7:04:04 PM9/5/12
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

Sep 21, 2012, 3:20:35 PM9/21/12
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 :-)
Reply all
Reply to author
0 new messages