我的大脑正在试图从生产规则中消除一些左递归。我正在使用 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()递归!!
我不知道从这里去哪里,并且掉了很多头发。任何见解将不胜感激!