CODEWITHSUNDEEP
parsingantlrgrammarlexer
sebastian
sebastian

Reputation: 412

ANTLR : issue with greedy rule

I never worked with ANTLR and generative grammars, so this is my first attempt.

I have a custom language I need to parse. Here's an example:

-- This is a comment
CMD.CMD1:foo_bar_123
CMD.CMD2
CMD.CMD4:9 of 28 (full)
CMD.NOTES:
This is an note.
    A line 
      (1) there could be anything here foo_bar_123 & $ £ _ , . ==> BOOM
      (3) same here
CMD.END_NOTES:

Briefly, there could be 4 types of lines:

1) -- comment
2) <section>.<command>
3) <section>.<command>: <arg>
4) <section>.<command>:
       <arg1>
       <arg2>
       ...
   <section>.<end_command>:

<section> is the literal "CMD"

<command> is a single word (uppercase, lowercase letters, numbers, '_')

<end_command> is the same word of <command> but preceded by the literal "end_"

<arg> could be any character

Here's what I've done so far:

grammar MyGrammar;

/*
* Parser Rules
*/

root                : line+ EOF ;

line                : (comment_line | command_line | normal_line) NEWLINE;

comment_line        : COMMENT ;

command_line        : section '.' command ((COLON WHITESPACE*)? arg)? ;

normal_line         : TEXT ;

section             : CMD ;

command             : WORD ;

arg                 : TEXT ;

/*
* Lexer Rules
*/

fragment LOWERCASE  : [a-z] ;
fragment UPPERCASE  : [A-Z] ;
fragment DIGIT      : [0-9] ;

NUMBER          : DIGIT+ ([.,] DIGIT+)? ;

CMD             : 'CMD';

COLON           : ':' ;

COMMENT         : '--' ~[\r\n]*;

WHITESPACE      : (' ' | '\t') ;

NEWLINE         : ('\r'? '\n' | '\r')+;

WORD            : (LOWERCASE | UPPERCASE | NUMBER | '_')+ ;

TEXT            : ~[\r\n]* ;

This is a test for my grammar:

$antlr4 MyGrammar.g4

warning(146): MyGrammar.g4:45:0: non-fragment lexer rule TEXT can match the empty string

$javac MyGrammar*.java

$grun MyGrammar root -tokens

CMD.NEW

[@0,0:6='CMD.NEW',<TEXT>,1:0]

[@1,7:7='\n',<NEWLINE>,1:7]

[@2,8:7='<EOF>',<EOF>,2:0]

The problem is that "CMD.NEW" gets swallowed by TEXT, because that rule is greedy.

Anyone can help me with this? Thanks

Upvotes: 2

Views: 692

Answers (1)

Pavel Smirnov
Pavel Smirnov

Reputation: 4799

There is a grammar ambiguity.

In the example you have provided CMD.NEW can match both command_line and normal_line.
Thus, given the expression:

 line                : (comment_line | command_line | normal_line) NEWLINE;

the parser can not definitely say what rule to accept (command_line or normal_line), so it matches it to normal_line which is actually a simple TEXT.

Consider rewriting your grammar in the way the parser can always say what rule to accept.

UPDATE:

Try this (I did not test that, but it should work):

grammar MyGrammar;

/*
* Parser Rules
*/

root                : line+ EOF ;

line                : (comment_line | command_line) NEWLINE;

comment_line        : COMMENT ;

command_line        : CMD '.' (note_cmd | command);

command             : command_name ((COLON WHITESPACE*)? arg)? ;

note_cmd            : notes .*? (CMD '.' END_NOTES) ;

command_name             : WORD ;

arg                 : TEXT ;

/*
* Lexer Rules
*/

fragment LOWERCASE  : [a-z] ;
fragment UPPERCASE  : [A-Z] ;
fragment DIGIT      : [0-9] ;

NUMBER          : DIGIT+ ([.,] DIGIT+)? ;

CMD             : 'CMD';

COLON           : ':' ;

COMMENT         : '--' ~[\r\n]*;

WHITESPACE      : (' ' | '\t') ;

NEWLINE         : ('\r'? '\n' | '\r')+;

WORD            : (LOWERCASE | UPPERCASE | NUMBER | '_')+ ;

NOTES            : 'NOTES';

END_NOTES        : 'END_NOTES';

TEXT            : ~[\r\n]* ;

Upvotes: 2

Related Questions