Disambiguation Strategy ?

[khkiley]

I'm having an issue with dealing with disambiguation.

Very simplified, my grammar is effectively this:

expression -> StringExpression | NumericExpression

StringExpression -> StringExpression | StringLiteral | Identifier
NumericExpression -> NumericExpression | NumericLiteral | Identifier

Because Identifier lives as an option under both StringExpression and NumericExpression, the grammar is ambiguous.

I thought of changing to this:

expression -> StringExpression | NumericExpression | Identifier

StringExpression -> StringExpression | StringLiteral
NumericExpression -> NumericExpression | NumericLiteral

But then the identifier cannot be a part of a String or Numeric Expression.

I could probably do something like this:

expression -> StringExpression | NumericExpression | Identifier

StringExpression -> expression | StringLiteral
NumericExpression -> expression | NumericLiteral

But then I am mixing types, but I could handle type validation after the parser, in the visitor.

Is there away around this that I am not seeing ?

Thanks!

[msujew]

Hey @khkiley,

the grammar isn't ambiguous due to the Identifier, but rather due to the StringExpression -> StringExpression and NumericExpression -> NumericExpression parts. It's not even really ambiguous: Instead this issue is called direct left recursion. It's one of the main limitations of LL parsers.

There are quite a few resources that show how to solve this. See here. It generally boils down to rewriting the grammar rules to eliminate the left recursive subrule call.

Regarding the Identifier issue: Most people don't actually write their grammar split by string or numeric expressions. They just have operation expression (i.e. with 2 or more operators), unary expressions and then primary expressions like Identifier or '(' expression ')' (parenthesized expressions). See the antlr3 related part of this answer.

[khkiley]

Thank you @msujew,

I will take another look, the grammar works fine when it was just the numeric expression, once I added the string expression is when it was complaining about the identifier and worked fine if I took the identifier out of one of the branches. My simplified grammar probably doesn't fairly represent what I'm doing.

I'll remove the typing aspect of it, and I think that will fix it.

Thank you for the reading on the LL parsers, very helpful.

K

[khkiley]

@msujew , I just looked at your link for antlr3. And this is pretty much how the grammar is structured.

[msujew]

Ah, I see. Yeah, then it's not necessarily the left recursion at fault there. A general recommendation is to not encode the type system of your language into the parser. This can work well in the start but almost always leads to headache down the line :)