消除间接左递归

我的大脑被炸，试图消除生产规则中的一些左递归。我建立与JavaCC的一个编译器，我需要用以下2生产规则：消除间接左递归

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

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

但问题是，片段与表达这是关系到片段，即：间接左递归。

我看了看周围的互联网，似乎每个人都使用这种算法，可以发现here。该网站并没有直接解释左递归消除，你可以找到here

我结束了这样的规则：

void expression(): {} 
{ 
    fragment() 
    (
    (<PLUS>|<MINUS>|<DIVIDE>|<ASTERISKS>) 
    fragment() 
)* 
} 

void k(): {} 
{ 
    (
    ((<PLUS>|<MINUS>|<DIVIDE>|<ASTERISKS>)fragment())*k() 
    | fragment() 
) 
} 

void fragment(): {} 
{ 
    (
    <ID>k() 
    | number()k() 
    | (<PLUS>|<MINUS>)fragment()k() 
) 
}

他们写在用于JavaCC的代码，所以希望你能理解他们。基本上我引入了一个规则K来处理递归，除了问题依然存在之外，因为K的第一部分可以减少为无，因为它是*（0或更多次），这会留下更多的K - > k（）递归！

我不知道该从哪里走，并失去了很多头发。任何见解将不胜感激！

来源

2012-12-12 carlmango11

你通常可以有'term'，'expression'，然后是一个终端符号，为什么这里不够好？ – 2012-12-12 19:10:32

我认为'fragment'的定义不正确。 “表达式”不应该出现在字面括号之间，比如'fragment：= ...'（'expression'）''？否则，在“片段”级别使用“表达式”是没有意义的。请注意，我并不熟悉JavaCC，但这在其他解析器生成器中会遇到问题。 – user1201210

我在想同样的事情提心吊胆。我似乎无法想象这样一种情况，即片段中的“表达式”会被使用。然而，这些规则在决定我是一名讲师的时候非常有用。也许我应该联系他？ H2CO3：你能解释一下吗？你的意思是我应该创建一个规则'term'？它会包括什么？我实际上已经看到人们在网络中使用“term”，但我认为遵循该算法会更好。 – carlmango11

我建议重写规则expression如下：

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

实际上，这仅仅是在原有定义的fragment替代，与克林运营商方便地吸收一些术语。

当然，无论从解析这个结构创建的结构都需要被包容，如果它应该反映原始规则。

来源

2012-12-22 00:42:34

消除间接左递归

回答

相关问题