• Author / Uploaded
• Jonathan Lopez

Citation preview

Lenguaje libre del Contexto

La mayoría lenguajes de programación, son lenguajes libres de contexto y están definidos por medio de gramáticas libres de contexto. Contexto se refiere al entorno en que se encuentra, como influye el entorno en el significado de cada parte. Puede ser reconocido por autómatas de pila. Está definido dentro de la jerarquía de Chomsky en el Tipo 2.

Es una gramática formal en la que cada regla de producción es de la forma: N→w Donde N es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal N puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera. Definición de la Gramática Es una cuádrupla G = (N,T,P,S) donde: N es un alfabeto de símbolos no terminales (variables). T es un alfabeto de símbolos terminales (constantes). Pueden ser cadenas de lenguaje. Es una gramática formal en la que cada regla de producción es de la forma: N→w Donde N es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal N puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera. Definición de la Gramática

Es una cuádrupla G = (N,T,P,S) donde: N es un alfabeto de símbolos no terminales (variables). T es un alfabeto de símbolos terminales (constantes). Pueden ser cadenas de lenguaje. S Є N es el símbolo inicial o axioma de la gramática. P es el conjunto de reglas de producción, P ⊆ N × (T U N)* Producción Donde cualquier símbolo No Terminal del lado derecho de la producción puede ser remplazado por cualquier definición de ese mismo terminal del lado derecho. Ejemplo: S → E E→E+E E → num Ejemplo Un ejemplo de una Gramática Libre del contexto que reconoce operaciones de suma y multiplicación con números enteros, como {5, 52+3, (1+3)*4}

• • •

Donde E es una expresión Numérica Num es un número Digito es cualquier entero de 0 a 9

Arboles de derivación

Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje. Un árbol es un conjunto de puntos, llamados nodos, unidos por líneas, llamadas arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de nodos y arcos debe satisfacer ciertas propiedades: Hay un único nodo distinguido, llamado raíz (se dibuja en la parte superior) que no tiene arcos incidentes.

Todo nodo c excepto el nodo raíz está conectado con un arco a otro nodo k, llamado el padre de c (c es el hijo de k). El padre de un nodo, se dibuja por encima del nodo. Todos los nodos están conectados al nodo raíz mediante un único camino. Los nodos que no tienen hijos se denominan hojas, el resto de los nodos se denominan nodos interiores. Propiedades de un árbol de derivación. Sea G = (N,T,S,P) una gramática libre de contexto, sea A Є N una variable. Diremos que un árbol TA = (N,E) etiquetado es un árbol de derivación asociado a G si verifica las propiedades siguientes: La raíz del árbol es un símbolo no terminal cada hoja corresponde a un símbolo terminal o λ. cada nodo interior corresponde a un símbolo no terminal. Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulo uno de los símbolos de la cadena.

Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulo uno de los símbolos de la cadena. Si un nodo está etiquetado con una variable X y sus descendientes (leídos de izquierda a derecha) en el árbol son X1,…,Xk , entonces hay una producción X → X1…Xk en G. Sea G=(N,T,S,P) una GLC. Un árbol es un árbol de derivación para G si: T U N U {λ} 1. Todo vértice tiene una etiqueta tomada de 2. La etiqueta de la raíz es el símbolo inicial S 3. Los vértices interiores tienen etiquetas de N 4. Si un nodo n tiene etiqueta A y n1n2...nk respectivamente son hijos del vértice n, ordenados de izquierda a derecha, con etiquetas x1,x2..xk respectivamente, entonces: A→ x1x2...xk debe ser una producción en P 5. Si el vértice n tiene etiqueta λ, entonces n es una hoja y es el único hijo de su padre.

Ejemplo Sea G=(N,T,S,P) una GLC con P: S→ ab|aSb La derivación de la cadena aaabbb será: y el árbol de derivación:

Relación entre derivaciones y árboles Si leemos las etiquetas de las hojas de izquierda a derecha tenemos una sentencia. Llamamos a esta cadena la producción del árbol de derivación. Teorema. Sea G=(N,T,S,P) una GLC. Entonces (de S se deriva α) si y sólo si hay un árbol de derivación en la gramática G con la producción α. Si w es una cadena de L(G) para la gramática libre de contexto G, entonces w tiene al menos un árbol de derivación. Referido a un árbol de derivación particular,w tendrá una única derivación a la izquierda y otra única a la derecha. Ejemplo

