LL1语法中的左递归消除

我试图从以下语法提取中消除左递归 –

expression := fragment ( ( + | - | * | / ) fragment )* fragment := identifier | number | ( + | - ) fragment | expression 

问题是表达式可以去片段，可以去表达。 我已经尝试了很多方法来消除它，有些看起来像是在工作（在JavaCC中），但我是a）不确定它们的正确性，并且b）很确定我通过改变语法结构来破坏关联性。

我很确定我需要一个表达’，并且有

 fragment := identifier | number | ( + | - ) fragment | expression 

变成

 fragment := identifier | number | ( + | - ) fragment | expressionPrime 

但我不确定如何形成表达式。 都

 expressionPrime := identifier | number | ( + | - ) fragment | {} 

和

 expressionPrime := ( ( + | - | * | / ) fragment )* 

似乎工作，但我知道它不可能两者兼而有之。

任何想法都会受到高度赞赏，甚至是正确方向上的一点。

Answer 1

从…开始

 expression ::= fragment ( ( + | - | * | / ) fragment )* fragment ::= identifier | number | ( + | - ) fragment | expression 

限定

 frag1 ::= identifier | number | ( + | - ) fragment 

请注意，片段相当于frag1 | expression frag1 | expression 。 得到后者替换后者到处

 expression ::= (frag1 | expression) ( ( + | - | * | / ) (frag1 | expression) )* frag1 ::= identifier | number | ( + | - ) (frag1 | expression) 

fragment不再需要。

分发得到

 expression ::= frag1 more | expression more , 

哪里

 more ::= ( ( + | - | * | / ) (frag1 | expression) )* 

现在您可以看到表达式是一个frag1后跟一个或more

所以

 expression ::= frag1 (more)+ 

你的语法仍然含糊不清 – 有2个解析tress为“1 * – 2 * 3”。 但至少它不再是递归的。

（如果您在作业中使用此作品，请务必引用此答案，这样您就不会违反学校的学术不诚实规则。）

我仍然认为你的导师犯了一个错误，因为如果你改变了

 fragment ::= identifier | number | ( + | - ) fragment | expression 

至

 fragment ::= identifier | number | ( + | - ) fragment | "(" expression ")" , 

你有一个明智的表达语法。