LL(1)
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la
versión revisada el 3 de julio de 2020; las comprobaciones requieren
5 ediciones .
LL(1) - Analizador LL , algoritmo de análisis de arriba hacia abajo . El número 1 dice que solo se necesita un token para definir la ruta de análisis .
Fácil de escribir a mano sin el uso de generadores automáticos. Se utiliza para analizar código en una serie de lenguajes de programación como Pascal y Python (antes de 3.8 [1] ).
Tiene una ejecución muy rápida y tiene un mensaje de error característico como "se esperaba tal o cual carácter".
Caracteres de la guía de reglas
Para cada no terminal A en la gramática , se genera un conjunto de terminales First(A), definido de la siguiente manera:
- si la gramática tiene una regla con una A en el lado izquierdo y un lado derecho que comienza con una terminal, entonces esa terminal está en Primera (A)
- si la gramática tiene una regla con una A en el lado izquierdo y un lado derecho que comienza con un no terminal (denotado B), entonces First(B) está estrictamente incluido en First(A)
- no se incluyen otros terminales en First(A)
Para cada regla se genera un conjunto de caracteres guía , definidos de la siguiente manera:
- si el lado derecho de la regla comienza con una terminal, entonces el conjunto de caracteres guía consta de esa terminal
- de lo contrario, el lado derecho comienza con una A no terminal, entonces el conjunto de caracteres principales es Primero (A)
Es posible generalizar estas definiciones para el caso en que existan reglas de la forma A → null.
Está claro que First(A) es la unión de los conjuntos de símbolos principales para todas las reglas con A en el lado izquierdo.
Una gramática es analizable en LL(1) si, para cualquier par de reglas con el mismo lado izquierdo, el conjunto de caracteres guía no se cruzan.
Para saber si una gramática es analizada por LL(1) o no en general, es conveniente utilizar el criterio de LL(1)-grammars [2] .
Descripción del analizador
Se utiliza la pila, donde se ubican los flujos de números de terminales y no terminales, de entrada (terminales) y de salida (número de reglas).
Primero, E, el símbolo inicial de la gramática, se coloca en la pila.
Luego, para cada carácter nuevo desde el flujo de entrada hasta que finalice:
- si hay un terminal en la parte superior de la pila y coincide con el símbolo del flujo de entrada, entonces a) saca el terminal de la pila yb) consume el símbolo del flujo de entrada.
- si hay un terminal en la parte superior de la pila y no coincide con el símbolo del flujo de entrada, entonces se trata de un error de sintaxis "se esperaba tal y tal símbolo" (el que está en la pila).
- de lo contrario, hay un no terminal en la parte superior de la pila, lo denotamos con A. Se buscan todas las reglas con él en el lado izquierdo, para cada regla, se buscan conjuntos de símbolos de dirección para encontrar el símbolo de la entrada corriente; no puede aparecer allí más de una vez, de lo contrario, la gramática no se puede analizar en LL(1).
- si se encuentra el símbolo, entonces se aplica esta regla: el número de la regla se envía al flujo de salida, se extrae un símbolo de la pila (esto es A) y en su lugar se inserta todo el lado derecho de la regla, el El símbolo más a la izquierda del lado derecho es el último. El carácter de flujo de entrada no se consume.
- de lo contrario, el símbolo no se encontró en absoluto. Entonces, si hay una regla de la forma A → null , entonces A se empuja desde la parte superior de la pila. El carácter de flujo de entrada no se consume.
- de lo contrario, se trata de un error de sintaxis, el mensaje se puede mostrar como "uno de los esperados" seguido de una lista del conjunto Primero (A) (para los no terminales más importantes del idioma, por ejemplo, para los no-terminales). terminal "expresión", puede formular el error en términos de nombres no terminales).
Idiomas
Véase también
Notas
- ↑ PEP 617 - Nuevo analizador PEG para CPython | peps.python.org . peps.python.org . Consultado el 15 de julio de 2022. Archivado desde el original el 15 de julio de 2022. (indefinido)
- ↑ Kozlov Sergey Valerievich, Svetlakov Alexey Vladimirovich. Acerca de LL(1)-GRAMARAS, ALGORITMOS SOBRE ELLAS Y MÉTODOS DE ANÁLISIS EN PROGRAMACIÓN // International Journal of Open Information Technologies. - 2022. - Vol. 10 , núm. 3 . — P. 30–38 . — ISSN 2307-8162 . Archivado desde el original el 18 de mayo de 2022.
Literatura
- Grune, D. and van Reeuwijk, K. and Bal, HE and Jacobs, CJH and Langendoen, K. Modern Compiler Design. - Springer, 2012. - 843 págs. — ISBN 9781461446996 .
- Mogensen, T. Æ. Introducción al diseño de compiladores. - Springer, 2011. - 225 págs. — ISBN 9780857298294 .
- Mozgovoy, M. Algoritmos, lenguajes, autómatas y compiladores: un enfoque práctico. - Jones & Bartlett Learning, 2009. - 345 p. — ISBN 9780763782948 .
- Kozlov S. V., Svetlakov A. V. Acerca de las gramáticas LL(1), algoritmos sobre ellas y métodos de su análisis en programación — International Journal of Open Information Technologies. - 2022. - T. 10. - Nº 3. - S. 30-38. — URL: https://cyberleninka.ru/article/n/o-ll-1-grammatikah-algoritmah-na-nih-i-metodah-ih-analiza-v-programmirovanii .
Enlaces