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 回答