Antlr program won't compile

Question

I am trying to make a grammar to parse the json language

The link i used to understand the automata for every entry http://www.json.com

grammar myjson;

prog
    : object+ EOF
    ;

object
    : '{'
        STRING  ':' value 
        (','  STRING  ':' value)*
      '}'
    | '{' EMPTY '}'
    ;

array
    : '[' 
        value 
        (',' value)* 
      ']'
    | '[' EMPTY ']
    ; 

value
    : object | STRING | NUMBER
    | array | BOOL | NULL
    ;

STRING
    : '"' (UNICODE | SPECIAL)* '"'
    ;

UNICODE
    : ~('\u0022' | '\u005C')
    ;

SPECIAL     
    : '\u005C'
      (
      | '"' | '\u005C'  | '\u002F'
      | 'b' | 'f' | 'n' | 'r'
      | 't' | 'u' DIGIT DIGIT DIGIT DIGIT
      )
    ;

NULL: 'null';
BOOL
    : 'true'
    | 'false'
    ;   


NUMBER : ('+'|'-')? DIGIT+ '.' DIGIT* EXPONENT?
       | ('+'|'-')? '.'? DIGIT+ EXPONENT?
       ;

fragment 
EXPONENT : ('e' | 'E') ('+' | '-') ? DIGIT+ 
         ;

fragment
DIGIT  : '0'..'9' 
       ;

fragment
LETTER
    : ('a'..'z' | 'A'..'Z')
    ;

COMM
    : '//' ~('\r'? '\n')   {skip();}    
    | '/*' .* '*/'         {skip();}
    ;

WS
    : ' ' | '\t' | '\r' | '\n' | '\u000c' {skip();} 
    ;

EMPTY
    : ''
    ;

I would like to state that i am using antlrworks v 1.4.3 because that's what my teacher suggested to work with.

My problem is that that this grammar won't even compile because i get the following error

java.util.NoSuchElementException: can't look backwards more than one token in this stream
    at org.antlr.runtime.misc.LookaheadStream.LB(LookaheadStream.java:159)
    at org.antlr.runtime.misc.LookaheadStream.LT(LookaheadStream.java:120)
    at org.antlr.runtime.RecognitionException.extractInformationFromTreeNodeStream(RecognitionException.java:144)
    at org.antlr.runtime.RecognitionException.<init>(RecognitionException.java:111)
    at org.antlr.runtime.MismatchedTreeNodeException.<init>(MismatchedTreeNodeException.java:42)
    at org.antlr.runtime.tree.TreeParser.recoverFromMismatchedToken(TreeParser.java:135)
    at org.antlr.runtime.BaseRecognizer.match(BaseRecognizer.java:115)
    at org.antlr.grammar.v3.TreeToNFAConverter.alternative(TreeToNFAConverter.java:2798)
    at org.antlr.grammar.v3.TreeToNFAConverter.block(TreeToNFAConverter.java:2662)
    at org.antlr.grammar.v3.TreeToNFAConverter.rule(TreeToNFAConverter.java:1995)
    at org.antlr.grammar.v3.TreeToNFAConverter.rules(TreeToNFAConverter.java:1338)
    at org.antlr.grammar.v3.TreeToNFAConverter.grammarSpec(TreeToNFAConverter.java:1288)
    at org.antlr.grammar.v3.TreeToNFAConverter.grammar_(TreeToNFAConverter.java:319)
    at org.antlr.tool.Grammar.buildNFA(Grammar.java:1006)
    at org.antlr.tool.CompositeGrammar.createNFAs(CompositeGrammar.java:390)
    at org.antlr.works.grammar.antlr.ANTLRGrammarEngineImpl.createLexerGrammarFromCombinedGrammar(ANTLRGrammarEngineImpl.java:219)
    at org.antlr.works.grammar.antlr.ANTLRGrammarEngineImpl.createCombinedGrammar(ANTLRGrammarEngineImpl.java:204)
    at org.antlr.works.grammar.antlr.ANTLRGrammarEngineImpl.createGrammars(ANTLRGrammarEngineImpl.java:165)
    at org.antlr.works.grammar.antlr.ANTLRGrammarEngineImpl.analyze(ANTLRGrammarEngineImpl.java:272)
    at org.antlr.works.grammar.engine.GrammarEngineImpl.analyze(GrammarEngineImpl.java:325)
    at org.antlr.works.debugger.local.DBLocal.analyzeGrammar(DBLocal.java:385)
    at org.antlr.works.debugger.local.DBLocal.generateAndCompileGrammar(DBLocal.java:365)
    at org.antlr.works.debugger.local.DBLocal.run(DBLocal.java:222)
    at java.lang.Thread.run(Unknown Source)

I read in a post about "can't look backwards more than one token in this stream" java exception that the lexer and parser grammar don't match but i have no idea what that is or what it refers to. I also apologize for not commenting the code. But I don't know too much antlr so I don't want to write something that could put you off.

Please help and thank you in advance

Bart Kiers Bart Kiers · Accepted Answer · 2013-11-28T07:36:11

There are a couple of things wrong in your grammar:

never match tokens that (potentially) match an empty string: your lexer would go in an infinite loop when it tries to match them. In short: remove the EMPTY token
' ' | '\t' | '\r' | '\n' | '\u000c' {skip();} is equivalent to ' ' | '\t' | '\r' | '\n' | ('\u000c' {skip();}). You'd want to do: (' ' | '\t' | '\r' | '\n' | '\u000c') {skip();} instead
your SPECIAL rule matches a single backslash: '\u005C' ( /* NOTHING HERE */ | '"' | ...: remove the first |: '\u005C' ( '"' | ...
a negated character set must contain single characters, not two as you did: ~('\r'? '\n')* (you can't negate \r\n). It should be: ~('\r' | '\n')*

Try something like this instead (untested!):

grammar myjson;

prog
 : object+ EOF
 ;

object
 : '{' (key_value (',' key_value)*)? '}'
 ;

array
 : '[' (value (',' value)*)? ']'
 ;

key_value
 : STRING ':' value
 ;

value
 : object
 | array
 | STRING
 | NUMBER
 | BOOL
 | NULL 
 ;

NULL
 : 'null'   
 ;

BOOL
 : 'true'
 | 'false'
 ;

STRING
  : '"' (UNICODE | SPECIAL)* '"'
  ;

NUMBER
 : ('+'|'-')? DIGIT+ '.' DIGIT* EXPONENT?
 | ('+'|'-')? '.'? DIGIT+ EXPONENT?
 ;

COMM
 : '//' ~('\r' | '\n')* {skip();}    
 | '/*' .* '*/'         {skip();}
 ;

SPACE
 : (' ' | '\t' | '\r' | '\n' | '\u000c')+ {skip();}
 ;

fragment
DIGIT
 : '0'..'9' 
 ;

fragment 
EXPONENT 
 : ('e' | 'E') ('+' | '-') ? DIGIT+ 
 ;

fragment
UNICODE
 : ~('\u0022' | '\u005C') 
 ;

fragment
SPECIAL     
 : '\u005C' ( '"' | '\u005C'  | '\u002F'
            | 'b' | 'f' | 'n' | 'r'
            | 't' | 'u' DIGIT DIGIT DIGIT DIGIT
            )
 ;

Also check the JSON grammar from the ANTLR Github repository: https://github.com/antlr/grammars-v4/blob/master/json/Json.g4 Although an ANTLR4 grammar, it looks to be ANTLR 3 compatible.

Antlr program won't compile

1 Answers