Análisis Lexicográfico 3m5y1f

República Bolivariana de Venezuela Ministerio de Educación Superior Sección II Ingeniería en Informática

Autores

Guatire, 12 de Septiembre de 2014

Introducción

Los árboles sintácticos en la práctica son realmente difíciles de construir porque ocuparían mucho espacio. Alternativamente se usan pilas.

En la Pila se guarda información sobre los nodos delárbol sintáctico relevantes en cada fase del proceso.Teoría Lenguajesárbol sintáctico relevantes en cada fase del proceso.Para el caso descendente: en la pila se guardan losnodos no expandidos.

El analizador sintáctico recibe una secuencia de tokens y decide si la secuencia está correcta o no.Los analizadores más usados están basados en un análisis que puede ser descendente o ascendente. Para realizar este análisis se deben construir los árboles sintácticos (derivación).árboles sintácticos (derivación).Dificultad: Búsqueda de la regla a aplicar, esto se efectúa analizando la cadena de entrada de izquierda a derecha.Los analizadores sintácticos más eficientes se basan en gramáticas LL y LR.

•

Análisis Lexicográfico

El analizador lexicográfico, o explorador, es la parte del compilador que lee el programa fuente, carácter a carácter, y construye a partir de éste unas entidades primarias llamadas tokens. Es decir, el analizador lexicográfico transforma el programa fuente en tiras de tokens.

•

Funciones de analizador lexicográfico Función principal del analizador léxico Leer los caracteres de entrada y elaborar como salida una secuencia de componentes léxicos que utiliza el analizador sintáctico para hacer el análisis. Funciones secundarias. • Eliminar del programa fuente comentarios y espacios en blanco (caracteres de espacio en blanco, caracteres TAB, caracteres de nueva línea). • Relacionar los mensajes de error con el lenguaje fuente. En otras palabras, las funciones del analizador léxico-gráfico son: Eliminación de espacios Reconocimiento de identificadores y Reconocimiento de - Mejorar la portabilidad del compilador

•

en palabras

blanco clave constantes

Fichas y lexemas:

El analizador lexicográfico puede tener la siguiente estructura. El analizador léxico opera bajo petición del analizador sintáctico con el fin de que este pueda avanzar en la gramática. Tiene como propósito agrupar las expresiones en fichas. Estas fichas están compuestas por 3 elementos: Componentes Léxicos (Token), Lexemas, Patrones

Componente léxico (token): Son las unidades lógicas que genera el analizador léxico. Es el conjunto de cadenas de entrada que produce como salida el mismo componente léxico. Cada token es una secuencia de caracteres que representa una unidad de información en el programa fuente. Los componentes léxicos más comunes son los siguientes:           

palabras clave o reservadas operadores aritméticos operadores relacionales operadores lógicos operador de asignación identificadores constantes cadenas literales signos de puntuación librerías

Lexema: Representan cadenas de caracteres en el programa fuente que se pueden tratar juntos como una unidad léxica. Un lexema es una secuencia de caracteres en el programa fuente con la que concuerda el patrón para un componente léxico. Patrón: Regla que describe el conjunto de lexemas que pueden representar a un determinado componente léxico en los programas fuente. Atributos de los componentes léxicos: El analizador léxico recoge información sobre los componentes léxicos en sus atributos asociados. Los componentes léxicos influyen en las decisiones del análisis sintáctico y los atributos en la traducción de los componentes léxicos.

•

Errores de Patrones

Si los compiladores tuvieran que procesar solamente programas correctos, su diseño e implementación se simplificaría en buena medida. Pero los programadores escriben programas incorrectos frecuentemente, y un buen compilador debe ayudar al programador a localizar e identificar los errores. Los errores en un programa pueden clasificarse en 4 grandes grupos: -

lexicológicos (escribir mal un número, un símbolo no permitido, etc.) sintácticos (expresión aritmética con paréntesis no balanceados) semánticos (aplicar un operador a un operando incompatible)

-

lógicos o de programación (ciclo infinito)

El analizador léxico detecta errores cuando los caracteres que restan de la entrada no forman ningún token válido en el lenguaje. Los errores referentes a que los tokens no cumplan con las reglas estructurales (sintaxis) del lenguaje se detectan en la fase de análisis sintáctico. Durante el análisis semántico el compilador trata de detectar estructuras que tengan una sintaxis correcta pero incorrecta semánticamente de acuerdo a las operaciones involucradas. Ejemplo si tratamos de sumar dos identificadores, uno el nombre de un arreglo y el otro el nombre de un procedimiento. Las fases de análisis sintáctico y semántico manejan usualmente la mayor parte de los errores detectables por el compilador. Como podemos apreciar en cada fase del proceso de compilación se pueden encontrar errores. Sin embargo, después de detectado el error, la fase puede tratar el error, de manera que el compilador pueda continuar, permitiendo así que se puedan detectar errores posteriores. Un compilador que se detenga cuando encuentre el primer error no es muy eficaz. El tratamiento de los errores durante el proceso de compilación (en cualquiera de sus fases) debe cumplir al menos los requisitos siguientes: -

•

reportar la presencia de los errores clara y precisamente recuperarse de los errores lo suficientemente rápido como para ser capaz de detectar los errores siguientes no demorar significativamente el procesamiento de los programas correctos.

Expresiones regulares

Las expresiones regulares son una serie de caracteres que forman un patrón, normalmente representativo de otro grupo de carácter mayor, de tal forma que podemos comparar el patrón con otro conjunto de caracteres para ver las coincidencias. Las expresiones regulares están disponibles en casi cualquier lenguaje de programación, aunque su sintaxis es relativamente uniforme, cada lenguaje usa su propio dialecto. El poder de las expresiones regulares radica precisamente en la flexibilidad de los patrones, que pueden ser confrontados con cualquier palabra o cadena de texto que tenga una estructura conocida. De hecho normalmente no es necesario usar funciones de expresiones regulares si vamos a usar patrones literales. Existen otras funciones (las funciones de cadena) que trabajan más eficaz y rápidamente con literales. • Método de Thompson

El mismo se crea en honor a Kenneth Lane Thompson, pionero en el desarrollo de sistemas operativos y procesadores. Diseñador y colaborador del Sistema Operativo Unix, Lenguaje Bon,B,C. El algoritmo se construye a partir de expresiones regulares un diagrama de AFN, para luego poder generar un AFD mínimo equivalente. Utiliza una notación estándar para generar un AFN

Para la representación de una cadena vacía se utiliza el símboloε

Para representar un símbolo, se utilizan dos estados y una transición para el movimiento con el símbolo rs

Para la elección de alternativas, crear transicionesεpara launión de las transiciones

Elección de Alternativa

Para la cerradura Positiva, se agregan transicionesεpararetornar al estado previo, permitiendo agregar 1 omás veces el símbolo

Cerradura de Kleene Para la cerradura de Kleene, se agregan transicionesε para retornar a estado previo. Y otra transiciónεparasaltar la transición con r

r*

UNIDAD V: 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)).

• Gramáticas LL (k): Es un método predictivo, no recursivo. Suele dar buenos resultados en aplicaciones pequeñas (shells, compiladores de pequeños lenguajes, etc.) donde precedencia simple no resulta suficiente.

El método de funcionamiento es independiente del lenguaje. Al variar este solo variarla la tabla. Como ya hemos comentado alguna vez, las casillas en blanco de la tabla suponen acciones semánticas, errores. Veremos en seguida su estructura y como se construye.

•

Conjuntos First (k): Definición de firstkpara unagramática gsea una cfg g =
s, p >, k ∈n ∧α∈ (n∪∑)*se define first k: ( n ∪∑) * →∑ ≤kfirstk(α) = {w ∈∑*/ |w <= k ∧α⇒*w }dónde:αes alguna forma sentencia generada por g. El resultado es el conjunto de terminales de longitud, a lo sumo k, con que pueden comenzar las cadenas derivadas de α Propiedades de los conjuntos firstk(α)siαcomienza con un terminalx,entonces:zfirst1(α) = {x} .zsiα⇒*λ, entoncesλ⊂first k (α) z firstk(λ) = {λ}

