Analizador LL

AjustarCompartirImprimirCitar

En informática, un parser LL (derivación de izquierda a derecha, más a la izquierda) es un analizador de arriba hacia abajo para un lenguaje restringido libre de contexto. Analiza la entrada de Lde izquierda a derecha, realizando la derivación más a la izquierda de la oración.

Un analizador LL se denomina analizador LL(k) si utiliza tokens k de anticipación al analizar una oración. Una gramática se denomina gramática LL(k) si se puede construir un analizador LL(k) a partir de ella. Un lenguaje formal se llama lenguaje LL(k) si tiene una gramática LL(k). El conjunto de lenguas LL(k) está propiamente contenido en el de lenguas LL(k+1), para cada k ≥ 0. A El corolario de esto es que no todos los lenguajes libres de contexto pueden ser reconocidos por un analizador LL(k).

Un analizador LL se llama LL-regular (LLR) si analiza un lenguaje LL-regular. La clase de gramáticas LLR contiene cada gramática LL(k) para cada k. Para cada gramática LLR existe un analizador LLR que analiza la gramática en tiempo lineal.

Dos tipos de analizadores de valores atípicos nomenclativos son LL(*) y LL(finito). Un analizador se denomina LL(*)/LL(finito) si utiliza la estrategia de análisis LL(*)/LL(finito). Los analizadores LL(*) y LL(finitos) son funcionalmente más parecidos a los analizadores PEG. Un analizador LL (finito) puede analizar una gramática LL (k) arbitraria de manera óptima en la cantidad de búsqueda anticipada y comparaciones anticipadas. La clase de gramáticas analizables por la estrategia LL(*) abarca algunos lenguajes sensibles al contexto debido al uso de predicados sintácticos y semánticos y no ha sido identificada. Se ha sugerido que los analizadores LL(*) se consideran mejor como analizadores TDPL. Contra el concepto erróneo popular, los analizadores LL(*) no son LLR en general, y están garantizados por la construcción para funcionar peor en promedio (superlineal frente a tiempo lineal) y mucho peor en el peor de los casos (exponencial frente a tiempo lineal).

Las gramáticas LL, en particular las gramáticas LL(1), son de gran interés práctico, ya que los analizadores para estas gramáticas son fáciles de construir, y muchos lenguajes informáticos están diseñados para ser LL(1) por este motivo. Los analizadores LL pueden estar basados en tablas, es decir, similares a los analizadores LR, pero las gramáticas LL también pueden ser analizadas por analizadores descendentes recursivos. Según Waite y Goos (1984), las gramáticas LL(k) fueron introducidas por Stearns y Lewis (1969).

Resumen

Para una gramática dada sin contexto, el analizador intenta encontrar la derivación más izquierda. Dado un ejemplo de gramática ${displaystyle G.$ :

${displaystyle Sto E}$
${displaystyle Eto (E+E)}$
${displaystyle Eto i}$

la derivación más izquierda para ${displaystyle w=(i+i)+i)}$ es:

{displaystyle S {overset {(1)}{ Rightarrow {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {}} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Principi}} {fncipi}}} {fncipi}}}fncipi}}}}}}}}}}}fncipi} {i} {fncipi}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}i}

Por lo general, existen múltiples posibilidades al seleccionar una regla para expandir el no terminal más a la izquierda. En el paso 2 del ejemplo anterior, el analizador debe elegir si aplicar la regla 2 o la regla 3:

