UNIDAD 6.-ANÁLISIS SINTÁCTICO

6.1 GLC

6.2 Árboles de derivación.

6.3 Formas normales de Chomsky.

6.4 Diagramas de sintaxis

6.5 Eliminación de la ambigüedad.

6.6 Generación de matriz predictiva ( cálculo first y follow)

6.7 Tipos de analizadores sintácticos

6.8 Manejo de errores

6.9 Generadores de analizadores sintácticos

Competencia específica de la unidad

Construir un analizador sintáctico a partir de un lenguaje de

programación o un analizador sintáctico para el reconocimiento de

gramáticas (p.e. YACC).

Criterios de evaluación de la Unidad

Mapa conceptual: 20%

Solución de ejercicios: 40%

Desarrollo de programa: 40%

Actividades de aprendizaje

Mapa conceptual: Realizar por equipos de trabajo una investigación y

mapa conceptual de los temas: GLC, Árboles de derivación, Formas

normales de Chomsky, Notación de los diagramas de sintaxis

Solución de ejercicios: Identificar la notación formal de una gramática.

Construir diagramas de sintaxis de un lenguaje. Construir una GLC a

partir de los diagramas de sintaxis. Eliminar la ambigüedad de una

gramática. Distinguir los Errores sintácticos.

Desarrollo de programa: Construir un analizador sintáctico (utilizar un

generador de analizador sintáctico o un LP).

UNIDAD 6 Análisis Sintáctico.

6.1 GLCCapturan la noción de constituyente sintáctico y la noción de orden.

Herramienta formal que puede ser vista tanto desde un punto de vista

generador como estructurador.

Propiedades computacionales interesantes: se puede reconocer en tiempo

polinómico.

Una Gramática Libre de Contexto es una tupla con 4 parámetros:G = (V,T,P,S)

V – conjunto de símbolos variables T – conjunto de símbolos terminales S Î V, símbolo inicial P – conjunto de reglas de producción:

A ® α, con α sucesión de símbolos de V È T, eventualmente vacía (α =ε).

Una GLC es un dispositivo generador.Definimos el lenguaje LG generado por una gramática G del siguiente modo:LG = { w / S ⇒* w } , siendo ⇒* una “especie” de clausura transitiva de ®y w una tira de terminales.

Reglas para oraciones aseverativas (esbozo)O ® GN GV O ® GVGV ® VGV ® V GN GV ® V GAdj GV ® V GAdv GV ® GV GP

6.2 Árboles de derivación.Podemos decir:

Del mismo modo se puede decir

deriva en uno o más pasos.

donde es el símbolo distinguido (o inicial) de lagramática, es un símbolo no terminal (o

Una derivación por la izquierda es aquella en la que se reemplaza el no terminal más a la izquierda en cada paso de la derivación.. análogamente para la derechaUna derivación por la izquierda corresponde a la numeración preorden de los nodos internos de su árbol de análisis gramatical asociado.. derecha . postorden inversa.

Toda derivación de las gramáticas de tipo 1, 2 ó 3 se puede representar mediante un árbol.

6.3 Formas normales de Chomsky.

Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:

oα o

donde , y son símbolos no terminales (o variables) y α es unsímbolo terminal.

Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.

En algunos textos se puede encontrar una definición de una GFNCH de forma que cualquier GFNCH produzca cualquier lenguaje independiente del contexto y de la misma manera, que para cualquier lenguaje independiente del contexto exista una GFNCH que lo defina. Esta definición apenas se diferencia en permitir una regla ε de la siguiente forma:

oα o ε

variable), y también son símbolos no terminales pero distintos de , α es un símbolo terminal, y ε es la cadena nula (o vacía).

6.4 Diagramas de sintaxisUn segundo método alternativo para desplegar las producciones de ciertas gramáticas de tipo 2 es el diagrama de sintaxis. Ésta es una imagen de las producciones que permite al usuario ver las sustituciones en forma dinámica, es decir, verlas como un movimiento a través del diagrama. En la figura 10.5 se ilustrará los diagramas que resultan de la traducción de conjuntos de producciones típicos, que son, por lo general, todas las producciones que aparecen en el lado derecho de algún enunciado BNF.

a) <w> ::= <w1> <w2> <w3>

