[antlr-interest] Difficult (to me) recursion problem
Johannes Luber
jaluber at gmx.de
Sat Feb 28 07:43:46 PST 2009
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
More information about the antlr-interest
mailing list