Extracción de la recursión izquierda indirecta
-
29-09-2020 - |
Pregunta
Quiero eliminar la recursión a la izquierda indirecta de estas reglas:
S-->TU,
T-->US|b,
U-->ST|a
No sé si puedo implementar el algoritmo correctamente.Mi suposición es hacerlo así:
S-->TU, T-->U'b, U'b-->U'a
es este correcto?
Solución
Es tedioso ... Espero no haber cometido un error ...
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
por sustitución de todas las posibilidades de T y u Puede eliminar los no terminales en la parte delantera de las expresiones para X, Y y S.
Otros consejos
no.El primer idioma no está vacío (por ejemplo, contiene la palabra "ba"), mientras que el segundo idioma está vacío.
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange