CODEWITHSUNDEEP
parsingantlrantlr4
user3246110
user3246110

Reputation: 73

What to use in ANTLR4 to resolve ambiguities in more complex cases (instead of syntactic predicates)?

In ANTLR v3, syntactic predicates could be used to solve ambiguitites, i.e., to explicitly tell ANTLR which alternative should be chosen. ANTLR4 seems to simply accept grammars with similar ambiguities, but during parsing it reports these ambiguities. It produces a parse tree, despite these ambiguities (by chosing the first alternative, according to the documentation). But what can I do, if I want it to chose some other alternative? In other words, how can I explicitly resolve ambiguities?

(For the simple case of the dangling else problem see: What to use in ANTLR4 to resolve ambiguities (instead of syntactic predicates)?)

A more complex example:

If I have a rule like this:

expr
    :   expr '[' expr? ']'
    |   ID expr
    |   '[' expr ']'
    |   ID
    |   INT
    ;

This will parse foo[4] as (expr foo (expr [ (expr 4) ])). But I may want to parse it as (expr (expr foo) [ (expr 4) ]). (I. e., always take the first alternative if possible. It is the first alternative, so according to the documentation, it should have higher precedence. So why it builds this tree?)

If I understand correctly, I have 2 solutions:

  1. Basically implement the syntactic predicate with a semantic predicate (however, I'm not sure how, in this case).

  2. Restructure the grammar.

For example, replace expr with e:

e   :   expr | pe
    ;

expr
    :   expr '[' expr? ']'
    |   ID expr
    |   ID
    |   INT
    ;

pe  :   '[' expr ']'
    ;

This seems to work, although the grammar became more complex.

I may misunderstood some things, but both of these solutions seem less elegant and more complicated than syntactic predicates. Although, I like the solution for the dangling else problem with the ?? operator. But I'm not sure how to use in this case. Is it possible?

Upvotes: 4

Views: 783

Answers (2)

peter.cyc
peter.cyc

Reputation: 1813

To get this expression (expr (expr foo) [ (expr 4) ]), you can use

top : expr EOF;

expr : expr '[' expr? ']' | ID | INT ;

Upvotes: 0

Sam Harwell
Sam Harwell

Reputation: 99859

You may be able to resolve this by placing the ID alternative above ID expr. When left-recursion is eliminated, all of your alternatives which are not left recursive are parsed before your alternatives which are left recursive.

For your example, the first non-left-recursive alternative ID expr matches the entire expression, so there is nothing left to parse afterwards.

Upvotes: 1

Related Questions