1

我的大脑正在试图从生产规则中消除一些左递归。我正在使用 JavaCC 构建编译器，我需要使用以下 2 个生产规则：

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

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

但问题是片段与片段相关的表达式有关，即：间接左递归。

我环顾了互联网，每个人似乎都在使用这个算法，可以在这里找到。该站点没有解释直接左递归消除，您可以在此处找到

我最终得到这样的规则：

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()递归！！

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

4

1 回答 1

1

我建议重写规则expression如下：

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

实际上，这只是fragment原始定义中的替换，Kleene 运算符方便地吸收了一些术语。

当然，如果它应该反映原始规则，则需要适应通过解析创建的任何结构。

于 2012-12-22T00:42:34.553 回答