Analizador LL - LL parser

En informática , un analizador LL (derivación de izquierda a derecha, más a la izquierda) es un analizador de arriba hacia abajo para un lenguaje restringido sin contexto . Se analiza el aporte de L EFT a derecha, realizando L derivación eftmost de la frase.

Un analizador LL se denomina analizador LL ( k ) si utiliza k tokens de búsqueda anticipada al analizar una oración. Una gramática se denomina gramática LL ( k ) si se puede construir un analizador sintáctico LL ( k ) a partir de ella. Un lenguaje formal se llama lenguaje LL ( k ) si tiene una gramática LL ( k ). El conjunto de lenguajes LL ( k ) está contenido correctamente en el de los lenguajes LL ( k +1), para cada k ≥ 0. Un 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 si analiza con precisión la clase de lenguajes LL-regulares . Las gramáticas LLR son un superconjunto adecuado de gramáticas LL (k) para cualquier k. Para cada gramática LLR existe un analizador de LLR que analiza la gramática en tiempo lineal.

Dos tipos de analizador de valores atípicos nomenclativos son LL (*) y LL (finito). Un analizador se llama LL (*) / LL (finito) si utiliza la estrategia de análisis LL (*) / LL (finito). Los analizadores sintácticos LL (*) y LL (finitos) son funcionalmente más parecidos a los analizadores sintácticos PEG . Un analizador LL (finito) puede analizar una gramática LL (k) arbitraria de manera óptima en la cantidad de comparaciones anticipadas y anticipadas. La clase de gramáticas que se pueden analizar mediante la estrategia LL (*) abarca algunos lenguajes sensibles al contexto debido al uso de predicados sintácticos y semánticos y no se ha identificado. Se ha sugerido que los analizadores sintácticos LL (*) se consideran mejor analizadores TDPL . En contra de la idea errónea popular, los analizadores de LL (*) no son LLR en general, y la construcción garantiza que su rendimiento sea peor en promedio (super-lineal contra tiempo lineal) y mucho peor en el peor de los casos (exponencial contra tiempo lineal).

Las gramáticas LL, particularmente las gramáticas LL (1), son de gran interés práctico, ya que los analizadores sintácticos para estas gramáticas son fáciles de construir, y muchos lenguajes de computadora están diseñados para ser LL (1) por esta razón. Los analizadores LL son analizadores basados en tablas, similares a los analizadores LR . Las gramáticas LL también se pueden analizar mediante analizadores sintácticos descendentes recursivos . Según Waite y Goos (1984), las gramáticas LL ( k ) fueron introducidas por Stearns y Lewis (1969).

Visión general

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

${\ Displaystyle S \ a E}$
${\ Displaystyle E \ a (E + E)}$
${\ Displaystyle E \ a i}$

la derivación más a la izquierda para es: ${\ Displaystyle w = ((yo + yo) + yo)}$

{\ Displaystyle S \ {\ overset {(1)} {\ Rightarrow}} \ E \ {\ overset {(2)} {\ Rightarrow}} \ (E + E) \ {\ overset {(2)} { \ Rightarrow}} \ ((E + E) + E) \ {\ overset {(3)} {\ Rightarrow}} \ ((i + E) + E) \ {\ overset {(3)} {\ Rightarrow }} \ ((i + i) + E) \ {\ overset {(3)} {\ Rightarrow}} \ ((i + i) + i)}

Generalmente, 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 aplica la regla 2 o la regla 3:

{\ Displaystyle S \ {\ overset {(1)} {\ Rightarrow}} \ E \ {\ overset {(?)} {\ Rightarrow}} \?}

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

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

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

Sea una gramática libre de contexto y . Decimos que es , si y solo si para dos derivaciones más a la izquierda: ${\ Displaystyle G}$ ${\ Displaystyle k \ geq 1}$ ${\ Displaystyle G}$ ${\ Displaystyle LL (k)}$

${\ Displaystyle S \ \ Rightarrow \ \ cdots \ \ Rightarrow \ wA \ alpha \ \ Rightarrow \ \ cdots \ \ Rightarrow \ w \ beta \ alpha \ \ Rightarrow \ \ cdots \ \ Rightarrow \ wu}$
${\ Displaystyle S \ \ Rightarrow \ \ cdots \ \ Rightarrow \ wA \ alpha \ \ Rightarrow \ \ cdots \ \ Rightarrow \ w \ gamma \ alpha \ \ Rightarrow \ \ cdots \ \ Rightarrow \ wv}$

