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.
Sam
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"il-antlr-interest" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/il-antlr-interest?hl=en
-~----------~----~----~----~------~----~------~--~---
/**
* ASN.1 Parsing
*/
grammar ASN_1;
options {
language = Java;
output = AST;
ASTLabelType = 'CommonTree';
memoize = true;
}
tokens {
ABSENT='ABSENT';
ABSTRACT_SYNTAX='ABSTRACT-SYNTAX';
ALL='ALL';
APPLICATION='APPLICATION';
AUTOMATIC='AUTOMATIC';
BEGIN='BEGIN';
BIT='BIT';
BMPString='BMPSTRING';
BOOLEAN='BOOLEAN';
BY='BY';
CHARACTER='CHARACTER';
CHOICE='CHOICE';
CLASS='CLASS';
COMPONENT='COMPONENT';
COMPONENTS='COMPONENTS';
CONSTRAINED='CONSTRAINED';
CONTAINING='CONTAINING';
DEFAULT='DEFAULT';
DEFINITIONS='DEFINITIONS';
EMBEDDED='EMBEDDED';
ENCODED='ENCODED';
ENCODING_CONTROL='ENCODING-CONTROL';
END='END';
ENUMERATED='ENUMERATED';
EXCEPT='EXCEPT';
EXPLICIT='EXPLICIT';
EXPORTS='EXPORTS';
EXTENSIBILITY='EXTENSIBILITY';
EXTERNAL='EXTERNAL';
FALSE='FALSE';
FROM='FROM';
GeneralizedTime='GeneralizedTime';
GeneralString='GeneralString';
GraphicString='GraphicString';
IA5String='IA5String';
IDENTIFIER='IDENTIFIER';
IMPLICIT='IMPLICIT';
IMPLIED='IMPLIED';
IMPORTS='IMPORTS';
INCLUDES='INCLUDES';
INSTANCE='INSTANCE';
INSTRUCTIONS='INSTRUCTIONS';
INTEGER='INTEGER';
INTERSECTION='INTERSECTION';
ISO646String='ISO646String';
MAX='MAX';
MIN='MIN';
MINUS_INFINITY='MINUS-INFINITY';
NOT_A_NUMBER='NOT-A-NUMBER';
NULL='NULL';
NumericString='NumericString';
OBJECT='OBJECT';
ObjectDescriptor='ObjectDescriptor';
OCTET='OCTET';
OF='OF';
OPTIONAL='OPTIONAL';
PATTERN='PATTERN';
PDV='PDV';
PLUS_INFINITY='PLUS-INFINITY';
PRESENT='PRESENT';
PrintableString='PrintableString';
PRIVATE='PRIVATE';
REAL='REAL';
RELATIVE_OID='RELATIVE-OID';
SEQUENCE='SEQUENCE';
SET='SET';
SIZE='SIZE';
STRING='STRING';
SYNTAX='SYNTAX';
T61String='T61String';
TAGS='TAGS';
TeletexString='TeletexString';
TRUE='TRUE';
TYPE_IDENTIFIER='TYPE-IDENTIFIER';
UNION='UNION';
UNIQUE='UNIQUE';
UNIVERSAL='UNIVERSAL';
UniversalString='UniversalString';
UTCTime='UTCTime';
UTF8String='UTF8String';
VideotexString='VideotexString';
VisibleString='VisibleString';
WITH='WITH';
}
@header {
package com.gobito.asn_1.parse;
import static com.gobito.asb_1.parse.ParseUtil.*;
}
@lexer::header {package com.gobito.asn_1.parse;}
@members {
}
@lexer::members {
}
// Lexical elements
//"real" stuff
WS : (WSNONL | NL) {$channel=HIDDEN;};
fragment
NL : ('\n' | '\r' | '\v' | '\f');
fragment
WSNONL : (' ' | '\t');
fragment
LETTER: 'a'..'z' | 'A'..'Z';
fragment
DIGIT: '0'..'9';
fragment
IDHYPHEN: '-' (LETTER|DIGIT);
fragment
IDBODY : (LETTER|DIGIT|IDHYPHEN);
CAPID : 'A'..'Z' IDBODY*;
LCID : 'a'..'z' IDBODY*;
fragment
MLCOMMENTf : '/*' .* (MLCOMMENTf .*)* '*/';
MLCOMMENT : MLCOMMENTf {$channel=HIDDEN;};
SLCOMMENT : ('--' .* ('--'|NL)) {$channel=HIDDEN;};
fragment
NUMBERf : '0' | '1'..'9' DIGIT*;
NUMBER : ;
REALNUMBER
: (NUMBERf '.')=> NUMBERf ('.'(DIGIT+)?)? (('e'|'E')('+'|'-')? NUMBERf)?
| NUMBERf {$type=NUMBER;};
fragment
BSTRINGCONT : ('0' | '1' | WS)*;
BSTRING : '\'' BSTRINGCONT '\'B';
fragment
HSTRINGCONT : ('0'..'9' | 'A'..'F' | WS)*;
HSTRING : '\'' HSTRINGCONT '\'H';
fragment
CSTRINGNL : WSNONL* NL WSNONL* {setText("");};
CSTRING : '"' ((CSTRINGNL)=> CSTRINGNL | '""' | ~'"') '"';
// handling xml
fragment
XMLNAMECHAR : 'A'..'Z' | 'a'..'z' | '0'..'9' | '-' | ':' | '_' | '.' ;
fragment
XMLNAMESTART: 'A'..'Z' | 'a'..'z' | '_' | ':' ;
fragment
INVALIDINXML : '<' | '&' ;
fragment
XMLENTREF : '&' XMLNAME ';' ;
fragment
XMLNAME : XMLNAMESTART XMLNAMECHAR+;
fragment
XMLSATTVAL : '\'' ( ('&')=>XMLENTREF | (~('\''|INVALIDINXML) ) )* '\'';
fragment
XMLDATTVAL : '"' ( ('&')=>XMLENTREF | (~('"'|INVALIDINXML) ) )* '"';
fragment
XMLATTVAL : XMLDATTVAL | XMLSATTVAL ;
fragment
XMLATTRIB : XMLNAME '=' XMLATTVAL ;
fragment
WSBLOCK : WS+;
fragment
XMLATTRIBS
: XMLATTRIB
| (XMLATTRIB WS)=>XMLATTRIB WSBLOCK XMLATTRIBS;
fragment
XMLTAGATTS
: WSBLOCK XMLATTRIBS ;
fragment
XMLOPENTAG : '<' XMLNAME XMLTAGATTS? WS* '>';
fragment
XMLCLOSETAG : '</' XMLNAME '>';
fragment
XMLSCLOSETAG : '<' XMLNAME XMLTAGATTS? WS* '/>';
fragment
XMLNONEMPTYELEMENT : XMLOPENTAG XMLCONTENT XMLCLOSETAG;
fragment
XMLEMPTYELEMENT : XMLSCLOSETAG;
fragment
XMLELEMENT options {
backtrack=true;
}
: XMLEMPTYELEMENT | XMLNONEMPTYELEMENT ;
fragment
XMLCONTENT : (XMLELEMENT | XMLENTREF | ~INVALIDINXML) *;
XMLFRAG : XMLELEMENT;
// Parser rules
modulereference : CAPID;
typereference : CAPID;
encodingreference : CAPID {ucidIsAllUC($CAPID.text)}?;
identifier : LCID;
valuereference : LCID;
moduleDefinition
: moduleIdentifier DEFINITIONS encodingReferenceDefault tagDefault
extensionDefault '::=' BEGIN moduleBody encodingControlSections END;
encodingReferenceDefault : (encodingreference INSTRUCTIONS)?;
moduleIdentifier : modulereference | definitiveIdentifier;
definitiveIdentifier : '{' definitiveObjIdComponentList '}' | ;
definitiveObjIdComponentList
: definitiveObjIdComponent
| definitiveObjIdComponent definitiveObjIdComponentList ;
definitiveObjIdComponent
: nameForm
| definitiveNumberForm
| definitiveNameAndNumberForm ;
definitiveNumberForm : NUMBER ;
definitiveNameAndNumberForm : identifier '(' definitiveNumberForm ')';
nameForm : identifier ;
tagDefault : (EXPLICIT | IMPLICIT | AUTOMATIC) TAGS | ;
extensionDefault : EXTENSIBILITY IMPLIED | ;
moduleBody : (exports imports assignmentList)? ;
exports
: EXPORTS symbolsExported ';'
| EXPORTS ALL ';'
| ;
symbolsExported : symbolList?;
imports : IMPORTS symbolsImported | ;
symbolsImported : symbolsFromModuleList? ;
symbolsFromModuleList : symbolsFromModule+ ;
symbolsFromModule : symbolList FROM globalModuleReference ;
globalModuleReference : modulereference assignedIdentifier ;
assignedIdentifier : (objectIdentifierValue | definedValue)? ;
symbolList : symbol (',' symbol)* ;
symbol : reference /*| parameterizedReference*/ ;
reference
: typereference
| valuereference
/* | objectclassreference
| objectReference
| objectSetReference */;
assignmentList : assignment+ ;
assignment options {backtrack=true;}
: typeAssignment
| valueAssignment
| xmlValueAssignment
| valueSetTypeAssignment
/*| objectClassAssignment
| objectAssignment
| objectSetAssignment
| parameterizedAssignment*/ ;
definedType
: externalTypeReference
| typereference
| /*parameterizedType
| parameterizedValueSetType*/ ;
definedValue
: externalValueReference
| typereference
/*| parameterizedValue*/ ;
externalTypeReference : modulereference '.' typereference ;
externalValueReference : modulereference '.' valuereference ;
typeAssignment : typereference '::=' type ;
valueAssignment : valuereference type '::=' value;
xmlValueAssignment : valuereference '::=' xmlTypedValue;
xmlTypedValue : XMLFRAG ; // needs some clever semantic predicating, probably
valueSetTypeAssignment options {backtrack=true;} : typereference (type
'::='|'::=' type) '{' elementSetSpecs '}';
type : (constrainedType)=>constrainedType | (builtinType)=>builtinType |
referencedType ;
builtinType
: bitStringType
| booleanType
| characterStringType
| choiceType
| embeddedPDVType
| enumeratedType
| externalType
/*| instanceOfType*/
| integerType
| nullType
/*| objectClassFieldType*/
| objectIdentifierType
| octetStringType
| realType
| relativeOIDType
| sequenceType
| sequenceOfType
| setType
| setOfType
| prefixedType ;
referencedType
: definedType
| usefulType
| selectionType
/*| typeFromObject */
/*| valueSetFromObjects*/ ;
namedType : identifier type;
value : builtinValue | referencedValue /*| objectClassFieldValue*/ ;
builtinValue
: bitStringValue
| booleanValue
| characterStringValue
| choiceValue
| embeddedPDVValue
| enumeratedValue
| externalValue
/*| instanceOfValue*/
| integerValue
| nullValue
| objectIdentifierValue
| octetStringValue
| realValue
| relativeOIDValue
| sequenceValue
| sequenceOfValue
| setValue
| setOfValue
| prefixedValue ;
referencedValue : definedValue /*| valueFromObject */;
namedValue : identifier value;
booleanType : BOOLEAN ;
booleanValue : TRUE | FALSE ;
integerType : INTEGER ('{' namedNumberList '}')?;
namedNumberList : namedNumber (',' namedNumber)*;
namedNumber : identifier '(' (signedNumber | definedValue) ')';
signedNumber : NUMBER | '-' NUMBER {$NUMBER.text != "0"}?;
integerValue : signedNumber | identifier ;
enumeratedType : ENUMERATED '{' enumerations '}' ;
enumerations : rootEnumeration (',' '...' exceptionSpec (','
additionalEnumeration)?)? ;
rootEnumeration : enumeration ;
additionalEnumeration : enumeration ;
enumeration : enumerationItem (',' enumerationItem)* ;
enumerationItem : identifier | namedNumber ;
enumeratedValue : identifier ;
realType : REAL ;
realValue : numericRealValue | specialRealValue ;
numericRealValue
: REALNUMBER
| '-' REALNUMBER {Double.parseDouble($REALNUMBER.text).doubleValue != 0.0}
| sequenceValue ;
specialRealValue : PLUS_INFINITY | MINUS_INFINITY | NOT_A_NUMBER;
bitStringType : BIT STRING ('{' namedBitList '}')? ;
namedBitList : namedBit (',' namedBit)* ;
namedBit : identifier '(' (NUMBER | definedValue) ')';
bitStringValue
: BSTRING
| HSTRING
| '{' identifierList? '}'
| CONTAINING value ;
identifierList : identifier (',' identifier)* ;
octetStringType : OCTET STRING ;
octetStringValue : BSTRING | HSTRING | CONTAINING value ;
nullType : NULL;
nullValue : NULL;
sequenceType : SEQUENCE '{' ( extensionAndException optionalExtensionMarker |
componentTypeLists )? '}';
extensionAndException : '...' exceptionSpec? ;
optionalExtensionMarker : (',' '...')? ;
ctlExtensionStuff
: extensionAndException extensionAdditions
( optionalExtensionMarker
| extensionEndMarker ',' rootComponentTypeList
) ;
componentTypeLists options {backtrack=true;}
: rootComponentTypeList
| ctlExtensionStuff
| rootComponentTypeList ',' ctlExtensionStuff ;
rootComponentTypeList : componentTypeList ;
extensionEndMarker : ',' '...';
extensionAdditions : (',' extensionAdditionList)? ;
extensionAdditionList : extensionAddition (',' extensionAddition)* ;
extensionAddition : componentType | extensionAdditionGroup ;
extensionAdditionGroup : '[[' versionNumber componentTypeList ']]' ;
componentTypeList : componentType (',' componentType)* ;
componentType
: namedType (OPTIONAL | DEFAULT value)?
| COMPONENTS OF type ;
sequenceValue : '{' componentValueList? '}';
componentValueList : namedValue (',' namedValue)* ;
sequenceOfType : SEQUENCE OF (type | namedType) ;
sequenceOfValue : '{' ( (namedValueList)=>namedValueList | valueList)? '}' ;
valueList : value (',' value)* ;
namedValueList : namedValue (',' namedValue)* ;
setType : '{' (componentTypeLists | extensionAndException
optionalExtensionMarker)? '}' ;
setValue : '{' componentValueList? '}' ;
setOfType : SET OF (type | namedType);
setOfValue : '{' (valueList | namedValueList)? '}' ;
choiceType : CHOICE '{' alternativeTypeLists '}' ;
alternativeTypeLists : rootAlternativeTypeList
(',' extensionAndException extensionAdditionAlternatives
optionalExtensionMarker)? ;
rootAlternativeTypeList : alternativeTypeList ;
extensionAdditionAlternatives : (',' extensionAdditionAlternativesList)? ;
extensionAdditionAlternativesList : extensionAdditionAlternative (','
extensionAdditionAlternative)* ;
extensionAdditionAlternative : extensionAdditionAlternativesGroup | namedType ;
extensionAdditionAlternativesGroup : '[[' versionNumber alternativeTypeList
']]';
choiceValue : identifier ':' value ;
alternativeTypeList : namedType (',' namedType)* ;
selectionType : identifier '<' type ;
prefixedType : taggedType | encodingPrefixedType ;
taggedType : tag (IMPLICIT|EXPLICIT)? type ;
tag : '[' encodingReference class classNumber ']' ;
encodingReference : (encodingreference ':')? ;
encodingPrefixedType : encodingPrefix type ;
encodingPrefix : '[' encodingReference /*encodingInstruction*/ ']' ;
prefixedValue : value ;
classNumber : NUMBER | definedValue ;
class : (UNIVERSAL | APPLICATION | PRIVATE)? ;
objectIdentifierType : OBJECT IDENTIFIER ;
objectIdentifierValue : '{' definedValue? objIdComponentsList '}' ;
objIdComponentsList : objIdComponents+ ;
objIdComponents : nameForm | numberForm | nameAndNumberForm | definedValue ;
numberForm : NUMBER | definedValue ;
nameAndNumberForm : identifier '(' numberForm ')' ;
relativeOIDType : RELATIVE_OID ;
relativeOIDValue : '{' relativeOIDComponentsList '}' ;
relativeOIDComponentsList : relativeOIDComponents+ ;
relativeOIDComponents : numberForm | nameAndNumberForm | definedValue ;
embeddedPDVType : EMBEDDED PDV ;
embeddedPDVValue : sequenceValue ;
externalType : EXTERNAL ;
externalValue : sequenceValue ;
characterStringType : restrictedCharacterStringType |
unrestrictedCharacterStringType ;
characterStringValue : restrictedCharacterStringValue |
unrestrictedCharacterStringValue ;
restrictedCharacterStringType
: BMPString
| GeneralString
| GraphicString
| IA5String
| ISO646String
| NumericString
| PrintableString
| TeletexString
| T61String
| UniversalString
| UTF8String
| VideotexString
| VisibleString ;
restrictedCharacterStringValue : CSTRING | characterStringList | quadruple |
tuple ;
characterStringList : '{' charSyms '}' ;
charSyms : charsDefn (',' charsDefn)* ;
charsDefn : CSTRING | quadruple | tuple | definedValue ;
quadruple : '{' group ',' plane ',' row ',' cell '}' ;
group : NUMBER;
plane : NUMBER;
row : NUMBER;
cell : NUMBER;
tuple : '{' tableColumn ',' tableRow '}' ;
tableColumn : NUMBER ;
tableRow : NUMBER ;
unrestrictedCharacterStringType : CHARACTER STRING ;
unrestrictedCharacterStringValue : sequenceValue ;
usefulType : typereference ;
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;
containedSubtype : INCLUDES? type;
//includes : INCLUDES? ;
valueRange : lowerEndpoint '..' upperEndpoint ;
lowerEndpoint : lowerEndValue '<'? ;
upperEndpoint : '<'? upperEndValue ;
lowerEndValue : value | MIN ;
upperEndValue : value | MAX ;
sizeConstraint : SIZE constraint ;
typeConstraint : type ;
permittedAlphabet : FROM constraint;
innerTypeConstraints : WITH (COMPONENT singleTypeConstraint | COMPONENTS
multipleTypeConstraints) ;
singleTypeConstraint : constraint ;
multipleTypeConstraints : fullSpecification | partialSpecification ;
fullSpecification : '{' typeConstraints '}' ;
partialSpecification : '{' '...' ',' typeConstraints '}' ;
typeConstraints : namedConstraint (',' namedConstraint)* ;
namedConstraint : identifier componentConstraint ;
componentConstraint : valueConstraint presenceConstraint ;
valueConstraint : constraint? ;
presenceConstraint : (PRESENT|ABSENT|OPTIONAL)? ;
patternConstraint : PATTERN value ;
exceptionSpec : ('!' exceptionIdentification)? ;
exceptionIdentification : signedNumber | definedValue | type ':' value ;
versionNumber : (NUMBER ':')? ;
encodingControlSections: encodingControlSection* ;
encodingControlSection : ENCODING_CONTROL encodingreference
encodingInstructionAssignmentList;
encodingInstructionAssignmentList : ~(END|ENCODING_CONTROL)* ;
List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe:
http://www.antlr.org/mailman/options/antlr-interest/your-email-address
