An ANTLR Grammar for EsterelCOMS W4115Prof. Stephen A. EdwardsFall 2004Columbia UniversityDepartment of Computer ScienceANTLREsterel.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 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 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 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 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".The Esterel LRM•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 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 EsterelNext, I wrote a rule for each punctuation character:PERIOD : ’.’ ;POUND : ’#’ ;PLUS : ’+’ ;DASH : ’-’ ;SLASH : ’/’ ;STAR : ’*’ ;PARALLEL : "||" ;A Lexer for EsterelIdentifiers are standard:ID: (’a’..’z’ | ’A’..’Z’)(’a’..’z’ | ’A’..’Z’ | ’_’ | ’0’..’9’)*;A 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 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 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 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.NumbersWith 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: (’0’..’9’)+( ’.’ (’0’..’9’)* (Exponent)?( (’f’|’F’) { $setType(FloatConst); }| /* empty */ { $setType(DoubleConst); })| /* empty */ { $setType(Integer); });Number Rules ContinuedFractionalNumber: ’.’ (’0’..’9’)+ (Exponent)?( (’f’|’F’) { $setType(FloatConst); }| /* empty */ { $setType(DoubleConst); });protectedExponent: (’e’|’E’) (’+’|’-’)? (’0’..’9’)+;CommentsFrom the LRM:Simple comments start with % and end at end-of-line.Multiple-line comments start with %{ and end with }%.CommentsComment: ’%’( (’{’) => ’{’( // 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 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 LRMNonParallel:AtomicStatementSequenceSequence:SequenceWithoutTerminator ;optSequenceWithoutTerminator:AtomicStatement ; AtomicStatementSequenceWithoutTerminator ; AtomicStatementAtomicStatement:nothingpause...Grammar 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 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?Nondeterminismsequence : atomicStatement(SEMICOLON atomicStatement)*(SEMICOLON)? ;Is equivalent tosequence : atomicStatement seq1 seq2 ;seq1 : SEMICOLON atomicStatement seq1| /* nothing */ ;seq2 : SEMICOLON| /* nothing */ ;Nondeterminismsequence : atomicStatement seq1 seq2 ;seq1 : SEMICOLON atomicStatement seq1| /* nothing */ ;seq2 : SEMICOLON| /* nothing */ ;How does it choose an alternative in seq1?First choice: next token is a semicolon.Second choice: next token is one that may follow seq1.But this may
View Full Document