Se cumple la siguiente condición: el prefijo de la cadena de longitud es igual al prefijo de la cadena de longitud que implica . ${\ Displaystyle u}$ ${\ Displaystyle k}$ ${\ Displaystyle v}$ ${\ Displaystyle k}$ ${\ Displaystyle \ beta \ = \ \ gamma}$

En esta definición, es el símbolo de inicio y cualquier no terminal. Los ya derivados de entrada , y sin embargo no leídos y cadenas son de terminales. Las letras griegas , y representan cualquier cadena de ambas terminales y no terminales (posiblemente vacía). La longitud del prefijo corresponde al tamaño del búfer de búsqueda anticipada, y la definición dice que este búfer es suficiente para distinguir entre dos derivaciones de palabras diferentes. ${\ Displaystyle S}$ ${\ Displaystyle A}$ ${\ Displaystyle w}$ ${\ Displaystyle u}$ ${\ Displaystyle v}$ ${\ Displaystyle \ alpha}$ ${\ Displaystyle \ beta}$ ${\ Displaystyle \ gamma}$

Analizador

El analizador es un autómata pushdown determinista con la capacidad de mirar los siguientes símbolos de entrada sin leer. Esta capacidad de visualización se puede emular almacenando el contenido del búfer de búsqueda anticipada en el espacio de estado finito, ya que tanto el búfer como el alfabeto de entrada tienen un tamaño finito. Como resultado, esto no hace que el autómata sea más poderoso, pero es una abstracción conveniente. ${\ Displaystyle LL (k)}$ ${\ Displaystyle k}$

El alfabeto de la pila es , donde: ${\ Displaystyle \ Gamma = N \ cup \ Sigma}$

${\ Displaystyle N}$ es el conjunto de no terminales;
${\ Displaystyle \ Sigma}$ el conjunto de símbolos de terminal (entrada) con un símbolo especial de fin de entrada (EOI) . ${\ Displaystyle \ $}$

La pila del analizador contiene inicialmente el símbolo de partida por encima de la EOI: . Durante la operación, el analizador reemplaza repetidamente el símbolo en la parte superior de la pila: ${\ Displaystyle [\ S \ \ $ \]}$ ${\ Displaystyle X}$

con algunos , si y hay una regla ; ${\ Displaystyle \ alpha}$ ${\ Displaystyle X \ in N}$ ${\ Displaystyle X \ to \ alpha}$
con (en algunas notaciones ), es decir, se saca de la pila, si . En este caso, se lee un símbolo de entrada y si el analizador rechaza la entrada. ${\ Displaystyle \ epsilon}$ ${\ Displaystyle \ lambda}$ ${\ Displaystyle X}$ ${\ Displaystyle X \ in \ Sigma}$ ${\ Displaystyle x}$ ${\ Displaystyle x \ neq X}$

Si el último símbolo que se eliminará de la pila es el EOI, el análisis se realiza correctamente; 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) utilizando una tabla de análisis más conveniente en su lugar. La tabla proporciona el siguiente mapeo:

fila: símbolo de la parte superior de la pila ${\ Displaystyle X}$
columna: contenido del búfer anticipado ${\ Displaystyle | w | \ leq k}$
celda: número de regla para o ${\ Displaystyle X \ to \ alpha}$ ${\ Displaystyle \ epsilon}$

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

Ejemplo concreto

Configurar

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

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

y analizar la siguiente entrada:

(a + a)

Una tabla de análisis sintáctico 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 utiliza para indicar el final del flujo de entrada).

Cada celda de la tabla puede apuntar como máximo a 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 la 'S' no terminal y la terminal '(' apunta a la regla número 2:

	(	)	a	+	PS
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 instrucción de la tabla de análisis sintáctico proviene de la columna encabezada por el símbolo de entrada ' ( ' y la fila encabezada por la pila- símbolo superior 'S'; esta celda contiene '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 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 una ' a' en su flujo de entrada y una 'S' en la parte superior de su 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 una ' a' en su flujo de entrada y una 'F' en la parte superior de su 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 una ' a' en el flujo de entrada y una 'a' en la parte superior de su pila. Debido a que son iguales, lo elimina del flujo de entrada y lo saca de la parte superior de la pila. El analizador luego tiene un ' +' en el flujo de entrada y '+' está en la parte superior de la pila, lo que significa que, como con 'a', se extrae de la pila y se elimina del flujo de entrada. Esto resulta en:

