Вопрос

Я хочу удалить косвенную левую рекурсию из этих правил:

    S-->TU,
    T-->US|b,
    U-->ST|a
.

Я не знаю, смогу ли я правильно реализовать алгоритм.Мое предположение состоит в том, чтобы сделать это так:

S-->TU, T-->U'b, U'b-->U'a
.

Это правильно?

Это было полезно?

Решение

Утомительно ... Я надеюсь, что не ошибился ...

S->TU
T->US|b
U->ST|a

1.
S->TU
T->U(TU)|b 
U->(TU)T|a

2.
S->TU
T->aTU|(TUT)TU|b 
U->bUT|(UTU)UT|a

3. * is regex for "repeated 0 or more times"
S->TU
T->aTU|T(UTTU)*|b 
U->bUT|U(TUUT)*|a

4.
S->TU
T->aTU|aTUX|bX|b 
U->bUT|bUTY|aY|a

X->UTTUX|UTTU
Y->TUUTY|TUUT
.

Подстановка всех возможностей t и вы можете удалить несексуалы в передней части выражений для x, y и s.

Другие советы

нет.Первый язык не пустой (например, он содержит слово «BA»), а второй язык пуст.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top