使用antlrworks解决左递归问题

Question

您好，我想编写一个语法（使用 ANTLRWORKS），稍后接受（在调试模式下）此代码

repeat_until
    :'repeat' seq_statement 'until' exp
    ;

read    :

          'read' ID ';'  
    ;

    fragment    
Operation_stat
    :   (NUMBER|ID) OP (NUMBER|ID) 
    ;

OP  :   ('+'|'-'|'*'|'/')
    ;

NUMBER  :
'0'..'9'+   
    ;

LOG_OP  :
('<' | '>' | '=' | '<=' | '>=' )
    ;


ID  :   ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
    ;



FLOAT
    :   ('0'..'9')+ '.' ('0'..'9')* EXPONENT?
    |   '.' ('0'..'9')+ EXPONENT?
    |   ('0'..'9')+ EXPONENT
    ;

COMMENT
    :   '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
    |   '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
    ;

WS  :   ( ' '
        | '\t'
        | '\r'
        | '\n'
        ) {$channel=HIDDEN;}
    ;

STRING
    :  '\'' ( ESC_SEQ | ~('\\'|'\'') )* '\''
    ;




fragment
EXPONENT : ('e'|'E') ('+'|'-')? ('0'..'9')+ ;

fragment
HEX_DIGIT : ('0'..'9'|'a'..'f'|'A'..'F') ;

fragment
ESC_SEQ
    :   '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
    |   UNICODE_ESC
    |   OCTAL_ESC
    ;

fragment
OCTAL_ESC
    :   '\\' ('0'..'3') ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7')
    ;

fragment
UNICODE_ESC
    :   '\\' 'u' HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
    ;

感谢您的帮助

Answer 1

我相信 ANLRWorks 有一个功能可以帮助从语法中删除左递归，尽管在我的记忆中，它只适用于非常基本的语法。自从我上次谈论这个问题以来已经有一段时间了，所以你必须在这方面调查一下自己。

要手动删除左递归，请参阅：http://www.antlr。 org/wiki/display/ANTLR3/Left-Recursion+Removal （确保浏览所有 3 个部分）

编辑

我不确定是否可以帮助你：你似乎完全忽略了 ANTLR 可以无法处理左递归语法。您的以下解析器规则：

seq_statement 
  :  seq_statement ';' statement 
  |  seq_statement
  ;

simple_exp
  :  simple_exp OP term 
  |  term    
  ;

term    
  :  term OP factor factor 
  |  factor  
  ;

显然都是递归的，我不知道如何更清楚地解释这一点。我的意思是，你难道看不出像这样的规则有什么问题吗

a
  : a b
  ;

？这与您的 seq_statement 规则基本相同。

我的印象是您正在尝试将一些现有语法转换为 ANTLR 语法。是这样吗？您真的知道左递归的真正含义吗？

编辑二

之类的东西：

parse
  :  block EOF 
  ;

block
  :  statement (';' statement)* ';'? 
  ;

statement
  :  'read' expression  
  |  'write' expression 
  |  ifStatement
  |  repeatStatement
  |  assignment
  ;

ifStatement
  :  'if' expression 'then' block? ('else' block?)? 'end' 
  ;

repeatStatement
  :  'repeat' block? 'until' expression 
  ;

assignment
  :  Identifier ':=' expression 
  ;

expression
  :  equalityExp
  ;

equalityExp
  :  relationalExp (('=' | '!=') relationalExp)*
  ;

relationalExp
  :  additiveExp (('>=' | '<=' | '>' | '<') additiveExp)*
  ;

additiveExp
  :  multiplicativeExp (('+' | '-') multiplicativeExp)*
  ;

multiplicativeExp
  :  atom (('*' | '/' | '%') atom)*
  ;

atom
  :  Identifier
  |  Int
  |  '(' expression ')' 
  ;

Int
  :  '0'..'9'+
  ;

Identifier
  :  'a'..'z'+
  ;

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

应该可以解决问题。