Análisis Sintáctico y Gramáticas GLC
Cargado por
ArturoEspinozaaAnálisis Sintáctico y Gramáticas GLC
Cargado por
ArturoEspinozaaInstituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Capítulo 6: Análisis Sintáctico.
6.1 GLC
En lingüística e informática, las Gramáticas Libres de Contexto (GLC) o, en inglés,
Context Free Grammars (CFG), juegan un papel central en el procesamiento de
lenguaje natural desde los 50’s y en los compiladores desde los 60’s. De acuerdo
con la mayoría de los autores, las GLC son un conjunto finito de símbolos o
variables que representan categorías aplicables a elementos léxicos y son muy
útiles para definir relaciones entre objetos sintácticos tales como la sintaxis de un
lenguaje de programación.
Una Gramática Libre de Contexto o de contexto libre, es una gramática formal en
la que cada regla de producción es de la forma: V → w
donde V es un símbolo no terminal y w es una cadena de terminales y/o no
terminales. El término libre de contexto se refiere al hecho de que el no terminal V
puede siempre ser sustituido por w sin tener en cuenta el contexto en el que
ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de
contexto que lo genera.
Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes
de programación, de hecho, la sintaxis de la mayoría de lenguajes de
programación está definida mediante gramáticas libres de contexto. Por otro lado,
estas gramáticas son suficientemente simples como para permitir el diseño de
eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres
dada determinen cómo puede ser generada desde la gramática. Los analizadores
LL y LR tratan subconjuntos restringidos de gramáticas libres de contexto. Donde
por ejemplo LL se refiere a que dicho analizador opera con lecturas de la entrada
iniciando por la izquierda y realizando derivaciones por la izquierda, LR es
análogo.
La notación más frecuentemente utilizada para expresar gramáticas libres de
contexto es el metalenguaje Backus-Naur-Form (BNF) o Forma Normal de Backus
(ver Cap. 1).
6.1.1. Lenguajes formales
Los lenguajes pueden ser definidos a través de la gramática que los genera.
Gramática: es la descripción completa de un lenguaje. Una gramática consiste de
un conjunto de reglas donde está definido cada símbolo no terminal. Uno de los
102
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
símbolos no terminales se marca como símbolo inicial y es el punto de partida de
la gramática, por ejemplo la palabra reservada Program en Pascal.
Definición: Gramática
Formalmente una gramática se define como sigue:
G(T, N, P, S)
donde:
T es el conjunto de símbolos terminales
N es el conjunto de símbolos no terminales
P es el conjunto de producciones
S ∈ N es el símbolo inicial.
Lenguaje formal L: se caracteriza con referencia a una gramática G,
L(G) = L(T, N, P, S)
Ejemplo: La siguiente es una gramática libre de contexto:
G1 (T1, N1, P1, S1) donde:
T1 = {0, 1}
N1 = {A}
P1 = { A → 0 A 1 | ε }
S1 = {A}
El lenguaje generado por esta gramática es: L(G)={0n1n | n>=1}, es decir, cadenas
con igual número de 1s y 0s en forma consecutiva.
6.2 Árboles de derivación.
Un árbol de derivación permite mostrar gráficamente cómo se puede derivar
cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática
que genera ese lenguaje.
Un árbol es un conjunto de puntos, llamados nodos, unidos por líneas, llamadas
arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de
nodos y arcos debe satisfacer ciertas propiedades:
• Hay un único nodo distinguido, llamado raíz (se dibuja en la parte superior)
que no tiene arcos incidentes.
• Todo nodo c excepto el nodo raíz está conectado con un arco a otro
nodo k, llamado el padre de c (c es el hijo de k). El padre de un nodo, se
dibuja por encima del nodo.
• Todos los nodos están conectados al nodo raíz mediante un único camino.
103
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
• Los nodos que no tienen hijos se denominan hojas, el resto de los nodos se
denominan nodos interiores. Ver Fig. 6.1.
• Algunas veces se utilizan círculos para representar nodos, pero también se
pueden representar solo los arcos y los contenidos de los nodos, sin los
círculos.
Nodo raíz
Nodos interiores
Hojas
Figura 6.1. Ejemplo de Árbol.
Propiedades de un árbol de derivación.
Sea G = (N, T, S, P) una gramática libre de contexto, sea A ∈ N una variable
entonces, un árbol etiquetado TA, es un árbol de derivación asociado a G si
verifica las propiedades siguientes:
o La raíz del árbol es un símbolo no terminal
o Cada hoja corresponde a un símbolo terminal o ε (cadena vacía).
o Cada nodo interior corresponde a un símbolo no terminal.
Para cada cadena del lenguaje generado por una gramática es posible construir
(al menos) un árbol de derivación, en el cual cada hoja tiene como rótulo uno de
los símbolos de la cadena.
Si un nodo está etiquetado con una variable X y sus descendientes (leídos de
izquierda a derecha) en el árbol son X1,…,Xk , entonces hay una producción X →
X1…Xk en G.
Sea G=(N, T, S, P) una GLC. Un árbol es un árbol de derivación para G si:
1. Todo vértice tiene una etiqueta tomada de T ∪ N ∪ { ε }.
2. La etiqueta de la raíz es el símbolo inicial S.
3. Los vértices interiores tienen etiquetas de N.
104
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
4. Si un nodo n tiene etiqueta A y n1n2...nk respectivamente son hijos del
vértice n, ordenados de izquierda a derecha, con etiquetas x1,x2..xk
respectivamente, entonces: A→ x1x2...xk debe ser una producción en P.
5. Si el vértice n tiene etiqueta ε, entonces n es una hoja y es el único hijo de
su padre.
Ejemplo:
Sea G=(N, T, S, P) una GLC con P: S→ ab|aSb. La derivación de la
cadena aaabbb será: S ⇒ aSb ⇒ aaSbb ⇒ aaabbb y el árbol de derivación se
muestra en la Fig. 6.2.
a S b
a S b
a b
Figura 6.2 Árbol de Derivación para la cadena aaabbb.
Si leemos las etiquetas de las hojas de izquierda a derecha tenemos una
sentencia. Llamamos a esta cadena la producción del árbol de derivación.
Derivación directa: una cadena β puede derivarse directamente a partir de α,
denotada como α→β, si existe una sola producción que produce β a partir de α.
Por ejemplo se puede derivar β=α1β2α3 a partir de α=α1α2α3, si existe la
producción: α2→β2.
Derivación: αn se puede derivar de una cadena α0 si y solo si existe una secuencia
de cadenas α0, α1, α2, …, αn-1, tal que cada αi puede derivarse directamente de αi-
1 (i= 1, 2, …, n)
α0→α1→α2→ … →αn-1αn
Esta secuencia se puede abreviar como α0 ⎯
⎯→
*
αn, y ⎯
⎯→
*
se conoce como la
cerradura transitiva y reflexiva de →.
Definición: Ahora podemos definir un lenguaje L(G) como el conjunto de todas las
cadenas de símbolos terminales que pueden derivarse del símbolo inicial S.
L = {σ | S ⎯
⎯→
*
σ y σ∈T*}
105
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
6.2.1 Propiedades y definiciones (relacionados con gramáticas)
Estrategias de derivación: Existen dos estrategias en el proceso de derivación
a) Derivaciones por la izquierda
Una derivación es denominada por la izquierda, si siempre se reemplaza el
no terminal más a la izquierda.
b) Derivaciones por la derecha
Una derivación es denominada por la derecha, si siempre se reemplaza el
no terminal más a la derecha.
Ejemplo: Sea la gramática G0 (T0, N0, P0, S0)
T0 = {x, y, +, -, *, /, (, )}
N0 = {expr, term, factor}
P0 = { expr→term | expr + term | expr – term
term→ factor| term * factor| term/factor
factor → x | y | (expr)
}
S0 = {expr}
que acepta expresiones aritméticas x + y – x * y.
La derivación por la izquierda de x+ y – x * y, sería:
expr → expr – term
→ expr + term – term
→ term + term – term
→ factor + term – term
→ x + term – term
→ x + factor – term
→ x + y – term
→ x + y – term * factor
→ x + y – factor * factor
→ x + y – x * factor
→x+y–x*y
106
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejercicio: hacer el árbol sintáctico.
- La derivación por la derecha de x + y – x * y, sería:
expr → expr – term
→ expr – term * factor
→ expr – term * y
→ expr – factor * y
→ expr – x * y
→ expr + termino – x * y
→ expr + factor – x * y
→ expr + y – x * y
→ term + y – x * y
→ factor + y – x * y
→x+y–x*y
Definición: Producciones independientes del contexto.
Una regla BNF ν→σ especifica que un solo símbolo no terminal ν∈N puede ser
sustituido por σ∈(N∪T*) sin importar el contexto donde aparezca ν.
Definición: lenguajes independientes del contexto.
Una gramática y su lenguaje correspondiente son independientes de contexto si y
solo si pueden definirse con un conjunto de producciones independientes del
contexto.
Definición: Gramáticas no ambiguas.
Una gramática independiente del contexto es no ambigua, si y solo si hay una sola
derivación por la derecha (o por la izquierda) y, por lo tanto, un solo árbol de
análisis sintáctico (es decir, la secuencia de derivaciones representada como una
estructura de árbol) para cada frase que pueda derivarse con las producciones de
la gramática.
Definición: Gramáticas ambiguas.
Una gramática independiente del contexto es ambigua, si hay más de un árbol de
análisis sintáctico y por consiguiente más de un significado.
Ejemplo: La gramática cuyo conjunto de reglas es
S → AA
A → aSa
A→a
107
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
es ambigua, ya que es posible elaborar más de un árbol sintáctico, por ejemplo
para la palabra o cadena “aaaaa” (Fig. 6.3).
Figura 6.3 árboles de derivación diferentes para la cadena “aaaaa”.
Se pueden definir otras gramáticas que producen el mismo lenguaje que G0.
Sea la gramática G’0 (T’0, N’0, P’0, S’0)
T’0 = {x, y, +, -, *, /, (, )}
N’0 = {exp, op}
P’0 = { exp→exp op exp| (exp) | x | y
op → +|-|*|/
}
S’0 = {exp}
Ejemplo: derivar x + y – x * y, y ver que se pueden derivar dos árboles para la
misma expresión.
La derivación por la izquierda sería como sigue:
exp → exp op exp
→x + exp op exp
→x + y - exp op exp
→x + y - x * y
El árbol de derivación (Fig. 6.4) provee la expresión (x + (y - (x * y)))
108
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
exp
exp op+ exp
exp op exp
exp op exp
x + y ‐ x * y
Figura 6.4 Árbol de derivación representando la expresión (x + (y - (x * y))).
Por otro lado, la derivación por la izquierda permite la siguiente derivación
exp → exp op exp
→ exp op exp op exp
→x + exp op exp op exp
→x + x - x op exp
→x + y - x * y
El árbol de derivación (Fig. 6.5) provee la expresión (x + (y - x)) * y
exp
exp op+ exp
op+ exp exp
exp op exp
x + y ‐ x * y
Figura 6.5 Árbol de derivación representando la expresión (x + (y - x)) * y
Otra variante de la misma gramática, pero que genera el mismo lenguaje es la
siguiente:
109
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Sea la gramática G’’0 (T’’0, N’’0, P’’0, S’’0)
T’’0 = {x, y, +, -, *, /, (, )}
N’’0 = {expr}
P’’0 = { expr→expr + expr| expr –expr | expr * expr| expr / expr| (expr) |x | y
}
S’’0 = {expr}
Una posible derivación para la cadena “x + y - x * y” es la siguiente:
expr → expr op expr
→x + expr op expr
→x + y - expr op expr
→x + y - x * y
ACTIVIDAD: Generar el árbol (x + (y – (x * y)))
Otra derivación para la misma cadena es:
expr → expr op expr
→ expr op expr op expr
→x + expr op expr op expr
→x + x - x op expr
→x + x - x * y
ACTIVIDAD: Generar el árbol x + (y - x)) * y
Definición: Gramática lineal izquierda.
Se dice que una gramática lineal izquierda si cada producción P tiene la forma
A→Ba o A→a, donde A y B están en N y ‘a’ esta en T*.
Definición: Gramática lineal derecha.
Se dice que una gramática lineal derecha si cada producción P tiene la forma
A→aB o A→a, donde A y B están en N y ‘a’ esta en T*.
Las gramáticas lineales derechas e izquierdas se conocen como regulares (o de
estado finito)
Definición: Símbolo no terminal recursivo.
Un símbolo no terminal X∈N en una gramática G(T, N, P, S) independiente de
contexto, es recursivo si X ⎯
⎯→
*
αXβ, para cualquier α y β.
110
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
X es recursivo izquierdo si α=ε
X es recursivo derecho si β=ε
6.3 Formas normales de Chomsky (FNC).
Definición de la Forma Normal de Chomsky
Una Gramática Libre de Contexto (GLC), G=(N,T,P,S) que no genera la cadena
vacía, está en FNC cuando todas sus reglas son de la forma:
A → BC o
A → a, con A, B, C Nya T
Teorema. Todo Lenguaje Libre de Contexto (LLC), L que no incluye la cadena
vacía, es generado por una gramática en FNC.
Excepcionalmente se permite la producción S → ε cuando ε ∈ L(G).
La idea de la transformación de una gramática a FNC se ejecuta en dos pasos:
1. Hacer que en la parte derecha de las producciones de longitud mayor o
igual que dos sólo haya terminales.
2. Dividir estas producciones para que tengan longitud dos.
Expresando formalmente estos dos pasos:
1. Para cada producción de la forma A → α1α2 … αn, αi∈(N∪T), n≥2.
Para cada αi, si αi es terminal: αi = a∈T
- Se añade la producción Ca → a
- Se cambia αi por Ca en A → α1..αn
2. Para cada producción de la forma A → B1...Bm, m ≥ 3
a) Se añaden (m-2) no terminales D1, D2, ..., Dm-2 (distintos para cada
producción)
b) La producción A → B1...Bm se reemplaza por
A → B1D1, D1 → B2D2, ... Dm-2 → Bm-1Bm
El algoritmo que implementa a estos dos pasos para la obtención de gramáticas
en FNC es el siguiente:
Entrada: G=(N,T,P,S) (sin producciones unitarias ni vacías)
Salida: G=(N'',T”,P'',S”)
111
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Método:
PASO 1
N'=N; P'= ;
Para toda regla (A → α) de P hacer
Si |α|=1 entonces añadir la regla a P' (*ya esta en FNC*)
Si no sea α=X1X2...Xm con m > 1
Para i=1 hasta m hacer
Si Xi=a Σ Entonces
Se añade a N' un nuevo no terminal Ca
Se añade a P' una nueva regla (Ca→ a)
finsi
finpara
Se añade a P' una regla (A → X'1X'2...X'm) con:
X'i=Xi si Xi N
X'i=Ca si Xi = a Σ
finSi
finPara
NOTA: al finalizar el PASO 1 todas las reglas de la gramática resultante
G'=(N',T’,P',S’) presentarán la forma:
A→a
A → B1B2...Bm con A N', Bi N' 1≤ i≤ m, a Σ.
Entonces esta gramática G' está en Forma Normal de Chomsky intermedia.
PASO 2
(*Se toma como entrada la gramática G' resultante del PASO 1*)
N''=N'; P''= ;
Para toda regla (A → α) de P' hacer
Si |α| < 3
Entonces añadir la regla a P'' (*ya esta en FNC*)
Si no sea α = B1B2 ...Bm con m > 2
Añadir a N' los no terminales {D1, D2, ..., Dm-2}
Añadir a P'' el siguiente conjunto de reglas:
A → B1D1
D1→ B2D2
...
Dm-3 → Bm-2Dm-2
Dm-2 → Bm-1Bm
finSi
finPara
La gramática resultado es G'' = (N'',T”,P'',S”).
fin_del_Método
112
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejemplo: Sea la GLC G definida por las siguientes reglas:
S → bA | aB
A → bAA | aS | a
B → aBB | bS | b
Tras la aplicación del PASO 1 se obtiene la gramática en FNC intermedia G':
S → CbA | CaB
A → CbAA | CaS | a
B → CaBB | CbS | b
Ca→ a
Cb→ b
A partir de G', tras el PASO 2 se obtiene la gramática en FNC G'':
S → CbA | CaB
A → CbD1 | CaS | a
D1→ AA
B → CaD2 | CbS | b
D2→ BB
Ca→ a
Cb→ b
6.4 Diagramas de sintaxis.
Un diagrama de sintaxis (también llamados diagramas de Conway) es un grafo
dirigido donde los elementos no terminales aparecen como rectángulos, y los
terminales como círculos o elipses.
Todo diagrama de sintaxis posee un origen y un destino, algunas veces esto es
representado mediante flechas y usualmente se asume que el origen se encuentra
a la izquierda del diagrama y el destino a la derecha.
De esta forma todos los posibles caminos desde el inicio del grafo hasta el final,
representan formas sentenciales válidas.
BNF nos permite representar la estructura sintáctica de un lenguaje. Los grafos
sintácticos o diagramas de sintaxis son otra alternativa.
De acuerdo con Teufel et al (1993), existen 6 reglas sintácticas equivalentes a la
notación BNF.
Existen 6 reglas sintácticas equivalentes a la notación BNF.
113
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
R1. Múltiples opciones: Producciones de la forma N → S1 |S2 … |Sn, se
representan con el grafo de la Fig. 6.6.
S1
S2
...
Sn
Figura 6.6 Grafo sintáctico para representar múltiples opciones (alternativas)
R2. El grafo sintáctico para los términos de la forma α = S1 S2 … Sn, se puede
representar como muestra la Fig. 6.7.
S S ... Sn
Figura 6.7 Grafo sintáctico para secuencia de símbolos no terminales
Repetición: Los grafos sintácticos para expresar repeticiones (R3 y R4) son
mostrados en la Fig. 6.8.
R3. Cero o más veces: N → S*, a veces representado también como {S}, para
indicar que la S puede aparecer cero o más veces.
R4. Cero o una ocurrencia: [S], indica que S puede aparecer cero o una vez.
a) {S}
b) [S]
S
Figura 6.8 Grafos sintácticos para representar repetición
R5. Representación de símbolo no terminal. Se representan dentro de una caja,
como se muestra en la Fig. 6.9.
114
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Figura 6.9 Grafo sintáctico para representar símbolos no terminales
R6. Referencia a un símbolo terminal: El grafo sintáctico para expresar la
referencia a un símbolo terminal, encierra al terminal en un circulo o en un
ovalo como es mostrado en la Fig. 6.10.
t
Figura 6.10 Grafo sintáctico para representar condicional
Con ayuda de estos diagramas (R1 a R6) podemos representar la sintaxis de
cualquier lenguaje, tal como lo podemos hacer utilizando la notación BNF.
Ejemplo: Sea la gramática G6(T6, N6, P6, S6), donde:
T6 = { id, +, -, *, /, (, ) }
N6 = {E, T, F}
P6 = { E → T{(+ | -)T},
T → F {(* | /)F},
F → id | (E) }
S6 = {E}
Note que la primera y última llave en P6, denotan el conjunto de producciones,
mientras que las llaves internas, indican repetición. Los grafos sintácticos de G6 se
muestran en la Fig. 6.11.
T F
E T
+ *
T F *
- /
F id
( E )
Figura 6.11 Grafo sintáctico para la gramática G6.
115
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Actividades sugeridas para el estudiante:
Realizar lo siguiente:
1. Definir una gramática para los números enteros y después representarla
usando la notación de grafos
2. Teniendo una gramática y la derivación de una cadena, representar dicha
derivación como un árbol de derivación
3. Contando con la gramática de PL/0 en BNF, representarla con la notación
de grafos sintácticos.
6.5 Eliminación de la ambigüedad.
6.5.1 Ambigüedad en una Gramática Libre de Contexto (GLC).
Una Gramática Libre de Contexto G, es ambigua si existe una cadena en el
lenguaje L generado por dicha gramática w∈L(G), que tiene más de una
derivación por la izquierda o más de una derivación por la derecha o si tiene dos o
más árboles de derivación. En caso de que toda cadena w∈L(G) tenga un único
árbol de derivación, la gramática no es ambigua. Los siguientes son ejemplos de
gramáticas ambiguas.
Ejemplo: La gramática S→aS|Sa|a, es ambigua porque “aa” tiene dos
derivaciones por la izquierda (Fig. 6.12).
S ⇒ aS ⇒ aa
S ⇒ Sa ⇒ aa
Figura 6.12. Dos derivaciones para “aa” con la gramática ambigua S→aS|Sa|a
Ejemplo: La gramática para expresiones aritméticas sobre las variables x y y cuyo
conjunto de reglas de producción es el siguiente:
1) E→E+E
2) E→E*E
3) E→x
4) E→y
es ambigua porque la cadena x + y * x tiene dos árboles de derivación (Fig.
6.13).
116
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Figura 6.13. La cadena “x + y * x” tiene dos derivaciones dentro de la gramática
ambigua que la deriva
6.5.2 Tipos de ambigüedad
Existen dos tipos fundamentales de ambigüedad, que son:
1. Ambigüedad Inherente:
Es el tipo de ambigüedad que no puede eliminarse completamente de una
gramática por más transformaciones que se le hagan. Es por ello que si una
gramática presenta este tipo de ambigüedad, no puede utilizarse para definir un
lenguaje de programación.
Un lenguaje L es inherentemente ambiguo, si todas las gramáticas que lo definen
son ambiguas. Sin embargo, si existe al menos una gramática no ambigua para L,
L no es ambiguo. Así por ejemplo, el lenguaje de las expresiones no es
inherentemente ambiguo y las expresiones regulares tampoco son inherentemente
ambiguas.
El siguiente es un ejemplo reportado en la literatura, de un lenguaje libre de
contexto (LLC) inherentemente ambiguo, está formado por la siguiente unión:
L = {anbncmdm | n ≥ 1, m ≥ 1} ∪ {anbmcmdn | n ≥ 1, m ≥ 1}
Una gramática que genera este lenguaje puede ser la siguiente:
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
La gramática es ambigua, hay cadenas con más de una derivación más izquierda.
Considere la cadena “aabbccdd” (m = n = 2), esta puede ser generada por dos
árboles diferentes (Fig. 6.14).
S AB aAbB aabbB aabbcBd aabbccdd
117
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
S C aCd aaDdd aabDcdd aabbccdd
S S
A B
C
a A b c B d
a C d
a b c d
a D d
b D c
b c
Figura 6.14. Estructuras diferentes para la cadena “aabbccdd” indicando que
provienen de una gramática ambigua
2. Ambigüedad Transitoria
Este tipo de ambigüedad puede llegar a ser eliminada realizando una serie de
transformaciones sobre la gramática original. Una vez que se logra lo anterior, la
gramática puede ser reconocida por la mayoría de los analizadores sintácticos.
Generalmente la Ambigüedad Transitoria se presenta en dos casos, cuando:
1. Existen producciones con factores comunes (distintas alternativas para un
símbolo no-terminal que inician de la misma forma);
2. Existen producciones que son recursivas izquierdas (producciones para un
símbolo no-terminal en las cuales el primer símbolo de su forma sentencial
es ese mismo símbolo no-terminal).
Para solucionar el problema de la Ambigüedad Transitoria, es necesario, primero
eliminar factores comunes izquierdos inmediatos y no-inmediatos y la
Recursividad izquierda inmediata y no-inmediata.
6.5.3 Eliminación de la ambigüedad.
No existe un algoritmo que nos indique si una Gramática Libre de Contexto (GLC)
es ambigua. Existen LLC que sólo tienen GLC ambiguas, es decir inherentemente
ambiguos.
118
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Para las construcciones de los lenguajes de programación comunes existen
técnicas para la eliminación de la ambigüedad.
Ejemplo: Da la siguiente gramática ambigua (Fig. 6.15), se pueden derivar la
sentencia E+E*E de dos maneras diferentes:
E→I
E→E+E E A
E→E*E
E → (E)
E→a E + E E * E
E→b
E → Ia
E → Ib E * E E + E
E → I0 a) b)
E → I1
Figura 6.15. Gramática ambigua
Las causas de ambigüedad en la gramática (Fig. 6.15) son:
1. No se respeta la precedencia de operadores, por ejemplo usualmente “*”
tiene mayor precedencia que “+”. Mientras que en la Fig 6.14 a) se agrupa
adecuadamente * antes que el operador +, la Fig 6.15 b) muestra un árbol
de derivación que también es válido, pero que agrupa de manera inversa,
primero el operador + y después *. Así que se requiere forzar la estructura
para que solo el árbol de la Fig 6.15b) sea válido en una gramática no
ambigua.
2. Una secuencia de operadores idénticos puede agruparse desde la izquierda
y desde la derecha. Por ejemplo si los “*” son reemplazados por “+” en la
Fig 6.15, entonces tendríamos dos estructuras para la sentencia E+E+E. Ya
que la suma es asociativa, no importa si agrupamos por la izquierda o por la
derecha, pero a fin de eliminar la ambigüedad, debe seleccionarse solo
una. El enfoque convencional es agrupar por la izquierda, de tal modo que
la estructura (árbol de derivación) de la Fig 6.15 b) para la sentencia
E+E+E, es el adecuado para agrupar dos signos +.
La solución al problema de forzar la precedencia, es introducir variables, cada una
de las cuales representa a aquellas expresiones que están asociadas en las reglas
de la gramática. Especialmente:
i) Un factor (F) es una expresión que no puede ser separada por un
operador adyacente, ya sea “*” o “+”. Los únicos factores en la
gramática para expresiones son:
a) Identificadores (I). No es posible separar las letras de un identificador
mediante la inclusión de un operador.
119
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
b) Una expresión con paréntesis “(E)”, sin importar lo que aparezca
dentro del paréntesis. El propósito del paréntesis es prevenir que lo
que está dentro sea el operando de un operador fuera del paréntesis.
ii) Un término (T) es una expresión que no puede ser separada por un
operador “+”. En el ejemplo, donde “+” y “*” son los únicos operadores,
un término es un producto de uno o más factores. Por ejemplo, el
termino a*b puede ser separado si usamos la asociatividad por la
izquierda y colocamos a1* a su izquierda. Es decir, a1*a*b es agrupado
(a1*a)*b, lo que separa a*b. Sin embargo, colocando el termino aditivo,
tal como a1+ a su izquierda o +a1 a su derecha no puede separar a*b.
El agrupamiento correcto de a1+a*b es a1 + (a*b), y el agrupamiento
correcto de a*b + a1 es (a*b)+a1.
iii) De aquí en adelante un expresión (E) se referirá a cualquier expresión,
incluyendo aquellas que pueden ser separadas por un * adyacente o por
un + adyacente. Así, la expresión del ejemplo es una suma de uno o
más términos.
De lo anterior, se puede escribir una versión no ambigua de la gramática dada (Fig
6.16), la cual forza la precedencia de los operadores, como sigue.
E → T|E + T
T → F|T * F
F → I| (E)
I → a|b|Ia|Ib|I0|I1
Figura 6.16. Versión no ambigua de la gramática en la Fig 6.15
Ejemplo. La gramática anterior (Fig. 6.16) permite solo un árbol de derivación
para la cadena “a+a*a”, como se muestra en la Fig. 6.17.
E + T
T T * F
F F I
I I a
a a
Figura 6.17. Árbol de derivación único para la cadena “a+a*a”
120
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
A continuación se listan algunas observaciones clave que clarifican porque la
gramática de la Fig. 6.16 no es ambigua.
Cualquier cadena derivada de T, un término, debe ser una secuencia de uno o
más factores conectados por *’s. Un factor es un identificador simple o una
expresión entre paréntesis.
Dada la forma de las dos reglas para T, el único árbol de derivación para una
secuencia de factores es el que separa f1*f2* …* fn, para n>1 en un término f1*f2*
…* fn-1 y un factor fn. La razón es que F no puede derivar expresiones tales como
fn-1 * fn sin introducir paréntesis. Así, no es posible que al usar la producción T →
F|T * F, la F derive otra cosa no sea factor. Esto es, el árbol de derivación para un
término pueden ser solo como en la Figura 6.18.
T * F
T * F
:
:
T
T * F
F
Figura 6.18. Forma de los árboles de derivación para un término
Del mismo modo una expresión es una secuencia de términos conectados por +.
Cuando se usa la producción E → T|E + T para derivar t1 +t2 +. . . , tn, entonces T
debe derivar solo a tn, y la E en el cuerpo deriva t1 + t2 + . . . tn−1. La razón,
nuevamente, es que T no puede derivar la suma de dos o más términos sin usar
paréntesis que los agrupe.
6.5.4 Eliminación de ambigüedad en Gramáticas ambiguas que producen
Lenguajes Regulares (LR)
Se puede eliminar la ambigüedad de una G que genera un LR, ya que hay al
menos un Autómata Finito (AF) que reconoce el L(G).
121
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejemplo: Asumiendo que contamos con una gramática ambigua G con la regla
A → bB, A → bC. El AFND de G sería como se muestra en la Fig. 6.19.
A
b
b
B C
Figura 6.19 AFND de una gramática ambigua
Cuando el autómata lee ‘b’ mediante la transición δ(A, b) = {B, C}, la G puede
producir ‘b’ aplicando bien la regla de producción A → bB o bien A → bC. En
definitiva la ambigüedad en un AFND tiene aparejada una ambigüedad en la
gramática que genera las palabras que el autómata acepta.
El método general de producir una G equivalente no ambigua es:
1. A partir de una expresión regular de L(G), construir el AFND-λ que le
corresponde, de acuerdo con el Teorema de Kleene (Aho et al, 1990). A
veces es mejor partir directamente de la G.
2. Construir el AF equivalente, suprimiendo las transiciones con vacío λ y las
ambigüedades (λ es la cadena vacía).
3. Deducir la GR que produce el mismo L.
Una gramática así construida es totalmente precisa.
6.5.5 Ambigüedad en los lenguajes de programación
La ambigüedad en una gramática debe ser tratada mediante el uso de reglas:
Ejemplo: El ELSE ambiguo. Considerar la siguiente gramática
Sentencia → Sent-if | otro
Sent-if → if (Exp) Sentencia | if (Exp) Sentencia else Sentencia
Exp → 0 | 1
Una sentencia válida en esta gramática sería:
if (0) if (1) otro else otro
Esta sentencia, que además es válida, nos enfrenta a una interrogante. ¿El “else”
pertenece al primer o segundo “if”?
122
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Regla de la anidación más cercana
Una posibilidad para eliminar dicha ambigüedad es usando la regla de la anidación
más cercana:
Siguiendo esta regla, el “else” pertenecería al segundo “if”. También se podrían
usar llaves
if (0)
{
if (1) otro
}
else otro
Otra solución: También se podrían usar palabras clave de agrupación
if (0) then
if (1) otro else otro endif
endif
if (0) then
if (1) otro endif
else
otro
endif
6.6 Generación de matriz predictiva (cálculo first y
follow).
6.6.1 Gramática LL
Dada una gramática, durante la derivación o reconocimiento de una cadena es
posible enfrentar problemas de decisión, es decir, que regla o producción
sintáctica aplicar, lo cual podría ocurrir en el caso de que la gramática sea
ambigua. Es posible que un analizador sintáctico tome una decisión errónea al
construir un árbol sintáctico, ya que puede haber diferentes alternativas para una
determinada situación. Es por lo anterior que existe la siguiente regla:
Regla para analizadores sintácticos. Para cada producción de la forma:
A Æ σ1| σ2|… | σn, el analizador siempre debe ser capaz de elegir la
alternativa correcta para la generación de un árbol de análisis sintáctico.
123
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Para cumplir con esta regla necesitamos la siguiente información adicional:
a) El conjunto de todos los símbolos terminales que pueden aparecer al
principio de una frase que puede derivarse de una secuencia arbitraria de
símbolos. Este conjunto es llamado PRIMERO.
b) El conjunto de todos los símbolos terminales que pueden aparecer después
de uno no terminal. Este conjunto es llamado SIGUIENTE.
Los conjuntos PRIMERO y SIGUIENTE se definen de la siguiente manera:
Sean G(N, T, P, S) una gramática y α una secuencia arbitraria de símbolos, es
decir, α∈(N∪T)*.
Definición: PRIMERO
Es el conjunto de símbolos terminales que pueden aparecer al principio de
cualquier frase derivable de α, es decir:
PRIMERO (α) = {t| t∈Tε ∧ α ⎯
⎯→
*
tα’}, donde Tε= T∪{ε}
El algoritmo de la Fig. 6.20, indica cómo construir el conjunto PRIMERO, dada una
gramática G.
FOR (∀ X ∈ T) DO INCLUIR (X, PRIMERO(X)) END; (* todo terminal es
FOR (∀ X ∈ N) DO primero de si mismo *)
FOR (∀ (X→∑) ∈ P DO
IF (∑ =ε) THEN
INCLUIR (ε, PRIMERO(X) ) (* INCLUIR(a, PRIMERO(X)) = insertar
ELSE (* ∑ = σ1, σ2, σ3, … σK *) a en X*)
i = 1;
WHILE (i<k) AND (σi ⎯ ⎯→*
ε) DO INC(i) END;
INCLUIR (PRIMERO(σi), PRIMERO(X));
END;
END;
END;
Figura 6.20 Algoritmo para construir el conjunto PRIMERO.
En la Fig. 6.20 La función INCLUIR (a, B) significa que a se convierte en un
elemento del conjunto B o que a se inserta en el conjunto B.
124
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejemplo: Considerar la gramática G (T, N, P, S):
T = {x, y, z}
N = {A, B, C}
P = {A → B|C
B → xB | y
C → xC|z}
S = {A}
Para G, los conjuntos de primeros para los símbolos no terminales A, B y C son
los siguientes:
PRIMERO (B) = {x, y}
PRIMERO (C) = {x, z}
PRIMERO (A) = {x, y, z}
Ejemplo: Sea G una gramática cuyo conjunto de reglas de producción es el
siguiente:
S → AaBc
A → Bbc | b
B→d
El conjunto PRIMERO (AaBc) = {b, d}
Ejemplo: Sea G una gramática cuyo conjunto de reglas de producción es el
siguiente:
S → AaBc
A → Bbc | b | ε
B→d
El conjunto PRIMERO (AaBc) = {a, b, d, ε}
Ejemplo: Sea G una gramática cuyo conjunto de reglas de producción es el
siguiente:
S → Aa
A → BCda
B→b
B→d
B→ε
C→c
C→ε
El conjunto PRIMERO(Aa) = {b, c, d, ε}
125
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejemplo: Sea G(T, N, P, S) una gramática, donde:
T = {e, f, g, h, i}
N = {S’, S, A, B, C, D}
P={
S’ → S$
S → AB
S → Cf
A → ef
A→ ε
B → hg
C → DD
C → fi
D→ g }
S = S’
Los conjuntos PRIMERO de los símbolos no terminales S', S, A, B, C y D son:
PRIMERO(S') = {e, f, g, h, ε}
PRIMERO(S) = {e, f, g, h, ε }
PRIMERO(A) = {e, ε }
PRIMERO(B) = {h }
PRIMERO(C) = {f, g}
PRIMERO(D) = {g}
Definición: SIGUIENTE
Sea X un símbolo no terminal entonces, SIGUIENTE(X) es el conjunto de
todos los símbolos terminales que pueden parecer inmediatamente a la
derecha de X, es decir:
SIGUIENTE(X) = {t| t∈Tε ∧ S ⎯
⎯→
*
αXtβ}
El algoritmo de la Fig. 6.21, indica cómo construir el conjunto SIGUIENTE, dada
una gramática G.
FOR (∀ X ∈ N) DO SIGUIENTE (X) = ∅
FOR ∀ (Y → α X β) ∈ P DO
IF (β = ε) OR (β ⎯
⎯→
*
ε) THEN
INCLUIR (SIGUIENTE (Y), SIGUIENTE (X)); (*1*)
IF (β ≠ ε) THEN
INCLUIR (PRIMERO (β) ∩ T, SIGUIENTE (X));
END;
END;
Figura 6.21. Algoritmo para construir Conjuntos SIGUIENTE
126
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejemplo: Sea G una gramática cuyo conjunto de reglas de producción es el
siguiente:
W→YZ
V→Wx
El conjunto SIGUIENTE (W) = {x}, pero ¿cual sería el conjunto SIGUIENTE (Z)?
La respuesta está constenida en la línea marcada con (*1*), en el algoritmo de la
Fig. 6.21, que indica que se incluya el conjunto SIGUIENTE(W) en el conjunto
SIGUIENTE(Z), de tal modo que para este ejemplo particular, SIGUIENTE(Z) =
SIGUIENTE (W) = {x}.
Ejemplo. Considerar nuevamente la gramática G(T, N, P, S), donde:
T= {e, f, g, h, i}
N = {S’, S, A, B, C, D}
P={
S’ → S$
S → AB
S → Cf
A → ef
A→ ε
B → hg
C → DD
C → fi
D→ g
}
S = S’
Los conjuntos SIGUIENTE de los símbolos terminales S', S, A, B, C y D se
muestran en la Tabla 1.
Tabla 1: Conjuntos PRIMERO y SIGUIENTE de todos los símbolos no terminales
de la gramática del ejemplo anterior.
No
PRIMERO SIGUIENTE
terminales
S' e, f, g, h vacío
S e, f, g, h $
A e, ε h
B h $
C f, g f
D g f, g
127
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Antes de incluir más ejemplos del cálculo de conjuntos SIGUIENTE, vale la pena
un comentario sobre el símbolo ’$’. Durante el análisis sintáctico cada cadena
analizada es terminada con el símbolo ‘$’, es decir, es una marca de terminación
de la cadena que se está analizando. Así, esta marca también forma parte del
conjunto SIGUIENTE en los siguientes dos casos:
a) ‘$’ está en SIGUIENTE (S), siendo S el símbolo inicial.
b) ‘$’ está en SIGUIENTE (Ni) cuando Ni (símbolo no terminal), está en el
extremo derecho de cualquier frase que pueda derivarse del axioma
(símbolo inicial), es decir:
$ ∈ SIGUIENTE (Ni), ∀Ni ∈ N : S ⎯⎯→
*
αNi
Estos dos casos pueden observarse en el ejemplo precedente.
Ejemplo. Los conjuntos PRIMERO y SIGUIENTE para los símbolos S, A y B en la
siguiente gramática: G(T, N, P, S), son:
T= {a, b, c}
N = {S, A, B}
P={S→ABc
A→a|ε
B→b|ε}
S = {S}
PRIMERO(S)=PRIMERO(A) ∪ PRIMERO(B) ∪ PRIMERO(c) = {a,b,c, ε}
PRIMERO(A) = {a, ε}
PRIMERO(B) = {b, ε}
SIGUIENTE(S) = {$} (por definición)
SIGUIENTE(A) = PRIMERO(B) ∪ {c} = {b, c} (excepto ε por algoritmo)
SIGUIENTE(B) = {c}
Ejemplo. Los conjuntos PRIMERO y SIGUIENTE para los símbolos S, A y B en la
siguiente gramática: G(T, N, P, S), son:
T= {a, b}
N = {S, A, B}
P={S→Ab
A→a|B|ε
B → b | ε}
S = {S}
PRIMERO(S) = PRIMERO(A) ∪ {b} = {a, b, ε}
PRIMERO(A) = {a} ∪ PRIMERO(B) ∪ {ε} = {a, b, ε}
PRIMERO(B) = {b} ∪ {ε} = {b, ε}
SIGUIENTE(S) = {$} (por definición)
SIGUIENTE(A) = {b}
SIGUIENTE(B) = SIGUIENTE(A) = {b}
128
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejemplo. Los conjuntos PRIMERO y SIGUIENTE para los símbolos S, A y B en la
siguiente gramática: G(T, N, P, S), son:
T= {a, b}
N = {S, A, B}
P = {S → A B B A
A→a|ε
B → b | ε}
S = {S}
PRIMERO(S) = PRIMERO(A) ∪ PRIMERO(B) = {a, b, ε}
PRIMERO(A) = {a, ε}
PRIMERO(B) = {b, ε}
SIGUIENTE(S) = {$} (por definición)
SIGUIENTE(A) = SIGUIENTE(S) ∪ PRIMERO(B) ∪ PRIMERO(A) = {$, b, a}
SIGUIENTE(B) = SIGUIENTE(S) ∪ PRIMERO(A) ∪ PRIMERO(B) = {$,b, a}
Ahora se cuenta con información para postular la siguiente definición.
Definición: Gramática LL(1)
Una gramática independiente de contexto G(N, T, P, S) se denomina
gramática LL(1) si tiene las siguientes características:
C1) Para cada producción A→σ1|σ2|… |σn, se requiere que:
PRIMERO (σi) ∩ PRIMERO (σj) = ∅ ∀i≠j,
o sea, que no haya múltiples opciones de donde elegir durante una
derivación.
C2) Si puede derivarse la cadena vacía ε de un símbolo no terminal X, se
requiere que
PRIMERO (X) ∩ SIGUIENTE (X) = ∅
LL = Lectura de la entrada iniciando por la izquierda y derivación por la
izquierda
Una gramática que no es LL(1) puede originar bloqueos mutuos como se ilustra en
el siguiente ejemplo.
Ejemplo. Sea G (T, N, P, S)
T = {x}
N = {A, B}
P = {A → Bx
B→x|ε}
S = {A}
129
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Esta gramática nos puede originar bloqueos mutuos, por ejemplo si tratamos de
derivar la frase x,
A → Bx
→ xx
En una derivación por la izquierda se podría elegir el camino equivocado en la
rebla para B, como se muestra arriba, lo que nos lleva a un bloqueo, el cual se
presenta porque G no es LL(1), es decir, no se cumple
C2: PRIMERO(B) ∩ SIGUIENTE(B) = {x}≠∅.
Ejemplo: Sea la gramática G3 (T3, N3, P3, S3), donde:
T3 = {+, a, b, c}
N3 = {S, A, B}
P3 = { S → A | B
A → cA+b | a
B → cB+a | b }
S3 = {S}
Al calcular los conjuntos primero y siguiente necesarios y verificar las condiciones,
concluimos que G3 no es LL(1), como se muestra a continuación.
σ PRIMERO(σ) SIGUIENTE (σ)
a a No definido
b b No definido
c c No definido
+ + No definido
A c, a +
B c, b +
S a, b, c $
G3 no es LL(1), ya que no cumple con
C1: PRIMERO (A) ∩ PRIMERO (B) = {c} ≠ ∅
Así, una gramática LL(1) es
a) No ambigua y
b) No recursiva izquierda, como se ilustrará a continuación.
Una gramática G es ambigua si hay una palabra en L(G) que posea dos
derivaciones por la izquierda (a partir del símbolo inicial). Equivalentemente: Hay
una producción con dos alternativas que generen los mismos símbolos iniciales y
por lo tanto C1 es violada.
130
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejemplo: Sea la gramática G cuyo concjunto de producciones es el siguiente:
P = { E → E O E | (E) | x | y
O→+|-|*|/}
Verificando la condición C1 de la las gramáticas LL(1), observamos que:
PRIMERO (E O E) = {(, x, y}
PRIMERO ((E)) = {(}
Así, PRIMERO (E O E) ∩ PRIMERO ((E)) = {(, x, y} ∩ {(} = {(} ≠ ∅, por lo tanto G si
es ambigua.
Por otra parte, una gramática LL(1) no puede ser recursiva izquierda
Demostración:
Condición C2)
Supongamos que
a) la gramática tiene una producción recursiva izquierda X→Xσ1
b) y que X puede derivar la cadena vacía X *→ ε (C2)
Entonces:
1: PRIMERO (σ1 )⊂ PRIMERO (X) y (dado que X ⎯ ⎯→*
ε)
2: PRIMERO (σ1 )⊂ SIGUIENTE (X)
Esto implica que:
PRIMERO (σ1) ⊂ (PRIMERO (X) ∩ SIGUIENTE (X)) ≠ ∅
Lo cual contradice C2
Condición C1)
Nuevamente, bajo la suposición de que la gramática tiene una producción
recursiva izquierda:
X→Xσ1 Si X no deriva a ε (i,e. no es cierto que X ⎯⎯→
*
ε (C1)),
Entonces:
Debe existir una producción X→σ2 y σ2 ⎯ ⎯→
*
t , donde t ∈ T
Lo cual implica que X→Xσ1 | σ2 (por la suposición inicial)
De lo cual se desprende que
PRIMERO (Xσ1) ∩ PRIMERO (σ2) = t
Lo cual contradice C1 y permite terminar la demostración.
Ejemplo: Sea G (T, N, P, S) la siguiente Gramática recursiva izquierda, donde:
T = {a, b}
N = {A}
P = {A → Aa | b}
S = {A}
131
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Podemos observar que PRIMERO (Aa) = PRIMERO (b) = {b}, por lo cual no
cumple con C1 y por lo tanto G no es LL (1) .
Ejemplo: Sea la gramática G4(T4, N4, P4, S4), donde:
T4 = {b, d, e, p, s, ;, .} (b = begin, d = declaración, e = end, p = program,
N4 = {A, X, Y} s = proposición.)
P4 = { A→pX
X→ d;X|bsYe.
Y→ε|;sY}
S4 = {A}
Al verificar las condiciones de las gramáticas LL(1), observamos que:
C1) : PRIMERO (d;X) ∩ PRIMERO (bsYe.) = {d} ∩ {b} = ∅
PRIMERO(ε) ∩ PRIMERO (;sY) = {ε} ∩ {;} = ∅
C2) : PRIMERO(Y) ∩ SIGUIENTE(Y) = {ε, ;} ∩ {e} = ∅
Por lo tanto G4 si es LL(1).
6.6.2 Matriz predictiva
Una matriz predictiva es una tabla que contiene las producciones de una
gramática, de tal modo que es posible desarrollar programas “genéricos”, que
realicen el análisis de sintáctico de cualquier gramática LL(1) contenida en dicha
tabla. Esto será detallado en la siguiente sección. Por el momento se revisará el
algoritmo para generar la tabla predictiva.
Considerar la gramática G7(T7, N7, P7, S7), donde:
T7 = {id, +, -, *, /, (, )}
N7 = {EXP, E, TERM, T, FACTOR}
P7 = { EXP → TERM E
TERM → FACTOR T
FACTOR → id|(EXP)
E → + TERM E | -TERM E| ε
T → * FACTOR T| / FACTOR T| ε }
S7 = {EXP}
Los conjuntos PRIMERO y SIGUIENTE se muestran en la Tabla 2.
132
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Tabla 2. Conjuntos PRIMERO y SIGUIENTE para la gramática G7.
σ PRIMERO(σ) SIGUIENTE(σ)
id id No definido
+ + No definido
- - No definido
* * No definido
/ / No definido
( ( No definido
) ) No definido
EXP id, ( )
E +, -, ε ), $
TERM id, ( ), +, -
T *, /, ε ), +, -, $
FACTOR id, ( ), +, -, *, /
A continuación se verifican las condiciones de una gramática Ll(1):
C1)
- PRIMERO( id ) ∩ PRIMERO((EXP) ) = {id} ∩ {(} = ∅
- PRIMERO(+ TERM E) ∩ PRIMERO( -TERM E) ∩ PRIMERO(ε) = {+} ∩ {-} ∩
{ε} = ∅
- PRIMERO(* FACTOR T) ∩ PRIMERO(/ FACTOR T) ∩ PRIMERO(ε) = {*} ∩
{/} ∩ {ε} = ∅
C2)
- PRIMERO(E) ∩ SIGUIENTE(E) = {+, -, ε} ∩ {), $} = ∅
- PRIMERO(T) ∩ SIGUIENTE(T) = {*, /, ε} ∩ {), +, -, $} = ∅
Por lo tanto concluimos que G7 es una gramática LL(1).
Algoritmo para obtener la tabla de análisis sintáctico (o Matriz predictiva)
FOR {∀ (N →σ) ∈ P} DO
FOR {∀ t∈T: t ∈ PRIMERO (σ)} DO
añadir N → σ a P [N, t];
IF (σ ⎯⎯→
*
ε) THEN
FOR {∀ x ∈ SIGUIENTE (N)} DO añadir N→σ a P [N, x];
END;
END;
133
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Como puede observarse, el algoritmo prescribe la formación de una tabla [N,T]
cuyos renglones y columnas están encabezados por los conjuntos N y T de la
gramática. Después solo tienen que introducirse en la tabla las producciones.
- En la primera parte, en la posición [N, t ] de la tabla, se insertan las reglas
(lado derecho de la producción), si es que t está en el conjunto PRIMERO
(σ), donde N → σ.
- En la segunda parte, si es que hay producción que pueda derivar ε (vacío),
en la posición [N, x ] de la tabla, se insertan las reglas (lado derecho de la
producción), si es que x está en el conjunto SIGUIENTE (N), donde N → σ.
Siguiendo el algoritmo para generar la matriz predictiva de G7, ésta quedaría
como se muestra en la Tabla 6.3.
Tabla 6.3. Matriz predictiva para la gramática G7.
N\T id + - * / ( ) $
EXP TERM E TERM E
E +TERM E -TERM E ε ε
TERM FACTOR T FACTOR T
T ε ε *FACTOR T /FACTOR T ε ε
FACTOR id (EXP)
Si G7 no fuera LL(1), podría haber más de una entrada en algunas posiciones de
su tabla predictiva.
6.7 Tipos de analizadores sintácticos.
El analizador sintáctico, analiza secuencias de símbolos para determinar si serán
aceptadas por el lenguaje de programación de que se trate.
Los métodos para realizar el análisis sintáctico son:
• el análisis sintáctico ascendente y
• el análisis sintáctico descendente.
Los analizadores sintácticos ascendente y descendente más eficientes se basan
en gramáticas LL y LR respectivamente, que son independientes del contexto.
LL = lectura de la entrada iniciando por la izquierda y derivación por la izquierda.
LR = lectura de la entrada iniciando por la izquierda y derivación por la derecha.
134
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
6.7.2. Análisis sintáctico descendente.
El análisis sintáctico descendente, es también llamado análisis sintáctico
descendente recursivo (ASDR) o análisis sintáctico predictivo (ASDP). Este
análisis se basa en gramáticas LL que permiten analizar una frase de entrada sin
que existan bloqueos mutuos.
El ASDR intenta encontrar una derivación por la izquierda para una entrada dada,
y generar un árbol de análisis sintáctico desde la parte superior (desde el axioma
de la gramática o símbolo inicial), hasta las hojas de dicho árbol. Dicho en otras
palabras, el ASDR al analizar un entrada, inicia con el símbolo inicial, después
mientras haya hojas etiquetadas con símbolos no terminales, se selecciona una de
las producciones que corresponda con la etiqueta del nodo, para formar las hojas
del nodo no terminal, de acuerdo con el lado derecho de la producción. Así la
entrada es correcta si la secuencia de hojas terminales corresponde a la
secuencia de símbolos de entrada..
El ASDR puede aplicarse a otros tipos de gramáticas, pero solo las gramáticas
LL(1) permiten este tipo de análisis sin bloqueos mutuos.
El siguiente ejemplo ilustra lo que sucede cuando trata de aplicarse el ASDR a una
gramática que no es LL(1).
Ejemplo: Dada la gramática G5 (T5, N5, P5, S5)
T5 = {a, b, c, d, e}
N5 = {S, A, B}
P5 = { S → cAd | dBc
A → ab | a
B → ae | A}
S5 = { S }
Verificando las condición C1 de las gramáticas LL(1):
PRIMERO (ab) ∩PRIMERO (a) = {a} ≠ ∅
PRIMERO (ae) ∩ PRIMERO (A) = {a} ≠ ∅
Por lo tanto G5 no es LL(1).
Al tratar de aplicar el ASDR para derivar la cadena “dac” usando G5, se obtiene lo
siguiente (Fig. 6.22):
135
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
i) ii)
S d a c ⇒ d a c S d a c ⇒ d a c
c A d d B c
ii) iv)
S d a c ⇒ d a c S d a c ⇒ d a c
d B c d B c
a e A
a b
v)
S
d B c
A
a d a c ⇒ d a c
Figura 6.22 Retrocesos al analizar la cadena “dac”
En la Fig. 6.22, en i) se inicia con la primera regla de producción, pero el primer
caracter “a” no corresponde con la entrada, así que se da el primer retroceso. En
ii) se intenta con la segunda regla (la alternativa), el primer carácter si concuerda.
Sin embargo en iii) al expandir B, se introduce un caracter “e” que no concuerda
con la entrada, se da otro retroceso. Ahora en iv) se intenta con la segunda
alternativa para expandir B, que es con A, después se toma la primera opción para
expandir A, pero se introduce “b” que tampoco concuerda con la entrada, así que
hay un retroceso más. Finalmente en v) se toma la segunda alternativa que
expande a A y finalmente la derivación concuerda con la entrada.
Se debe ser cuidadoso con el manejo de los retrocesos, en compilación puede ser
esencialmente ineficiente, sobre todo cuando se esté trabajando con una
gramática recursiva izquierda, donde puede ocasionar un ciclo infinito, lo cual no
se da en las gramáticas LL.
Considerar nuevamente la gramática G4, que ya se verificó que es LL(1) en la
sección anterior. En el siguiente ejemplo se puede observer lo que sucede al tratar
de derivar una cadena (Fig. 6.22).
136
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejemplo. Derivar la cadena program begin proposición end. = p b s e. usando
G4(T4, N4, P4, S4), donde:
T4 = {b, d, e, p, s, ;, .} (b = begin, d = declaración, e = end, p = program,
N4 = {A, X, Y} s = proposición.)
P4 = { A→pX
X→ d;X|bsYe.
Y→ε|;sY}
S4 = {A}
i) ii)
A p b s e. ⇒ p b s e . A p b s e . ⇒ p b s e .
p X p X
b s Y e . p b s e . ⇒ p b s e .
iii)
A
p X
b s e . pbse. ⇒pbse.
Figura 6.23 Derivación de la cadena “pbse.”
En la Fig. 6.23, en i) se inicia con la derivación de la cadena “pbse.” con la primera
regla de producción, el primer carácter coincide con la entrada. En ii) se utiliza la
segunda alternativa de X ya que inicia con el carácter “b” que es el siguiente
caracter después de “p”, el caracter ya reconocido. Además nos permite reconocer
el siguiente caracter a analizar, o sea “s”. En iii) simplemente se sustituye Y por ε,
y esto nos permite terminar de reconocer el resto de la cadena de entrada.
En caso de haber diferentes alternativas durante el análisis de una cadena de
entrada, tenemos siempre un apuntador al siguiente carácter a reconocer en dicha
cadena de entrada (indicado en pequeños recuadros en las figuras 6.22 y 6.23, ),
este carácter junto con los conjuntos PRIMERO de cada alternativa, nos permite
saber que alternativa seguir, es decir, si el carácter siguiente a reconocer, no se
encuentra en el conjunto PRIMERO (σi) de alguna de las alternativas (σi) en el
lado derecho de una producción, entonces no se debe seguir por esa alternativa
para continuar con el reconocimiento de la cadena de entrada. Esto nos ayuda a
evitar retrocesos en las gramáticas LL(1).
137
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
6.7.3. Estructura de un analizador sintáctico descendente recursivo.
La estrategia más común para implantar un analizador sintáctico descendente
recursivo, es asociando un procedimiento recursivo a cada símbolo no terminal de
la gramática. Al usar una gramática LL(1), el símbolo de búsqueda por anticipación
(siguiente símbolo a reconocer), permite saber exactamente a que procedimiento
llamar, evitando retrocesos.
Así, dada la gramática G(T, N, P, S) que es LL(1), donde N = {N1, N2, …, Nm} y S =
N0, el ASDR está dado por la estructura de la Fig. 2.24.
PROGRAM
PROCEDURE Error(…);
PROCEDURE N0; . . .;
PROCEDURE N1; . . .;
...
PROCEDURE Nm; . . .;
BEGIN
LeerSimbolo;
N0;
END.
Figura 2.24. Estructura del analizador sintáctico descendente recursivo-ASDR.
En la sección 6.4 se mostro que había una equivalencia entre grafos sintácticos y
la notación BNF. Es posible también asociar un programa a cada grafo sintáctico
como se muestra a continuación.
M1. El grafo sintáctico para alternativas, corresponde a un enunciado condicional
(Fig. 6.25).
S1
S2
...
Sn
IF ch IN PRIMERO(S1) THEN P(S1) ELSE
IF ch IN PRIMERO(S2) THEN P(S2) ELSE
...
138
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
IF ch IN PRIMERO(Sm) THEN P(Sm) ELSE
Error
Figura 6.25 Grafo sintáctico para múltiples alternativas
M2. El grafo sintáctico para los términos de la forma α = S1 S2 … Sn,
corresponde a una secuencia lineal de llamados a procedimientos Fig. 6.26.
S S ... Sn
BEGIN P(S1); P(S2); … ; P(Sm) END;
Figura 6.26 Grafo sintáctico para secuencia de símbolos no terminales
(R3 y R4) son mostrados en la.
M3. Cero o más veces: N → S*, a veces representado también como {S}, para
indicar repetición. El grafo sintáctico para expresar repeticiones, en donde S
puede aparecer cero o más veces, equivale a una instrucción de repetición,
Fig. 6.27.
{S}
WHILE ch IN PRIMERO (S); DO P(S);
Figura 6.27 Grafos sintácticos para representar repetición
M4. El grafo sintáctico para representar cero o una ocurrencia de S ([S]),
corresponde a una instrucción condicional (Fig. 6.28).
[S]
IF ch IN PRIMERO (S) THEN P(S);
Figura 6.28 Grafos sintácticos para representar repetición
139
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
M5. El grafo de la representación de un símbolo no terminal, corresponde a la
llamada de un procedimiento Fig. 6.29.
P(S);
Figura 6.29 Grafo sintáctico para representar símbolos no terminales
M6. El grafo de referencia a un símbolo terminal, corresponde a una proposición
de lectura condicional. Fig. 6.30.
t
IF ch = ‘t’ THEN LeeSimbolo (ch) ELSE Error;
Figura 6.30 Grafo sintáctico para representar condicional
Con ayuda de estos diagramas y los programas asociados de las reglas (M1 a M6)
podemos desarrollar ASDR de una gramática LL(1).
Considerar nuevamente a la gramática G6(T6, N6, P6, S6), donde:
T6 = { id, +, -, *, /, (, ) }
N6 = {E, T, F}
P6 = { E → T{(+ | -)T},
T → F {(* | /)F},
F → id | (E) }
S6 = {E}
Verificamos primero si G6 es una gramática LL(1)
X∈N PRIMERO (X) SIGUIENTE
(X)
E id, ( ), $
T id, ( +, -, )
F id, ( +. -, *, /, )
PRIMERO (id) ∩ PRIMERO ((E)) = {id} ∩ {(} = ∅. Por lo tanto G6 es una gramática
LL(1).
El análisis sintáctico utiliza principalmente los siguientes procedimientos:
• LeerSimbolo: Analizador léxico
• Error: Para detener el proceso en caso de error
• AnalizadorSintactico: Estructura principal Fig. 2.24
140
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
• Un procedimiento por cada símbolo no terminal (M1 - M6)
PROGRAM AnalizadorSintactico;
VAR_Global símbolo
PROCEDURE Error (n: INTEGER);
BEGIN WRITELN (“Error sintáctico No: ”, n); Halt; END;
PROCEDURE E; (* Implementa E → T{(+ | -)T} *)
BEGIN
T; WHILE simbolo IN [‘+’, ’-’] DO LeerSimbolo; T; END;
END
PROCEDURE T; (* Implementa T → F {(* | /)F} *)
BEGIN
F; WHILE simbolo IN [‘*’, ’/’] DO LeerSimbolo; F; END;
END;
PROCEDURE F; (* Implementa F → id | (E) *)
BEGIN
CASE Simbolo OF
id: LeerSimbolo;
‘(’: LeerSimbolo; E;
IF simbolo = ‘)’ THEN LeerSimbolo;
ELSE Error(1);
ELSE Error (2);
END;
END
BEGIN (* Analizador sintáctico *)
LeerSimbolo; E; Halt;
END
Actividad:
Tomando como base el seudocódigo anterior, verificar si la expresión “(a + b) * c”
pertenece al lenguaje generado por la gramática G6.
6.7.4. Análisis sintáctico tabular
El método de análisis presentado en la sección anterior (ASDR), es una forma
general de análisis que no depende de la sintaxis del lenguaje de programación y
por lo tanto se puede diseñar un programa general de análisis, que obtenga de
una tabla la información de la sintaxis específica de un lenguaje determinado. A
141
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
este método se le llama Análisis Sintáctico Tabular (AST) y son componentes son
mostradas en la Fig. 6.31.
Componentes del modelo de AST.
a) Buffer de entrada:
Contiene la cadena a analizar seguida de $ (fin de cadena)
Entrada
a + b - a * b $
Pila X
Y Programa Tabla de análisis
Z de análisis sintáctico
A
$
Figura 6.31. Modelo del análisis sintáctico tabular
b) Pila:
Al inicio solo tiene el símbolo $ y el símbolo inicial de la gramática
c) Tabla de análisis sintáctico:
Es una matriz bidimensional [Ni, t] = [No terminal, terminal]
d) Programa de análisis:
Coordina el uso de las otras componentes
El algoritmo mostrado abajo describe como opera la la componente del “Programa
de análisis”.
Algoritmo de análisis sintáctico tabular
Este algoritmo asume lo siguiente:
- La pila contiene el símbolo inicial y $
- El primer símbolo de entrada ya se leyó (variable “a”)
- X es la cima de la pila
142
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
REPEAT
If X IN T THEN
IF X = a THEN
Sacar X de la pila y leer el siguiente caracter de entrada “a”
ELSE Error
ELSE (*X∈N*)
IF P(X, a) = X → Y1 Y2, … Ym THEN
Reemplazar X en la cima de la pila por Ym… Y2 Y1
(Y1 queda en la cima de la pila; la salida es X → Y1 Y2 … Ym)
ELSE Error (*P(X, a) esta vacio*)
UNTIL (X= $) AND (a = $):
Descripción del algoritmo de análisis sintáctico tabular
1. Si X = a = $, el analizador sintáctico acepta la cadena y se detiene
2. Si X = a ≠ $, el analizador sintáctico saca X de la pila y lee el siguiente carácter
de entrada
3. Si (X∈T y X ≠ a) o (X∈N y P (X, a) está vacío), el analizador sintáctico llama a
un procedimiento de recuperación de errores, pues ha ocurrido un error de
sintaxis.
4. Si X∈N y P(X, a) = X → Y1 Y2 … Ym, donde Yi ∈ (N∪T), i = 1, 2, …, m, el
analizador sintáctico reemplaza X en la cima de la pila por Ym … Y2 Y1 en la
cima. Así el analizador sintáctico tiene como salida la producción X → Y1 Y2 …
Ym.
Ejemplo. Considerando la gramática G7 mostrada en la sección anterior, así
como su tabla de análisis sintáctico. Verificar si la cadena expresión “id+id-id*id$”
pertenece a G7. Este análisis se muestra en la Tabla 6.4.
143
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Tabla 6.4. Análisis de la cadena “id+id-id*id$” usando el análisis sintáctico tabular
pila entrada salida
$EXP id+id-id*id$
$E TERM id+id-id*id$ EXP →TERM E
$E T FACTOR id+id-id*id$ TERM→ FACTOR T
$E T id id+id-id*id$ FACTOR→ id
$E T +id-id*id$
$E +id-id*id$ T→ ε
$E TERM + +id-id*id$ E → +TERM E
$E TERM id-id*id$
$E T FACTOR id-id*id$ TERM → FACTOR T
$E T id id-id*id$ FACTOR → id
$E T -id*id$
$E -id*id$ T →ε
$E TERM - -id*id$ E → -TERM E
$E TERM id*id$
$E T FACTOR id*id$ TERM → FACTOR T
$E T id id*id$ FACTOR → id
$E T *id$
$E T FACTOR * *id$ T → * FACTOR T
$E T FACTOR id$
$E T id id$ FACTOR → id
$E T $
$E $ T→ε
$ $ E→ε
Ejemplo.
1. Comprobar si la gramática G, cuyo conjunto de producciones es:
S → cA
A → aB
B→b|ε
es LL(1) y si es así, construir la tabla de análisis sintáctico, calculando todos
los conjuntos PRIMERO y SIGUIENTE.
2. Reconocer la cadena “cab” con la tabla del analizador construida.
Primero se obtienen los conjuntos PRIMERO y Siguiente de G.
144
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
PRIMERO SIGUIENTE
S c
A a $
B b, ε $
Se verifica si la G es LL(1). La gramática G si es LL(1), ya que no hay reglas con
alternativas y al verificar la condición C2, se obtiene un conjunto vacío.
C2) PRIMERO(B) ∩ SIGUIENTE(B = {b, ε} ∩ {$} = ∅
Se obtiene la matriz o tabla de análisis sintáctico.
N\T a b c $
S cA
A aB
B b ε
Finalmente se analiza la cadena “cab” utilizando la tabla de análisis sintáctico.
Pila Entrada Salida
$S cab$
$Ac cab$ S Æ cA
$A ab$
$Ba ab$ A Æ aB
$B b$
$b b$ BÆb
$ $
145
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Actividades sugeridas para el estudiante:
1. Comprobar si la siguiente gramática G cuyo conjunto de producciones
es:
E → TE’
E’ → +TE’ | ε
T → FT’
T’ → *FT’ | ε
F → (E) | id
es LL(1) y construir la tabla de análisis sintáctico. Para esto se requiere
Actividad.
obtener todos los conjuntos PRIMERO y SIGUIENTE de G.
2. Reconocer la cadena “(3+5*8)” con la tabla del analizador construida.
6.7.5. Análisis sintáctico ascendente
El análisis sintáctico ascendente implica generar el árbol de análisis sintáctico de
una entrada dada comenzando por las hojas y ascender hacia la raíz del árbol.
Esto es equivalente a la reducción por la izquierda (o a la derivación por la
derecha) de una frase α∈T* al símbolo inicial S de la gramática
Antes de continuar se introducen algunas definiciones.
.
Significado de LR(k)
L indica que la cadena de entrada se lee de izquierda a derecha y la R
indica derivaciones por la derecha, k indica lectura por anticipado de k
símbolos.
Mando
Es una subcadena de una cadena que puede reducirse usando el lado
izquierdo de una producción apropiada, siempre y cuando la reducción
corresponda a un paso en la reducción por la izquierda de la cadena de
símbolos inicial de la gramática.
Definición formal: Mando
Formalmente, sea G(N, T, P, S) una gramática independiente del contexto,
y supongamos que:
S ⎯⎯→αXt →αβt *
es una derivación por la derecha (donde t está en T*). Entonces, β es un
mando de αβt.
Se dice que una subcadena β de una cadena αβt es un mando si
αβt← αXt.
146
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Reducción por la izquierda
El procesamiento de una frase que emplea reducciones por la izquierda
puede realizarse con una pila. Los cambios en la cima de la pila se dan por
dos razones:
a) por empilar símbolos de entrada o
b) por reducir un mando en la pila.
Uso de la pila
El procesamiento de una frase que emplea reducciones por la izquierda
puede realizarse con una pila.
Ejemplo: Dada la gramática G0 (T0, N0, P0, S0) donde:
T0 = {x, y, +, -, *, /, (, )}
N0 = {expr, term, factor}
P0 = { expr→term | expr + term | expr – term
term→ factor| term * factor | term/factor
factor → x | y | (expr)
}
S0 = {expr}
Realizar el análisis por desplazamiento y reducción de la cadena x+y-x. Dicha
reducción puede observarse en la siguiente tabla.
entrada pila
0 x+y-x
1 x+y-x x Pasa x a la pila
2 +y-x FACTOR x se reduce a FACTOR
3 +y-x TERM FACTOR se reduce a TERM
4 +y-x EXPR TERM se reduce a EXPR
5 y-x EXPR + Pasa + a la pila
6 -x EXPR + y Pasa y a la pila
7 -x EXPR + FACTOR y se reduce a FACTOR
8 -x EXPR + TERM FACTOR se reduce a TERM
9 -x EXPR EXPR+TERM se reduce a EXPR
10 x EXPR - Pasa - a la pila
11 EXPR – x Pasa x a la pila
12 EXPR – FACTOR x se reduce a FACTOR
13 EXPR- TERM FACTOR se reduce a TERM
14 EXPR EXPR-TERM se reduce a EXPR
Lo que se hace en la tabla no son más que desplazamientos de datos de la
entrada a la pila y reducciones (por la izquierda).
La derivación por la derecha de la misma cadena sería la siguiente:
147
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Ejercicio: - Derivación por la derecha de la cadena x+y-x
expr → expr – term
→ expr – factor
→ expr – x
→ expr + term – x
→ expr + factor – x
→ expr + y – x
→ term + y – x
→ factor + y – x
→x+y-x
Ejemplo. Dada la gramática G8 (T8, N8, P8, S8) donde:
T8= {x1, x2, x3, x4, x5, “,”,:, integer}
N8= {S, listaVar, var}
P8 = { (1) S →listaVar: integer
(2) listaVar→ listaVar, var | var
(3) var → x1| x2| x3| x4 |x5}
S8= {S}
Esta gramática permite declarar variables en Pascal, por ejemplo:
x1, x2, x3: integer;
La reducción por la izquierda de la cadena “x1, x2, x3: integer” sería como sigue:
x1, x2, x3: integer ← var, x2, x3:integer
← listaVar, x2, x3: integer
← listaVar, var, x3: integer
← listaVar, x3: integer
← listaVar,var: integer
← listaVar: integer
←S
Algoritmo para el análisis por desplazamiento y reducción
El algoritmo asume que inicialmente la pila está vacía y el apuntador, apunta al
primer carácter de entrada.
148
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
REPEAT
IF mando_en_cima_de_pila THEN
Reducir (* reemplazar cima de pila por lado
izquierdo de una prod.*)
ELSE
Desplazar (* colocar en la pila el siguiente símbolo
de entrada *)
END
UNTIL entrada_vacia AND NoHayMandosEnCimaDePila
IF axioma_en_cima_pila THEN
Aceptar (* la entrada es sintácticamente correcta *)
ELSE
Rechazar (* la entrada es sintácticamente incorrecta *)
END;
Figura 6.32. Algoritmo para el análisis sintáctico por desplazamiento y reducción
Ejemplo. Análisis por desplazamiento y reducción de la cadena “x1, x2, x3:
integer$”.
Nuevamente se utiliza una tabla para ilustrar el análisis.
entrada pila Acción
x1, x2, x3: integer$ Desplazar
, x2, x3: integer$ x1 Reducir (3)
, x2, x3: integer$ Var Reducir (2)
, x2, x3: integer$ ListaVar Desplazar
x2, x3: integer$ ListaVar, Desplazar
, x3: integer$ ListaVar, x2 Reducir(3)
, x3: integer$ ListaVar, Var Reducir(2)
, x3: integer$ ListaVar Desplazar
x3: integer$ ListaVar, Desplazar
: integer$ ListaVar, x3 Reducir (3)
: integer$ ListaVar, Var Reducir (2)
: integer$ ListaVar Desplazar
integer$ ListaVar : Desplazar
$ ListaVar: Reducir (1)
$ Integer Aceptar
S
149
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Definición: Gramática LR(k).
Se dice que una gramática es LR(k) si siempre es posible determinar en
forma única el mando, teniendo en cuenta el contenido vigente de la pila y
los siguientes k caracteres de entrada (es decir no habrá conflictos de
desplazamiento-reducción ni de reducción - reducción).
6.7.6. Analizador sintáctico LR
Hasta ahora se ha explicado el principio de de análisis sintáctico ascendente, pero
no se explico de qué manera se decide si se debe realizar una reducción o un
desplazamiento, es decir, no se explico cómo puede reconocerse un mando. Para
el proceso de decisión se hace uso de tablas similar a ASRD tabular.
El modelo general para el análisis LR se muestra en la Fig. 6. 33. Sus
componentes son muy similares a las del modelo para el ASDR tabular, solo que
las tabla de análisis sintáctico se divide en dos:
1) una tabla de acciones y
2) una tabla de funciones ir_a
Por otra parte la pila no solo contiene símbolos de la gramática (Xi), sino que
además contiene estados (si), que indican el contenido de la pila.
Es el estado en la cima de la pila, junto con el símbolo de entra da corriente, los
que determinan el proceso de decisión mencionado arriba, es decir, estos dos
elementos sirven como índice de la tabla de análisis sintáctico. Cada estado en la
pila refleja de manera única el proceso de análisis de ejecución.
150
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Entrada
a + b - a * b $
Pila
Sk
Xk
sk- 1 Tabla de análisis sintáctico
Programa
xk -1 de análisis
acción Ir_a
:
:
S0
Figura 6.33. Modelo del análisis sintáctico LR
Las acciones de la tabla de acciones, en el análisis por desplazamiento y
reducción son las siguientes:
Desplazar :
El siguiente símbolo de entrada se desplazará a la pila
Reducir:
Se reduce cuando se reconoce un mando. Dependiendo del símbolo y del
estado vigente, se coloca un nuevo estado en la cima de la pila.
Aceptar:
Se aceptará la entrada cuando se detecte el final de la entrada $
Error: en caso contrario
Como se mencionó antes, el estado en la cima de la pila, junto con el símbolo de
entrada vigente, sirven como índice de la tabla de análisis sintáctico, es decir, la
tabla bidimensional de acciones tiene entradas pares (si, tj) donde tj es un terminal y si es
un estado de la pila.
151
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Tabla de acciones y de ir_a
Al tener el estado sk en la cima de la pila y tm como símbolo de entrada
vigente, el programa de análisis consultará la tabla de acciones A(sk, tm)
para decidir el siguiente paso del análisis, de la siguiente manera:
Análisis sintáctico LR
- Si A(sk, tm) es un estado si (es decir, desplazar si) de la pila, entonces al
examinar el símbolo tm en el estado sk, se meterá tm a la pila y después el
estado si se colocará en la cima de la pila.
- Si A(sk, tm) es una producción (es decir, con la producción pi) de la
gramática (X→α), entonces al examinar un símbolo tm en el estado sk, se
reconocerá un mando (α) y se reducirá mediante la producción dada (se
efectuarán 2*(longitud mando) operaciones de desempilar); quedando un
estado sj en la cima de la pila. Después X es desplazado a la cima de la
pila y el nuevo estado en la cima de la pila se determinará consultando la
tabla ir_a(sj, X)
- Si A(sk, tm) es una aceptación, el proceso de análisis y la entrada es
correcta, o sea, se habrá aceptado.
- Si A(sk, tm) no contiene entrada, ha ocurrido un error de modo que la
entrada es incorrecta y no será aceptada.
Ejemplo: Reconsiderando la gramática G8 (T8, N8, P8, S8), la cual es ha sido
aumentada y re-expresada como sigue:
T8= {x1, x2, x3, x4, x5, “,”,:, integer}
N8= {S, listaVar, var}
P8 = { (0) S’ → S
(1) S →listaVar: integer
(2) listaVar→ listaVar, var
(3) listVar → var
(4) var → x1
(5) var → x2
(6) var → x3
(7) var → x4
(8) var → x5}
S8= {S}
Notar que G8 ha sido aumentada con la regla S’ → S. esta producción adicional
podemos determinar de manera única la aceptación de la frase de entrada, es
decir, la entrada será aceptada si y solo si el analizador reduce con esta
producción adicional.
Considerar la siguiente tabla de acciones e ir_a para la gramática G8. Más
adelante se describe el procediendo para obtener dichas tablas.
152
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Tabla 6.5. Tabla de acciones e ir_a para la gramática G8
Tabla de acciones Tabla de ir_a
Estados x1 x2 x3 x4 x5 , : INT $ S LVar Var
s0 s4 s5 s6 s7 s8 s1 s2 s3
s1 acc
s2 s10 s9
s3 p3 p3
s4 p4 p4
s5 p5 p5
s6 p6 p6
s7 p7 p7
s8 p8 p8
s9 s11
s10 s4 s5 s6 s7 s8 s12
s11 p1
s12 p2 p2
A fin de especificar un poco más las acciones considerar lo siguiente:
Desplazar
o transferir un terminal de la parte frontal de la entrada hasta la parte
superior de la pila
Reducir
una cadena α en la parte superior de la pila a un no terminal A, dada la
producción A →α
A continuación se muestra el análisis LR de la cadena “x1, x2, x3: INTEGER$”, en
la Tabla 6.6.
Tabla 6.6. Análisis sintáctico LR para la cadena x1, x2, x3: INTEGER$” usando la
gramática G8
153
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Entrada Pila Acción/reducción
x1, x2, x3: INTEGER$ $s0 Desplazar
, x2, x3: INTEGER$ $s0 x1 s4 X1←Var: (4)
, x2, x3: INTEGER$ $s0 V s3 Var← ListaVar (3)
, x2, x3: INTEGER$ $s0 LV s2 Desplazar
x2, x3: INTEGER$ $s0 LV s2, s10 Desplazar
, x3: INTEGER$ $s0 LV s2, s10 x2 s5 X2←Var (5)
, x3: INTEGER$ $s0 LV s2, s10 V s12 ListaVar, Var ← ListaVar(2)
, x3: INTEGER$ $s0 s0 LV s2 Desplazar
x3: INTEGER$ $s0 LV s2, s10 Desplazar
: INTEGER$ $s0 LV s2, s10 x3 s6 X3 ← Var (6)
: INTEGER$ $s0 LV s2, s10 V s12 ListaVar, Var ← ListaVar (2)
: INTEGER$ $s0 LV s2 Desplazar
INTEGER$ $s0 LV s2: s9 Desplazar
$ $s0 LV s2: s9 INT s11 LIstaVar: INTEGER ← S (1)
$ $s0 S s1 Aceptar
6.8 Manejo de errores.
Un error de sintaxis se detecta cuando el analizador sintáctico espera un símbolo
que no corresponde al que se acaba de leer. Los analizadores sintácticos LL y LR
tienen la ventaja de que pueden detectar errores sintácticos lo más pronto posible,
es decir, se genera un mensaje de error en cuanto el símbolo analizado no sigue
la secuencia de los símbolos analizados hasta ese momento.
Lo ideal es que, al producirse un error, el compilador sea capaz de informar del
error y seguir compilando.
El manejo de errores de sintaxis es el más complicado desde el punto de vista de
la creación de compiladores. Nos interesa que cuando el compilador encuentre un
error, se recupere y siga buscando errores. Por lo tanto el manejador de errores
de un analizador sintáctico debe tener como objetivos:
Indicar los errores de forma clara y precisa. Aclarar el tipo de error y su
localización.
Recuperarse del error, para poder seguir examinando la entrada.
No hacer lento, significativamente, el proceso de la compilación.
• Un buen compilador debe hacerse siempre teniendo también en mente
los errores que se pueden producir; con ello se consigue:
Simplificar la estructura del compilador.
154
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Mejorar la respuesta ante los errores.
De acuerdo con Teufel, et al, 1993, existen varias estrategias para corregir
errores, una vez detectados, entre las principales estrategias de recuperación se
encuentran las siguientes:
a) Ignorar el problema (Modo de Pánico o Alarma).
Consiste en ignorar el resto de la entrada hasta llegar a una condición de
seguridad.
Una condición de seguridad se produce cuando nos encontramos un token
especial (por ejemplo un ‘;’ o un ‘END’). A partir de este punto se sigue el análisis
normalmente.
b) Recuperación a nivel de frase.
Intenta recuperar el error una vez descubierto. En el caso anterior, por ejemplo,
podría haber sido lo suficientemente inteligente como para insertar el token ‘;’. Hay
que tener cuidado con este método, pues puede dar lugar a recuperaciones
infinitas.
c) Reglas de producción adicionales para el control de errores.
La gramática se puede aumentar con las reglas que reconocen los errores más
comunes.
d) Corrección Global
Dada una secuencia completa de tokens a ser reconocida, si hay algún error por el
que no se puede reconocer, consiste en encontrar la secuencia completa más
parecida que sí se pueda reconocer. Es decir, el analizador sintáctico le pide toda
la secuencia de tokens al léxico, y lo que hace es devolver lo más parecido a la
cadena de entrada pero sin errores, así como el árbol que lo reconoce.
No hay una estrategia de aceptación universal: Abundan técnicas heurísticas y
adhoc.
El principio general de recuperación es:
• Minimizar tokens eliminados/modificados
• Dejar el analizador listo para continuar procesando
Los objetivos de la recuperación son:
155
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
• Informar con claridad, exactitud y extensión
• Evitar errores en cascada y procesos infinitos
El analizador sintáctico detecta un error de sintaxis cuando el analizador léxico
proporciona el siguiente símbolo y éste es incompatible con el estado actual del
analizador sintáctico. Los errores sintácticos típicos son:
1. Paréntesis o corchetes omitidos, por ejemplo, x : = y * (1 + z;
2. Operadores u operando omitidos, por ejemplo, x : = y (1 + z );
3. Delimitadores omitidos, por ejemplo, x : = y + 1 IF a THEN y : = z.
No hay estrategias de recuperación de errores cuya validez sea general, y la
mayoría de las estrategias conocidas son heurísticas, ya que se basan en
suposiciones acerca de cómo pueden ocurrir los errores y lo que probablemente
quiso decir el programador con una determinada construcción. Sin embargo, hay
algunas estrategias que gozan de amplia aceptación:
1. Recuperación de emergencia (o en modo pánico): Al detectar un error, el
analizador sintáctico salta todos los símbolos de entrada hasta encontrar un
símbolo que pertenezca a un conjunto previamente definido de símbolos de
sincronización. Estos símbolos de sincronización son el punto y como, el
símbolo end o cualquier palabra clave que pueda ser el inicio de una
proposición nueva, por ejemplo. Es fácil implantar la recuperación de
emergencia, pero sólo reconoce un error por proporción. Esto no
necesariamente es una desventaja, ya que no es muy probable que ocurran
varios errores en la misma proposición (véase [RIPL 78], por ejemplo). Esta
suposición es un ejemplo típico del carácter heurístico de esta estrategia.
2. Recuperación por inserción, borrado y reemplazo: éste también es un método
fácil de implantar y funciona bien en ciertos casos de error. Usemos como
ejemplo una declaración de variable en PASCAL, cuando una coma va seguida
por dos puntos, en lugar de un nombre de variable, es posible eliminar esta
coma. En forma similar, se puede insertar un punto y coma omitido o
reemplazar un punto y coma por una coma en una lista de parámetros.
3. Recuperación por expansión de gramática: De acuerdo con [RIPL, 78], el 60% de
los errores en los programas fuente son errores de puntuación, por ejemplo, la
escritura de un punto y coma en lugar de una coma, o viceversa. Una forma de
recuperarse de estos errores es legalizarlos en ciertos casos, introduciendo lo que
llamaremos producciones de error en la gramática del lenguaje de programación.
La expansión de la gramática con estas producciones no quiere decir que ciertos
errores no serán detectados, ya que pueden incluirse acciones para informar de su
detección.
La recuperación de emergencia es la estrategia que se encontrará en la mayoría
de los compiladores, pero la legalización de ciertos errores mediante la definición
156
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
de una gramática aumentada es una técnica que se emplea con frecuencia. No
obstante, hay que expandir la gramática con mucho cuidado para asegurarse de
que no cambien el tipo y las características de la gramática.
Los errores de sintaxis se detectan cuando el analizador sintáctico espera un
símbolo que no concuerda con el símbolo que está analizando. En los
analizadores sintácticos LL, los errores de sintaxis se detectan cuando a y el no
terminal que están en la cima de la pila nos llevan a un índice de una posición
vacía de la tabla de análisis sintáctico. En los analizadores sintácticos LR, los
errores de sintaxis se detectan cuando hay un índice a una posición vacía de la
tabla, o sea, cuando no se especifica ninguna transición al analizar á en el estado
actual. Sin embargo, si se emplea una gramática aumentada con producciones de
error adicionales, no sólo se detectarán errores por medio de los índices a
posiciones vacías de la tabla de análisis sintáctico.
6.9 Generadores de analizadores sintácticos.
El análisis léxico facilita la tarea de reconocer los elementos de un lenguaje uno a
uno. El análisis sintáctico nos permitirá averiguar si un archivo de entrada
cualquiera respeta las reglas de una gramática concreta.
Básicamente se cuenta con dos ejemplos de generadores de análisis sintáctico:
YACC y BISON.
Las siglas del nombre YACC significan "Yet Another Compiler Compiler". YACC
genera un analizador sintáctico (la parte de un compilador que intenta darle
sentido a la entrada) basado en una gramática analítica escrita en una notación
BNF. YACC genera el código para el analizador sintáctico en el Lenguaje de
programación C. YACC es un programa informático muy común en los sistemas
UNIX. A partir de un archivo fuente en YACC, se genera un archivo fuente en C
que contiene el analizador sintáctico. Sin embargo, un analizador sintáctico de
YACC no puede funcionar por sí solo, sino que necesita un analizador léxico
externo para funcionar. Dicho de otra manera, el código fuente en C que genera
YACC contiene llamadas a una función yylex() que debe estar definida y debe
devolver el tipo de lexema encontrado. Además, es necesario incorporar también
una función yyerror(), que será invocada cuando el analizador sintáctico
encuentre un símbolo que no encaja en la gramática.
Un programa fuente de YACC se parece bastante a uno de LEX. La diferencia
principal está en la sección de reglas, que en vez de expresiones regulares
contiene las reglas de la gramática, Ver Fig. 5.17.
YACC fue desarrollado por Stephen C. Johnson en AT&T para el sistema
operativo de UNIX. Después se escribieron programas compatibles, por ejemplo
157
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Berkeley YACC, GNU BISON, MKS YACC y Abraxas YACC (una versión
actualizada de la versión original de AT&T que también es software libre como
parte del proyecto de OpenSolaris de Sun). Cada una ofrece mejoras leves y
características adicionales sobre el YACC original, pero el concepto ha seguido
siendo igual. YACC también se ha reescrito para otros lenguajes, incluyendo
Ratfor, EFL, ML, Ada, Java, y Limbo.
6.9.1. BISON (Programa generador de analizadores sintácticos de
propósito general perteneciente al proyecto GNU).
Bison es un generador de analizadores sintácticos de propósito general que
convierte una descripción para una gramática independiente del contexto (en
realidad de una subclase de éstas, las LALR) en un programa en C, C++,
o Java que analiza esa gramática.
BISON: es un programa generador de analizadores sintácticos de propósito
general perteneciente al proyecto GNU:
• BISON pertenece al proyecto GNU. GNU es un acrónimo recursivo que
significa GNU No es Unix (GNU is Not Unix) bajo licencia GPL (Licencia
Pública General), disponible para prácticamente todos
los sistemas operativos.
• Se usa normalmente acompañado de FLEX aunque los analizadores
léxicos se pueden también obtener de otras formas.
• Es compatible al 100% con YACC, una herramienta clásica de UNIX para la
generación de analizadores sintácticos, pero es un desarrollo diferente
realizado por GNU.
• Es utilizado para crear analizadores para muchos lenguajes, desde simples
calculadoras hasta lenguajes complejos.
• Para utilizar BISON, es necesaria experiencia con el la sintaxis usada para
describir gramáticas.
• Todas las gramáticas bien escritas para Yacc, funcionan en Bison sin
necesidad de ser modificadas. Cualquier persona que esté familiarizada con
YACC podría utilizar BISON sin problemas.
• Usándolo junto a FLEX esta herramienta permite construir compiladores de
lenguajes.
• BISON fue escrito en un principio por Robert Corbett; Richard Stallman lo
hizo compatible con Yacc y Wilfred Hansen de la Carnegie Mellon
University añadió soporte para literales multicaracter y otras características.
158
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
• Un archivo fuente para BISON (normalmente un archivo con extensión .y)
describe una gramática.
• El ejecutable que se genera indica si un archivo de entrada dado pertenece
o no al lenguaje generado por esa gramática.
La manera habitual de invocar a Bison es la siguiente:
bison archivo-entrada
Aquí archivo-entrada es el nombre del archivo de la gramática, que normalmente
termina en ‘.y’. El nombre del archivo del analizador se construye reemplazando
el ‘.y’ con ‘.tab.c’. Así, el nombre de archivo ‘bison foo.y’ produce ‘[Link].c’, y el
nombre de archivo ‘bison hack/foo.y’ produce ‘hack/[Link].c’.
Opciones de BISON
BISON soporta las opciones tradicionales de una única letra y nombres de opción
mnemónicos largos. Los nombres de opción largos se indican con ‘—‘ en lugar
de ‘-‘. Las abreviaciones para los nombres de opción se permiten siempre que
sean únicas. Cuando una opción larga toma un argumento, como ‘--file-prefix’, se
conecta el nombre de la opción con el argumento con ‘=’.
Aquí hay una lista de opciones que puede utilizar con BISON, alfabetizadas por la
opción corta.
‘-b prefijo-archivo’
‘--file-prefix=prefijo’
Especifica un prefijo a ser usado por todos los nombres de archivo de salida
de BISON. Los nombres se eligen como si el archivo de entrada se
llamase `prefijo.c'.
‘-d’
‘—defines’
Escribe un archivo extra de salida conteniendo las definiciones de las
macros para los nombres de tipo de tokens definidos en la gramática y el
tipo de valor semántico YYSTYPE, además de unas cuantas declaraciones
de variables extern. Si el archivo de salida del analizador se
llama ‘name.c’ entonces este archivo se llama ‘name.h’. Este archivo de
salida es esencial si desea poner las definiciones de yylex en un archivo
fuente por separado, porque yylex necesita ser capaz de hacer referencia a
los códigos de tipo de token y las variables yylval.
‘-l’
‘--no-lines’
No pone ningún comando #line del preprocesador en el archivo del
analizador. Normalmente BISON los pone en el archivo del analizador de
159
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
manera que el compilador de C y los depuradores asocien errores con su
archivo fuente, el archivo de la gramática. Esta opción hace que asocien los
errores con el archivo del analizador, tratándolo como un archivo fuente
independiente por derecho propio.
‘-n’
‘--no-parser’
No incluye ningún código C en el archivo del analizador; genera únicamente
las tablas. El archivo del analizador contiene sólo directivas #define y
declaraciones de variables estáticas. Esta opción también le dice a BISON
que escriba el código C para las acciones gramaticales en un archivo
llamado `[Link]', en la forma de un cuerpo encerrado entre
llaves para formar una sentencia switch.
‘-o archivo-salida’
‘--output-file=archivo-salida’
Especifica el nombre archivo-salida para el archivo del analizador. El resto
de los nombres de archivo de salida son construidos a partir de archivo-
salida como se describió bajo las opciones ‘-v’ y ’-d’.
‘-p prefijo’
‘--name-prefix=prefijo’
Renombra los símbolos externos utilizados en el analizador de manera que
comiencen con prefijo en lugar de ‘yy’. La lista precisa de símbolos
renombrados es yyparse, yylex, yyerror,yynerrs, yylval, yychar y
yydebug. Por ejemplo, si utiliza ‘-p c’, los nombres serán cparse, clex,
etc.
‘-r’
‘—raw’
Hace que parezca que haya sido especificado %raw.
‘-t’
‘—debug’
Produce una definición de la macro YYDEBUG en el archivo del analizador,
de manera que las facilidades de depuración sean compiladas.
‘-v’
‘—verbose’
Escribe un archivo de salida extra conteniendo descripciones amplias de los
estados del analizador y qué se hace para cada tipo de token de
preanálisis en ese estado. Este archivo también describe todos los
conflictos, aquellos resueltos por la precedencia de operadores y los no
resueltos. Este nombre de archivo se construye quitando ‘.tab.c’ o ‘.c’ del
nombre de salida del analizador, y añadiendo ‘.output’ en su lugar. Por lo
tanto, si el archivo de entrada es ‘foo.y', entonces el archivo del analizador
se llama ‘[Link].c’ por defecto. Como consecuencia, el archivo de salida
amplia se llama ‘[Link]'.
‘-V’
‘—version’
Imprime el número de versión de BISON y termina.
‘-h’
‘—help’
160
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Imprime un sumario de las opciones de línea de comando de BISON y
termina.
‘-y’
‘—yacc’
‘--fixed-output-files’
Equivalente a ‘-o [Link].c’; el archivo de salida del analizador se
llama ‘[Link].c', y el resto de salida se llama ‘[Link]’ y ‘[Link].h’. El
propósito de esta opción es la de imitar las convenciones de los nombres
de archivo de YACC. De este modo, el siguiente script de comandos puede
ser sustituto de YACC: bison -y $*
Formato del archivo de entrada para BISON.
La forma general de una gramática de BISON se muestra en la Fig. 6.34.
%{
Declaraciones en C
%}
Declaraciones de Bison
%%
Reglas gramaticales
%%
Código C adicional
Figura 6.34. Estructura del Archivo para BISON.
De acuerdo con la Fig. 6.34, los ‘%%’, ‘%{‘y ‘%}’ son signos de puntuación que
aparecen en todo archivo de gramática de BISON para separar las secciones.
[Link]. Declaraciones en C.
Las declaraciones en C pueden definir tipos y variables utilizadas en las acciones.
Puede también usar comandos del preprocesador para definir macros que se
utilicen ahí, y utilizar #include para incluir archivos de cabecera que realicen
cualquiera de estas cosas.
[Link]. Declaraciones de BISON.
En la sección de declaraciones de BISON se declaran los nombres de los
símbolos terminales y no terminales, y también podrían describir la precedencia de
operadores y los tipos de datos de los valores semánticos de varios símbolos.
[Link]. Reglas Gramaticales.
Las reglas gramaticales son las producciones de la gramática, que además
pueden llevar asociadas acciones, código en C, que se ejecutan cuando el
analizador encuentra las reglas correspondientes.
161
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
[Link]. Código C adicional.
El código C adicional puede contener cualquier código C que desee utilizar. A
menudo suele ir la definición del analizador léxico yylex, más subrutinas
invocadas por las acciones en las reglas gramaticales. En un programa simple,
todo el resto del programa puede ir aquí.
[Link]. Símbolos, terminales y no terminales.
Los símbolos terminales de la gramática se denominan en BISON tokens y deben
declararse en la sección de definiciones. Por convención se suelen escribir los
tokens en mayúsculas y los símbolos no terminales en minúsculas.
Hay tres maneras de escribir símbolos terminales en la gramática. Aquí se
describen las dos más usuales:
• Un token declarado se escribe con un identificador, de la misma manera que un
identificador en C. Por convención, debería estar todo en mayúsculas. Cada uno
de estos nombres debe definirse con una declaración de %token.
• Un token de carácter se escribe en la gramática utilizando la misma sintaxis
usada en C para las constantes de un carácter; por ejemplo, ‘+’ es un tipo de
token de carácter. Un tipo de token de carácter no necesita ser declarado a menos
que necesite especificar el tipo de datos de su valor semántico, asociatividad, o
precedencia. Por convención, un token de caracter se utiliza únicamente para
representar un token consistente en ese caracter en particular.
[Link]. Sintaxis de las reglas gramaticales (producciones).
Una regla gramatical de BISON tiene la siguiente forma general:
resultado: componentes...
;
donde
resultado es el símbolo no terminal que describe esta regla y componentes son los
diversos símbolos terminales y no terminales que están reunidos por esta regla.
Por ejemplo:
exp: exp ‘+’ exp
;
Aquí se especifica que dos agrupaciones de tipo exp, con un token ‘+’ en medio,
puede combinarse en una agrupación mayor de tipo exp.
162
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Los espacios en blanco en las reglas son significativos únicamente para separar
símbolos. Puede añadir tantos espacios en blanco extra como desee.
Distribuidas en medio de los componentes puede haber acciones que determinan
la semántica de la regla. Una acción tiene el siguiente aspecto:
{sentencias en C}
Normalmente hay una única acción que sigue a los componentes.
Se pueden escribir por separado varias reglas para el mismo resultado o pueden
unirse con el caracter de barra vertical ‘|’ así:
resultado: componentes-regla1...
| componentes-regla2...
...
;
Estas aún se consideran reglas distintas incluso cuando se unen de esa manera.
Si los componentes en una regla están vacíos, significa que resultado puede
concordar con la cadena vacía (en notación formal sería ε). Por ejemplo, aquí
aparece cómo definir una secuencia separada por comas de cero o más
agrupaciones exp:
expseq: /* vacío */
| expseq1
;
Es habitual escribir el comentario ‘/* vacío */’ en cada regla sin componentes.
Una regla se dice recursiva cuando su no-terminal resultado aparezca también en
su lado derecho. Casi todas las gramáticas de BISON hacen uso de la recursión,
ya que es la única manera de definir una secuencia de cualquier número de cosas.
Considere esta definición recursiva de una secuencia de una o más expresiones:
expseq1: exp
| expseq1 ‘,’ exp
;
Puesto que en el uso recursivo de expseq1 este es el símbolo situado más a la
izquierda del lado derecho, llamaremos a esto recursión por la izquierda. Por
contraste, aquí se define la misma construcción utilizando recursión por la
derecha:
expseq1: exp
| exp ‘,’ expseq1
;
163
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Cualquier tipo de secuencia se puede definir utilizando ya sea la recursión por la
izquierda o recursión por la derecha, pero debería utilizar siempre recursión por la
izquierda, porque puede analizar una secuencia de elementos sin ocupar espacio
de pila (es decir, de forma mucho más eficiente en memoria). La recursión
indirecta o mutua sucede cuando el resultado de la regla no aparece directamente
en su lado derecho, pero aparece en las reglas de otros no terminales que
aparecen en su lado derecho.
Por ejemplo:
expr: primario
| primario ‘+’ primario
;
primario: constante
| ‘(‘ expr ‘)’
;
define dos no-terminales recursivos mutuamente, ya que cada uno hace referencia
al otro.
Semántica del lenguaje
Las reglas gramaticales para un lenguaje determinan únicamente la sintaxis. La
semántica viene determinada por los valores semánticos asociados con varios
tokens y agrupaciones, y por las acciones tomadas cuando varias agrupaciones
son reconocidas.
En un programa sencillo podría ser suficiente con utilizar el mismo tipo de datos
para los valores semánticos de todas las construcciones del lenguaje. Por defecto
BISON utiliza el tipo int para todos los valores semánticos. Para especificar algún
otro tipo, defina YYSTYPE como una macro, de esta manera:
#define YYSTYPE double
Esta definición de la macro debe ir en la sección de declaraciones en C del archivo
de la gramática.
En la mayoría de los programas, se necesitarán diferentes tipos de datos para
diferentes clases de tokens y agrupaciones. Por ejemplo, una constante numérica
podría necesitar el tipo int o long, mientras que una cadena constante necesita el
tipo char *.
Para utilizar más de un tipo de datos para los valores semánticos en un
analizador, BISON requiere dos cosas:
o Especificar la colección completa de tipos de datos posibles, con la declaración
de BISON %union.
164
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
o Elegir uno de estos tipos para cada símbolo (terminal o no terminal). Esto se
hace para los tokens con la declaración de BISON %token y para los no
terminales con la declaración de BISON %type.
Acciones
Una acción acompaña a una regla sintáctica y contiene código C a ser ejecutado
cada vez que se reconoce una instancia de esa regla. La tarea de la mayoría de
las acciones es computar el valor semántico para la agrupación construida por la
regla a partir de los valores semánticos asociados a los tokens o agrupaciones
más pequeñas.
Una acción consiste en sentencias de C rodeadas por llaves, muy parecidas a las
sentencias compuestas en C. Se pueden situar en cualquier posición dentro de la
regla; la acción se ejecuta en esa posición.
El código C en una acción puede hacer referencia a los valores semánticos de los
componentes reconocidos por la regla con la construcción $n, que hace referencia
al valor de la componente n-ésima. El valor semántico para la agrupación que se
está construyendo es $$. Aquí hay un ejemplo típico:
exp: ...
| exp ‘+’ exp
{ $$ = $1 + $3; }
Esta regla construye una exp de dos agrupaciones exp más pequeñas
conectadas por un token de signo más. En la acción, $1 y $3 hacen referencia a
los valores semánticos de las dos agrupaciones exp componentes, que son el
primer y tercer símbolo en el lado derecho de la regla. La suma se almacena en $$
de manera que se convierte en el valor semántico de la expresión de adición
reconocida por la regla. Si hubiese un valor semántico útil asociado con el token
‘+’, debería hacerse referencia con $2.
Si no especifica una acción para una regla, BISON suministra una por defecto:
$$ = $1.
De este modo, el valor del primer símbolo en la regla se convierte en el valor de la
regla entera. Por supuesto, la regla por defecto solo es válida si concuerdan los
dos tipos de datos. No hay una regla por defecto con significado para la regla
vacía; toda regla vacía debe tener una acción explícita a menos que el valor de la
regla no importe.
165
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Tipos de Datos de Valores en Acciones.
Si ha elegido un tipo de datos único para los valores semánticos, las
construcciones $$ y $n siempre tienen ese tipo de datos.
Si ha utilizado %union para especificar una variedad de tipos de datos, entonces
debe declarar la elección de entre esos tipos para cada símbolo terminal y no
terminal que puede tener un valor semántico. Entonces cada vez que utilice $$ o
$n, su tipo de datos se determina por el símbolo al que hace referencia en la regla.
En este ejemplo:
exp: ...
| exp ‘+’ exp
{ $$ = $1 + $3; }
$1 y $3 hacen referencia a instancias de exp, de manera que todos ellos tienen el
tipo de datos declarado para el símbolo no terminal exp. Si se utilizase $2, tendría
el tipo de datos declarado para el símbolo terminal ‘+’, cualquiera que pudiese ser.
De forma alternativa, puede especificar el tipo de datos cuando se hace referencia
al valor, insertando ‘<tipo>’ después del ‘$’ al comienzo de la referencia. Por
ejemplo, si ha definido los tipos como se muestra aquí:
%union {
int tipoi;
double tipod;
}
entonces puede escribir $<tipoi>1 para hacer referencia a la primera subunidad
de la regla como un entero, o $<tipod>1 para referirse a este como un double.
Ejemplo. Calculadora de Notación Polaca Inversa.
Este ejemplo es el de una simple calculadora de doble precisión de notación
polaca inversa (una calculadora que utiliza operadores postfijos). Este ejemplo
provee un buen punto de partida, ya que no hay problema con la precedencia de
operadores. El código fuente para esta calculadora se llama `rpcalc.y'. La
extensión `.y' es una convención utilizada para los archivos de entrada de BISON.
El código fuente para esta calculadora se llama `rpcalc.y'. La extensión `.y' es una
convención utilizada para los archivos de entrada de Bison.
166
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
Declaraciones para rpcalc:
En la Fig. 6.35, están las declaraciones de C y BISON para la calculadora de
notación polaca inversa. Como en C, los comentarios se colocan entre `/*...*/'.
/* Calculadora de notación polaca inversa. */
%{
#define YYSTYPE double
#include <math.h>
%}
%token NUM
%% /* A continuación las reglas gramaticales y las acciones
*/
Figura. 6.35. Declaraciones de C y BISON para la calculadora de
notación polaca inversa.
La sección de declaraciones en C contiene dos directivas del [Link]
directiva #define define la macro YYSTYPE, de este modo se especifica el tipo de
dato de C para los valores semánticos de ambos, tokens y agrupaciones. El
analizador de BISON utilizará cualquier tipo que se defina para YYSTYPE; si no lo
define, por defecto es int. Como hemos especificado double, cada token y cada
expresión tiene un valor asociado, que es un número en punto flotante.
La directiva #include se utiliza para declarar la función de exponenciación pow.
La segunda sección, declaraciones de BISON, provee información a BISON
acerca de los tipos de tokens. Cada símbolo terminal que no sea un caracter literal
simple debe ser declarado aquí (Los caracteres literales simples no necesitan ser
declarados.) En este ejemplo, todos los operadores aritméticos se designan por un
caracter literal simple, así que el único símbolo terminal que necesita ser
declarado es NUM, el tipo de token para las constantes numéricas.
Reglas Gramaticales para rpcalc.
En la fig. 6.36, están las reglas gramaticales para una calculadora de notación
polaca inversa.
167
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
input: /* vacío */
| input line
;
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
exp: NUM { $$ = $1; }
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
| exp exp '*' { $$ = $1 * $2; }
| exp exp '/' { $$ = $1 / $2; }
/* Exponenciación */
| exp exp '^' { $$ = pow ($1, $2); }
/* Menos unario */
| exp 'n' { $$ = -$1; }
;
%%
Figura. 6.36. Reglas gramaticales para una calculadora de notación polaca
inversa.
Las agrupaciones del "lenguaje" de rpcalc definidas en la Fig. 6.36, son la
expresión (con el nombre exp), la línea de entrada (line), y la transcripción
completa de la entrada (input). Cada uno de estos símbolos no terminales tiene
varias reglas alternativas, unidas por el símbolo ‘|’ que se lee como "o". Las
siguientes secciones explican lo que significan estas reglas.
La semántica del lenguaje se determina por las acciones que se toman cuando
una agrupación es reconocida. Las acciones son el código C que aparecen entre
llaves.
Debe especificar estas acciones en C, pero BISON facilita la forma de pasar
valores semánticos entre las reglas. En cada acción, la pseudo-
variable $$ representa el valor semántico para la agrupación que la regla va a
construir. El trabajo principal de la mayoría de las acciones es la asignación de un
valor para $$. Se accede al valor semántico de los componentes de la regla
con $1, $2, y así sucesivamente.
Explicación para input
Considere la definición de input:
168
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
input: /* vacío */
| input line
;
Esta definición se interpreta así: "Una entrada completa es o una cadena vacía, o
una entrada completa seguida por una línea de entrada". Note que "entrada
completa" se define en sus propios términos. Se dice que esta definición
es recursiva por la izquierda ya que input aparece siempre como el símbolo más
a la izquierda en la secuencia.
La primera alternativa está vacía porque no hay símbolos entre los dos puntos y el
primer símbolo ‘|’; esto significa que input puede corresponder con una cadena de
entrada vacía (sin tokens). Escribimos estas reglas de esa manera porque es
legítimo escribir Ctrl-d después de arrancar la calculadora. Es clásico poner una
alternativa vacía al principio y escribir en esta el comentario '/* vacío */'’.
La segunda alternativa de la regla (input line) maneja toda la entrada no trivial. Esta
significa, "Después de leer cualquier número de líneas, leer una más si es
posible". La recursividad por la izquierda convierte esta regla en un ciclo. Ya que la
primera alternativa concuerda con la entrada vacía, el ciclo se puede ejecutar cero
o más veces.
La función yyparse del analizador continúa con el procesamiento de la entrada
hasta que se encuentre con un error gramatical o el analizador diga que no hay
más tokens de entrada; convendremos que esto último sucederá al final del
archivo.
Explicación para line
Ahora considere la definición de line:
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
La primera alternativa es un token que es un caracter de nueva-línea; esta quiere
decir que rpcalc acepta una línea en blanco (y la ignora, ya que no hay ninguna
acción). La segunda alternativa es una expresión seguida de una línea nueva.
Esta es la alternativa que hace que rpcalc sea útil. El valor semántico de la
agrupación exp es el valor de $1 porque la exp en cuestión es el primer símbolo en
la alternativa. La acción imprime este valor, que es el resultado del cálculo que
solicitó el usuario.
Esta acción es poco común porque no asigna un valor a $$. Como consecuencia,
el valor semántico asociado con line está sin inicializar (su valor será
impredecible). Se trataría de un error si ese valor se utilizara, pero nosotros no lo
169
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
utilizaremos: una vez que rpcalc haya imprimido el valor de la línea de entrada del
usuario, ese valor no se necesitará más.
Explicación para expr
La agrupación exp tiene varias reglas, una para cada tipo de expresión. La primera
regla maneja las expresiones más simples: aquellas que son solamente números.
La segunda maneja una expresión de adición, que tiene el aspecto de dos
expresiones seguidas de un signo más. La tercera maneja la resta, y así
sucesivamente.
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
...
;
Se ha utilizado el símbolo `|' para unir las tres reglas de exp, pero igualmente se
podría haber escrito por separado:
exp: NUM ;
exp: exp exp '+' { $$ = $1 + $2; } ;
exp: exp exp '-' { $$ = $1 - $2; } ;
...
La mayoría de las reglas tienen acciones que calculan el valor de la expresión en
términos del valor de sus componentes. Por ejemplo, en la regla de la
adición, $1 hace referencia al primer componente exp y $2 hace referencia al
segundo. El tercer componente, ‘+’, no tiene un valor semántico asociado con
significado, pero si tuviese alguno podría hacer referencia a este con $3.
Cuando yyparse reconoce una expresión de suma usando esta regla, la suma de
los valores de las dos subexpresiones produce el valor de toda la expresión.
No se tiene que dar una acción para cada regla. Cuando una regla no tenga
acción, por defecto BISON copia el valor de $1 en $$. Esto es lo que sucede en la
primera regla (la que usa NUM).
El formato mostrado aquí es la convención recomendada, pero BISON no lo
requiere. Puede añadir o cambiar todos los espacios en blanco que desee. Por
ejemplo, esto:
exp : NUM | exp exp '+' {$$ = $1 + $2; } | ...
expresa lo mismo que esto:
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| ...
El último, sin embargo, es mucho más legible.
170
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
El Analizador Léxico de rpcalc
El trabajo del analizador léxico es el análisis a bajo nivel: la conversión de los
caracteres o secuencia de caracteres en tokens. El analizador de BISON obtiene
sus tokens llamando al analizador léxico.
Solamente se necesita un analizador léxico sencillo para la calculadora de
Notación Polaca Inversa. Este analizador léxico ignora los espacios en blanco y
los tabuladores, luego lee los números como double y los devuelve como
tokens NUM. Cualquier otro caracter que no forme parte de un número es un token
por separado. Tenga en cuenta que el código del token para un token de caracter
simple es el propio caracter.
El valor de retorno de la función de análisis léxico es un código numérico que
representa el tipo de token. El mismo texto que se utilizó en las reglas de BISON
para representar el tipo de token también es una expresión en C con el valor
numérico del tipo. Esto funciona de dos maneras. Si el tipo de token es un caracter
literal, entonces su código numérico es el código ASCII de ese caracter; puede
usar el mismo caracter literal en el analizador léxico para expresar el número. Si el
tipo de token es un identificador, ese identificador lo define BISON como una
macro en C cuya definición es un número apropiado. En este ejemplo, por lo
tanto, NUM se convierte en una macro para que la use yylex.
El valor semántico del token (si tiene alguno) se almacena en la variable
global yylval, que es donde el analizador de BISON lo buscará. (El tipo de datos
de C para yylval es YYSTYPE, que se definió al principio de la gramática.
Se devuelve un código de tipo de token igual a cero cuando se llega al final del
archivo. (BISON reconoce cualquier valor no positivo como indicador del final del
archivo de entrada.)
Aquí está el código para el analizador léxico (Fig. 6.37):
/* El analizador léxico devuelve un número en punto flotante (double) en la pila y
el token NUM, o el caracter ASCII leído si no es un número. Ignora todos los
espacios en blanco y tabuladores, devuelve 0 como EOF. */
171
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
#include <ctype.h>
yylex ()
{
int c;
/* ignora los espacios en blanco */
while ((c = getchar ()) == ' ' || c == '\t')
;
/* procesa números */
if (c == '.' || isdigit (c))
{
ungetc (c, stdin);
scanf ("%lf", &yylval);
return NUM;
}
/* devuelve fin-de-fichero */
if (c == EOF)
return 0;
/* devuelve caracteres sencillos */
return c;
}
Figura 6.37 Código para el analizador léxico
La Función de Control
Para continuar acordes a este ejemplo, la función de control se mantiene escueta
al mínimo. El único requisito es que llame a yyparse para comenzar el proceso de
análisis.
main ()
{
yyparse ();
}
La Rutina de Informe de Errores
Cundo yyparse detecta un error de sintaxis, realiza una llamada a la función de
informe de errores yyerror para que imprima un mensaje de error (normalmente
pero no siempre un "parse error"). Es cosa del programador el proveer yyerror, luego
aquí está la definición que utilizaremos:
172
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
#include <stdio.h>
yyerror (s) /* Llamada por yyparse ante un error */
char *s;
{
printf ("%s\n", s);
}
Después de que yyerror retorne, el analizador de BISON podría recuperarse del
error y continuar analizando si la gramática contiene una regla de error apropiada.
De otra manera, yyparse devolverá un valor distinto de cero. No hemos escrito
ninguna regla de error en este ejemplo, así que una entrada no válida provocará
que termine el programa de la calculadora. Este no es el comportamiento
adecuado para una calculadora real, pero es adecuado en el primer ejemplo.
Ejecutando BISON para Hacer el Analizador
Antes de ejecutar BISON para producir un analizador, necesitamos decidir cómo
ordenar todo en código fuente en uno o más archivos fuente. Para un ejemplo tan
sencillo, la manera más fácil es poner todo en un archivo. Las definiciones
de yylex, yyerror y main van al final, en la sección de "código C adicional" del archivo.
Para un proyecto más grande, probablemente tendría varios archivos fuente, y
utilizaría make para ordenar la recompilación de estos.
Con todo el código fuente en un único archivo, utilice el siguiente comando para
convertirlo en el archivo del analizador:
bison nombre_archivo.y
En este ejemplo el archivo se llamó ‘rpcalc.y’ (de la abreviatura "Reverse Polish
CALCulator", "Calculadora Polaca Inversa"). BISON produce un archivo
llamado `nombre_archivo.tab.c', quitando el ‘.y’ del nombre del archivo original. El
archivo de salida de BISON contiene el código fuente para yyparse. Las funciones
adicionales en el archivo de entrada (yylex, yyerror y main) se copian literalmente a la
salida.
Compilando el Archivo del Analizador
# Lista los archivos en el directorio actual:
% ls
[Link].c rpcalc.y
# Compila el analizador de BISON:
# `-lm' le dice al compilador que busque la librería math para pow.
173
Instituto Tecnológico de Zacatepec. Ingeniería en Sistemas Computacionales. 2013.
Lenguajes y Autómatas I. M.C. Norma J. Ontiveros Hernández. njoh_314@[Link]
% cc [Link].c -lm -o rpcalc
# Lista de nuevo los archivos:
% ls
rpcalc [Link].c rpcalc.y
El archivo ‘rpcalc’ contiene ahora el código ejecutable. He aquí una sesión de
ejemplo utilizando rpcalc.
% rpcalc
49+
13
3 7 + 3 4 5 *+-
-13
37+345*+-n Note el menos unario, `n'
13
56/4n+
-3.166666667
34^ Exponenciación
81
^D Indicador de Fin-de-archivo
%
174
También podría gustarte
- Gramática Libre de Contexto: Definición y UsoAún no hay calificacionesGramática Libre de Contexto: Definición y Uso9 páginas
- Análisis Sintáctico en CompiladoresAún no hay calificacionesAnálisis Sintáctico en Compiladores21 páginas
- Análisis Sintáctico y Gramáticas FormalesAún no hay calificacionesAnálisis Sintáctico y Gramáticas Formales19 páginas
- Árbol de Derivación en GramáticasAún no hay calificacionesÁrbol de Derivación en Gramáticas11 páginas
- Lenguajes Libres de Contexto y GramáticasAún no hay calificacionesLenguajes Libres de Contexto y Gramáticas16 páginas
- Gramáticas y Lenguajes de Contexto LibreAún no hay calificacionesGramáticas y Lenguajes de Contexto Libre20 páginas
- Gramáticas de Libre Contexto y Árboles de DerivaciónAún no hay calificacionesGramáticas de Libre Contexto y Árboles de Derivación4 páginas
- Gramáticas de Libre Contexto y AmbigüedadAún no hay calificacionesGramáticas de Libre Contexto y Ambigüedad4 páginas
- Máquinas de Estados Finito en Matemática DiscretaAún no hay calificacionesMáquinas de Estados Finito en Matemática Discreta17 páginas
- Teoría de La Computación: Gramática Libre de Contexto100% (2)Teoría de La Computación: Gramática Libre de Contexto9 páginas
- Rodriguez Joan 12 1030 GramaticaLibreDeContextoAún no hay calificacionesRodriguez Joan 12 1030 GramaticaLibreDeContexto12 páginas
- Gramática y Máquinas de Estados FinitosAún no hay calificacionesGramática y Máquinas de Estados Finitos10 páginas
- Análisis Sintáctico en Lenguajes de Programación100% (2)Análisis Sintáctico en Lenguajes de Programación21 páginas
- Gramáticas Libres del Contexto y BNFAún no hay calificacionesGramáticas Libres del Contexto y BNF3 páginas
- Estructura de Árboles de DerivaciónAún no hay calificacionesEstructura de Árboles de Derivación7 páginas
- Introducción a Gramáticas de Libre ContextoAún no hay calificacionesIntroducción a Gramáticas de Libre Contexto187 páginas
- Introducción A Gramáticas FormalesAún no hay calificacionesIntroducción A Gramáticas Formales24 páginas
- Análisis Gramatical en ProgramaciónAún no hay calificacionesAnálisis Gramatical en Programación12 páginas
- Análisis Sintáctico Investigacion Unidad 5Aún no hay calificacionesAnálisis Sintáctico Investigacion Unidad 519 páginas
- Gramáticas Independientes del ContextoAún no hay calificacionesGramáticas Independientes del Contexto3 páginas
- Gramáticas Independientes del ContextoAún no hay calificacionesGramáticas Independientes del Contexto52 páginas
- Árboles de Derivación en GramáticasAún no hay calificacionesÁrboles de Derivación en Gramáticas2 páginas
- Gramáticas Independientes del ContextoAún no hay calificacionesGramáticas Independientes del Contexto16 páginas
- Análisis Sintáctico y Gramáticas CFGAún no hay calificacionesAnálisis Sintáctico y Gramáticas CFG75 páginas
- Lenguajes Independientes del ContextoAún no hay calificacionesLenguajes Independientes del Contexto50 páginas
- Comparativa de Gramáticas FormalesAún no hay calificacionesComparativa de Gramáticas Formales7 páginas
- Métodos Formales de Describir La Sintaxis - PPLAún no hay calificacionesMétodos Formales de Describir La Sintaxis - PPL15 páginas
- Gramáticas y su Aplicación en LenguajesAún no hay calificacionesGramáticas y su Aplicación en Lenguajes16 páginas
- Tipos de Gramáticas y su AplicaciónAún no hay calificacionesTipos de Gramáticas y su Aplicación16 páginas
- Evolución de Lenguajes de ProgramaciónAún no hay calificacionesEvolución de Lenguajes de Programación15 páginas
- Gramáticas Libres de Contexto: RepasoAún no hay calificacionesGramáticas Libres de Contexto: Repaso22 páginas
- Autoevaluacion#2Automatas2 IsmarCortez 0901 21 506Aún no hay calificacionesAutoevaluacion#2Automatas2 IsmarCortez 0901 21 50618 páginas
- Introducción a Lenguajes FormalesAún no hay calificacionesIntroducción a Lenguajes Formales9 páginas
- Tema 15. Árboles de Derivación y AmbigüedadAún no hay calificacionesTema 15. Árboles de Derivación y Ambigüedad18 páginas
- Fundamentos de Lenguajes FormalesAún no hay calificacionesFundamentos de Lenguajes Formales12 páginas
- Gramáticas y Autómatas en Lenguajes FormalesAún no hay calificacionesGramáticas y Autómatas en Lenguajes Formales6 páginas
- INVESTIGACION ANALIZADOR SINTACTICO - Sandoval Alvarez IsidroAún no hay calificacionesINVESTIGACION ANALIZADOR SINTACTICO - Sandoval Alvarez Isidro10 páginas
- Árboles de Derivación en GIC y AmbigüedadAún no hay calificacionesÁrboles de Derivación en GIC y Ambigüedad21 páginas
- Análisis Sintáctico y Gramáticas en ProgramaciónAún no hay calificacionesAnálisis Sintáctico y Gramáticas en Programación6 páginas
- Gramatica Libre de Contexto (GLC)Aún no hay calificacionesGramatica Libre de Contexto (GLC)7 páginas
- Lenguajes Libres y Autómatas de PilasAún no hay calificacionesLenguajes Libres y Autómatas de Pilas49 páginas
- Función y Diseño del Analizador SintácticoAún no hay calificacionesFunción y Diseño del Analizador Sintáctico13 páginas
- Compiladores Unidad 3 Análisis SintácticoAún no hay calificacionesCompiladores Unidad 3 Análisis Sintáctico21 páginas
- Configuración del Registro en Windows 10Aún no hay calificacionesConfiguración del Registro en Windows 109 páginas
- Crear y Gestionar Usuarios en Windows 10Aún no hay calificacionesCrear y Gestionar Usuarios en Windows 1020 páginas
- Prácticas de LabVIEW en IngenieríaAún no hay calificacionesPrácticas de LabVIEW en Ingeniería32 páginas
- Contrato Servicio Web Broker ExpedienteAún no hay calificacionesContrato Servicio Web Broker Expediente12 páginas
- Evolución y Futuro de los PortátilesAún no hay calificacionesEvolución y Futuro de los Portátiles3 páginas
- Ejercicios de Algoritmos de Búsqueda y OrdenaciónAún no hay calificacionesEjercicios de Algoritmos de Búsqueda y Ordenación16 páginas
- Historia de los Microprocesadores IntelAún no hay calificacionesHistoria de los Microprocesadores Intel17 páginas
- Configuración OSPF en Mikrotik Freddy BeltranAún no hay calificacionesConfiguración OSPF en Mikrotik Freddy Beltran8 páginas
- Algoritmos de Encaminamiento en RedesAún no hay calificacionesAlgoritmos de Encaminamiento en Redes12 páginas
- Introducción a Variables en Visual BasicAún no hay calificacionesIntroducción a Variables en Visual Basic95 páginas
- Bases de Datos Orientadas A ObjetosAún no hay calificacionesBases de Datos Orientadas A Objetos7 páginas
- Guía Completa sobre la BIOS y sus TiposAún no hay calificacionesGuía Completa sobre la BIOS y sus Tipos23 páginas
- Construcción de Un Cluster de 4 Nodos Con Raspberry PiAún no hay calificacionesConstrucción de Un Cluster de 4 Nodos Con Raspberry Pi11 páginas
- Algoritmo Floyd-Warshall: Caminos MínimosAún no hay calificacionesAlgoritmo Floyd-Warshall: Caminos Mínimos4 páginas
- Seguridad de la Información y Controles TIAún no hay calificacionesSeguridad de la Información y Controles TI6 páginas
- Nomad: Orquestador de Aplicaciones EficienteAún no hay calificacionesNomad: Orquestador de Aplicaciones Eficiente4 páginas
- Cracking con OllyDbg: Análisis de IATAún no hay calificacionesCracking con OllyDbg: Análisis de IAT246 páginas
- Guía del Curso de Compiladores 2018/19Aún no hay calificacionesGuía del Curso de Compiladores 2018/1912 páginas
