Jak usunąć lewa rekursja

Question

Chciałbym stworzyć gramatykę, która pozwoli na curry wywołania funkcji.

Czyli:

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

Moje pierwsze ukłucie było to:

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

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

expr : ID|fncall; 

Ale to nie ze względu na lewej rekursji.

Answer 1

Zakładając (a)() byłoby również ważne, oto sposobem rozwiązania to:

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

Parser wygenerowany z gramatyki powyżej będzie analizować dane wejściowe:

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

i skonstruować następującą AST:

Bez reguł przepisywania drzewa gramatyka wyglądałaby następująco:

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