Derivación a la izquierda: Derivación a la derecha: Forma Normal de Chomsky

MYMY Gramática ambigua. Una sentencia w se denomina ambigua si puede obtenerse por más de un árbol de derivación (o equivalentemente, más de una derivación más a la izquierda o más a la derecha). Una gramática G se denomina ambigua si el lenguaje que genera contiene alguna sentencia ambigua. Lenguaje inherentemente ambiguo Un lenguaje se denomina inherentemente ambiguo si no existe una gramática no ambigua que lo genere. Una GLC se dice que está en Forma Normal de Chomsky (FNC) si todas sus producciones son de la forma: Excepcionalmente se permite la producción La idea de la transformación de una gramática limpia a FNC se ejecuta en dos pasos: Hacer que en la parte derecha de las producciones de longitud mayor o igual que dos sólo haya terminales. Trocear estas producciones para que tengan longitud dos. Algoritmo FNC: Para cada producción de la forma (a)Para cada αi, si αi es terminal

- Se añade la producción Ca → a - Se cambia αi por Ca en A → α1..αn 2. Para cada producción de la forma A → B1...Bm, m ≥ 3 (a) Se añaden (m-2) no terminales D1, D2, ..., Dm-2 (distintos para cada producción) (b) La producción A → B1...Bm se reemplaza por A → B1D1, D1 → B2D2, ... Dm-2 → Bm-1Bm

FORMA NORMALES DE CHOMSKY Las gramáticas se pueden expresar de diferentes formas, en ocasiones podemos llegar al mismo resultado utilizando gramáticas que difieren en su estructura, una norma para estandarizar la gramática es la Forma Normal de Chomsky.

A continuación el teorema 2.4 Si L es un lenguaje independiente del contexto que no contiene la cadena vacía, entonces existe una gramática G independiente del contexto tal que L(G)=L y el lado derecho de cualquier regla de reescritura en G consiste en un solo terminal o exactamente dos no terminales. Se dice que una gramática cuyas reglas de reescritura se adhieren a las restricciones del teorema 2.4 tiene la FORMA NORMAL DE CHOMSKY (FNC o CNF), llamada así en honor a Noam Chomsky. Por ejemplo la siguiente gramática cuyo símbolo inicial es S tiene la forma normal de Chomsky. S XM M SY Xx Yy Mientras que la siguiente gramática que genera el mismo lenguaje no la tiene S xSy S xy Para obtener la forma normal de Chomsky ejemplo: Considere la siguiente gramática S zMz MN M yMy Nx S zMz zyMyz zyNyz zyxyz . Paso 1 Introducir los nuevos no terminales YZ y convertir la gramática anterior en la siguiente: S ZMZ MN Zz Yy Nx Paso 2 Lo siguiente es reemplazar la regla S ZMZ por el par de reglas S ZR; R MZ, mientras que M YMY se reemplaza por M YP; P MY para obtener la siguiente gramática: S ZR R MZ MN M YP P MY

Zz Yy Nx Paso 3 Finalmente la regla M N se reemplaza por la regla M x, produciendo así la siguiente gramática ya que tiene la forma normal de Chomsky. S ZR R MZ Mx M YP P MY Zz Yy Nx S ZR zMZ zYPZ zyPZ zyMYZ zyxYZ zyxyZ zyxyz

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 noterminal 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.

Generación

de

matriz

predictiva

(cálculo

first

y

follow)

FIRST: Si α 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: Sea G:= (V; ∑; Q0; P) una gramática libre de contexto. Para cada forma sentencial α Є (V U ∑)* y para cada k Є N definiremos la función.

En otras palabras, el operador FIRST k asocia a cada forma sentencial los primeros k símbolos de cualquier forma terminal alcanzable desde α mediante derivaciones “masa a izquierda". 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).

FOLLOW: Se define FOLLOW(A), para él no terminal A, como el conjunto de terminales a que pueden aparecer inmediatamente a la derecha de A en alguna forma sentencia, 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 sentencia, 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). Con las mismas notaciones anteriores, para cada forma sentencia α Є (V U ∑)* definiremos la función FOLLOWG GK (α) del modo siguiente.

