at15 / reika

[WIP] A DSL for query and benchmark TSDB
MIT License
1 stars 0 forks source link

[antlr] Left Recursion #20

Closed at15 closed 6 years ago

at15 commented 6 years ago

When reading the book Language Implementation Patterns (ANTLR3), found a example of list, which seems to have indirect left recursion. But as I remember ANTLR4 handles LR better but still can't handle indirect left recursion (it is mentioned in the ANTLR4 book somewhere)

From ANTLR3 book P26, example text is [a, b, c], [a, [b, c], d]

grammar NestedNameList;
list : '[' elements ']' ;
elements : element (',' element)* ;
element: NAME | list ;
NAME : [a-zA-Z]+;
at15 commented 6 years ago

based on ANTLR3 P27, it seems the example in the issue is not left recursion

left recursion is a rule that invokes itself without consuming a token, result in an infinite method invocation loop

r: r X ;

result in a function (that doesn't match any progress)

void r() { r(); match(X); }
at15 commented 6 years ago

ANTLR4 P249 Chapter 14 Removing Direct Left Recursion

expr: expr '*' expr
       | expr '+' expr
       | INT
       | ID
       ;

P252 mentioned minus sign #18 when saying this (?precedence climbing or the transformation on rules?) is not operator precedence parsing

Operator precedence parsing can't handle things like minus sign that has two different precedences