从这个奇怪的表达式语法中消除左递归

Question

我正在尝试编写一个表达式语法，其中有 3 个运算符“+”、“-”和“/”。乘法运算符由并列表示：

(1+2)(3+4 5)

语法如下：

S -> A ('+' A)*

A -> B ('-' B)*

B -> C ('/' C)*

C -> D ( D )*

D ->ID
    |Num
    |'(' S ')'

我正在使用 Xtext，它使用 ANTLR 解析器，它说这在规则 C 上是递归的。如果我将规则 4 更改为

C -> D ('\*' D)*

然后错误就消除了。我很迷惑。需要一些帮助！

Answer 1

我对Xtext一无所知，但是Antlr 4对这个语法没问题：

grammar Expr; 
s: a ('+' a)* ;
a: b ('-' b)* ;
b: c ('/' c)* ;
c: d ( d )* ;
d: ID | NUM |'(' s ')' ;
ID: [a-z][a-z0-9]* ;
NUM: [0-9]+ ;
WS: [ \t\r\n]+ -> skip ;

当我编译运行你的例子 (1+2)(3+4 5) 时，我得到了这个解析树：

可能是 Xtext 使用的是旧版本的 Antlr。这是一个很棒的软件，但在旧版本中尤其不完美。根据标准定义，此文法不是左递归的。有可能 Antlr 正在将其转换为更简单的语法，是左递归，但这将是一个显然已修复的错误。

因此，如果我的猜测是正确的，您将成功使用以下显式 "simplified" 语法：

grammar Expr; 
s: a ap ;
ap: '+' a ap | /* eps */ ;
a: b bp ;
bp: '-' b bp | /* eps */ ;
b: c cp ;
cp: '/' c cp | /* eps */ ;
c: d dp ;
dp: d dp | ;
d: ID | NUM |'(' s ')' ;
ID: [a-z][a-z0-9]* ;
NUM: [0-9]+ ;
WS: [ \t\r\n]+ -> skip ;

新的解析树：

从这个奇怪的表达式语法中消除左递归

Eliminating Left Recursion from this weird Expression Grammar

grammar

parsing

left-recursion