b) <w> ::= <w1><w2> | <w1>a | bc<w2>

c) <w> ::= ab<w>.

d) <w> ::= ab | ab<w>.

6.5 Eliminación de la ambigüedad.Una GLC es ambigua si existe una cadena w Î L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más árboles de derivación. En caso de que toda cadena w Î L(G) tenga un único árbol de derivación, la gramática no es ambigua.

TIPOS DE AMBIGÜEDADDentro del estudio de gramáticas existen dos tipos fundamentales de ambigüedad, los cuales son:

Ambigüedad Inherente:Las gramáticas que presentan este tipo de ambigüedad no pueden utilizarse para lenguajes de programación, ya que por más transformaciones que se realicen sobre ellas, nunca se podrá eliminar completamente la ambigüedad que presentan.

Un lenguaje L es inherentemente ambiguo si todas sus gramáticas son ambiguas;si existe cuando menos una gramática no ambigua para L, L no es ambiguo.

El lenguaje de las expresiones no es Ambiguo Las expresiones regulares no son ambiguas

Ambigüedad Transitoria:Este tipo de ambigüedad puede llegar a ser eliminada realizando una serie de transformaciones sobre la gramática original. Una vez que se logra lo anterior, la gramática queda lista para ser reconocida por la mayor parte de los analizadores sintácticos. (Se le considera "ambigüedad" porque existen métodos para realizar análisis sintáctico que no aceptan gramáticas con estas características)

Dónde se presenta la Ambigüedad Transitoria generalmente la ambigüedad se presenta cuando existen producciones con factores comunes (distintas alternativas para un símbolo no-terminal que inician de la misma forma); ó cuando existen producciones que son recursivas izquierdas (producciones para un

símbolo no-terminal en las cuales el primer símbolo de su forma sentencial es ese mismo símbolo no-terminal).

¿Cómo solucionar el problema de la Ambigüedad Transitoria?Para eliminar este tipo de ambigüedad, es necesario, primero eliminar:

Factores comunes izquierdos inmediatos y No-inmediatos. Recursividad izquierda inmediata y No-inmediata.

ELIMINACIÓN DE LA AMBIGÜEDAD.

No existe un algoritmo que nos indique si una GIC es ambigua Existen LIC que sólo tienen GIC ambiguas: inherentemente ambiguos Para las construcciones de los lenguajes de programación comunes existen

técnicas para la eliminación de la ambigüedad

Ejemplo: causas de ambigüedad en la siguiente gramática

No se respeta la precedencia de operadores

Una secuencia de operadores idénticos puede agruparse desde la izquierda y desde la derecha. Lo convencional es agrupar desde la izquierda.

6.6 Generación de matriz predictiva (cálculo first y follow)FIRSTSi α es cualquier cadena de símbolos gramaticales, se considera FIRST(α) como el conjunto de terminales que encabezan las cadenas derivadas de α. Si α = * => λ, entonces λ también está en FIRST(α).

Para calcular FIRST(X) para algún símbolo X de la gramática, se aplican las siguientes reglas hasta que no se pueda añadir nada nuevo al conjunto FIRST:

1. Si X es terminal, entonces FIRST(X) es {X}.

2. Si X es no terminal y existe la producción X → λ, entonces añadir λ a FIRST(X).

3. Si X es no terminal y X → Y1 Y2 .. . Yk es una producción entonces, para todo i (con i variando desde 1 hasta k) tal que Y1 , Y2 , ..., Yi-1 sean todos no terminales y FIRST(Y1), FIRST(Y2), ..., FIRST(Yi-1) contengan todos λ, se añaden todos los símbolos no nulos de FIRST(Yi ) a FIRST(X). Finalmente, si λ está en FIRST(Yj ) para j = 1, 2, ..., k (o sea, en todos), entonces se añade λ a FIRST(X).

Dicho de otra forma, lo anterior significa que todos los elementos de FIRST(Y1), excepto λ, pertenecen también a FIRST(X). Si Y1 no deriva λ, entonces ya ha terminado el cálculo de FIRST(X), pero en caso contrario, es decir, si Y1 =*=> λ,

entonces todos los elementos de FIRST(Y2) excepto λ pertenecen también a FIRST(X), y así sucesivamente. Finalmente, si todos los Yi derivan λ, entonces λ se añade a FIRST(X).

