Eclipse Community Forums: TMF (Xtext) » How to resolve ambiguity with label syntax

Help

Home

Home » Modeling » TMF (Xtext) » How to resolve ambiguity with label syntax

Show: Today's Messages :: Show Polls :: Message Navigator

How to resolve ambiguity with label syntax [message #900672]

Wed, 08 August 2012 06:35

Dobes Vandermeer

Messages: 26
Registered: July 2009

Junior Member

I'm having trouble figuring out how to resolve ambiguity in the grammar where C-style labels are supported.

So for example:

print "foo";
A: print "bar";
if some_cond goto A;

Because a "name" like "something" can be the start of an expression or the start of a label, it doesn't know which one to pick until it finds the ":".

Report message to a moderator

Re: How to resolve ambiguity with label syntax [message #900739 is a reply to message #900672]

Wed, 08 August 2012 11:07

Henrik Lindberg

Messages: 2509
Registered: July 2009

Senior Member

Disclaimer: Here are some (untried) suggestions to give you some ideas.
What you want to do depends very much on the rest of your language.

Using a Predicate
---
You can solve with a semantic predicate, or by left factoring (like what
you do for + - * / etc.).

Here is an illustration

Expression : LabelExpression | VariableExpression | Variable | ... ;

LabelExpression returns Expression
: =>(name = ID ':')
;

Variable
: '$' name = ID
;

VariableReference returns Expression
: variable = [Variable | ID]
;

i.e., when parsing a LabelExpression, and some other rule(s) are also
possible and they both start with ID, then if the next token is a :',
use the LabelExpression.

This gets difficult as you need longer and longer predicates. Say that
you require variables to be just:

Variable : name = ID ;

Now, you have no way of predicating - when seeing an ID, which rule
applies? You have to place the predicate higher up in the rule chain,
and it may not be possible to resolve this (depending on the rest of the
rules).

Left Factoring
----
Or, solve it by thinking of ':' as a postfix operator on a general
expression. Instead of just a LiteralName as a PrimaryExpression, you
have something like:

LabelExpression returns Expression
: LiteralName ({LabelExpression.name = current} ':')?
;

One problem here is if "LiteralName" should be a link to a variable
declaration. But without seeing the entire grammar it is hard to know.

Use a DataRule with Predicate
----
Label
: =>(ID ':')
;

Terminal with Predicate
----
Not sure if this works:
terminal Label : =>(...ruleforid... ':') ;
terminal ID : ...

Turn on backtracking in the Lexer
----
May give you other surprises, but may work fine. Depends on how many
other similar issues you run into in your language.

External Lexer
---
Actually, the best solution, and what you probable end up needing if
your language is C like, is to solve this at the lexical level.

With an external lexer you can do all the ANTLR tricks with both
semantic and syntactic predicates. Your lexer then simply delivers LABEL
or ID, and ambiguities between the two does not become an issue in the
grammar.

In the worst case, (like in C), this becomes very difficult as the lexer
needs to be almost as semantically complete as the grammar itself to be
able to understand the context.

Hope I did not send you on a chase after something that does not work...
Maybe someone else can point out if I am completely off somewhere :)

Regards
- henrik

On 2012-08-08 8:35, Dobes Vandermeer wrote:
> I'm having trouble figuring out how to resolve ambiguity in the grammar
> where C-style labels are supported.
>
> So for example:
>
> print "foo";
> A: print "bar";
> if some_cond goto A;
>
>
> Because a "name" like "something" can be the start of an expression or
> the start of a label, it doesn't know which one to pick until it finds
> the ":".
>
>

Report message to a moderator