compiladores1

Temas:• Introducción a la teoría de lenguajes• Definición de S intaxis• Traducción dirigida por sintaxis

S e puede definir un lenguaje de programación describiendo el aspecto de sus programas (la sintaxis del lenguaje) y el significado de sus programas (la semántica del lenguaje).

Para especificar la sintaxis de un lenguaje se presenta una notación muy usada llamada gramáticas independientes del contexto o B NF (Forma de B ackus – Naur).

Con las notaciones disponibles hoy, es mucho más difícil describir la semántica de un lenguaje que su sintaxis. Para especificar la semántica de un lenguaje se usarán descripciones informales y ejemplos ilustrativos.

Una gramática independiente del contexto se puede usar para guiar la traducción de programas y además sirve para especificar la sintaxis de un lenguaje.

Una técnica de compilación orientada a la gramática, conocida como traducción dirigida por la sintaxis, es muy útil para organizar la etapa inicial de un compilador

ANA LIZADOR LEXICO

TRADUCTOR DIRIGIDO POR LA S INTA XIS

Cadena de caracteres

Cadena de componentes léxicos

Representación intermedia

.En este compilador el analizador léxico convierte la cadena de caracteres de entrada en una cadena de componentes léxicos que se convierte en la entrada para la siguiente fase.

El “ traductor dirigido por la sintaxis, es una combinación de un analizador sintáctico y un generador e código intermedio.

Una razón para empezar con expresiones formadas por dígitos y operadores consiste en hacer que el analizador léxico sea en un principio muy fácil.

Cada carácter de entrada forma un conjunto léxico único

Gramática independiente del contexto (para abreviar, gramática) para especificar la sintaxis de un lenguaje.

Una gramática describe de forma natural la estructura jerárquica de muchas construcciones de los lenguajes de programación.

Por ejemplo if – else en C tiene la forma if (expresión) proposición else proposición

Empleando la variable expr para denotar una expresión, y la variable prop, para una proposición

S e expresa:prop if (expr) prop else prop

Donde es posible leer la flecha como “ puede tener la forma” , dicha regla se denomina producción.

En una producción, los elementos léxicos, como la palabra clave if y los paréntesis, se llaman componentes léxicos.

Las variables expr y prop representan secuencias de componentes léxicos y se llaman no terminales.

Una gramática independiente del contexto tiene cuatro componentes:2.Un conjunto de componentes léxicos, denominados símbolos terminales3.Un conjunto de no terminales4.Un conjunto de producciones en el que cada producción consta de un no terminal, llamado lado izquierdo de la producción, una flecha y una secuencia de componentes léxicos y no terminales, o ambos, llamado lado derecho de la producción5.La denominación de uno de los terminales como símbolo inicial

Ejemplos: -Los dígitos, los signos como y las cadenas en negritas, como while son terminales.-Un nombre en cursiva es un no terminal, y se supondrá que cualquier nombre o símbolo que no esté en cursiva es un componente léxico.-La s producciones con el mismo no terminal del lado izquierdo pueden tener sus lados derechos agrupados, con los lados derechos alternativos separados por el símbolo , que se leerá “ o” .

Ejemplos: S e utilizan expresiones formadas por dígitos y signos más y menos, sea el caso, 9-5+2, 3-1,, y 7.Como un signo más o menos debe aparecer entre dos dígitos, se dice de dichas expresiones que son “ listas de dígitos separados por signos más o menos” . De acuerdo con las convenciones, los componentes léxicos de la gramática son los símbolos+ - 0 1 2 3 4 5 6 7 8 9

Los no terminales son los nombres en cursva lista y dígito, siendo lista el no terminal inicial, porque sus producciones se dieron primero

S e dice que una producción es para un no terminal si el no terminal aparece en el lado izquierdo de la producción. Una cadena de componentes léxicos es una secuencia de cero o más componentes léxicos. La cadena que contiene cero componentes léxicos, que se escribe є, recibe el nombre de cadena vacía.

Indica gráficamente cómo del símbolo inicial de una gramática deriva una cadena de lenguaje. Si el no terminal A tiene una producción A XYZ, entonces un árbol de análisis sintáctico puede tener un nodo interior etiquetado con A y tres hijos etiquetados con X, Y y Z, de izquierda a derecha:

A

X Y Z

Un árbol de análisis sintáctico es un árbol con las propiedades siguientes:2.La raíz está etiquetada con el símbolo inicial 3.Cada hoja está etiquetada con un componente léxico o con є.4.Cada nodo interior está etiquetado con un no terminal.5.Si A es el no terminal que etiqueta a algún nodo interior y X1, X2….. Xn, son las etiquetas de los hijos de ese nodo, de izquierda a derecha, entonces A X1,X2… Xn es una producción.

