[antlr-interest] Difficult (to me) recursion problem

[Johannes Luber]

Sam Barnett-Cormack schrieb:
> Hey all,
> 
> So, my ASN.1 grammar is progressing, but I've run into a problem that I
> *think* is due to left-recursion complexities. I've attached the whole
> grammar (bits that are commented out are generally references to rules
> from other bits of the standards that I haven't reached yet - want to
> see about getting the basic one running without error), but the area I
> think the problem is actually in is lines 640--686:
> 
> constrainedType : type constraint | typeWithConstraint ;
> 
> typeWithConstraint : (SET | SEQUENCE) (constraint | sizeConstraint) OF
> type ;
> 
> constraint : '(' constraintSpec exceptionSpec ')' ;
> 
> constraintSpec : subtypeConstraint /*| generalConstraint*/ ;
> 
> subtypeConstraint : elementSetSpecs ;
> 
> elementSetSpecs : rootElementSetSpec (',' '...' (','
> additionalElementSetSpec)?)? ;
> 
> rootElementSetSpec : elementSetSpec;
> 
> additionalElementSetSpec : elementSetSpec;
> 
> elementSetSpec : unions | ALL exclusions ;
> 
> unions : intersections uElems unionMark intersections ;
> 
> uElems : unions ;
> 
> intersections : intersectionElements iElems intersectionMark
> intersectionElements ;
> 
> iElems : intersections ;
> 
> intersectionElements : elements exclusions? ;
> 
> exclusions : EXCEPT elements ;
> 
> unionMark : '|' | UNION ;
> 
> intersectionMark : '^' | INTERSECTION ;
> 
> elements : subtypeElements /*| objectSetElements*/ | '(' elementSetSpec
> ')' ;
> 
> subtypeElements
>     : singleValue
>     | containedSubtype
>     | valueRange
>     | permittedAlphabet
>     | sizeConstraint
>     | typeConstraint
>     | innerTypeConstraints
>     | patternConstraint;
> 
> singleValue : value;
> 
> Now, I can see where there could be recursion issues here. The grammar
> is taken from the ASN1 spec, which I think assumes a YACC-style parser.
> 
> The errors I end up getting are multitudinous, and I'm just not sure
> which are causes and which are effects, as I know you can get
> snowball-errors.
> 
> If anyone can offer me some guidance, I'd really appreciate it.

Did you see
<http://www.antlr.org/wiki/display/ANTLR3/Left-Recursion+Removal> already?

Johannes

> Sam
> 
> 
> ------------------------------------------------------------------------
> 
> 
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address