Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » A warning on the performance of syntactic predicates in Xtext
A warning on the performance of syntactic predicates in Xtext [message #929620] Mon, 01 October 2012 16:06
Andrew Gacek is currently offline Andrew Gacek
Messages: 32
Registered: October 2011
Member
I'm writing this post to share a pitfall with the performance of syntactic predicates that I experienced. Hopefully this will prove useful if somebody else runs into this issue.

The traditional example for syntactic predicates in Xtext is the dangling else-problem shown by the following ambiguous grammar:

Model:
    statement+=IfStatement*;

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

Expression:
    IfStatement | {ValueReference} name=ID;


This grammar is taken from a blog post on "Meinte's DSL Blog" that I'm unable to link to. This ambiguity can be resolved via a syntactic predicate on the 'else' clause:

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


This tells Xtext that if it can parse an 'else' it should do so without considering any other alternatives. The thing to avoid is following:

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


This tells Xtext that if it can parse an 'else' followed by an expression it should do so without considering any other alternatives. The problem is that Xtext then parses the expression to the right of the 'else' twice, once for the syntactic predicate and once for the true parse. This results in an exponential blowup in run-time for nested if-then-else expressions.

It may seem trivial to avoid this pitfall, but it's less obvious when there is an action. This is where I got caught. Consider if the following was ambiguous:

Expression:
    Atom ({BinaryExpression.left=current} op=('+'|'-') right=Atom)*


Now consider where to put the syntactic predicate:

1.
Expression:
    Atom =>({BinaryExpression.left=current} op=('+'|'-') right=Atom)*


Bad. This creates exponential blowup.

2.
Expression:
    Atom (=> {BinaryExpression.left=current} op=('+'|'-') right=Atom)*


Error. This is not well-formed.

3.
Expression:
    Atom ({BinaryExpression.left=current} =>op=('+'|'-') right=Atom)*


Error. The syntactic predicate is masked by the action.

4.
Expression:
    Atom (=>({BinaryExpression.left=current} op=('+'|'-')) right=Atom)*


Correct. The scope of the syntactic predicate is limited by the inner parenthesis.

From this I've learned that it's very important to consider what exactly a syntactic predicate applies to in order to avoid any limit double parsing. Fixing this issue dropped the parse time on one of our models from 150 seconds down to 4 seconds.

-Andrew
Previous Topic:Getting text in StatefulFactory
Next Topic:How to avoid format XBlockExpression in my DSL
Goto Forum:
  


Current Time: Sat Oct 25 00:43:59 GMT 2014

Powered by FUDForum. Page generated in 0.09081 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software