Search code examples
cgrammarsemanticspredicatextext

Xtext - solving ambiguity without semantic predicates?

Problem

Entry
    : temp += (Expression | Declaration | UserType)*
;

Declaration
    : Type '*' name=ID ';'
;

Expression
    : temp1 = Primary ('*' temp2 += Primary)* ';'
;

Primary
    : temp1 = INT
    | temp2 = [Declaration]
;

Type
    : temp1 = SimpleType
    | temp2 = [UserType]
;

SimpleType
    : 'int' | 'long'
;

UserType
    : 'typedef' name=ID ';'
;

Rules Declaration and Expression are ambiguous due to the fact that both rules share the exact same syntax and problems occur because both cross references [Declaration] as well as [UserType] are based on the terminal rule ID.

Therefore generating code for the grammar above will throw the ANTLR warning:

Decision can match input such as "RULE_ID '*' RULE_ID ';'"
using multiple alternatives: 1, 2

Goal

I would like the rule to be chosen which was able to resolve the cross reference first.

Assume the following:

typedef x;

int* x;
int* b;

The AST for

x*b

should look something like:

x = Entry -> Expression -> Primary (temp1) -> [Declaration] -> Stop!
* = Entry -> Expression -> Primary '*' -> Stop!
b = Entry -> Expression -> Primary (temp2) -> [Declaration] -> Stop!

Therefore

Entry -> Declaration

should never be considered, since

Entry -> Expression -> [Declaration]

could already validate the cross reference [Declaration].

Question

Because we do not have semantic predicates in Xtext (or am I wrong?), is there a way to validate a cross reference and explicitly choose that rule based on that validation?

PS: As a few might already know, this problem stems from the C language which I am trying to implement with Xtext.

Solution

  • Regarding the current version of Xtext, semantic predicates are not supported.

    Cross-references are resolved to their terminals (in my case UserRole and Declaration to terminal ID). And only during the linking process references are validated, which in my case is too late since the AST was already created.

    The only possible way to use context sensitive rule decisions is to actually define an abstract rule within the grammar that states the syntax. In the example above, rules Expression and Declaration would be rewritten to one. Semantic validation then follows in the necessary areas such as content assist with the use of scoping.