An ANTLR Grammar for EsterelAn ANTLR Grammar for EsterelCOMS W4115Prof. Stephen A. EdwardsSpring 2003Columbia UniversityDepartment of Computer ScienceANTLRANTLREsterel.gclass EsterelParserextends Parser;file : expr EOF!;class EsterelLexerextends Lexer;ID : LETTER (LETTER| DIGIT)* ;→EsterelParser.javapublic classEsterelParser extendsantlr.LLkParserimplementsEsterelParserTokenTypes{}EsterelLexer.javapublic class EsterelLexerextends antlr.CharScannerimplementsEsterelParserTokenTypes,TokenStream {}ANTLR Lexer SpecificationsANTLR Lexer SpecificationsLook likeclass MyLexer extends Lexer;options {option = value}Token1 : ’char’ ’char’ ;Token2 : ’char’ ’char’ ;Token3 : ’char’ (’char’)? ;Tries to match all non-protected tokens at once.ANTLR Parser SpecificationsANTLR Parser SpecificationsLook likeclass MyParser extends Parser;options {option = value}rule1 : Token1 Token2| Token3 rule2 ;rule2 : (Token1 Token2)* ;rule3 : rule1 ;Looks at the next k tokens when deciding which option toconsider next.An ANTLR grammar for EsterelAn ANTLR grammar for EsterelEsterel: Language out of France. Programs look likemodule ABRO:input A, B, R;output O;loop[ await A || await B ];emit Oeach Rend moduleThe Esterel LRMThe Esterel LRMLexical aspects are classical:•Identifiers are sequences of letters, digits, and theunderline character , starting with a letter.•Integers are as in any language, e.g., 123, andfloating-point numerical constants are as in C++ andJava; the values 12.3, .123E2, and 1.23E1 areconstants of type double, while 12.3f, .123E2f, and1.23E1f are constants of type float.•Strings are written between double quotes, e.g.,"a string", with doubled double quotes as in"a "" double quote".•Keywords are reserved and cannot be used asidentifiers. Many constructs are bracketed, like“present ... end present”. For suchconstructs, repeating the initial keyword is optional;one can also write “present ... end”.•Simple comments start with % and end at end-of-line.Multiple-line comments start with %{ and end with }% .A Lexer for EsterelA Lexer for EsterelOperators from the langauge reference manual:. # + - / * || < > , = ; : := ( )[ ] ? ?? <= >= <> =>Main observation: none longer than two characters. Needk = 2 to disambiguate, e.g., ? and ??.class EsterelLexer extends Lexer;options {k = 2;}A Lexer for EsterelA Lexer for EsterelNext, I wrote a rule for each punctuation character:PERIOD : ’.’ ;POUND : ’#’ ;PLUS : ’+’ ;DASH : ’-’ ;SLASH : ’/’ ;STAR : ’*’ ;PARALLEL : "||" ;A Lexer for EsterelA Lexer for EsterelIdentifiers are standard:ID: (’a’..’z’ | ’A’..’Z’)(’a’..’z’ | ’A’..’Z’ | ’_’ | ’0’..’9’)*;A Lexer for EsterelA Lexer for EsterelString constants must be contained on a single line andmay contain double quotes, e.g.,"This is a constant with ""double quotes"""ANTLR makes this easy: annotating characters with !discards them from the token text:StringConstant: ’"’!( ˜(’"’ | ’\n’)| (’"’! ’"’))*’"’!;A Lexer for EsterelA Lexer for EsterelI got in trouble with the ˜ operator, which inverts acharacter class. Invert with respect to what?Needed to change options:options {k = 2;charVocabulary = ’\3’..’\377’;exportVocab = Esterel;}A Lexer for EsterelA Lexer for EsterelAnother problem: ANTLR scanners check eachrecognized token’s text against keywords by default.A string such as "abort" would scan as a keyword!options {k = 2;charVocabulary = ’\3’..’\377’;exportVocab = Esterel;testLiterals = false;}ID options { testLiterals = true; }: (’a’..’z’ | ’A’..’Z’) /* ... */ ;Numbers DefinedNumbers DefinedFrom the LRM:Integers are as in any language, e.g., 123, andfloating-point numerical constants are as in C++ and Java;the values 12.3, .123E2, and 1.23E1 are constants oftype double, while 12.3f, .123E2f, and 1.23E1f areconstants of type float.NumbersNumbersWith k = 2, for each rule ANTLR generates a set ofcharacters that can appear first and a set that can appearsecond. But it doesn’t consider the possible combinations.I split numbers into Number and FractionalNumber toavoid this problem: If the two rules were combined, thelookahead set for Number would include a period (e.g.,from “.1”) followed by end-of-token e.g., from “1” by itself).Example numbers:.1$.21$First Second. EOT1 .2 1Number RulesNumber RulesNumber: (’0’..’9’)+( ’.’ (’0’..’9’)* (Exponent)?( (’f’|’F’) { $setType(FloatConst); }| /* empty */ { $setType(DoubleConst); })| /* empty */ { $setType(Integer); });Number Rules ContinuedNumber Rules ContinuedFractionalNumber: ’.’ (’0’..’9’)+ (Exponent)?( (’f’|’F’) { $setType(FloatConst); }| /* empty */ { $setType(DoubleConst); });protectedExponent: (’e’|’E’) (’+’|’-’)? (’0’..’9’)+;CommentsCommentsFrom the LRM:Simple comments start with % and end at end-of-line.Multiple-line comments start with %{ and end with }%.CommentsCommentsComment: ’%’( (’{’) => ’{’( // Prevent .* from eating the whole fileoptions {greedy=false;}:((’\r’ ’\n’) => ’\r’ ’\n’ { newline(); }| ’\r’ { newline(); }| ’\n’ { newline(); }| ˜( ’\n’ | ’\r’ )))*"}%"| ((˜’\n’))* ’\n’ { newline(); }){ $setType(Token.SKIP); };A Parser for EsterelA Parser for EsterelEsterel’s syntax started out using ; as a separator andlater allowed it to be a terminator.The language reference manual doesn’t agree with whatthe compiler accepts.Grammar from the LRMGrammar from the LRMNonParallel:AtomicStatementSequenceSequence:SequenceWithoutTerminator ;optSequenceWithoutTerminator:AtomicStatement ; AtomicStatementSequenceWithoutTerminator ; AtomicStatementAtomicStatement:nothingpause...Grammar from the LRMGrammar from the LRMBut in fact, the compiler acceptsmodule TestSemicolon1:nothing;end modulemodule TestSemicolon2:nothing; nothing;end modulemodule TestSemicolon3:nothing; nothingend moduleRule seems to be “one or more statements separated bysemicolons except for the last, which is optional.”Grammar for Statement SequencesGrammar for Statement SequencesObvious solution:sequence: atomicStatement(SEMICOLON atomicStatement)*(SEMICOLON)?;warning: nondeterminism uponk==1:SEMICOLONbetween alt 1 and exit branch of blockWhich option do you take when there’s a semicolon?NondeterminismNondeterminismsequence : atomicStatement(SEMICOLON atomicStatement)*(SEMICOLON)? ;Is equivalent
View Full Document
Unlocking...