Izquierda-Factoring una gramática en LL (1)

Question

I tiene una tarea donde necesito para convertir una gramática en LL (1). Ya he quitado la recursión por la izquierda, pero estoy teniendo problemas para hacer la factorización-izquierda. Todos los ejemplos que he encontrado son simples, y algo parecido a esto:

A -> aX | aY
se convierte en:
A -> aZ
Z -> X | Y

lo entiendo. Sin embargo, mi gramática se parece más a esto:

X -> aE | IXE | (X)E
E -> IE | BXE | ϵ
I -> ++ | --
B -> + | - | ϵ

No estoy seguro de cómo aplicar el ejemplo más sencillo de esto. He estado intentando durante al menos un par de horas y he perdido la cuenta de todas las cosas que he probado. En general, mis intentos han visto algo como esto:

X  -> X' | IXE
X' -> aE | (X)E
E  -> IE | BIX'E | BX'E | ϵ

Y entonces trato de convertir las reglas de correo en los que tienen sólo una producción a partir de + o -:

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> IE | B'IX'E | IX'E | B'X'E | X'E | ϵ

Y entonces ...

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> +P | -M | ϵ
P  -> +E | IX'E | +X'E | X'E
M  -> -E | IX'E | -X'E | X'E

Y así sucesivamente. Pero termino continuamente con una gran cantidad de no terminales adicionales, y algunas muy largas producciones / cadenas de producción, sin tener que factorizar izquierda. No estoy seguro de cómo abordar este - Me parece que no puede eliminar algunos no terminal que tiene múltiples producciones que comienzan con un + y un -.

Answer 1

Vamos a echar un vistazo a su gramática:

$ \ qquad \ begin {align} X & \ AE \ mediados IXE \ mid (X) E \\ E & \ IE \ mediados BXE \ mid \ varepsilon \\ I & \ a \ text {++} \ mid \ text {-} \\ B & \ a \ text {+} \ mid \ text {-} \ mid \ varepsilon \ End {align} $

Tenga en cuenta que $ X $ no necesita izquierdo factoring: todas las reglas tienen PRIMERA sets¹ disjuntos. Si desea hacer esto obvio, se puede eliminar $ I $ e integrados que:

$ \ qquad \ begin {align} X & \ AE \ mid \ text {++} XE \ mid \ text {-} XE \ mid (X) E \\ E & \ a \ text {++} E \ mid \ text {-} E \ mediados BXE \ mid \ varepsilon \\ B & \ a \ text {+} \ mid \ text {-} \ mid \ varepsilon \ End {align} $

Del mismo modo, podemos inline $ B $:

$ \ qquad \ begin {align} X & \ AE \ mid \ text {++} XE \ mid \ text {-} XE \ mid (X) E \\ E & \ a \ text {++} E \ mid \ text {-} E \ mid \ text {+} XE \ mid \ text {-} XE \ mediados XE \ mid \ varepsilon \ End {align} $

Ahora vemos que en realidad tenemos que hacer la factorización-izquierda en $ E $: tenemos conflictos obvios, y obtenemos conflictos adicionales a través XE $ $. Por lo tanto, vamos a inline $ X $ una vez en XE $ $:

$ \ qquad \ begin {align} X & \ AE \ mid \ text {++} XE \ mid \ text {-} XE \ mid (X) E \\ E & \ a \ text {++} E \ mid \ text {-} E \ mid \ text {+} XE \ mid \ text {-} XE \ mediados AEE \ mid \ text {++} XEE \ mediados \ text {-} XEE \ mid (X) EE \ mid \ varepsilon \ End {align} $

Y ahora podemos factor de izquierda con tanta facilidad como en el ejemplo:

$ \ qquad \ begin {align} X & \ AE \ mid \ text {++} XE \ mid \ text {-} XE \ mid (X) E \\ E & \ a \ text {+} P \ mid \ text {-} M \ mediados AEE \ mid (X) EE \ mid \ varepsilon \\ P & \ a \ text {+} E \ mediados XE \ mid \ text {+} \\ XEE M & \ a \ text {-} E \ mediados XE \ mid \ text {-} XEE \ End {align} $

Por ahora podemos ver que no estamos llegando a ningún lado: por factorización de distancia $ \ text {+} $ o $ \ text {-} $ de las alternativas, que desenterrar otra $ X $ que a su vez tiene tanto $ \ texto {+} $ y $ \ text {-}. $ en su primer conjunto

Así que vamos a echar un vistazo a su idioma. Via

$ \ qquad \ displaystyle X \ Rightarrow aE \ Rightarrow ^ * ^ n aI E \ Rightarrow aI ^ nBXE $

y

$ \ qquad \ displaystyle X \ Rightarrow aE \ Rightarrow ^ * ^ n aI E \ Rightarrow aI ^ NIE $

tiene arbitrariamente larga prefijos de la forma $ + ^ + $ que final diferente , semántico-sabia: un (1) analizador LL no puede decidir si en un dado (siguiente) $ \ text {+} $ pertenece a un par - lo que significaría la elección alternativa $ $ IE - o viene solo -. lo que significaría la elección de $ BXE $

En consecuencia, no se parece a su idioma se puede expresar por cualquier LL (1) gramática, por lo que tratar de convertir a la suya en uno es inútil.

Es aún peor: como $ BXE \ Rightarrow BIXEE \ Rightarrow ^ * BI ^ n X E ^ n E $, no se puede decidir para elegir $ BXE $ con cualquier finita de preanálisis. Esto no es una prueba formal, pero sugiere fuertemente que la lengua no es ni siquiera LL.

Si se piensa en lo que está haciendo - mezclar la notación polaca con operadores unitarios - que no es muy sorprendente que el análisis debería ser difícil. Básicamente, usted tiene que contar desde la izquierda y desde la derecha para identificar incluso una sola $ B $ - $ \ text {+} $ en una larga cadena de $ \ text {+} $. Si pienso en múltiples $ B $ - $ \ text {+} $ en una cadena, no estoy siquiera seguro de la lengua (con dos semánticamente diferente , pero sintácticamente igual a $ \ text {+} $ ) se puede analizar de manera determinista (sin dar marcha atrás) en absoluto.

---

1. Eso sería los juegos de terminales que pueden venir por primera vez en las derivaciones de una alternativa de gobierno / no terminal.