Analisis Lexico

Análisis Léxico

Cuando definimos la gramática G mencionamos los 4 componentes de la cuádrupla como Vn,
Vt, Start y las producciones R. Las mismas son partes del modelos matemáticos que definen
palabras que constituyen un lenguaje llamado lenguaje definido por la gramática L(G).
x}
Formalmente este lenguaje se define como L(G)={x/x pertenezca a Vt* y S
Es decir que el lenguaje que genera lagramática G es el conjunto de todas las palabras que
siendo cadenas de terminales tiene un árbol de derivación con raíz en S y las hojas del mismo
concatenados constituyen la tira x.
Ejemplo
Sea G la gramática definida por Vt={S},Vn={a,b}, S Start
Y las producciones SÆaSb, SÆab.
En este caso el lenguaje que genera es L(G)={ab, aabb, aaabbb, …., anbn, ….}.
Las palabras que determinan este lenguaje sontodas aquellas que cumplen con las dos
proposiciones que aparecen como conjunción en la definición formal. Es decir que cada
palabra debe satisfacer ambas condiciones ,1- pertenecer a Vt* ( cadena de terminales) y
2- existir el árbos de derivación correspondiente.
Tomemos una palabra cualquiera del lenguaje por ejemplo aaabbb
La primera proposición la cumple. ya que pertenece al conjunto decadenas de la clausura de
Vt, o lo que es lo mismo, es una cadena de terminales.
En cuanto a la segunda proposición necesitamos disponer de las producciones de una manera
particular para construir el árbol de derivación

Remarquemos aquí la importancia que presenta la definición como conjunción de las dos
proposiciones.
La cadena ababab también es una cadena de terminales (Cumple con la primeraproposición)
pero no pertenece al lenguaje ya que no existe una forma de presentar las producciones para
obtener el árbol de derivación. Cumple la primera preposición pero no la segunda.
Para pertenecer al lenguaje tiene que cumplir ambas proposiciones ya que es una conjunción.
Otra palabra como aSb cumple con la segunda proposición. Es fácil ver que basta con una de
las producciones iniciales. Es estecaso el problema es que dicha palabra no cumple con la
primera proposición porque la cadena formada con las hojas del árbol no es una cadena de
terminales debido a la presencia en la misma del símbolo S que es no Terminal.

***********************************************************************************************

Con esta idea vamos a hacer el mismo análisis pero considerando unagramática un poco mas
complicada.
Æ if EXP then PROP
If EXP then PROP else PROP
&
EXP
ÆTERMINO oprel TERMINO
TERMINO
TERMINO Æ id
num

PROP

Esta gramática podría ser un fragmento de una gramática Pascal.
En ella tenemos Vt= {if,then,else,oprel,id,num}
Vn= {EXP,PROP,TERMINO}
Start=PROP

El lenguaje que genera esta gramática es
*
L(G)={x/x pertenece a { if,then,else,oprel,id,num} y PRO

x}

Por ejemploL(G)={(if)(id)(oprel)(num)(then),(if)(id)(oprel)(id)(then)(if)(id)(oprel)(num)(then), ...}
Es fácil ver como ejemplo, (if)(id)(oprel)(num)(then) pertenece al lenguaje, ya que cumple con
ambas proposiciones requeridas en la definición formal.
En primer lugar es una cadena de terminales y, en segundo, se puede armar el árbol de
derivación

&
Ahora bien, vemos como se mantiene la idea de la definiciónlenguaje que genera una
gramática ya sea en una forma elemental como en el primer caso o en una más compleja

como en el segundo.
Es bueno aclarar, a esta altura, que los compiladores se dividen en módulos de los cuales
parece oportuno mencionar que el primero de los mismos, el analizador léxico, es el encargado
de validar si cada renglón del programa fuente cumple con la primera proposiciónmencionada
antes, es decir, verificar si cada palabra cumple con ser una cadena de terminales, mientras
que el segundo módulo, analizador sintáctico, es el encargado de verificar si con lo aprobado
por el léxico se puede armar el árbol de derivación, o sea cumple con la segunda proposición
S

x.

Sintéticamente el cumplimiento de las proposiciones mencionadas se reflejan en la función de
ambos...