Análisis Lexicografico

ANÁLISIS LEXICOGRÁFICO

Un analizador léxico y/o analizador lexicográfico (en inglés scanner) es la primera fase de un compilador consistente en un programa que recibe como entrada el código fuente de otro programa (secuencia de caracteres) y produce una salida compuesta de tokens (componentes léxicos) o símbolos. Estos tokens sirven para una posterior etapa del proceso de traducción, siendo la entrada para el analizador sintáctico (en inglés parser).

La especificación de un lenguaje de programación a menudo incluye un conjunto de reglas que definen el léxico. Estas reglas consisten comúnmente en expresiones regulares que indican el conjunto de posibles secuencias de caracteres que definen un token o lexema.

En algunos lenguajes de programación es necesario establecer patrones para caracteres especiales (como el espacio en blanco) que la gramática pueda reconocer sin que constituya un token en sí.

 FUNCIONES DE ANALIZADOR LEXICOGRÁFICO

El analizador léxico es la primera fase de un compilador. Su principal función consiste en 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. Esta interacción, suele aplicarse convirtiendo al analizador léxico en una subrutina o corrutina del analizador sintáctico.

Recibida la orden “Dame el siguiente componente léxico” del analizador sintáctico, el analizador léxico lee los caracteres de entrada hasta que pueda identificar el siguiente componente léxico.

Otras funciones que realiza:

• Eliminar los comentarios del programa.

• Eliminar espacios en blanco, tabuladores, retorno de carro, etc, y en general, todo aquello que carezca de significado según la sintaxis del lenguaje.

• Reconocer los identificadores de usuario, números, palabras reservadas del lenguaje, …,

y tratarlos correctamente con respecto a la tabla de símbolos (solo en los casos que debe

de tratar con la tabla de símbolos).

• Llevar la cuenta del número de línea por la que va leyendo, por si se produce algún error, dar información sobre donde se ha producido.

• Avisar de errores léxicos. Por ejemplo, si @ no pertenece al lenguaje, avisar de un error.

• Puede hacer funciones de preprocesador.

 FICHAS Y LEXEMAS

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

 ERRORES DE PATRONES

Regla que describe el conjunto de lexemas que pueden representar a un determinado componente léxico en los programas fuente. En otras palabras, es la descripción del componente léxico mediante una regla.

 EXPRESIONES REGULARES

Las expresiones regulares se utilizan para describir los componentes léxicos de un lenguaje o tokens. Las expresiones regulares utilizan varios tipos de operadores para definir los componentes léxicos:

- Paréntesis. Para agrupar símbolos

- Operación concatenación.

- Se permite la concatenación de cadenas.

- Operación alternativa. Se representa por, y permite la elección entre dos o más alternativas.

Con estos elementos podemos definir los componentes léxicos. Por ejemplo, para desarrollar la expresión regular para identificador, definimos su patrón y a partir se define su expresión regular.

 MÉTODO DE THOMPSON

El Método de Thompson es una manera sistemática de construir un Autómata Finito M que acepta el mismo lenguaje que una Expresión Regular dada.

Para una expresión regular s Hacemos la transformación N(s) sobre un árbol de sintaxis abstracta de la expresión recorriendo los nodos en orden de profundidad primero (depth first).

 Para un símbolo a ∈ Σ hacemos:

 Para un nodo | con subárboles s y t hacemos:

 Para un nodo ⋅ con subárboles s y t hacemos:

 Para un nodo * con subárbol s hacemos:

Ejemplo

Para la expresión regular:

((ε|a)b*)*

Construimos el siguiente árbol de sintaxis abstracta:

Para los nodos ε, a, y b, construimos los siguientes autómatas:

Para el nodo | construimos el siguiente autómata:

Para el nodo * hacemos:

Para el nodo ⋅ hacemos:

Finalmente, para el * en el nodo raíz hacemos:

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

 GRAMÁTICAS LL (k)

UNA GRAMATICA QUE CUMPLA CON LAS CONDICIONES

ANTEDICHAS:

• NO SER RECURSIVA A IZQUIERDA.

• NO SER AMBIGUA.

• SI A → α1 | α2 | ….. | αn ∈ P, con G = < ∑, N, S, P >

LOS SIMBOLOS TERMINALES CON QUE COMIENZA CADA αi DEBEN SER DISTINTOS.

SE DICE QUE ES UNA GRAMATICA LL(K)

DEFINICION:

SEA G = < N, ∑, S, P > UNA CFG, k ∈ N, A → α | β ∈ P SE

DICE QUE G ES UNA GRAMATICA LL(K) , ⇔

1. S ⇒* wAδ ⇒ wαδ ⇒* wx

2. S ⇒* wAδ ⇒ wβδ ⇒* wy

3. FIRSTK(x) = FIRSTK(y) ⇒ α=β

 CONJUNTOS FIRST (k)

Definición de firstkpara unagramática gsea una cfg g = <n, ∑, 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)

Condiciones LL (1)

Para cumplir las condiciones LL(1) la gramática debe satisfacer

...