De nuevo nos ocuparemos solamente de FOLLOW: = FOLLOW1. Obsérvese que FOLLOW k (α) ⊂ ∑* y que para cada x Є FOLLOW (α), Ixl ≤ k. Obsérvese que para cada variable A Є V, FOLLOW(A) son todos los símbolos terminales que pueden aparecer a la derecha de A en alguna forma sentencia de la gramática.

ANÁLISIS SINTÁCTICO DESCENDENTE

En éste analizador las entradas son de izquierda a derecha, y construcciones de derivaciones por la izquierda de una sentencia o enunciado.

CARÁCTERISTICAS El análisis sintáctico descendente (ASD) intenta encontrar entre las producciones de la gramática la derivación por la izquierda del símbolo    

inicial para una cadena de entrada. Parte del axioma de la gramática. Procesa la entrada de izquierda a derecha. Escoge reglas gramaticales.

ELIMINAR AMBIGUEDAD: Para eliminar la ambigüedad se debe reescribir la gramática. ELIMINAR RECURSIVIDAD POR LA IZQUIERDA: Una gramática es recursiva por la izquierda si tiene un nodo Terminal a tal que existe una derivación A->Aα para alguna cadena. Es decir por simple observación podemos identificar. Para eliminar la recursividad por la izquierda se utiliza la siguiente formula.

Factorizar: Se trata de rescribir las producciones de la gramática con igual comienzo para retrasar la decisión hasta haber visto lo suficiente de la entrada como para elegir la opción correcta.

EJEMPLO

Análisis Sintáctico Descendente Con Retroceso. El método parte del axioma inicial y aplica todas las posibles reglas al no terminal más a la izquierda.  Se usa el retroceso para resolver la incertidumbre.  Sencillo de implementar.  Muy eficiente.

Análisis Sintáctico Descendente Predictivo (Asdp) El analizador debe realizar la previsión de la regla a aplicar sólo con ver el primer símbolo que produce para que el algoritmo tenga una complejidad lineal. Las gramáticas que son susceptibles de ser analizadas sintácticamente de forma descendente mediante un análisis predictivo y consultando un únicamente un símbolo de entrada pertenecen al grupo LL (1). A partir de gramáticas LL (1) se pueden construir analizadores sintácticos descendentes predictivos (ASDP), que son ASD sin retroceso.

ANÁLISIS SINTÁCTICO ASCENDENTE El objetivo de un análisis ascendente consiste en construir el árbol sintáctico desde abajo hacia arriba, esto es, desde los tokens hacia el axioma inicial, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente (si hablamos del caso con retroceso) o amplía el número de gramáticas susceptibles de ser analizadas (si hablamos del caso LL (1)).

Tipos Análisis ascendente con retroceso Al igual que ocurría con el caso descendente, este tipo de análisis intenta probar todas las posibles

operaciones (reducciones y desplazamientos) mediante un método de fuerza bruta, hasta llegar al árbol sintáctico, o bien agotar todas las opciones, en cuyo caso la cadena se rechaza. En el análisis con retroceso no se permiten las reglas ԑ, puesto que estas se podrán aplicar de forma indefinida. Análisis Ascendente sin Retroceso  El análisis ascendente sin retroceso busca una derivación derecha de la cadena de entrada de forma determinista  La L viene de la lectura de la cadena de entrada de izquierda a derecha.  La R de producir un árbol de derivación derecho.  La k indica el número de símbolos que es necesario leer a la entrada para tomar la decisión de qué producción emplear.  Un parser del tipo shift-reduce puede verse como un autómata de pila determinista extendido que realiza el análisis de abajo hacia arriba.  Dada una cadena de entrada w, simula una derivación más a la derecha. ¿Cuál es su diferencia?  En el análisis sintáctico descendente: se construye el árbol sintáctico arriba hacia abajo y se utiliza más reglas.  En el análisis sintáctico ascendente: se construye el árbol sintáctico de abajo hacia arriba, lo cual disminuye el número de reglas mal aplicadas con respecto al caso descendente.

Otros • Analizador sintáctico • Chart • Left • Analizador • Analizador sintáctico LL

descendente corner sintáctico

recursivo parser parser LR