FOLLOWSe define FOLLOW(A), para el no terminal A, como el conjunto de terminales a que pueden aparecer inmediatamente a la derecha de A en alguna forma sentencial, es decir, el conjunto de terminales a tal que haya una derivación de la forma S=*=>αAaβ para algún α y β. Si A puede ser el símbolo de más a la derecha en alguna forma sentencial, entonces $ está en FOLLOW(A).

Para calcular FOLLOW(A) para un símbolo no terminal A, se aplican las siguientes reglas hasta que no se pueda añadir nada más al conjunto FOLLOW.

1. $ está en FOLLOW(S), siendo S el axioma de G.

2. Si existe una producción A → αBβ, entonces todo lo que esté en FIRST(β), excepto λ, está en FOLLOW(B).

3. Si existe la producción A → αBβ y FIRST(β) contiene λ (es decir, β=*=>λ), o bien si existe una producción A → αB, entonces todo lo que esté en FOLLOW(A) está en FOLLOW(B).

6.7 Tipos de analizadores sintácticosAnalizador Descendente:

Se construye el árbol de análisis sintáctico partiendo del símbolo inicial y aplicando las producciones mediante derivaciones por la izquierda, el símbolo a expandir es el que este más a la izquierda.

Ejemplo:G=({+,*, ID, (, )}, {E, T, P}, E, P)P={ E:=E+T | T; T:=T*P | P; P:= ID | ( E ) } FraseID + ( ID * ID )

Analizador Ascendente:Se construye el árbol de análisis sintáctico partiendo de la frase a reconocer y aplicando las producciones mediante reducciones hasta llegar a símbolo inicial de la gramática.

Ejemplo:G=({+,*, ID, (, )}, {E, T, P}, E, P)P={ E:=E+T | T; T:=T*P | P; P:= ID | ( E ) } FraseID + ( ID * ID )

L L (1)

DescendentesEs Predictivo

Se aplican las producciones por izquierda

El orden de lectura de la entrada es de izquierda a derecha

S L R (1)

Tipos deAnalizadores

Es Predictivo

Se aplican las producciones por derecha

El orden de lectura de la entrada es de izquierda a derecha

L R (1)Simple

AscendentesEs Predictivo

Se aplican las producciones por derecha

LA L R (1)

El orden de lectura de la entrada es de izquierda a derecha

Es Predictivo

Se aplican las producciones por derecha

El orden de lectura de la entrada es de izquierda a derecha

Look a Head: Al construir el analizador va a tratar de mirar por adelantado el texto para comprenderlo y hacer mas sencillo y mejores estados

6.8 Manejo de erroresRutinas de Manejo de ErroresOcupan gran parte de los compiladores

Objetivos

Informar con claridad, exactitud Recuperación rápida

recuperación no es corrección No debe retrasar el procesamiento de programas sin errores No generar errores en cascada (ej. eliminar identificador)

Acciones posibles

Detectar errores Informar de los errores Recuperar de los errores Corregir errores

¿Necesidad actual de recuperación?

Más rápido re-compilar que leer siguiente erro

Tipos de errores Léxicos: escribir mal un identificador, número. Sintácticos: no poner un “;” al final de una sentencia, estructura incorrecta. Semánticos: multiplicar por una variable booleana Lógicos: bucle infinito

Herramientas para disminuir el número de errores

Léxicos Si se utiliza alguna herramienta que complete palabras

Sintácticos Si se utiliza algún editor basado en sintaxis (colores)

Semánticos Busca funciones/clases e indica tipos especificados

Modo de PánicoCaracterísticas

Método más sencillo Lo pueden usar la mayoría de los AS No entra en lazos infinitos Adecuado para lenguajes en los que son raros múltiples errores en

la misma proposición

Funcionamiento general

El AS desecha símbolos de la entrada, uno por uno, hasta encontrar un token de sincronización para continuar

Delimitadores (punto y coma, palabras clave como end) Inconvenientes Podrían omitirse gran cantidad de símbolos sin analizar

A nivel de fraseCaracterísticas

Correcciones en la cadena de entrada

Funcionamiento

