MBA. Ing. Walter Pereira García

El proceso de análisis sintáctico La tarea del analizador sintáctico es determinar la

estructura sintáctica de un programa a partir de los tokens producidos por el analizador léxico, ya sea de manera explícita o implícita, construir un árbol de análisis gramatical o árbol sintáctico que represente esta estructura. De este modo, se puede ver el analizador sintáctico como una función que toma como su entrada la secuencia de tokens producidos por el analizador Léxico y que produce como su salida el árbol sintáctico

La secuencia de tokens por lo regular no es un parámetro de entrada explícito, pero el analizador sintáctico llama a un procedimiento del analizador léxico, como getToken, para obtener el siguiente token desde la entrada a medida que lo necesite durante el proceso de análisis sintáctico. De este modo, la etapa de análisis sintáctico del compilador se reduce a una llamada al analizador Léxico de la manera siguiente:

Sintaxtree=parse() En un compilador de una sola pasada el analizador sintáctico

incorporará todas las otras fases de un compilador, incluyendo la generación del código, y no es necesario construir ningún árbol sintáctico explícito (las mismas etapas del analizador sintáctico representarán de manera implícita al árbol sintáctico), y. por consiguiente, una llamada lo hará. Por lo común, un compilador será de múltiples pasadas, en cuyo caso las pasadas

Parse()

La estructura del árbol sintáctico depende en gran medida de la estructura sintáctica particular del lenguaje. Este árbol por lo regular se define como una estructura de datos dinámica, en la cual cada nodo se compone de un registro cuyos campos incluyen los atributos necesarios para el resto del proceso de compilación (es decir, no sólo por aquellos que calcula el analizador sintáctico). A menudo la estructura de nodos será un registro variante para ahorrar espacio. Los campos de atributo también pueden ser estructuras que se asignen de manera dinámica a medida que se necesite, como una herramienta adicional para ahorrar espacio.

Gramáticas libres de contexto Una gramática libre de contexto es una especificación

para La estructura sintáctica de un lenguaje de programación. Una especificación así es muy similar a la especificación de la estructura léxica de un lenguaje utilizando expresiones regulares, excepto que una gramática libre de contexto involucra reglas de recursividad.

Ejemplo se utilizara expresiones aritméticas simples de enteros con operaciones:

Exp exp op exp | (exp) | numero

Op +|-|*|/

Comparación de la notación con respecto a las expresiones regulares Las reglas gramaticales utilizan notaciones semejantes. Los nombres se

escriben en cursivas o itálicas (pero ahora con una fuente diferente, de modo que podamos distinguirlas de los nombres para las expresiones regulares). La barra vertical todavía aparece como el metasímbolo para selección. La concatenación también se utiliza corno operación estándar.

Sin embargo, no hay ningún metasímbolo para la repetición (como el * ), se utilizara el mismo nombre, también se utilizara el símbolo de la flecha -->. en lugar del de igualdad para expresar las definiciones de los nombres.

las reglas gramaticales se usaron por primera vez en la descripción del lenguaje Algol60. La notación fue desarrollada por John Backus y adaptada por Peter Naur para el informe AlgoL60. De este modo. generalmente se dice que las reglas gramaticales en esta forma están en la forma Backus-Naur, o BNF (Backus- Naur Form).

Derivaciones y el lenguaje definido por una gramática. Las reglas gramaticales libres de contexto determinan el

conjunto de cadenas sintácticamente legales de símbolos de token para las estructuras definidas por las reglas. Por ejemplo, la expresión aritmética: (34-3)*42

corresponde a la cadena legal de siete tokens ( número - número ) * número donde los tokens de número tienen sus estructuras

determinadas por el analizador léxico y la cadena misma es legalmente una expresión porque cada parte corresponde a selecciones determinadas por las reglas gramaticales

Exp exp op exp | (exp) | numero Op +|-|*|/ Por otra parte (34-3*42 no es una expresión legal.

Las reglas gramaticales determinan las cadenas legales de símbolos de token por medio de derivaciones. Una derivación es una secuencia de reemplazos de nombres de estructura por selecciones en los lados derechos de las reglas gramaticales. Una derivación comienza con un nombre de estructura simple y termina con una cadena de símbolos de token. En cada etapa de una derivación se hace un reemplazo simple utilizando una selección de una regla gramatical.

Ejemplo para (34-2)*42

Derivaciones Una derivación por la izquierda es aquella con la cual

se reemplaza el no terminal más a la izquierda en cada paso con la derivación. Corresponde también a una numeración preorden de los nodos internos de su árbol.

Una derivación por la derecha es aquella en la cual el no terminal más a la derecha se reemplaza en cada paso de la derivación. Corresponde también a una numeración postorden en reversa.

Árboles de análisis gramatical Una derivación proporciona un método para construir

una cadena particular de terminales a partir de un no terminal inicial. Pero las derivaciones no sólo representan la estructura de Las cadenas que construyen. En general, existen muchas derivaciones para la misma cadena.

ejemplo

( número - número )

Un árbol de análisis gramatical corresponde a una derivación es un árbol etiquetado ,en el cual los nodos interiores también están etiquetados por no terminales, los nodos hoja están etiquetados por terminales y los hijos de cada nodo interno representan el reemplazo del no terminal asociado con un paso de la derivación.

Ejemplo 2: (34-3)*42

Ejercicios Realice la gramática, las derivaciones y el árbol

gramatical para:

45+3*2-4

Un ciclo while en c