{displaystyle S {fnuncio {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} Rightarrow ¿Qué?

Para ser eficiente, el analizador debe ser capaz de hacer esta elección determinísticamente cuando sea posible, sin retroceder. Para algunas gramáticas, puede hacer esto espiando en la entrada sin leer (sin leer). En nuestro ejemplo, si el analizador sabe que el siguiente símbolo no leído es ${displaystyle (}$ la única regla correcta que se puede utilizar es 2.

Generalmente, un ${displaystyle LL(k)}$ parser puede mirar hacia adelante ${displaystyle k}$ símbolos. Sin embargo, dada una gramática, el problema de determinar si existe ${displaystyle LL(k)}$ parser para algunos ${displaystyle k}$ que lo reconoce es indecible. Para cada uno ${displaystyle k}$ , hay un idioma que no puede ser reconocido por un ${displaystyle LL(k)}$ parser, pero puede ser por un ${displaystyle LL(k+1)}$ .

Podemos usar el análisis anterior para dar la siguiente definición formal:

Vamos ${displaystyle G.$ ser una gramática sin contexto y ${displaystyle kgeq 1}$ . Decimos eso ${displaystyle G.$ es ${displaystyle LL(k)}$ , si y sólo si para cualquier dos derivaciones más izquierda:

${displaystyle S\Rightarrow cdots Rightarrow wAalpha rightarrow cdots rightarrow wbeta alpha rightarrow cdots Rightarrow wu}$
${displaystyle S\Rightarrowcdots Rightarrow wAalpha Rightarrow cdots \Rightarrow wgamma alpha Rightarrow cdots Rightarrow wv}$

la siguiente condición sostiene: el prefijo de la cadena ${displaystyle u}$ de longitud ${displaystyle k}$ iguala el prefijo de la cadena ${displaystyle v}$ de longitud ${displaystyle k}$ implicación ${displaystyle beta =gamma }$ .

En esta definición, ${displaystyle S.$ es el símbolo de inicio y ${displaystyle A}$ cualquier no-terminal. El aporte ya derivado ${displaystyle w}$ , y aún sin leer ${displaystyle u}$ y ${displaystyle v}$ son cadenas de terminales. Las letras griegas ${displaystyle alpha }$ , ${displaystyle beta }$ y ${displaystyle gamma }$ representan cualquier cadena de terminales y no terminales (posiblemente vacías). La longitud del prefijo corresponde al tamaño del búfer de la cara, y la definición dice que este búfer es suficiente para distinguir entre dos derivaciones de diferentes palabras.

Analizadora

(feminine)

El ${displaystyle LL(k)}$ parser es un autómata determinista con la capacidad de mirar en el siguiente ${displaystyle k}$ símbolos de entrada sin lectura. Esta capacidad de puerco puede emularse almacenando el contenido del amortiguador en el espacio estatal finito, ya que tanto el búfer como el alfabeto de entrada son finitos en tamaño. Como resultado, esto no hace que el autómata sea más poderoso, pero es una abstracción conveniente.

El alfabeto es ${displaystyle Gamma =Ncup Sigma }$ , donde:

${displaystyle N}$ es el conjunto de no-terminales;
${displaystyle Sigma }$ el conjunto de símbolos terminales (input) con un símbolo especial final de entrada (EOI) ${displaystyle$}$ .

La pila de parser contiene inicialmente el símbolo inicial por encima de la EOI: ${displaystyle [ S\\\$00}$ . Durante la operación, el analizador repetidamente reemplaza el símbolo ${displaystyle X}$ arriba de la pila:

con algunos ${displaystyle alpha }$ , si ${displaystyle Xin N}$ y hay una regla ${displaystyle Xto alpha }$ ;
con ${displaystyle epsilon }$ (en algunas notaciones ${displaystyle lambda }$ ), i.e. ${displaystyle X}$ está saltado de la pila, si ${displaystyle Xin Sigma }$ . En este caso, un símbolo de entrada ${displaystyle x}$ es leído y si ${displaystyle xneq X}$ , el analizador rechaza la entrada.

Si el último símbolo que se eliminó de la pila es el EOI, el análisis es exitoso; el autómata acepta a través de una pila vacía.

Los estados y la función de transición no se dan explícitamente; se especifican (generan) usando una tabla de análisis más conveniente. La tabla proporciona el siguiente mapeo:

fila: símbolo superior de la mesa ${displaystyle X}$
columna: ${displaystyle TENIDO TERMINADO }$ contenidos de amortiguación
celda: número de regla para ${displaystyle Xto alpha }$ o ${displaystyle epsilon }$

Si el analizador no puede realizar una transición válida, la entrada se rechaza (celdas vacías). Para hacer la tabla más compacta, solo se muestran las filas que no son terminales, ya que la acción es la misma para las terminales.

Ejemplo concreto

Configurar

Para explicar el funcionamiento de un analizador LL(1), consideraremos la siguiente gramática pequeña LL(1):

S → F
S → (S + F)
F → a

y analice la siguiente entrada:

(a + a)

Una tabla de análisis LL(1) para una gramática tiene una fila para cada uno de los no terminales y una columna para cada terminal (incluido el terminal especial, representado aquí como $, que se usa para indicar el final del flujo de entrada).

Cada celda de la tabla puede señalar como máximo una regla de la gramática (identificada por su número). Por ejemplo, en la tabla de análisis de la gramática anterior, la celda para el no terminal 'S' y terminal '(' apunta a la regla número 2:

	()	)	a	+	$
S	2	—	1	—	—
F	—	—	3	—	—

El algoritmo para construir una tabla de análisis se describe en una sección posterior, pero primero veamos cómo el analizador usa la tabla de análisis para procesar su entrada.

Procedimiento de análisis

En cada paso, el analizador lee el siguiente símbolo disponible del flujo de entrada y el símbolo superior de la pila. Si el símbolo de entrada y el símbolo de la parte superior de la pila coinciden, el analizador los descarta a ambos, dejando solo los símbolos no coincidentes en el flujo de entrada y en la pila.

Por lo tanto, en su primer paso, el analizador lee el símbolo de entrada '(' y el símbolo de la parte superior de la pila 'S'. La tabla de análisis instrucción proviene de la columna encabezada por el símbolo de entrada '(' y la fila encabezada por el símbolo de la parte superior de la pila 'S'; esta celda contiene &# 39;2', que indica al analizador que aplique la regla (2). El analizador tiene que reescribir 'S' a '( S + F )' en la pila quitando 'S' de la pila y presionando ')', 'F', '+', 'S', '(' en la pila, y esto escribe la regla número 2 en la salida. La pila entonces se convierte en:

[ (), S, +, F, ), $ ]

En el segundo paso, el analizador elimina el '(' de su flujo de entrada y de su pila, ya que ahora coinciden. La pila ahora se convierte en:

[S, +, F, ), $ ]

Ahora el analizador tiene un 'a' en su flujo de entrada y un 'S' como su parte superior de la pila. La tabla de análisis le indica que aplique la regla (1) de la gramática y escriba la regla número 1 en el flujo de salida. La pila se convierte en:

[F, +, F, ), $ ]

El analizador ahora tiene un 'a' en su flujo de entrada y un 'F' como su parte superior de la pila. La tabla de análisis le indica que aplique la regla (3) de la gramática y escriba la regla número 3 en el flujo de salida. La pila se convierte en:

[ a, +, F, ), $ ]

El analizador ahora tiene un 'a' en el flujo de entrada y un 'a' en la parte superior de la pila. Como son iguales, lo elimina del flujo de entrada y lo extrae de la parte superior de la pila. El analizador entonces tiene un '+' en el flujo de entrada y '+' está en la parte superior de la pila, lo que significa, como con 'a', se extrae de la pila y se elimina del flujo de entrada. Esto resulta en:

[F, ), $ ]

En los próximos tres pasos, el analizador reemplazará 'F' en la pila por 'a', escriba la regla número 3 a la secuencia de salida y elimine 'a' y ')' tanto de la pila como de la secuencia de entrada. Por lo tanto, el analizador termina con '$' tanto en su pila como en su flujo de entrada.

En este caso, el analizador informará que ha aceptado la cadena de entrada y escribirá la siguiente lista de números de regla en el flujo de salida:

[ 2, 1, 3, 3]

Esta es de hecho una lista de reglas para una derivación más a la izquierda de la cadena de entrada, que es:

S → () S + F ) → () F + F ) → (a + F ) → (a + a)

Implementación del analizador en C++

A continuación se muestra una implementación en C++ de un analizador LL basado en tablas para el lenguaje de ejemplo:

#include ■iostream#include Identificado#include - No.enum Símbolos {}// los símbolos:// símbolos terminales:TS_L_PARENS,//TS_R_PARENS,//)TS_A,//aTS_PLUS,// +TS_EOS,// $, en este caso corresponde a '

Contenido relacionado

Más resultados...