Bug 314935

Description Sven Efftinge 2010-05-28 14:36:22 EDT

Hi,

We have been using XText for some time now, and we are very pleased with the results we have. However, in some extreme cases, we have some performances issues. I created a small example that shows this. The grammar is the following one:

*******
grammar org.xtext.example.MyDsl with org.eclipse.xtext.common.Terminals

generate myDsl "http://www.xtext.org/example/MyDsl"

ADT:
     ("Operations" (operations+=Operation ";")+)?
     ("Axioms" (axioms+=Equation ";")+)?
     ("Variables" (variables+=Variable ";")+)?
;

Operation:
    name = ID
;

Equation:
  left=Term '=' right=Term
;

Term:
    InfixTerm | TerminalTerm
;

TerminalTerm returns Term:
    VariableRef | PrefixTerm | '(' Term ')'
;
    
VariableRef:
    "$" variable = [Variable]
;

PrefixTerm:
    opSymbol=[Operation] ("(" subTerms+=Term ("," subTerms+=Term)* ")")?
;

InfixTerm:
    subTerms+=TerminalTerm opSymbol=[Operation] subTerms+=TerminalTerm
;

Variable:
    name=ID
;
*******

The problem appears when we try to create big terms in the instances, like the following one (integers defined in a Peano-like form):

***
Operations
    zero;
    next;
    plus;
Axioms
    zero plus $n = $n;
    next($n) plus $m = next ($n plus $m);
    next(next(next(next(next(next(next(next(next(next(next(next(next(next(next(next(next(next(next(next(zero)))))))))))))))))))) = zero;
Variables
    n;
    m;
***

Parsing a term with 20 levels takes about 800Mb of in the heap space, which seems a lot of memory (it's really a heap space problem, not a stack size problem).

I have enabled backtracking for this to work, and I absolutely need backtracking in my grammar anyway. Getting rid of infix terms solves the performances problem, but infix terms are a nice feature we'd like to keep.

Is there a way to reduce this memory consumption? Maybe a different definition for my grammar?

Any help will be appreciated :)

Cheers,

Alexis