CODEWITHSUNDEEP
antlrxtextll-grammarambiguous-grammar
alexp82539
alexp82539

Reputation: 77

XText Dangling Else - The Other Option

So I've been using X-Text and playing with Syntactic Predicates.

The classic example is the dangling else problem, where the solution given is to greedily parse the else statement, i.e. don't terminate the inner expression, like so:

IfStatement: 'if' condition=Expression 'then' then=Expression (=>'else' else=Expression)?;

I have a grammar of processes, where two may be combined to create one big process with a binary operator, for example process 1 + process 2 affords the choice between process 1 and process 2

In addition, processes may call other processes: process 1 -> process 2 means do process 1, then do process two.

In my grammar, the following: process 1 -> process 2 + process 3

should be interpreted as

(process 1 -> process 2) + process 3

However, considering this as a dangling else problem, the resolution everyone gives provides me the wrong solution. How then, in X-Text can I say, "if it makes sense to, and the program still parses, jump out of the inner statement at the earliest possible opportunity"

Here is a snippit of my grammar for clarity: PProc: PProcAtomic ({Binary.left = current} '+' right=Proc)?
; PProcAtomic returns PProc: dotted=Dotted (fields+=Field)* type="->" proc=Proc | bool=Bool type="&" proc=Proc | type="(" proc=Proc ")"
| type="||" (gens+=Gen)+ "@" "[" rset=Set "]" proc=Proc | type="|~|" (gens+=Gen)+ "@" proc=Proc | type="[]" (gens+=Gen)+ "@" proc=Proc
| type="|||" (gens+=Gen)+ "@" proc=Proc
| type=";" (gens+=Gen)+ "@" proc=Proc
| type="[|" rset=PSet "|]" (gens+=Gen)+ "@" proc=Proc
| type="|[" rset=PSet "]|" (gens+=Gen)+ "@" proc=Proc | type="<->" (gens+=Gen)+ "@" "[" (exprs+=Expr)+ "]" proc=Proc | type="STOP" | type="SKIP" | type="CHAOS" "(" rset=PSet ")" ; Proc: PProc | "namedprocess" ;

Obviously if I put the '=>' on the "+" then it will consume that greedily, resulting in the wrong AST. How do I make it "look ahead" for a "+" symbol, and then split the statement into two if it sees that?

Upvotes: 0

Views: 315

Answers (1)

Miro Sp&#246;nemann
Miro Sp&#246;nemann

Reputation: 273

When describing operator-based expressions, ambiguities can often be eliminated without the => predicate by writing chains of parser rules and avoiding back-references to rules that are lower in the chain. The operator precedence is simply controlled by the order of rules in the chain.

In your case the ambiguity is caused by the frequent back-reference to the Proc rule. You can avoid it by writing something like this:

PProc returns Proc:
    PProcAdvanced ({Binary.left = current} '+' right=PProcAdvanced)*;

PProcAdvanced returns Proc:
    PProcAtomic
    | dotted=Dotted (fields+=Field)* type="->" proc=PProcAdvanced
    | bool=Bool type="&" proc=PProcAdvanced

    | type="||" (gens+=Gen)+ "@" "[" rset=Set "]" proc=PProcAdvanced 
    | type="|~|" (gens+=Gen)+ "@" proc=PProcAdvanced
    | type="[]" (gens+=Gen)+ "@" proc=PProcAdvanced

    | type="|||" (gens+=Gen)+ "@" proc=PProcAdvanced

    | type=";" (gens+=Gen)+ "@" proc=PProcAdvanced

    | type="[|" rset=PSet "|]" (gens+=Gen)+ "@" proc=PProcAdvanced

    | type="|[" rset=PSet "]|" (gens+=Gen)+ "@" proc=PProcAdvanced 
    | type="<->" (gens+=Gen)+ "@" "[" (exprs+=Expr)+ "]" proc=PProcAdvanced;

PProcAtomic returns Proc:
    "(" Proc ")"
    | type="STOP"
    | type="SKIP" 
    | type="CHAOS" "(" rset=PSet ")";

Here the only back-reference is "(" Proc ")", which is prefixed by the opening parenthesis and thus free of ambiguity.

Upvotes: 1

Related Questions