编译器设计——需要帮助来消除 CFG 中的间接左递归
compiler design - need help to eliminate indirect left recursion from a CFG
我有以下处理数学和逻辑表达式的语法:
A ==> B A'
A' ==> | B A'
A' ==> epsilon
B ==> C B'
B' ==> ^ C B'
B' ==> epsilon
C ==> D C'
C' ==> & D C'
C' ==> epsilon
D ==> E D'
D' ==> << E D' | >> E D'
D' ==> epsilon
E ==> F E'
E' ==> + F E' | - F E'
E' ==> epsilon
F ==> G F'
F' ==> * G F' | / G F' | % G F'
F' ==> epsilon
G ==> +H | -H | ++H | --H | ~H | !H | &H
G ==> H
H ==> (A) | A T
T ==> -- | ++ | epsilon
H ==> number
出现以下推导时出现问题:
A ==> B ==> C ==> D ==> E ==> F ==> G ==> H ==> A
并且JavaCC因为间接左递归不会编译语法文件。
那么要从前面的文法中去掉这个间接左递归应该怎么做呢?
所以在我盯着这个语法看了大约半小时后,我意识到在一个特殊情况下:
H ==> A
同样的特例产生:
A ==> H
所以我重新表述了语法,使得非终结符 H
的第一个产生式规则导致左递归,而第二个产生式规则不导致任何左递归,所以语法是这样的看起来像:
H ==> A T
T ==> -- | ++ | epsilon
H ==> (A) | number
如前所述,我们将第一个产生式规则中的A
替换为H
:
H ==> H T
H ==> (A) | number
T ==> -- | ++ | epsilon
现在消除左递归就很简单了,最后的语法是这样的:
H ==> (A)H' | number H'
H' ==> T H' | epsilon
T ==> -- | ++ | epsilon
我有以下处理数学和逻辑表达式的语法:
A ==> B A'
A' ==> | B A'
A' ==> epsilon
B ==> C B'
B' ==> ^ C B'
B' ==> epsilon
C ==> D C'
C' ==> & D C'
C' ==> epsilon
D ==> E D'
D' ==> << E D' | >> E D'
D' ==> epsilon
E ==> F E'
E' ==> + F E' | - F E'
E' ==> epsilon
F ==> G F'
F' ==> * G F' | / G F' | % G F'
F' ==> epsilon
G ==> +H | -H | ++H | --H | ~H | !H | &H
G ==> H
H ==> (A) | A T
T ==> -- | ++ | epsilon
H ==> number
出现以下推导时出现问题:
A ==> B ==> C ==> D ==> E ==> F ==> G ==> H ==> A
并且JavaCC因为间接左递归不会编译语法文件。
那么要从前面的文法中去掉这个间接左递归应该怎么做呢?
所以在我盯着这个语法看了大约半小时后,我意识到在一个特殊情况下:
H ==> A
同样的特例产生:
A ==> H
所以我重新表述了语法,使得非终结符 H
的第一个产生式规则导致左递归,而第二个产生式规则不导致任何左递归,所以语法是这样的看起来像:
H ==> A T
T ==> -- | ++ | epsilon
H ==> (A) | number
如前所述,我们将第一个产生式规则中的A
替换为H
:
H ==> H T
H ==> (A) | number
T ==> -- | ++ | epsilon
现在消除左递归就很简单了,最后的语法是这样的:
H ==> (A)H' | number H'
H' ==> T H' | epsilon
T ==> -- | ++ | epsilon