Rozwiązywanie lewostronnej rekurencji w mojej gramatyce - parsowanie, rekurencja, kompilacja-konstrukcja, gramatyka, rekursja lewostronna

Moja gramatyka ma przypadek lewostronnej rekurencji w szóstej regule produkcji.

Rozwiązałem to, zastępując Regułę 6 i 7 w następujący sposób:

Nie mogłem znaleźć żadnych pośrednich lewych rekurencji w tej gramatyce.

Jedyne, co mnie niepokoi, to ostateczna reguła produkcyjna, która ma terminal otoczony dwoma nieterminalami.

Moje dwa pytania to:

• Czy moja rozstrzygnięta lewa rekurencja jest poprawna?
• Czy ostateczna reguła produkcji jest lewą rekurencją? Nie jestem pewien jak to zrobić traktuj ten szczególny przypadek.

Odpowiedzi:

Tak, twoja rozdzielczość jest poprawna. Możesz usunąć regułę epsilon, aby ułatwić korzystanie, ale akceptowane ciągi są poprawne.

X -> -
X -> -Z
Z -> +
Z -> +Z
Z -> X + Y
... and Y is of the form 0* 1 (no syntax collisions)

W ramach czeku zauważ, że ty mógłby teraz zastąp tę ostatnią regułę dwiema nowymi regułami, po jednej dla każdego rozszerzenia X:

Z -> -  + Y
Z -> -Z + Y

To całkowicie usuwa X z reguł Z i każda reguła Z zaczynałaby się od terminala.

Nie, twoja ostateczna reguła produkcji nie jest już lewostronna. X musi teraz przekształcić się w ciąg rozpoczynający się od nieterminala.

Muszę jednak przyznać, że jestem ciekawy, jak używa tego języka. :-)