[ F, ), $ ]

En los siguientes tres pasos, el analizador reemplazará ' F' en la pila por ' a' , escribirá la regla número 3 en el flujo de salida y eliminará la ' a' y ' )' tanto de la pila como del flujo de entrada. Por 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]

De hecho, esta es 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 <map>
#include <stack>

enum Symbols {
	// the symbols:
	// Terminal symbols:
	TS_L_PARENS,	// (
	TS_R_PARENS,	// )
	TS_A,		// a
	TS_PLUS,	// +
	TS_EOS,		// $, in this case corresponds to '\0'
	TS_INVALID,	// invalid token

	// Non-terminal symbols:
	NTS_S,		// S
	NTS_F		// F
};

/*
Converts a valid token to the corresponding terminal symbol
*/
Symbols lexer(char c)
{
	switch (c)
	{
		case '(':  return TS_L_PARENS;
		case ')':  return TS_R_PARENS;
		case 'a':  return TS_A;
		case '+':  return TS_PLUS;
		case '\0': return TS_EOS; // end of stack: the $ terminal symbol
		default:   return TS_INVALID;
	}
}

int main(int argc, char **argv)
{
	using namespace std;

	if (argc < 2)
	{
		cout << "usage:\n\tll '(a+a)'" << endl;
		return 0;
	}

	// LL parser table, maps < non-terminal, terminal> pair to action
	map< Symbols, map<Symbols, int> > table;
	stack<Symbols>	ss;	// symbol stack
	char *p;	// input buffer

	// initialize the symbols stack
	ss.push(TS_EOS);	// terminal, $
	ss.push(NTS_S);		// non-terminal, S

	// initialize the symbol stream cursor
	p = &argv[1][0];

	// set up the parsing table
	table[NTS_S][TS_L_PARENS] = 2;
	table[NTS_S][TS_A] = 1;
	table[NTS_F][TS_A] = 3;

	while (ss.size() > 0)
	{
		if (lexer(*p) == ss.top())
		{
			cout << "Matched symbols: " << lexer(*p) << endl;
			p++;
			ss.pop();
		}
		else
		{
			cout << "Rule " << table[ss.top()][lexer(*p)] << endl;
			switch (table[ss.top()][lexer(*p)])
			{
				case 1:	// 1. S → F
					ss.pop();
					ss.push(NTS_F);	// F
					break;

				case 2:	// 2. S → ( S + F )
					ss.pop();
					ss.push(TS_R_PARENS);	// )
					ss.push(NTS_F);		// F
					ss.push(TS_PLUS);	// +
					ss.push(NTS_S);		// S
					ss.push(TS_L_PARENS);	// (
					break;

				case 3:	// 3. F → a
					ss.pop();
					ss.push(TS_A);	// a
					break;

				default:
					cout << "parsing table defaulted" << endl;
					return 0;
			}
		}
	}

	cout << "finished parsing" << endl;

	return 0;
}

Implementación del analizador en Python

# All constants are indexed from 0
TERM = 0
RULE = 1

# Terminals
T_LPAR = 0
T_RPAR = 1
T_A = 2
T_PLUS = 3
T_END = 4
T_INVALID = 5

# Non-Terminals
N_S = 0
N_F = 1

# Parse table
table = [[ 1, -1, 0, -1, -1, -1],
         [-1, -1, 2, -1, -1, -1]]

RULES = [[(RULE, N_F)],
         [(TERM, T_LPAR), (RULE, N_S), (TERM, T_PLUS), (RULE, N_F), (TERM, T_RPAR)],
         [(TERM, T_A)]]

stack = [(TERM, T_END), (RULE, N_S)]

def lexical_analysis(inputstring):
    print("Lexical analysis")
    tokens = []
    for c in inputstring:
        if c   == "+": tokens.append(T_PLUS)
        elif c == "(": tokens.append(T_LPAR)
        elif c == ")": tokens.append(T_RPAR)
        elif c == "a": tokens.append(T_A)
        else: tokens.append(T_INVALID)
    tokens.append(T_END)
    print(tokens)
    return tokens

