LL gramáticas y recursos izquierdo

Question

¿Por qué LL (k) y LL (∞) son incompatibles con la recursión izquierda? Entiendo que un lenguaje LL (k) puede soportar la recursividad izquierda siempre que con los tokens K-sobrélave se pueda resolver cualquier ambigüedad. Pero, con una gramática LL (∞), ¿qué tipo de ambigüedades no se pueden resolver?

Answer 1

El problema que las variantes $ ll $ tienen con la recursión a la izquierda es inherente a la forma en que $ ll $ funciona: es un analizador de tipo de arriba hacia abajo, lo que significa que reemplaza a los no terminales por sus producciones.

Un analizador de $ ll $-estilo funciona de la siguiente manera. Atraviesa la entrada de izquierda a derecha de una vez. Si estamos en algún momento de la entrada, entonces sabemos que todo a la izquierda de este punto está bien. Para todo a la derecha de este punto, el analizador ha construido una 'aproximación' de lo que espera ver a continuación. Considere, por ejemplo, esta gramática:

1: $ e a e + e $
2: $ e a x $

Tenga en cuenta que la gramática no es $ ll $, pero aún podemos analizar las entradas en $ ll $-syle. En la entrada $ x+x+x $, un analizador de estilo $ ll $ puede terminar en posición $ x+ bullet x+x $. Supongamos que ha decidido que la parte izquierda, $ x+$, está bien, y para el resto de la entrada espera ver $ x+e $. Luego descubrirá que $ x+x+$ está bien, con $ e $ restante. Luego puede reemplazar este $ E $ por una producción, en particular la producción 2 anterior. Con $ x $ restante, el analizador aceptará la entrada.

El truco es decidir correctamente la producción de reemplazo para un no terminal dado. Una gramática es $ ll (k) $ si podemos hacer esto solo mirando los próximos símbolos de entrada de $ k $, y se conocen otras técnicas que son más poderosas.

Ahora considere la siguiente gramática:

1: $ a a A $
2: $ a a varepsilon $

Si un analizador $ ll $ intenta reemplazar $ A $ por una producción, tiene que decidir entre la producción 1 y 2.

Consideremos cuál sería el curso de acción adecuado si nuestro analizador fuera omnisciente. Cada vez que reemplaza el $ A $ por Production 1, 'agrega' un $ A $ a lo que espera para el aporte restante (el resto esperado va de $ A $ a $ AA $ a $ AAA $ ...),), Pero el $ A $ al principio no desaparece. Finalmente, debe elegir la producción 2, después de lo cual el $ A $ desaparece y nunca más puede agregar $ A $ s a la expectativa.

Como no hay posibilidad de igualar algunos símbolos de entrada más, el analizador debe decidir exactamente esa posición de entrada cuántas veces se debe igualar la producción 1. Esto significa que debe saber exactamente cuántas veces en nuestro caso, el $ A $ aparecerá en el resto de la entrada en este momento.

Sin embargo, $ ll (k) $ puede ver solo $ k $ símbolos por delante. Esto significa que si la producción 1 debe elegirse más de $ k $ veces, el analizador no puede "ver" esto y, por lo tanto, está condenado a fallar. $ Ll (*) $ es mejor en análisis que $ ll (k) $, porque puede ver arbitrariamente muy por delante en la entrada, pero el detalle crucial (que no siempre se menciona) es que este lookhead es regular.

Para imaginar lo que sucede, puede ver el algoritmo de la siguiente manera: cuando tiene que decidir qué producción tomar, inicia una máquina de estado finito (un DFA, que es equivalente en el poder de las expresiones regulares) y permite que esta máquina mire la resto de la entrada. Esta máquina puede informar 'usar esta producción'. Sin embargo, esta máquina está severamente limitada en lo que puede hacer. Aunque es estrictamente mejor que mirar solo los próximos símbolos de $ K $, no puede, por ejemplo, "contar", lo que significa que no puede ayudar en la situación anterior.

Incluso si ibas a "hackear" en alguna función de conteo en este autómata finito, entonces todavía hay gramáticas recursivas a la izquierda para las cuales realmente necesitas más potencia. Por ejemplo, para esta gramática:

$ A a AB $
$ A a varepsilon $
$ B a (b) $
$ B a varepsilon $

Tendría que hacer coincidir con las 'torres' de aparatos ortopédicos, que es algo que un autómata finito no puede hacer. Peor aún:

$ A a bcade $
$ A a a '$
$ A ' a a' de $
$ A ' a Varepsilon $
$ B a a b a mid b b b mid aa mid bb $
$ C a c c c mid d c d mid cc mid dd $
$ D a e d e mid f d f mid ee mid ff $
$ E to g e g mid h e h mid gg mid hh $

es una gramática totalmente horrible, para la cual estoy bastante seguro de que no se conoce el algoritmo de análisis de tiempo lineal y todos los algoritmos de análisis generales conocidos toman un tiempo cuadrático. Peor aún, cualquier gramática que describa este idioma sea necesariamente recursiva a la izquierda. Sin embargo, la gramática sigue siendo inequívoca. Necesita un analizador hecho a mano para analizar estos monstruos en tiempo lineal.