Definiciones y teoremas (Teoría de Lenguajes)

Gramaticas LL(1)

Forma sentencial

Cualquier cadena que puedo derivar a partir del símbolo distinguido.

Primeros

primeros: V* --> P(Vt)
primeros(γ) = { t in Vt / γ -*-> α, α = t α'}

Algoritmo para calcular primeros:

Para cada x en V
  Si x esta en Vt
    primeros(x) := {x}
  Si x esta en Vn y x -> Y1Y2...Yk esta en P
    Si a pertenece a primeros(Yi) con Y1,...,Yi-1 anulables (forall i<=k)
      poner a en primeros(x)

Siguientes

siguientes: Vn --> P(Vt)
siguientes(N) = { t in Vt / S -*-> ... Nt ... }

Algoritmo para calcular siguientes:

 Agregar $ a siguientes(S)
 Repetir hasta que siguientes no cambie
   Si A -> α B β
     agregar primeros(β) a siguientes(B)
   Si A -> α B o A -> α B β con β anulable
     agregar los siguientes(A) a los siguientes(B)

Símbolos directrices (SD)

$SD:P\to \mathbb {P} (V_{T})$

$SD(N\to \beta )={\begin{cases}{\textrm {PRIMEROS}}(\beta )&si\ \beta \ {\textrm {no\ es\ anulable}}\\{\textrm {PRIMEROS}}(\beta )\cup {\textrm {SIGUIENTES}}(N)&{\textrm {sino}}\end{cases}}$

Gramática LL(1)

Sea G = <Vn, Vt, P, S>, es LL(1) si, siendo N no terminal y β y β' cadenas de V*, vale:

$\forall (N\rightarrow \beta ,N\rightarrow \beta ')\in P:(\beta \neq \beta '\Longrightarrow SD(N\rightarrow \beta )\cap SD(N\rightarrow \beta ')=\emptyset )$

Esto implica que la gramatica G debe ser no ambigua ni recursiva a izquierda.

Equivale a pedir las siguientes condiciones dado cualquier $A\rightarrow \alpha |\beta$:

• No puede pasar que tanto α como β deriven en strings que comiencen con un mismo terminal a.
• A lo sumo uno de los dos puede derivar en la cadena vacia.
• Si β deriva en la cadena vacia, entonces α no puede derivar en ninguna cadena que comience con un terminal en siguientes(A).

Analizador Sintáctico Descendente de Pila (A. S. D. P.) con tabla

Inicialización

Agregamos la siguiente producción:

S' --> S#

Tenemos una lista w con la cadena a analizar, t es el símbolo apuntado en dicha lista.

Sea M una matriz con tantas columnas como símbolos terminales y tantas filas como símbolos no terminales tal que:

M(a, s) = s --> α, si a pertenece a SD(s --> α)

Algoritmo

Repetir
  Si tope in Vt
      Si tope === t
         extraigo tope de la pila
         avanzo 1 en w
      Si no
         error
  Si no
      Si M(t, tope) === (tope --> Y1Y2 ... Yk)
         extraigo tope de la pila
         apilo YkYk-1 ... Y1 
      Si no
         error
Hasta que tope === # && t === #

Observación: No comerse el detalle de que el lado derecho de la producción Y1Y2 ... Yk se apila al revés de manera que el primer símbolo quede como tope.

Oh! Mi gramática no es LL(1)... Y ahora qué hago?!?!?

Tenés dos posibles maneras de zafarla. Una es factorizar:
A --> α β1 | α β2 | ... | α βK | γ1 | ... | γN

Pasa a ser:
A --> α A' | γ1 | ... | γN
A' --> β1 | β2 | ... | βK

O, si tu gramática es recursiva a izquierda, podés "desrecursivizar":
A --> A α1 | ... | A αN | β1 | ... | βK

Pasa a ser:
A --> β1 A' | ... | βK A'
A' --> α1 A' | ... | αN A' | lambda

Gramáticas y parsers LR

Los parsers LR(K) son (al igual que los parsers LL) una familia de parsers para analizar una clase grande de gramáticas libres de contexto. Se caracterizan por:

• Ser analizadores sintácticos ascendentes (analizan la sintaxis de abajo hacia arriba)
• Por leer la entrada de izquierda a derecha para encontrar y producir una derivación más a la derecha de la cadena de entrada (LR de Left to right Rightmost derivation).
• La K corresponde a la cantidad de símbolos de entrada de "lookahead" que se tienen en cuenta para tomar las decisiones de parseo (o sea, es como en los analizadores descentes predictivos, espía 0, 1 o más caracteres que vienen para decidir que producción usar).
• Se usan mucho porque son más potentes que los LL y porque son eficientes, pero tienen la desventaja de que es difícil programarlos a mano, por eso se suele usar generadores de parsers (que se encargan de armar las tablas usadas en los algoritmos).

Hay distintos tipos de parsers LR que son más y menos tolerantes a problemas (LR(0), SLR, LR(1) y LALR). Se habla de gramáticas LR(K) como aquellas gramáticas cuyo lenguaje puede ser parseado por un parser LR(K) sin problemas. Entonces hay gramáticas que van a ser LR(1) pero no LR(0), o SLR pero no LR(0), etc. La forma básica del algoritmo LR es la misma para todos, lo que cambia en cada uno es la construcción de una tabla que se usa para tomar decisiones durante el mismo.

Forma general de los algoritmos LR

Todos los algoritmos LR funcionan con un stack y una tabla de parseo, y las operaciones básicas que hacen hasta aceptar la cadena o generar un error son shift y reduce (desplazamiento y reducción). El algoritmo mantienene en el stack símbolos de la gramática, que tarde o temprano van a formar parte del lado derecho de una producción usada para generar la cadena de entrada. Lo que hace es ir consumiendo símbolos de entrada y agregándolos en el stack (a esto se le llama hacer shifts) hasta que decide que tiene suficiente información e "identifica" en el tope del stack uno o más símbolos que son la parte derecha de una producción. Entonces hace una reducción, que consiste en reemplazar todos los símbolos del tope del stack que coinciden con la parte derecha de la producción por la parte izquierda de la misma. Una vez que hace esto continua haciendo shift/reduce hasta que redujo toda la entrada al símbolo terminal, momento en el cual el parser "acepta" la entrada (y en el camino se enocontró la derivación de la cadena, que se puede reconstruir conociendo todos los reduce que se hicieron).

Lo difícil del algoritmo es cómo saber cuando hacer un shift y cuando hacer un reduce. Lo primero que uno piensa es que como hacer "pattern matching" entre el stack y los lados derechos de todas las producciones es fácil, simplemente hago shift hasta tener en el stack algo que matchee y ahí hago una reducción. El problema es que esta actitud golosa de suponer que hay que usar la primer producción que "funcione" (habiendo analizado sólo un prefijo de la cadena de entrada) no siempre anda, ya que por hacer esa reducción podemos llegar a algo en el stack que no hay manera de seguir reduciendo al símbolo S. Cómo se hace entonces? Bueno, lo groso de los parsers LR es que tienen como invariante que en el stack mantienen lo que se conoce como "prefijos viables". Y hay una propiedad que dice que el conjunto de los prefijos viables de un lenguaje LR es un lenguaje regular, con lo cual hay un AFND que puede identificar estos prefijos viables.

Entonces, los algoritmos LR lo que hacen es:

1. Construir el AFND de este lenguaje
2. A partir de este calculan una tabla que es lo que usan para decidir si hay que hacer un shift o un reduce. Al calcular esta tabla pueden surgir conflictos que indican que la gramática no es del tipo LR que se estaba tratando de usar.
3. Una vez con la tabla terminada y sin conflictos el algoritmo es muy fácil

Los distintos algoritmos LR

Construir el AFND ideal o necesario una una gramática cualquiera no es fácil y puede llegar a tener miles de estados, ya que cada estado del AFND representa un momento determinado en el parsing de una cadena de entrada cualquiera, y tiene que tener implícita la información de todo lo se leyó hasta el momento.

Hay entonces formas de construir AFND más simples y que sirven en muchas situaciones (aunque no todas).

• Los más simples son los parsers LR(0), que en el AFND no tienen lookahead.
• Los SLR usan el mismo AFND que los LR(0), pero cuando usan el AFND para armar la tabla que se usa en el algoritmo, se utiliza la función SIGUIENTES para filtrar algunas reducciones inválidas
• Los parsers LR(1) tienen un lookahead de un símbolo y construyen un AFND donde hay distintos estados que se diferencian por el símbolo de lookahead. Como consecuencia hay muchísimos más estados que un parser LR(0), y pasan a ser menos eficientes.
• Los parsers LALR son una solución de compromiso entre LR(1) y LR(0), ya que lo que hacen esencialmente es podar el AFND LR(1) agrupando un montón de estados que representan lo mismo. Consigue así achicar la cantidad de estados drásticamente, pero en contrapartida puede llegar a crear conflictos de tipo reduce-reduce (que antes no había) al agrupar estados.

Vale que $LR(0)\subset SLR\subset LALR\subset LR(1)$. La forma de calcular el AFND en los cuatro casos es parecida, y se basa en dos funciones: Clausura y Goto

Estas funciones tienen su versión para LR(0) y otra para LR(1). Una vez definidas, cada parser LR tiene pequeñas diferencias en el algoritmo para armar la tabla de parseo.

Resumiendo, para hacer el parser LR de una gramática necesitamos conocer:

• El algoritmo general de parseo LR basado en el stack y la tabla
• El algoritmo específico para construir la tabla y el AFND. A su vez, este algoritmo dependerá de:
  • La función clausura
  • La función Goto

Los algoritmos en detalles

Para los detalles de estas funciones en cada parser recomiendo altamente leer este ppt:

Algoritmos LR0, SLR, LR1 y LALR

Es didáctico, con ejemplos paso a paso y si bien parece largo por tener cientos de slides, la mayoría son por los ejemplos paso a paso. Recomiendo en serio leerlo si quieren ver como construir los AFND en detalle.

Gramaticas de Atributos

Una gramatica de atributos es una gramatica en la que se le asignan atributos (variables tipadas) a los no terminales de cada produccion y se opera a partir de los mismos, con asignaciones y funciones asociadas a cada produccion. Si bien los terminales no tienen atributos propiamente dichos, se puede considerar que tienen ciertos valores asignados por el lexer, y a veces manejarlos como atributos. Por ejemplo, la siguiente es una gramatica no ambigua para operaciones de suma y producto de numeros, como ser 4*(1+2), que obtiene en el atributo val de la raiz el valor de la expresion.

int L.val, E.val, T.val, F.val

L -> E			{L.val := E.val}
E -> E1 + T	{E.val := E1.val + T.val}
E -> T			{E.val := T.val}
T -> T1 * F	{T.val := T1.val * F.val}
T -> F			{T.val := F.val}
F -> ( E )		{F.val := E.val}
F -> digit		{F.val := value(digit)}

La funcion value() aplicada al terminal digit devuelve el valor del token (notar que al definir la gramatica, se asume que el lexer ya convirtio los terminales a tokens). Luego, a partir de dicho valor, al evaluar cada produccion se resuelven los atributos incluidos.

Es conveniente siempre antes de dar las producciones de la gramatica, indicar cuales son los atributos de cada no terminal, su tipo y si son heredados o sintetizados, para verificar que no se hayan cometido errores.

Es importante no confundir gramatica de atributos y definicion dirigida por sintaxis (o DDS). Si bien las dos son iguales en apariencia, la primera no admite funciones con efectos colaterales (como por ejemplo print) mientras que la segunda si.

Atributos Sintetizados y Heredados

Los atributos pueden ser sintetizados o heredados. Los atributos sintetizados son aquellos que se asignan en funcion de los atributos de los hijos del no terminal al que pertenecen, por ejemplo, val en la gramatica anterior. Un atributo sintetizado que aparezca en el lado izquierdo de una produccion siempre debe ser asignado.

Un atributo heredado es aquel cuyo valor depende de los atributos de su padre o hermanos en una produccion. Siempre que un heredado aparece en la parte derecha de una produccion debe ser asignado. Por ejemplo, en producciones como las siguientes, los atributos z e y de Z y de Y son heredados.

S -> X Y Z	{Y.y := X.x ; Z.z = X.x}

Y -> aZ 	{Z.z := Y.y}

Un atributo de un no terminal puede ser solamente sintetizado o heredado. No puede darse que en algunas producciones se comporte como heredado y en otras como sintetizado.

Los atributos son funcion siempre de otros atributos o constantes. Pueden usarse todo tipo de funciones: operaciones aritmeticas, operador ternario if-then-else (como el cond ? val1 : val2 de cpp), etc; siempre y cuando no tengan efectos colaterales.

A partir de esta clasificacion de atributos, se pueden clasificar las gramaticas. Una gramatica S-atribuida es una gramatica que solamente tiene atributos sintetizados; y una gramatica L-atribuida es una gramatica en la que todos sus atributos heredados dependen de atributos que se encuentran mas a la izquierda en la produccion. Esto permite que parseando de arriba hacia abajo y de izquierda a derecha puedan calcularse todos los atributos en una sola pasada.

Notar que el que una gramatica sea S-atribuida implica que sea L-atribuida, pero no al reves.

Arbol decorado

Dada una gramatica de atributos y una cadena de entrada, el arbol de analisis sintactico es el arbol construido por el parser al analizar la cadena. Dicho arbol se dice decorado si ademas tiene los atributos de cada simbolo y sus valores.

Orden de evaluacion

Para determinar el orden de evaluacion de los atributos se puede construir un grafo de dependencias. El digrafo tiene en los nodos los atributos de cada simbolo y los arcos representan dependencias (es decir, si A.a := f(B.b, C.c), entonces A.a depende de B.b y C.c). Cabe destacar que el grafo se construye para una cadena de entrada en particular, es decir, no hay un grafo para una gramatica, sino un grafo para una cadena en una gramatica (pensar en el arbol decorado, donde se dejan solamente los atributos, y los arcos marcan dependencias).

Una gramatica es circular si existe alguna cadena para la cual su grafo de dependencias tiene algun ciclo dirigido. Esto implica que no es posible calcular los valores de sus atributos.

En caso de que el digrafo sea aciclico, entonces se puede determinar un orden de evaluacion para los atributos siguiendo los arcos. Si la gramatica es ademas L-atribuida, no es necesario analizar este grafo pues se sabe que un orden de evaluacion valido para cualquier cadena de entrada es de arriba hacia abajo y de izquierda a derecha.

Condition

Ademas de las asignaciones, en las gramaticas de atributos es posible incluir una clausula condition. Esta clausula recibe una expresion booleana que depende de los valores de los atributos de los simbolos de la produccion y permite rechazar una cadena. Por ejemplo, la siguiente produccion rechaza la cadena si los atributos size de X e Y no coinciden.

S -> X Y	{ Condition: X.size = Y.size }

Traduccion Dirigida por Sintaxis

Denominada TDS o esquema de traduccion, es una gramatica en la que se asignan atributos (variables tipadas) a los simbolos de cada produccion, y se agregan bloques de codigo a las partes derechas de las producciones, los cuales pueden estar intercalados entre los simbolos, referenciar a los atributos y tener efectos colaterales.

La diferencia entre una TDS y una gramatica de atributos es, entonces, que la primera tiene bloques de codigo ubicados en las partes derechas de las producciones, mientras que la segunda tiene exclusivamente clausulas de asignacion (y condicion) asociadas a cada produccion.

La diferencia entre una TDS y DDS es que la TDS permite codigo intercalado en las producciones, y la DDS en rigor solamente permite asignaciones y llamadas a funciones (que pueden generar efectos colaterales) asociadas a una produccion.

El siguiente ejemplo toma declaraciones de tipos de la forma tipo var, var, var... y los guarda en una tabla de simbolos tras parsearlos.

D -> T {L.tipo := T.tipo} L
T -> int {T.tipo := "int"}
T -> bool {T.tipo := "bool"}
L -> var {add(var.nombre, L.tipo); L2.tipo = L1.tipo} L2
L -> var {add(var.nombre, L.tipo}

No hay restriccion para el codigo a utilizar dentro de los bloques. Puede usarse el pseudocodigo que se desee a conveniencia, cuanto mas sencillo mejor.

Orden de Ejecucion

El arbol de analisis sintactico se genera de arriba hacia abajo y de izquierda a derecha (al igual que como se evaluaban las gramaticas L-atribuidas). A medida que se recorren las producciones, se ejecuta el codigo contienen en el orden correspondiente. Esto impone ciertas restricciones en el uso de los atributos en los bloques de codigo, pues los mismos deben estar inicializados siempre antes de ser usados.

Atributos Sintetizados y Heredados

La diferenciacion entre atributos sintetizados y heredados se mantiene en las TDS y debe respetarse el equivalente a las reglas de asignacion que se manejaban en las gramaticas de atributos.

• Un atributo heredado de un simbolo S en la parte derecha de una produccion debe ser asignado en un bloque de codigo antes del simbolo S.

• Un bloque de codigo no puede referirse a un atributo sintetizado de un simbolo que se encuentre a la derecha del codigo, pues el simbolo aun no fue parseado y sus atributos sintetizados no fueron inicializados.

• Un atributo sintetizado que aparezca en la parte izquierda de una produccion solo puede asignarse cuando todos los atributos de los que depende han sido asignados

Rechazar una cadena

Puesto que ya no se manejan clausulas de asignacion y de condicion (como en la gramatica de atributos), para rechazar una cadena basta con llamar a la funcion "error", burbujear un valor "error" dentro de algun atributo o lanzar una excepcion.