•

Condición LL (k):Símbolos directores, ayudan a decidir qué regla utilizar en cada paso

Condiciones necesarias para ser LL(1) 

No ambigua



Factorizada por la izquierda



No recursiva a izquierdas

Se dice que una gramática cumple la condición LL(1)si para cada par de reglas de la gramática que tengan el mismo antecedente la intersección de sus símbolos directores es vacía. Es decir, Si se tienen las producciones del no terminal A: A

1|2|.....|

Nse debe cumplir que 1. PRIM(i) PRIM(j)=i j i*2.Si λ PIM(j)entoncesPRIM(i) SIG(A)=i j

•

Eliminación de la Recursión a la Izquierda

Para eliminar la recursividad por la izquierda lo que haremos será: Si tenemos A->Aa1|Aa2|...|Aap|b1|b2|...|bq podemos escribirlo como A->Aai 1<=i<=p A->bj 1<=j<=q Para quitar la recursividad por la izquierda escribimos A->biA' 1<=i<=q, A' nuevo símbolo e Te

A'->ajA'|l 1<=j<=p

•

Análisis recursivo descendente: Esta es la fase en la construcción del analizador

donde la fase de análisis es sintáctico. Esta toma como entrada el flujo de terminales y construye como salida el árbol de análisis sintáctico abstracto. El árbol de análisis sintáctico abstracto es una representación compactada del árbol de análisis sintáctico concreto que contiene la misma información que éste. Existen diferentes métodos de análisis sintáctico. La mayoría caen en una de dos categorías: ascendentes y descendentes. Los ascendentes construyen el árbol desde las hojas hacia la raíz. Los descendentes lo hacen en modo inverso. El que describiremos aquí es uno de los más sencillos: se denomina método de análisis predictivo descendente recursivo.

•

Analizador predictivo no recursivo:Es posible construir un analizador sintáctico

predictivo no recursivo (APNR) manteniendo una pilapara no usar la recursividad.Estos analizadores buscan la producción a usar dentro de una tabla de análisis sintáctico. Dentro de una tabla de análisis sintáctico.También se conocen como analizadores sintácticos dirigidos por tablas.Un método descendente dirigido por tablas es el método que se basa en gramáticas LL(1)

•

Algoritmos de Análisis predictivo:Análisis descendente recursivo (ARD)Método

descendente en el que se ejecuta un conjunto de métodos recursivos para procesar la entrada.A cada no terminal de la gramática se asocia un método.La secuencia de métodos llamados durante elprocesamiento de la entrada define implícitamente unTeoría Lenguajesprocesamiento de la entrada define implícitamente unárbol de análisis sintáctico. Adicionalmente se tiene:»Un método de tratamiento de error »Un método de lectura de un símbolo de entrada (léxico)

Una forma eficiente de un analizador sintáctico descendente sin retroceso es el denominado Analizador sintáctico predictivo.Preliminar: Dado un símbolo de entrada ay el no terminal A con Teoría Lenguajes6Dado un símbolo de entrada ay el no terminal A con la siguiente producción:A →→→→ αααα1 αΑαα2

3

. . . ααααnes necesario conocer la única alternativa que

comienzacon el símbolo a

UNIDAD VI: Análisis Descendente El análisis sintáctico descendente es una técnica de análisis sintáctico que intenta comprobar si una cadena x pertenece al lenguaje definido por una gramática L(G) aplicando los siguientes criterios: – – – – –

Partir del axioma de la gramática Escoger reglas gramaticales estratégicamente Hacer derivaciones por la izquierda (LeftMostDerivation) Procesar la entrada de izquierda a derecha Obtener el árbol de análisis sintáctico o error