Manejo de errores sintácticos Si un compilador tuviera que procesar sólo programas correctos, su diseño e implementación se simplificarían mucho. Las primeras versiones de los programas suelen ser incorrectas, y un buen compilador debería ayudar al programador a identificar y localizar errores. Es más, considerar desde el principio el manejo de errores puede simplificar la estructura de un compilador y mejorar su respuesta a los errores. Los errores en la programación pueden ser de los siguientes tipos:  Léxicos: producidos al escribir mal un identificador, una palabra clave o un operador.  Sintácticos: por una expresión aritmética o paréntesis no equilibrados.  Semánticos: como un operador aplicado a un operando incompatible. • Lógicos, puede ser una llamada infinitamente recursiva.  De corrección: cuando el programa no hace lo que el programador realmente deseaba. Errores de corrección no pueden ser detectados por un compilador, ya que en ellos interviene el concepto abstracto que el programador tiene sobre el programa que construye, lo cual es desconocido, y probablemente incognoscible, por el

compilador. La detección de errores lógicos implica un esfuerzo computacional muy grande en tanto que el compilador debe ser capaz de averiguar los distintos flujos que puede seguir un programa en ejecución lo cual, en muchos casos, no sólo es costoso, sino también imposible. Los compiladores actuales se centran en el reconocimiento de los tres primeros tipos de errores. Los errores de sintaxis, que son los que pueden impedir la correcta construcción de un árbol sintáctico. El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, no cancele definitivamente la compilación, sino que se recupere y siga buscando errores. Recuperar un error no quiere decir corregirlo, sino ser capaz de seguir construyendo el árbol sintáctico a pesar de los errores encontrados. El manejador de errores de un analizador sintáctico debe tener como objetivos: Indicar los errores de forma clara y precisa. Debe informar mediante los correspondientes mensajes del tipo de error y su localización Recuperarse del error, para poder seguir examinando la entrada Distinguir entre errores y advertencias. Las advertencias se suelen utilizar para informar sobre sentencias válidas pero que, por ser poco frecuentes, pueden constituir una fuente de errores lógicos No ralentizar significativamente la compilación. Un buen compilador debe conocer los errores que se pueden producir, con lo que se consigue simplificar su estructura. Si el propio compilador está preparado para admitir incluso los errores más frecuentes, entonces se puede mejorar la respuesta ante esos errores incluso corrigiéndolos. Generadores de analizadores sintácticos

****YACC****

Yacc convierte una gramática independiente del contexto y el código traducido en un conjunto de tablas para un LR (1) analizador y traductor. La gramática puede ser ambigua; reglas de prioridad especificados se utilizan para romper las ambigüedades. El archivo de salida, y.tab.c, debe ser compilado por el compilador C para producir un programa de yyparse. Este programa debe ser cargado con una función del Analizador Léxico, yylex (void) (a menudo generada por la lex (1)), con un main (int argc, char * argv []) del programa, y con la rutina de manejo de errores, yyerror (char *). Transiciones de estado. -V.- Crear y.output archivo, que contiene una descripción de las tablas de análisis sintáctico y de los conflictos que surgen de las ambigüedades de la gramática. -D.- Crea y.tab.h archivo, que contiene declaraciones #define que asocian yaccasignado códigos simbólicos `` 'con nombres de token-declarada por el usuario'. Incluirlo en los archivos de base distintos de y.tab.c para dar acceso a los códigos simbólicos.

-s stem .- y cambiar el prefijo de la y.tab.c nombres de archivo, y.tab.h, y.debug, y y.output para frenar. -S.- Escribir un analizador que utiliza Stdio en lugar de las rutinas de impresión en libc. La especificación de yacc en sí es esencialmente el mismo que la versión UNIX se describe en las referencias mencionadas. Además de la opción -D, las principales diferencias relevantes son: La interfaz con el medio ambiente C es de forma predeterminada a través en lugar de ; la opción -S invierte este. El analizador acepta entrada de texto UTF (ver utf (6)), que tiene un par de efectos. En primer lugar, el valor de retorno de yylex () ya no cabe en un corto; segundo, el valor de partida para no terminales es ahora 0xe000 en lugar de 257. El analizador generado puede ser recursiva: acciones pueden llamar a yyparse, por ejemplo, para poner en práctica una especie de instrucción # include en un intérprete. YACC Tipo de analizador: Ascendente, LALR(1). Código generado: C, C++. Características adicionales: • Se puede integrar con Lex dejando a éste el análisis léxico. • La precedencia se puede definir al margen de la gramática, manteniendo ésta más simple. • Conjuntamente con Memphis se puede construir un árbol sintáctico como salida del analizador.