antlr4 json语法和间接左递归

Question

我读了"The Definite ANTLR4 Reference"，它说

While ANTLR v4 can handle direct left recursion, it can’t handle indirect left recursion.

第 71 页。
但在第 90 页的 json 语法中，我看到下一个

grammar JSON;

json:   object
    |   array
    ;

object
    :   '{' pair (',' pair)* '}'
    |   '{' '}' // empty object
    ;
pair:   STRING ':' value ;

array
    :   '[' value (',' value)* ']'
    |   '[' ']' // empty array
    ;

value
    :   STRING
    |   NUMBER
    |   object  // indirect recursion
    |   array   // indirec recursion
    |   'true'
    |   'false'
    |   'null'
    ;

是否正确？

Answer 1

你提到的JSON语法不是问题，因为它实际上不包含任何间接左递归。

规则 value 可以产生 array 并且 array 可以再次产生包含 value 的东西，但不是因为它最左边的部分。（在value之前有一个[）

value 规则只会是一个问题，如果有某种方法可以生成 value 后跟任何终端和 non-terminals.

来自本书

A left-recursive rule is one that either directly or indirectly invokes itself on the left edge of an alternative.

示例：

expr : expr '*' expr // match subexpressions joined with '*' 
     | expr '+' expr // match subexpressions joined with '+' operator
     | INT // matches simple integer atom
     ;

它是左递归，因为至少有一个选择直接从expr开始。也是直接左递归。

间接左递归示例：

expr : addition // indirectly invokes expr left recursively via addition
     | ...
     ;

addition : expr '+' expr 
         ;

antlr4 json语法和间接左递归

antlr4 json grammar and indirect left recursion

antlr4