Supprimer la récursion gauche indirecte

Question

Je veux supprimer la récursion gauche indirecte de ces règles:

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

Je ne sais pas si je peux mettre en œuvre l'algorithme correctement.Mon hypothèse est de le faire comme ça:

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

est-ce correct?

Answer 1

C'est fastidieux ... j'espère que je n'ai pas commis une erreur ...

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

Par substitution de toutes les possibilités de T et U, vous pouvez retirer les non-terminaux à l'avant des expressions pour X, Y et S.

Answer 2

non.La première langue n'est pas vide (par exemple, il contient le mot "BA"), tandis que la deuxième langue est vide.