дизайн компилятора - нужна помощь в устранении косвенной левой рекурсии из 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 не будет компилировать файл грамматики из-за косвенной левой рекурсии.

Итак, какие шаги нужно сделать, чтобы устранить эту косвенную левую рекурсию из предыдущей грамматики?


parsing compiler-construction left-recursion context-free-grammar
person Eyad Mohammed Osama    schedule 21.12.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Итак, после того, как я изучал эту грамматику около получаса, я понял, что в особом случае:

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
person Eyad Mohammed Osama    schedule 22.12.2018