Descubierto el error se corrige (localmente) la entrada por un prefijo que permite continuar el AS Sustituir una coma por un punto y coma, insertar un punto y coma, etc.

Inconvenientes

Dificultad para resolver situaciones en las que el error se produjo antes de la detección de éste

Pueden producir lazos infinitos Evitar insertar símbolos antes del símbolo actual en la entrada

Producciones de errorFuncionamiento

Conocidos los errores más comunes, se extiende la gramática con producciones de error

Reconocido el error, se dan diagnósticos precisos de la construcción errónea

Ej.: E->E op T | E->T E-> E T //falta operador T->id | num

Inconvenientes

Dificultad para ir más allá de los casos particulares más frecuentes Generación ambigüedades

6.9 Generadores de analizadores sintácticosHemos visto cómo el análisis léxico facilita la tarea de reconocer los elementos de un lenguaje uno a uno. A partir de ahora, vamos a centrarnos en el análisis sintáctico, que nos permitirá averiguar si un fichero de entrada cualquiera respeta las reglas de una gramática concreta. Para el tema del análisis sintáctico vamos a utilizar la herramienta yacc (Yet Another Compiler Compiler).

Funcionamiento de yaccIgual que sucedía con lex, yacc no es directamente un analizador sino un generador de analizadores. A partir de un fichero fuente en yacc, se genera un fichero fuente en C que contiene el analizador sintáctico. Sin embargo, un analizador sintáctico de yacc no puede funcionar por sí solo, sino que necesita un analizador léxico externo para funcionar. Dicho de otra manera, el fuente en C que genera yacc contiene llamadas a una función yylex() que debe estar definida y debe devolver el tipo de lexema encontrado. Además, es necesario incorporar también una función yyerror(), que será invocada cuando el analizador sintáctico encuentre un símbolo que no encaja en la gramática.

El lenguaje YaccEsquema generalUn programa fuente de Yacc se parece bastante a uno de lex. La diferencia principal está en la sección de reglas, que en vez de expresiones regulares contiene las reglas de la gramática:

De estas tres secciones, sólo la segunda es obligatoria, y no debe estar vacía (nótese que en lex, las tres secciones pueden estar vacías). Esto quiere decir que el mínimo programa en yacc es:

%%

regla gramatical acción en C

La sección de declaraciones puede incluir varias cosas, tal y como ocurría en lex, pero ahora su función principal no es definir expresiones regulares, sino declarar los símbolos terminales de la gramática mediante la directriz

%token. Todo lo que no sea un terminal, será considerado un símbolo no terminal, y por tanto debe haber una regla para él:

%token IF,ELSE,LLAVE_AB,LLAVE_CE,IDENT

La sección de reglas contiene la gramática en sí. Componentes es una combinación de terminales y no terminales que describe al no terminal de la izquierda de la regla:

no_terminal: componentes {acciones en C}

La sección de rutinas tiene la misma función que la de lex, pero yacc (dependiendo de su variante) no define por defecto las funciones main(), yylex() e yyerror(), así que hay que incluirlas aquí, o bien en otro fichero que se enlazará en la fase final de la compilación.

Yacc genera una función llamada yyparse() que contiene el analizador sintáctico.

Esta función se comporta como una máquina de estados cuya misión es intentar

reducir todo el fichero de entrada al símbolo inicial de la gramática (el primero que

se haya definido). Si yacc lo consigue, el analizador sintáctico volverá sin error, y

en caso contrario, se invocará a la función yyerror(), que debe estar definida

también en algún sitio.

Actividades:Mapa conceptual: Realizar por equipos de trabajo una investigación y

mapa conceptual de los temas: GLC, Árboles de derivación, Formas

normales de Chomsky, Notación de los diagramas de sintaxis

Solución de ejercicios: los realizaremos en clases .

Desarrollo de programa: Construir un analizador sintáctico ver lo

siguiente

Video

https://www.youtube.com/watch?v=uoMlO8JFRxY

Archivos del video descargarlos

https://docs.google.com/file/d/0B3_b21Tb1us5UzUyUkJYanJUU00/edit

otros de apoyo

http://crysol.org/es/node/819

http://elblogdepicodev.blogspot.mx/2011/10/ejemplo-sencillo-con-

javacc-de-un.html