def syntactic_analysis(tokens):
    print("Syntactic analysis")
    position = 0
    while len(stack) > 0:
        (stype, svalue) = stack.pop()
        token = tokens[position]
        if stype == TERM:
            if svalue == token:
                position += 1
                print("pop", svalue)
                if token == T_END:
                    print("input accepted")
            else:
                print("bad term on input:", token)
                break
        elif stype == RULE:
            print("svalue", svalue, "token", token)
            rule = table[svalue][token]
            print("rule", rule)
            for r in reversed(RULES[rule]):
                stack.append(r)
        print("stack", stack)

inputstring = "(a+a)"
syntactic_analysis(lexical_analysis(inputstring))

Observaciones

Como puede verse en el ejemplo, el analizador realiza tres tipos de pasos dependiendo de si la parte superior de la pila es un no terminal, un terminal o el símbolo especial $ :

Si la parte superior es un no terminal, entonces el analizador busca en la tabla de análisis, sobre la base de este no terminal y el símbolo en el flujo de entrada, qué regla de la gramática debe usar para reemplazar el no terminal en la pila. El número de la regla se escribe en el flujo de salida. Si la tabla de análisis indica que no existe tal regla, el analizador informa un error y se detiene.
Si la parte superior es una terminal, el analizador lo compara con el símbolo en el flujo de entrada y, si son iguales, ambos se eliminan. Si no son iguales, el analizador informa un error y se detiene.
Si la parte superior es $ y en el flujo de entrada también hay un $ , el analizador informa que ha analizado correctamente la entrada; de lo contrario, informa un error. En ambos casos, el analizador se detendrá.

Estos pasos se repiten hasta que el analizador se detiene, y luego habrá analizado completamente la entrada y escrito una derivación más a la izquierda en el flujo de salida o habrá informado un error.

Construir una tabla de análisis de LL (1)

Para llenar la tabla de análisis, tenemos que establecer qué regla gramatical debe elegir el analizador si ve un no terminal A en la parte superior de su pila y un símbolo a en su flujo de entrada. Es fácil ver que dicha regla debe tener la forma A → w y que el lenguaje correspondiente a w debe tener al menos una cadena que comience con a . Para este propósito, definimos el primer conjunto de w , escrito aquí como Fi ( w ), como el conjunto de terminales que se pueden encontrar al comienzo de alguna cadena en w , más ε si la cadena vacía también pertenece a w . Dada una gramática con las reglas A ₁ → w ₁ ,…, A _n → w _n , podemos calcular Fi ( w _i ) y Fi ( A _i ) para cada regla de la siguiente manera:

inicializar cada Fi ( A _i ) con el conjunto vacío
agregue Fi ( w _i ) a Fi ( A _i ) para cada regla A _i → w _i , donde Fi se define de la siguiente manera:
- Fi ( aw ' ) = { a } para cada terminal a
- Fi ( Aw ' ) = Fi ( A ) para cada A no terminal con ε no en Fi ( A )
- Fi ( Aw ' ) = ( Fi ( A ) \ {ε}) ∪ Fi ( w' ) para cada A no terminal con ε en Fi ( A )
- Fi (ε) = {ε}
agregue Fi ( w _i ) a Fi ( A _i ) para cada regla A _i → w _i
siga los pasos 2 y 3 hasta que todos los conjuntos de Fi permanezcan iguales.

El resultado es la solución de punto fijo menos para el siguiente sistema:

Fi ( A ) ⊇ Fi ( w ) para cada regla A → w
Fi ( a ) ⊇ { a }, para cada terminal a
Fi ( w ₀ w ₁ ) ⊇ Fi ( w ₀ ) · Fi ( w ₁ ), para todas las palabras w ₀ y w ₁
Fi (ε) ⊇ {ε}

donde, para los conjuntos de palabras U y V, el producto truncado se define por , y w: 1 denota el prefijo inicial de longitud-1 de las palabras w de longitud 2 o más, o w, en sí mismo, si w tiene una longitud de 0 o 1. ${\ Displaystyle U \ cdot V = \ {(uv): 1: u \ in U, v \ in V \}}$

Desafortunadamente, los primeros conjuntos no son suficientes para calcular la tabla de análisis. Esto se debe a que el lado derecho w de una regla podría finalmente reescribirse en la cadena vacía. Por lo que el analizador también debe utilizar la regla A → w si ε es en internet ( w ) y se ve en la entrada de transmitir un símbolo que podría seguir una . Por lo tanto, también necesitamos el conjunto de seguimiento de A , escrito aquí como Fo ( A ), que se define como el conjunto de terminales a tal que hay una cadena de símbolos αAaβ que se pueden derivar del símbolo de inicio. Usamos $ como terminal especial que indica el final del flujo de entrada y S como símbolo de inicio.

El cálculo de los conjuntos de seguimiento para los no terminales en una gramática se puede hacer de la siguiente manera:

inicializar Fo ( S ) con { $ } y cada otro Fo ( A _i ) con el conjunto vacío
si hay una regla de la forma A _j → wA _i w ' , entonces
- si el terminal a está en Fi ( w ' ), agregue a a Fo ( A _i )
- si ε está en Fi ( w ' ), entonces agregue Fo ( A _j ) a Fo ( A _i )
- si w ' tiene longitud 0, agregue Fo ( A _j ) a Fo ( A _i )
repita el paso 2 hasta que todos los conjuntos de Fo permanezcan iguales.

Esto proporciona la solución de punto menos fijo para el siguiente sistema:

Fo ( S ) ⊇ { $ }
Fo ( A ) ⊇ Fi ( w ) · Fo ( B ) para cada regla de la forma B → ... A w

Ahora podemos definir exactamente qué reglas aparecerán en qué lugar de la tabla de análisis. Si T [ A , a ] denota la entrada en la tabla para el no terminal A y el terminal a , entonces

T [ A , a ] contiene la regla A → w si y solo si

a está en Fi ( w ) o

ε está en Fi ( w ) y a está en Fo ( A ).

De manera equivalente: T [ A , a ] contiene la regla A → w para cada a ∈ Fi ( w ) · Fo ( A ).

Si la tabla contiene como máximo una regla en cada una de sus celdas, entonces el analizador siempre sabrá qué regla debe usar y, por lo tanto, puede analizar cadenas sin retroceder. Es precisamente en este caso que la gramática se llama un LL (1) gramática .

Construir una tabla de análisis de LL ( k )

La construcción de los analizadores sintácticos LL (1) se puede adaptar a LL ( k ) para k > 1 con las siguientes modificaciones:

el producto truncado está definido , donde w: k denota el prefijo inicial de longitud-k de palabras de longitud> k, o w, en sí mismo, si w tiene una longitud de k o menos, ${\ Displaystyle U \ cdot V = \ {(uv): 1: u \ in U, v \ in V \}}$
Fo ( S ) = { $ ^k }

donde una entrada tiene el sufijo k end-markers $ , para tener en cuenta completamente el contexto k lookahead.

Hasta mediados de la década de 1990, se creía ampliamente que el análisis sintáctico de LL ( k ) (para k > 1) no era práctico, ya que la tabla del analizador sintáctico tendría un tamaño exponencial en k en el peor de los casos. Esta percepción cambió gradualmente después del lanzamiento del conjunto de herramientas de construcción del compilador Purdue alrededor de 1992, cuando se demostró que muchos lenguajes de programación pueden ser analizados de manera eficiente por un analizador LL ( k ) sin desencadenar el peor comportamiento del analizador. Además, en ciertos casos, el análisis de LL es factible incluso con una búsqueda anticipada ilimitada. Por el contrario, los generadores de analizadores sintácticos tradicionales como yacc utilizan tablas de analizadores sintácticos LALR (1) para construir un analizador sintáctico LR restringido con una anticipación fija de un token.

Conflictos

Como se describe en la introducción, los analizadores sintácticos LL (1) reconocen los lenguajes que tienen gramáticas LL (1), que son un caso especial de gramáticas libres de contexto; Los analizadores de LL (1) no pueden reconocer todos los lenguajes libres de contexto. Los lenguajes LL (1) son un subconjunto adecuado de los lenguajes LR (1), que a su vez son un subconjunto adecuado de todos los lenguajes libres de contexto. Para que una gramática libre de contexto sea una gramática LL (1), no deben surgir ciertos conflictos, que describimos en esta sección.

Terminología

Sea A un no terminal. PRIMER ( A ) es (definido a ser) el conjunto de terminales que pueden aparecer en la primera posición de cualquier secuencia derivada de A . SIGUE ( A ) es la unión sobre:

PRIMERO ( B ) donde B es cualquier no terminal que sigue inmediatamente a A en el lado derecho de una regla de producción .
SIGA ( B ) donde B es cualquier encabezado de una regla de la forma B → wA .

LL (1) conflictos

Hay dos tipos principales de conflictos LL (1):

PRIMER / PRIMER conflicto

Los PRIMEROS conjuntos de dos reglas gramaticales diferentes para la misma intersección no terminal. Un ejemplo de un conflicto LL (1) FIRST / FIRST:

S -> E | E 'a'
E -> 'b' | ε

PRIMER ( E ) = { b , ε} y FIRST ( E un ) = { b , a }, así que cuando se dibuja la tabla, hay conflicto bajo terminal de b de regla de producción S .

Caso especial: recursión por la izquierda

La recursividad a la izquierda provocará un conflicto FIRST / FIRST con todas las alternativas.

E -> E '+' term | alt1 | alt2

Conflicto PRIMERO / SEGUIMIENTO

El PRIMER y SEGUIMIENTO conjunto de una regla gramatical se superponen. Con una cadena vacía (ε) en el PRIMER conjunto, se desconoce qué alternativa seleccionar. Un ejemplo de un conflicto LL (1):

S -> A 'a' 'b'
A -> 'a' | ε

El PRIMER conjunto de A ahora es { a , ε} y el SIGUIENTE conjunto { a }.

Soluciones a conflictos LL (1)

Factorización izquierda

Un factor de izquierda común es "factorizado".

A -> X | X Y Z

se convierte en

A -> X B
B -> Y Z | ε

Se puede aplicar cuando dos alternativas comienzan con el mismo símbolo, como un conflicto PRIMERO / PRIMERO.

Otro ejemplo (más complejo) usando el ejemplo de conflicto FIRST / FIRST anterior:

S -> E | E 'a'
E -> 'b' | ε

se convierte en (fusionándose en un solo no terminal)

S -> 'b' | ε | 'b' 'a' | 'a'

luego, a través de la factorización a la izquierda, se convierte en

S -> 'b' E | E
E -> 'a' | ε

Sustitución

Sustituir una regla por otra para eliminar conflictos indirectos o FIRST / FOLLOW. Tenga en cuenta que esto puede causar un conflicto PRIMERO / PRIMERO.

Eliminación de recursividad izquierda

Ver.

Para obtener un método general, consulte eliminar la recursividad por la izquierda . Un ejemplo simple para eliminar la recursividad por la izquierda: la siguiente regla de producción ha dejado la recursividad en E

E -> E '+' T
E -> T

Esta regla no es más que una lista de "Yoes" separados por "+". En una forma de expresión regular T ('+' T) *. Entonces la regla podría reescribirse como

E -> T Z
Z -> '+' T Z
Z -> ε

Ahora no hay recursividad izquierda ni conflictos en ninguna de las reglas.

Sin embargo, no todas las gramáticas libres de contexto tienen una gramática LL (k) equivalente, por ejemplo:

S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε

Se puede demostrar que no existe ninguna gramática LL (k) que acepte el lenguaje generado por esta gramática.

Ver también

Notas

^ Rosenkrantz, DJ; Stearns, RE (1970). "Propiedades de las gramáticas de arriba hacia abajo deterministas" . Información y control . 17 (3): 226–256. doi : 10.1016 / s0019-9958 (70) 90446-8 .
^ Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "LL-Gramáticas regulares". Instytutu Maszyn Matematycznych : 107-119.
^ Jarzabek, Stanislav; Krawczyk, Tomasz (noviembre de 1975). "LL-Gramáticas regulares" . Cartas de procesamiento de información . 4 (2): 31–37. doi : 10.1016 / 0020-0190 (75) 90009-5 .
^ David A. Poplawski (agosto de 1977). Propiedades de LL-Lenguajes regulares (Informe técnico). Universidad Purdue , Departamento de Ciencias de la Computación.
^ Parr, Terence y Fisher, Kathleen (2011). "LL (*) la base del generador analizador ANTLR". Avisos ACM SIGPLAN . 46 (6): 425–436. doi : 10.1145 / 1993316.1993548 .CS1 maint: varios nombres: lista de autores ( enlace )
^ Belcak, Peter (2020). "La estrategia de análisis sintáctico LL (finito) para un análisis sintáctico óptimo de LL (k)". arXiv : 2010.07874 [ cs.PL ].
^ Ford, Bryan (2004). "Análisis de gramáticas de expresión: una base sintáctica basada en el reconocimiento". Avisos ACM SIGPLAN . doi : 10.1145 / 982962.964011 .
^ Pat Terry (2005). Compilando con C # y Java . Educación Pearson. págs. 159-164. ISBN 9780321263605.
^ William M. Waite y Gerhard Goos (1984). Construcción del compilador . Textos y monografías en informática. Heidelberg: Springer. ISBN 978-3-540-90821-0.Aquí: Sect. 5.3.2, pág. 121-127; en particular, p. 123.
^ Richard E. Stearns y PM Lewis (1969). "Gramáticas de propiedad y máquinas de tabla" . Información y control . 14 (6): 524–549. doi : 10.1016 / S0019-9958 (69) 90312-X .
^ "Gramáticas LL" (PDF) . Archivado (PDF) desde el original el 18 de junio de 2010 . Consultado el 11 de mayo de 2010 .
^ Diseño de compilador moderno , Grune, Bal, Jacobs y Langendoen

enlaces externos

Un tutorial sobre la implementación de analizadores LL (1) en C # (archivado)
Simulador de análisis Este simulador se utiliza para generar tablas de análisis LL (1) y para resolver los ejercicios del libro.
Analizador de DSL PEG LL (1) (marco del kit de herramientas)
Comparación de la teoría del lenguaje de las gramáticas LL y LR
LL (k) Teoría de análisis

[1] Rosenkrantz, DJ; Stearns, RE (1970). "Propiedades de las gramáticas de arriba hacia abajo deterministas" . Información y control . 17 (3): 226–256. doi : 10.1016 / s0019-9958 (70) 90446-8 .

[2] Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "LL-Gramáticas regulares". Instytutu Maszyn Matematycznych : 107-119.

[3] Jarzabek, Stanislav; Krawczyk, Tomasz (noviembre de 1975). "LL-Gramáticas regulares" . Cartas de procesamiento de información . 4 (2): 31–37. doi : 10.1016 / 0020-0190 (75) 90009-5 .

[4] David A. Poplawski (agosto de 1977). Propiedades de LL-Lenguajes regulares (Informe técnico). Universidad Purdue , Departamento de Ciencias de la Computación.

[5] Parr, Terence y Fisher, Kathleen (2011). "LL (*) la base del generador analizador ANTLR". Avisos ACM SIGPLAN . 46 (6): 425–436. doi : 10.1145 / 1993316.1993548 .CS1 maint: varios nombres: lista de autores ( enlace )

[6] Belcak, Peter (2020). "La estrategia de análisis sintáctico LL (finito) para un análisis sintáctico óptimo de LL (k)". arXiv : 2010.07874 [ cs.PL ].

[7] Ford, Bryan (2004). "Análisis de gramáticas de expresión: una base sintáctica basada en el reconocimiento". Avisos ACM SIGPLAN . doi : 10.1145 / 982962.964011 .

[8] Pat Terry (2005). Compilando con C # y Java . Educación Pearson. págs. 159-164. ISBN 9780321263605.

[9] William M. Waite y Gerhard Goos (1984). Construcción del compilador . Textos y monografías en informática. Heidelberg: Springer. ISBN 978-3-540-90821-0.Aquí: Sect. 5.3.2, pág. 121-127; en particular, p. 123.

[10] Richard E. Stearns y PM Lewis (1969). "Gramáticas de propiedad y máquinas de tabla" . Información y control . 14 (6): 524–549. doi : 10.1016 / S0019-9958 (69) 90312-X .

[11] "Gramáticas LL" (PDF) . Archivado (PDF) desde el original el 18 de junio de 2010 . Consultado el 11 de mayo de 2010 .

[12] Diseño de compilador moderno , Grune, Bal, Jacobs y Langendoen

Languages

In other projects