• Implementación por pila de un analizador corrimientos-reducción: En el área de los lenguajes formales, un analizador de sintaxis por precedencia simple es un tipo de analizador sintácticoascendente para gramáticas libres de contexto que pueden ser utilizados para reconocer gramáticas de precedencia simple. La implementación del parser es bastante similar al analizador sintáctico ascendente genérico. Una pila es utilizada para almacenar el prefijo viable de una forma sentencial de una derivación más a la derecha. Los símbolos , y son utilizados para identificar el pivote, por lo tanto sabremos cuando Desplazar o cuando Reducir.

•

Prefijos viables:Son los posibles contenidos de la pilapara cada regla de la

gramática:Hemos de decidir cuándo convieneusarla para reducir m, es decir, y sabiendolo que hay en la pila",y sabiendo cual es el próximo símbolo de la entrada,saber si hemos de reducir por esa regla o no.Consideramos un paso intermedio de la derivación derecha: que esnecesario conocer para saber cuál fue el paso anterior

• Gramáticas LR (k):Este tipo de analizadores recibe este nombre por lo siguiente: la L hace referencia a qué el examen de la entrada se realiza de izquierda a derecha; la R se debe a que las reconstrucciones en orden inverso nos llevan a derivaciones por la derecha y la K, como ya imaginamos, es por el número de símbolos de anticipación que se necesitan para una correcta toma de decisiones.

•

Método SLR: La condición que impone el análisis LR(0), como ya hemos dicho, es

muy restrictiva, ya que los ítems completos han de aparecer en conjuntos separados. Esto no se cumple en la mayoría de las gramáticas que describen lenguajes de programación. Sin embargo existe una forma sencilla de ampliar la aplicación de ésta a una gama más amplia de gramáticas, mediante la lectura de un símbolo en la entrada para determinar la función a realizar. Cuando una máquina de reconocimiento LR está en un determinado estado, el conjunto de ítems válidos para la subcadena que se encuentra en la pila en ese momento es precisamente el conjunto de la colección asociado a dicho estado. Si en este conjunto aparece un ítem completo y otro ítem más (ya sea completo o no), se produce un conflicto en el análisis LR(0), ya que no podemos decidir qué acción realizar. El caso del análisis de la cadena tas. (t,a,s pertenecen a T, que en un momento determinado del análisis, y tras leer la subcadena t, tendremos en la pila una subcadena viable

, quedando por leer aún la subcadena as. Esto nos indica que

as es una forma

sentencial del lenguaje. Supongamos también que existe un ítem completo válido asociado a esta subcadena viable, de la forma [A -> ·]. Tras efectuar la reducción correspondiente obtendríamos la tira

Aas, que debe ser una forma sentencial de nuestro lenguaje. Es

evidente que una condición necesaria para que esto suceda es que el símbolo a pueda aparecer a la derecha de A en alguna forma sentencial. Es decir, que a pertenezca al conjunto SIGUIENTE(A), tal y como se definió en el apartado dedicado al análisis LL(1). Bibliografía:

http://www.google.co.ve/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CB0QFj AA&url=http%3A%2F%2Fwww.dirinfo.unsl.edu.ar%2Fcompi%2Forganizacion%2Fproco m02.doc&ei=cMkRVK6vFYHLgwTNhYG4Dg&usg=AFQjCNERfazPR6QnMdnx0Px9V QV4HtUYQg

http://www.dirinfo.unsl.edu.ar/compi/teorias/as-2010.pdf

http://ocw.unican.es/ensenanzas-tecnicas/teoria-de-automatas-y-lenguajesformales/material-de-clase-nuevo/nuevo/4-6LL%28K%29_II.pdf

http://nereida.deioc.ull.es/~pl/perlexamples/node84.html http://www.educaunica.galeon.com/cursos/silabo_diapositiva/SintacI.pdf

http://es.wikipedia.org/wiki/Analizador_sint%C3%A1ctico_de_precedencia_simple