cách xóa bỏ đệ quy trái

Question

Tôi muốn tạo một ngữ pháp cho phép thực hiện các cuộc gọi chức năng được thực hiện.

Đó là:

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

đâm đầu tiên của tôi là thế này:

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

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

expr : ID|fncall; 

Nhưng điều đó không do đệ quy trái.

Answer 1

Giả sử (a)() cũng sẽ có giá trị, đây là một cách để giải quyết việc này:

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'|'_')*; 

Các phân tích cú pháp được tạo ra từ ngữ pháp trên sẽ phân tích đầu vào:

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

và xây dựng AST sau:

Nếu không có quy tắc viết lại cây, ngữ pháp sẽ trông giống như sau:

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'|'_')*;