Ejemplo: En la figura la raíz está etiquetada con lista, que es el símbolo inicial de la gramática del ejemplo inicial. Los hijos de la raíz están etiquetados, de izquierda a derecha, lista +, y dígito. Obsérvese que

Lista lista + dígito Es una producción en la gramática del ejemplo 1. el mismo patrón – se repite en el hijo izquierdo de la raíz, y cada uno de los tres nodos, etiquetados con dígito tiene un hijo que está etiquetado con un dígito.

Se ha de tener cuidado al considerar la estructura de una cadena según una gramática. Aunque es evidente que cada árbol de análisis sintáctico deriva exactamente la cadena que se lee en sus hojas, una gramática puede tener más de un árbol de análisis sintáctico que genere una cadena dada de componentes léxicos. Para demostrar que una gramática es ambigua, lo único que se requiere es encontrar una cadena de componentes léxicos que tenga más de un árbol de análisis sintáctico.

Como una cadena que cuenta con más de un árbol de análisis sintáctico suele tener más de un significado, para aplicaciones de compilación es necesario diseñar gramáticas no ambiguas o utilizar gramáticas ambiguas con reglas adicionales para resolver las ambigüedades.

Supóngase que no se hizo la distinción entre dígitos y listas según el ejemplo 1, se podía haber escrito la gramática:

Cadena cadena + cadena cadena – cadena 0 1 2 3 4 5 6 7 8 9

Precedencia y asociatividad de operadores

La precedencia de operadores especifica cómo se agrupan las expresiones_ Por ejemplo, en la expresión 1 + 5 * 3, la respuesta es 16 y no 18 porque el operador de multiplicación ("*") tiene una mayor precedencia que el de adición ("+")_La siguiente tabla lista la precedencia de operadores, indicándose primero los de menor precedencia_

Precedencia de Operadores

Precedencia de Operadores

OBJETIVO: La traducción de un lenguaje guiada por la gramática context free que lo define.IDEA BASICA:

Asociar información con las construcciones del lenguaje asociando atributos con los símbolos de la gramática.

Los valores de los atributos son calculados por medio de reglas semánticas asociadas con las producciones de la gramática.Existen dos mecanismos usados en la construcción de compildores para especificar la semántica y traducción de las construcciones del lenguaje usando gramáticas de atributos.

DEFINICIONES DIRIGIDAS POR LA SINTAXIS (SDD) que son gramáticas de atributos en las cuales el orden de evaluación de las reglas semánticas no están dadas.

ESQUEMAS DE TRADUCCION (TSDS): son gramáticas de atributos en las cuales el orden de evaluación de las reglas semánticas está explícitamente dado.

ESTRUCTURA DE UN COMPILADOR USANDO DDS

GRAFOS DE DEPENDENCIAS

• ARBOL DE DERIVACION DECORADO O ANOTADO es un árbol de derivación que muestra los valores de los atributos de los símbolos de la grámatica, en cada nodo.•GRAFO DE DEPENDENCIA DE ATRIBUTOS, un grafo cuyos nodos son atributos y cuyos arcos representan las dependencias entre los atributos de los nodos.• GRAFO DE DEPENDENCIA es un grafo de dependencia de los atributos de los símbolos rotulando el árbol de derivación.• CALCULO DE VALORES DE ATRIBUTOS, al proceso de calcular los valores de los atributos, según las reglas semánticas, en cada nodo de un árbol de derivación se lo llama anotación o decoración del árbol de derivación.

FORMA DE UNA DDS

cada producción de la forma A tiene asociada reglas semánticas de la forma:

b = f(c1, ... , cn) donde: f es una funciónb, c1, ... , cn son atributos de los símbolos en A , b depende de c1, ... , cn.

Si b es un atributo sintetizado entonces es un atributo de A y c1, ... , cn son atributos de los símbolos de .

Si b es un atributo heredado entonces es un atributo de un símbolo en y c1,..., cn son atributos de A y de símbolos en .

(Definición dirigida por la sintaxis

NOTACION

Si b = f(c1, ... , cn) es una regla semántica entonces debe existir un arco ci b, i=1,...,n, en el grafo de dependencia de atributos.

Si f no tiene efectos colaterales puede ser una expresión. Si f tiene efectos colaterales y es escrita como una

invocación a procedimiento o un fragmento de programa define el valor de un atributo vacío (dummy) de A.

EJEMPLO DE DDS

Dada la gramática que sigue que define el L(G) = {xnynzn, n 1} construir un DDS que controle que sean iguales las cantidades de x, y y z.

<string> ::= <xstring> <ystring> <ztring> <xstring> ::= x | <xstring> x <ystring> ::= y | <ystring> y <zstring> ::= z | <zstring> z En una DDS los símbolos terminales tienen sólo atributos

sintetizados que son provistos por el scanner. El símbolo distinguido de la gramática no posee atributos

heredados.