Jim Idle wrote:
> Sam Barnett-Cormack wrote:
>> Sam Barnett-Cormack wrote:
>>
>>> Sam Barnett-Cormack wrote:
>>>
>>>
>>> type : ((typeWithConstraint)=>typeWithConstraint | builtinType |
>>> referencedType) constraint* ;
>>>
>>> And a load of parser warnings and errors that it wasn't bothering to
>>> generate before... *sigh*
>>>
>>
>> Or even *lexer* warnings and errors
(turns out those were the result of weird behaviour I've been seeing
that I can only assume is a bug; I'll report on that separately)
> I think that you need to start again and go a lot more slowly in
> building up your grammar. There is no point asking about each and every
> error you are getting, as you won't learn anything. Do this:
Well, I think I've been learning a lot... nowhere near every error I've
got has come here, only the ones I've failed to trace on my own. After
getting a pointer on a few, I've managed to fix most of the rest myself.
I'm currently wrestling with something odd that I can't see how to
resolve, but I'm trying to understand it myself before I ask for help. I
apologise if I'm currently too incompetent to be worth anyone helping.
> 1) Do not use 'xxxx' type things in the parser rules;
I'm aware of the issues - they lead to a more readable grammar, more
natural-feeling, and I'm pretty damn sure that they aren't causing any
of my problems.
> 2) Start with a blank lexer and parser;
Well, I certainly did this time.
> 3) Build the parser rules for expressions, by starting with the primary
> elements and gradually inserting rules in the expression tree one at a
> time - compile and test after each rule, fix issue as soon as you see
> them, do not leave them to accumulate as you will get nowhere;
> 4) Now add one parser rule at a time (you will sometimes need a few at
> once of course) and compile and test after each change - compile and
> test after each rule, fix issue as soon as you see them, do not leave
> them to accumulate as you will get nowhere;
Now, I'll admit I did get a bit tied up, and starting like that
originally would have been good (and was what I was trying to do). Once
it seemed to be going okay, I got frustrated looking between screen and
standard so often, and let myself go too far. However, I doubt very much
that starting again now would help. I'd just run into the remaining
problem(s) from a different angle.
> The things you are seeing are standard things that happen when you start
> out by typing in a grammar from the normative grammar of some language
> spec. Such language specs are not really written with writing a parser
> spec in mind (most say this) and even if they are they are usually
> written with yacc/bison in mind. Consequently they are full of
> ambiguities that you must left factor as you go.
Well, I didn't just blindly copy them out, although I'll admit I got
tied up in left-recursion issues. The grammar actually seems to have
some ambiguities that would be ambiguous anywhere, actually, which is a
pain in the neck, by c'est la vie.
I also didn't want to refactor it anymore than necessary because there
is a relationship between the structure of rules in the standard and the
semantic structure, which should help at later stages.
> Unless you have built a lot of grammars, that is why you need to do this
> in small steps - otherwise you will end up turning on backtracking and
> adorning the grammar with predicates that include entire rules such as
> (typeWithConstraint)=> when the real issue is that you have not left
> factored the grammar correctly.
Oop, thanks for that one, I'd missed that when I was removing
unnecessary predicates that were exploratory.
> Get a copy of the book if you can, it will help a lot, and read through
> as much of the Wiki as you can before your fingers itch to get back at
> the keyboard.
Got the book. Read it, in fact. Also have a good mark on languages &
compilers from my undergrad days, but that doesn't really mean anything.
Read a lot of the wiki, which seems to largely have a more judgemental
tone than the book, but read a lot of it anyway.
In case you're interested, and by way of demonstrating that I am making
progress, the current state of the grammar is attached. Only one error
stopping it compiling, and one non-breaking warning that I will want to
fix before using this for anything.
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 {
// literals
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';
// tokens accessed by actions
HSTRING;
BSTRING;
NUMBER;
// virtual tokens
}
@header {
package com.gobito.asn_1.parse;
import static com.gobito.asn_1.parse.ParseUtil.*;
}
@lexer::header {
package com.gobito.asn_1.parse;
import static com.gobito.asn_1.parse.ParseUtil.*;
}
@members {
}
@lexer::members {
}
// Lexical elements
//"real" stuff
WS : (WSNONL | NL) {$channel=HIDDEN;};
fragment
NL : ('\n' | '\r' | '\u000B' | '\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*;
REALNUMBER
: (NUMBERf '.')=> NUMBERf ('.'(DIGIT+)?)? (('e'|'E')('+'|'-')? NUMBERf)?
| NUMBERf {$type=NUMBER;};
fragment
HSTRINGCONT : ('0'..'9' | 'A'..'F' | WS)*;
HorBSTRING : '\'' cont=HSTRINGCONT '\'' ('H' {$type=HSTRING;}|'B'
{$type=BSTRING;}) {($type == HSTRING) || isValidBSTRING($cont.text)}?;
fragment
CSTRINGNL : WSNONL* NL WSNONL*;
CSTRING options {backtrack=true;}: ('"') {skip();} ((WS)=>
((CSTRINGNL)=>CSTRINGNL {skip();} | WSNONL+) | '"' {skip();} '"' | ~'"')* ('"'
{skip();}) {$channel=DEFAULT;};
// 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
((objectIdentifierValue)=>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
| valuereference
/*| 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 : typereference (type '::='|'::=' type) '{'
elementSetSpecs '}';
type : (typeWithConstraint | builtinType | referencedType) constraint* ;
builtinType
: bitStringType
| booleanType
| characterStringType
| choiceType
| embeddedPDVType
| enumeratedType
| externalType
/*| instanceOfType*/
| integerType
| nullType
/*| objectClassFieldType*/
| objectIdentifierType
| octetStringType
| realType
| relativeOIDType
| sequenceType
| sequenceOfType
| setType
| setOfType
| prefixedType ;
referencedType
: (usefulType)=>usefulType
| definedType
| selectionType
/*| typeFromObject */
/*| valueSetFromObjects*/ ;
namedType : identifier type;
value options {backtrack=true;} : builtinValue | referencedValue /*|
objectClassFieldValue*/ ;
builtinValue options {backtrack=true;}
: 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) != 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 '{' sequenceTypeBody '}';
sequenceTypeBody options {backtrack=true;}
: componentTypeLists?
;
extensionAndException : '...' exceptionSpec ;
optionalExtensionMarker : (',' '...')? ;
ctlExtensionStuff
: extensionAndException extensionAdditions
( optionalExtensionMarker
| extensionEndMarker ',' rootComponentTypeList
) ;
componentTypeLists
: 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? '}' ;
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 clazz classNumber ']' ;
encodingReference : (encodingreference ':')? ;
encodingPrefixedType : encodingPrefix type ;
encodingPrefix : '[' encodingReference /*encodingInstruction*/ ']' ;
classNumber : NUMBER | definedValue ;
clazz : (UNIVERSAL | APPLICATION | PRIVATE)? ;
objectIdentifierType : OBJECT IDENTIFIER ;
objectIdentifierValue : '{' ( ((definedValue)=>definedValue objIdComponents+) |
objIdComponents+) '}' ;
objIdComponents options{backtrack=true;} : nameForm {isStandardOIDName($text)}?
| numberForm | nameAndNumberForm | definedValue ;
numberForm : NUMBER ;
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 : a=typereference {$a.text == "GeneralizedTime" || $a.text ==
"UTCTime" || $a.text == "ObjectDescriptor" }? ;
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 (unionMark intersections)* ;
//uElems : unions ;
intersections : intersectionElements (intersectionMark intersectionElements)* ;
//iElems : intersections ;
intersectionElements : elements exclusions? ;
exclusions : EXCEPT elements ;
unionMark : '|' | UNION ;
intersectionMark : '^' | INTERSECTION ;
elements : subtypeElements /*| objectSetElements*/ | '(' elementSetSpec ')' ;
subtypeElements
options {backtrack=true;}
: valueRange
| singleValue
| containedSubtype
| 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
