如何刪除左遞歸

Question

我想創建一個允許curried函數調用的語法。

即：

a() /// good 
a()() /// good 
a()()() /// good 
a(a) /// good 
a(a()()) /// good 
/// etc 

我的第一個嘗試是這樣的：

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

fncall : expr '(' (expr (',' expr)*)? ')'; 

expr : ID|fncall; 

但是失敗，因爲左遞歸。

Answer 1

假設(a)()也將是有效的，這裏的解決此問題的方法：

grammar T; 

options { 
    output=AST; 
} 

tokens { 
    EXPR_LIST; 
    CALL; 
    INDEX; 
    LOOKUP; 
} 

parse 
: expr EOF -> expr 
; 

expr 
: add_expr 
; 

add_expr 
: mul_exp (('+' | '-')^ mul_exp)* 
; 

mul_exp 
: atom (('*' | '/')^ atom)* 
; 

atom 
: fncall 
| NUM 
; 

fncall 
: (fncall_start -> fncall_start) ('(' expr_list ')' -> ^(CALL $fncall expr_list) 
            | '[' expr ']'  -> ^(INDEX $fncall expr) 
            | '.' ID   -> ^(LOOKUP $fncall ID) 
           )* 
; 

fncall_start 
: ID 
| '(' expr ')' -> expr 
; 

expr_list 
: (expr (',' expr)*)? -> ^(EXPR_LIST expr*) 
; 

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

從語法生成上述將解析輸入解析器：

(foo.bar().array[i*2])(42)(1,2,3) 

和構造如下的AST：

沒有樹重寫規則，語法看起來是這樣的：

grammar T; 

parse 
: expr EOF 
; 

expr 
: add_expr 
; 

add_expr 
: mul_exp (('+' | '-') mul_exp)* 
; 

mul_exp 
: atom (('*' | '/') atom)* 
; 

atom 
: fncall 
| NUM 
; 

fncall 
: fncall_start ('(' expr_list ')' | '[' expr ']' | '.' ID)* 
; 

fncall_start 
: ID 
| '(' expr ')' 
; 

expr_list 
: (expr (',' expr)*)? 
; 

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