Compiladores e Interpretes

Análisis sintáctico y gramáticas

libres de contexto.
 Introducció
n
• Análisis Gramatical o sintáctico:

Tarea de determinar la sintaxis de un programa.

• La sintaxis de un lenguaje se determina normalmente por una gramática

libre de contexto, de forma similar a como el análisis usa las expresiones
regulares para determinar los tokens o testigos de un lenguaje.

• Con la única diferencia de que las reglas de gramáticas libres de contexto son
recursivas.

• Las estructuras de datos utilizadas para representar la estructura sintáctica de

un lenguaje ahora también deben ser recursivas, siendo usado por lo general
alguna clase de árbol, que se conoce como árbol de análisis gramatical o árbol
sintáctico.
 Introducció n
• Análisis Gramatical o sintáctico:

El análisis sintáctico describe las funciones de ciertas unidades gramaticales (palabras y oraciones) insertas en una
unidad superior, la oración. Se trata de explicar qué papel desempeñan para que la oración posea significación
completa e independencia estructural

Esta presentación sigue la gramática clásica. Se debe tener en cuenta porque se pueden encontrar otras
aproximaciones razonables, en las que además cambia la nomenclatura. El rendimiento pedagógico de este tema es
más que dudoso, pero como los programas de estudio lo exigen imperativamente, lo ofrecemos aquí como
complemento de alumnos y profesores. Acaso les ayude a adquirir unas destrezas analíticas suficientes. La
presentación busca la claridad y brevedad, de modo que no ha lugar a una casuística minuciosa, excepciones mínimas
o disquisiciones teóricas.
 El Proceso de Aná lisis
Sintáctico
• Se puede ver al analizador sintáctico como una función que toma
como su entrada la secuencia de tokens o testigos producida por
el analizador léxico y que produce como su salida el árbol
sintáctico.
Analizador sintáctico
Secuencia de testigos árbol sintáctico

NO Siendo esta secuencia de testigos un parámetro de entrada

explícito, sino normalmente es la llamada a un procedimiento del
analizador léxico para obtener el siguiente testigo o token desde
la entrada a medida que se necesite durante el proceso de análisis
sintáctico.
 El Proceso de aná lisis
sintáctico
• Por lo general los compiladores son de múltiples pasadas, en cuyo
caso las entradas adicionales usaran el árbol sintáctico como su
entrada.

• Ahora el problema de tratamiento de errores es más difícil que

durante el análisis léxico, igualmente no se debe mostrar solo un
mensaje de error, sino que se debe recuperar del error y continuar
el análisis sintáctico para encontrar tantos errores como sea posible.
 Gramá ticas Libres de
Contexto
• Es una especificación para la estructura sintáctica de un lenguaje.
Por ejemplo, las expresiones aritméticas simples de enteros con
operaciones de suma, resta y multiplicación, se podrían dar con la
siguiente gramática:

exp  exp op exp | (exp) | número

op  + | - | *
Notació n Gramá ticas Libres de
Contexto Vs Expresiones regulares
• En las expresiones regulares tenemos tres operaciones básicas: selección (|),
concatenación, y repetición ( * ), por ejemplo:

número = dígito dígito*

dígito = 0|1|2|3|4|5|6|7|8|9

• En la reglas gramaticales también existe una notación semejante: la barra

vertical es símbolo de selección, la concatenación también existe, sin embargo
no hay metasímbolo para la repetición, una diferencia es que ahora se usará una
flecha
en lugar de igual para representar la definición de nombres. Por ejemplo se
puede observar que en la gramática definida la repetición se logra con la
recursividad en la regla exp, igualmente se usan expresiones regulares como
componentes de las reglas (número, ( ), +, -, * )

exp  exp op exp | (exp) | número

op  + | - | *
• Siendo esta notación creadas por primera vez por Jhon Backus y adaptadas para
el informe Algol60 por Peter Naur, conociéndose entonces como las reglas
gramaticales en la forma Backus-Naur o BNF.
 Especificació n de una gramá tica
libre
de
contexto
• Como la expresiones regulares, las reglas gramaticales están definidas
sobre un alfabeto o conjunto de símbolos.

• En el caso de expresiones regulares estos símbolos eran el alfabeto,

pero ahora son generalmente testigos o tokens que representan
cadenas del lenguaje.

• Dado un alfabeto una regla gramatical se compone libre de contexto

en BNF se compone de una cadena de símbolos:
1. Primero el nombre de la estructura.
2. El metasímbolo .
3. Una cadena de símbolos compuesta por un símbolo del alfabeto, un
nombre de una estructura o el metasímbolo de selección (|).
 Especificació n de una gramá tica
libre
de
contexto
• Informalmente se puede decir que una regla BNF, se define por el
nombre que se encuentra a la izquierda de la flecha, estructurando la
misma para que incluya una de las selecciones del lado derecho
separadas por barras verticales, por ejemplo:

exp  exp op exp | (exp) | número

op  + | - | *
1. En la primera regla se define la expresión (exp) compuesta por: una
expresión seguida de un operador y una expresión, por una
expresión dentro de paréntesis o bien por un número.

2. La segunda regla define un operador (op) compuesto por uno de los

símbolos de suma, resta o multiplicación.
 Especificació n de una gramá tica
libre
de
contexto
• Aunque los metasímbolo anteriores son de uso general, no existe un
estándar universal para estas convenciones y por ejemplo existen
alternativas para los símbolos como cambiar la flecha por = o : o ::=,
las definiciones se encierran en “psicoparéntesis” <…>, como por
ejemplo:

<exp> ::= <exp> <op> <exp> | (<exp>) | NÚMERO

<op> ::= + | - | *
 Especificació n de una gramá tica
libre
de
contexto
• A veces los paréntesis son útiles para reasignar la precedencia de las
expresiones regulares, por ejemplo:

exp  exp( “+”|”-”|”*”)exp | “(“ exp “)” | número

• Pero los paréntesis no son absolutamente necesarios, ya que es

posible separar las partes entre paréntesis en una nueva regla
gramatical:

exp  exp op exp

exp  ( exp )
exp  número
op  +
òp -
op  *
 Derivaciones y el lenguaje
definido
por una gramá tica
• Para determinar un lenguaje, las reglas gramaticales libres de
contexto, deben determinar el conjunto de cadenas
sintácticamente legales del mismo, por ejemplo en la expresión
aritmética:

( 34 - 3 ) * 42
• Corresponde a la cadena sintácticamente legal de 7 tokens:
( número – número) * número

• Y la misma es legalmente una expresión porque cada parte

corresponde a selecciones determinadas de las reglas gramaticales:
exp  exp op exp | (exp) | número
op  + | - | *
 Derivaciones y el lenguaje
definido
por una
gramá tica
• Por otra parte, la cadena:

( 34 – 3 * 42

• No es una expresión legal, porque tiene un paréntesis izquierdo que no

tiene su correspondiente paréntesis derecho y la segunda selección en la
regla gramatical para una expresión exp requiere que los paréntesis se
generen en pares.

• Ahora podemos decir que las reglas gramaticales determinan las cadenas
legales a través de derivaciones de las mismas.

• Una derivación es una secuencia de reemplazos de nombres de estructura

por selecciones en los lados derechos de las reglas gramaticales, comenzando
la misma en un nombre simple y terminando con una cadena de símbolos de
token, al hacer en cada etapa de una derivación un reemplazo simple
utilizando una selección de una regla gramatical.
 Derivaciones y el lenguaje
definido
por una
gramá tica
Por ejemplo, la derivación para la expresión:
(34-3)*42 [1] exp  exp op exp | (exp) | número
[2] op  + | - | *

(1) exp ⇒ exp op exp [1]

(2) ⇒ exp op número [1]
(3) ⇒ exp * número [2]
(4) ⇒ (exp) * número [1]
(5) ⇒ (exp op exp) * número [1]
(6) ⇒ (exp op número) * número [1]
(7) ⇒ (exp - número) * número [2]
(8) ⇒ (número - número) * número [1]

En las derivaciones se usa el símbolo ⇒ en lugar de 

 Derivaciones y el lenguaje
definido
por una
gramá tica
• Es importante entonces conocer que el conjunto de todas las cadenas
de símbolos de token obtenidas por derivaciones del símbolo exp
(ejemplo anterior) es el lenguaje definido por la gramática de
expresiones y contiene todas las expresiones sintácticamente legales,
pudiendo escribir esto de manera simbólica como:

L(G) = { s | exp ⇒* s}

Donde G es la gramática de la expresión, s una cadena arbitraria de

símbolos de token y ⇒* representa una derivación.
Las reglas gramaticales en ocasiones se conocen como producciones
porque “producen” las cadenas L(G) mediante derivaciones.
 Resumiendo la terminología
2 no terminales

exp → exp op exp | ( exp ) | número

op → + | - | 6 terminales

* 6 producciones (3 en cada línea)

¿Qué es lo que realmente diferencia una gramática libre de

contexto de una expresión regular?
digito = 0|1|…|9
numero = digito digito*
Recursividad!
Reglas recursivas Regla “Base”
o No recursiva
16
 Resumiendo
• Las gramáticas libres de contexto, CFG por sus sigla en inglés, están
diseñadas para representar estructuras recursivas.

• Pero las consecuencias de esto son grandes:

• La estructura de una cadena que concuerde (con la gramática) ya no es dada
por una secuencia de símbolos (lexema), sino por un árbol (árbol de análisis
gramatical).

• Los reconocedores del lenguaje ya no son finitos, pero pueden tener un

tamaño de datos arbitrario y deben tener alguna forma de almacenamiento
como una pila.

• El proceso de reconocimiento de cadenas es mucho más complejo:

1. Los algoritmos pueden usar la pila como deseen.
2. El no determinismo es mucho más difícil de eliminar.
3. El número de estados necesarios puede variar.

• Existen muchos algoritmos de análisis sintáctico y no solo uno.

Ejemplos

(1) Considere la gramática G con la regla gramatical simple:

E(E)|a
¿ Cuál será una posible derivación ((a)) ?

(2) Considere la gramática G con la regla gramatical simple:

E(E)
¿Cuáles cadenas puede generar esta gramática?
 Ejemplos
(3) Considere la gramática G con la regla gramatical simple:

E E+a|a

¿Qué cadenas generará esta gramática?

(4) Considere la siguiente gramática muy simplificada de sentencias:

sentencia  sent-if | otro

sent-if  if (exp) sentencia | if (exp) sentencia else sentencia
exp  0 | 1

La gramática esta compuesta por expresiones if anidadas semejantes

al lenguaje C.

Elabore algunos ejemplos de cadenas generadas por esta gramática.

Derivaciones por la Izquierda y
Derecha
• Para lograr la operación de repetición se debe aplicar recursividad, por lo
tanto si quisiéramos repetir un numero indefinido de letras a, existirían
dos formas básicas de hacerlo:

• A  Aa | a
• A  aA | a

• Este lenguaje sería equivalente al generado por la expresión regular a+

• La primera de estas reglas gramaticales es recursiva por la izquierda,

porque el no terminal A aparece el primer símbolo del lado derecho de la
regla que el mismo define.
• La segunda regla gramatical es recursiva por la derecha.
 Producció n épsilon
• Si queremos crear una gramática que genere el mismo lenguaje de
a*, se debe tener una notación para una regla gramatical que
genere la cadena vacía.

• Para esto emplearemos el metasímbolo épsilon (Ɛ)

• Una regla gramatical de este tipo se conoce como producción Ɛ
(“producción épsilon”).

• Por ejemplo, ahora podemos escribir el lenguaje equivalente a la

expresión regular a* ya sea como

A  Aa | Ɛ
o como
A  aA | Ɛ
Ejemplo
(1) Considere la gramática
A  (A) A | Ɛ

¿Qué lenguaje genera esta gramática?

(2) La siguiente gramática:

sentencia  sent-if | otro
sent-if  if (exp) sentencia parte-else
parte-else  else sentencia | Ɛ
exp  0 | 1

¿Es una manera alternativa de escribir la gramática de las

sentencias vista anteriormente?
Ejemplo
El orden importa:
1. secuencia-sent → sentencia ; secuencia-sent |
sentencia
una o más sentencias separadas por una ;

2. secuencia-sent → sentencia ; secuencia-sent | ε

cero o más sentencias terminadas en una ;

3. secuencia-sent → secuencia-sent; sentencia | sentencia

una o más sentencias separadas por una ;

4. secuencia-sent → secuencia-sent; sentencia | ε

cero o más sentencias precedidas por una ;
 Á rboles de aná lisis Gramatical
• Una derivación proporciona un método de construir una cadena particular de terminales a partir
de no terminal inicial.
• Existen muchas derivaciones para la misma cadena, por ejemplo usando la gramática de
operaciones matemáticas para obtener la cadena de tokens:
( número – número ) * número [1] exp  exp op exp | (exp) | número
Tenemos: [2] op  + | - | *
(1) exp ⇒ exp op exp [exp → exp op exp] (5) ⇒ (número -
(2) ⇒ exp op número [exp → número] exp) op exp
(3) ⇒ exp * número [op → * ] [op → - ]
(4) ⇒ ( exp ) * número [exp → ( (6) ⇒ (número - número )
exp )] op exp [exp →
(5) ⇒ ( exp op exp ) * número [exp → exp op número]
exp] (7) ⇒ (número -
(6) ⇒ (exp op número ) * número [exp → número ) * exp
número ] [exp → *]
(7) ⇒ (exp - número ) * número [op → (8) ⇒ (número - número
- ] )* número [exp →
(8) ⇒ (número - número )* número [exp → número ]
número ]
o
(1) exp ⇒ exp op exp [exp → exp op exp]
(2) ⇒ (exp) op exp [exp → ( exp )]
(3) ⇒ (exp op exp) op exp [exp → exp op
exp]
(4) ⇒ (número op exp) op exp [exp →
número]
La única diferencia entre las dos derivaciones es el orden
en el cual se
suministran los reemplazos.
 Á rboles de aná lisis Gramatical
• Para intentar aclarar entonces la ambigüedad proveniente de las
derivaciones, necesitamos una representación para la estructura
de una cadena de terminales que abstraiga las características
esenciales de una derivación mientras se factorizan las diferencias
superficiales del orden.

• Esta representación se hace con una estructura de árbol y se

conoce como árbol de análisis gramatical.
Á rboles de aná lisis Gramatical
• Un árbol de análisis gramatical correspondiente a una derivación es un
árbol etiquetado en el cual los nodos interiores están etiquetados por no
terminales, los nodos hoja están etiquetados por terminales y los hijos de
cada nodo interno representan el reemplazo del no terminal asociado en
un paso de la derivación.
(1) exp ⇒ exp op exp
Por ejemplo la derivación: (2) ⇒ número op exp
(3) ⇒ número + exp
(4) ⇒ número + número

Corresponde al árbol de análisis gramatical:

 Á rboles de aná lisis
Gramatical
• En el ejemplo el primer paso en la derivación corresponde a los tres hijos del nodo
raíz.
• El segundo paso al hijo número de exp en el extremo izquierdo debajo de la raíz
y de manera similar para los nodos restantes.
• Podemos enumerar entonces los nodos internos del árbol gramatical mediante el
número de paso en el cual se reemplaza su no terminal asociado en una derivación
correspondiente, quedando así:

Debe advertir que esta numeración

de los nodos internos del árbol gramatical
es en realidad una numeración preorden .

Recorridos de arboles:

preorden : visitar el elemento de la raíz , recorrer en preorden el

subárbol izquierdo y luego recorrer en preorden el subárbol derecho.
Ejemplo: 60 , 30 , 10 , 50 , 55 , 80
postorden : recorrer en postorden el subárbol izquierdo, luego
recorrer en postorden el subárbol derecho y finalmente visitar el
elemento de la raíz. Ejemplo: 10 , 55 , 50 , 30 , 80 , 60
 Á rboles de aná lisis Gramatical
• El mismo árbol de análisis gramatical también corresponde a otras
derivaciones, si tomamos el ejemplo anterior, correspondería también
a:
ORIGINAL OTRA #1 OTRA #2
(1) exp ⇒ exp op exp (1) exp ⇒ exp op exp (1) exp ⇒ exp op exp
(2) ⇒ número op exp (2) ⇒ exp op número (2) ⇒ exp + exp
(3) ⇒ número + exp (3) ⇒ exp + número (3) ⇒ número + exp
(4) ⇒ número + número (4) ⇒ número + número (4) ⇒ número + número

• Pero se aplicaran diferentes numeraciones a los nodos internos, por

ejemplo la primera de las otras derivaciones corresponde a:

• Lo que corresponde a la inversa de una numeración postorden de los nodos

del árbol gramatical.
 Á rboles de aná lisis Gramatical
• En general un árbol gramatical corresponde a muchas derivaciones, que en
conjunto representan la misma estructura básica para la cadena de terminales
analizada gramaticalmente. Pero se pueden distinguir derivaciones
particulares que están asociadas de manera única con el árbol de análisis
gramatical.

• Una derivación por la izquierda es aquella en la cual se reemplaza el no

terminal más a la izquierda en cada paso de la derivación. Y corresponde a la
numeración preorden de los nodos internos del árbol de análisis gramatical
(top-down, usando LL = Left-to-right traversal of input,
constructing a Leftmost derivation).
• Por consiguiente una derivación por la derecha es aquella en la cual el no
terminal más a la derecha se reemplaza en cada paso de la derivación. Y
corresponde a la numeración postorden inversa de los nodos internos del
árbol de análisis gramatical (bottom-up, usando Left-to-right
traversal of input, constructing a Rightmost
derivation ).
 Á rboles de aná lisis Gramatical
• Como un ejemplo más complejo veamos el árbol de la derivación de
(34-3)*42
(1) exp ⇒ exp op exp [exp → exp op exp]
(2) ⇒ exp op número [exp → número]
(3) ⇒ exp * número [op → * ]
(4) ⇒ ( exp ) * número [exp → ( exp )]
(5) ⇒ ( exp op exp ) * número [exp → exp op exp]
(6) ⇒ (exp op número ) * número [exp → número ]
(7) ⇒ (exp - número ) * número [op → - ]
(8) ⇒ (número - número )* número [exp → número ]

Siendo esta una derivación por la derecha, y la

numeración correspondiente al árbol de análisis gramatical
es una numeración postorden inversa.

Pero ¿Cómo quedara entonces la numeración preorden

de la derivación por la izquierda?

(1) exp ⇒ exp op exp [exp → exp op exp]

(2) ⇒ (exp) op exp [exp → ( exp )]
(3) ⇒ (exp op exp) op exp [exp → exp op exp]
(4) ⇒ (número op exp) op exp [exp → número]
(5) ⇒ (número - exp) op exp [op → - ]
(6) ⇒ (número - número ) op exp [exp → número]
(7) ⇒ (número - número ) * exp [exp → *]
(8) ⇒ (número - número )* número [exp → número ]
 Derivaciones por la Izquierda
y
Derecha
• Derivación recursiva por la izquierda: A → A x |
y
• yxx: A

A x

A x

• Derivación recursiva por la derecha: A → x A | y

• xxy: A

x A
x A

y
 Á rboles sintá cticos abstractos
• Un árbol de análisis gramatical es una representación útil de la
estructura de una cadena de testigos o tokens, ya que estos aparecen
como las hojas del árbol y los nodos internos representan una
derivación en algún orden.

• Sin embargo, un árbol de análisis gramatical contiene mucha

información, mucho más de lo que es absolutamente necesario para
que un compilador produzca código ejecutable.
 Á rboles sintá cticos
abstractos
• Para ver mediante un ejemplo lo anterior, veamos el árbol de análisis gramatical la
expresión
simple 3+4:

• El principio de la traducción dirigida por sintaxis establece que el significado, o semántica de la

cadena 3+4 debería relacionarse directamente con su estructura sintáctica como se representa
mediante el árbol de análisis gramatical.

• Esto significa que el árbol debería dar a suponer que el valor de 3 y 4 se van a sumar. En
realidad se observa que esto se da a entender de la siguiente manera: la raíz representa la
operación de suma de los valores de los dos subárboles exp hijos. Sin embargo existe una
manera más simple de representar esta misma información, a saber, mediante el árbol:
 Acá, el nodo raíz simplemente se etiqueta por
la operación que representa, y los nodos hojas
se etiquetan mediante sus valores.
 Á rboles sintá cticos
abstractos
• De hecho podemos representar de manera similar la expresión
(34-3)*42

• En este árbol los testigos o tokens de paréntesis han desaparecido,

aunque todavía representan precisamente el contenido semántico
de restar 3 de 34, para después multiplicarlo por 42.
 Á rboles sintá cticos abstractos
Los árboles sintácticos abstractos poseen ciertas características que
se deben conocer:

• Representan abstracciones de secuencias de testigos o tokens del

código fuente real, y las secuencias de testigos no se pueden recuperar
a partir de ellas, a diferencia de los árboles de análisis gramatical.

• Contienen toda la información necesaria para traducir de una

forma más eficiente que los árboles de análisis gramatical. Por lo
que corresponde a la verdadera estructura interna producida por
un analizador sintáctico (parser, en ingles).
 Á rboles sintá cticos
abstractos
Los árboles sintácticos abstractos poseen ciertas características que
se deben conocer:

• Un analizador recorrerá normalmente todos los pasos representados

por un árbol de análisis gramatical, pero por lo regular solo construirá el
árbol sintáctico abstracto o su equivalente.

• Los árboles sintácticos abstractos pueden imaginarse como una

representación de árbol de una notación abreviada denominada
sintaxis abstracta.
 Á rboles sintá cticos abstractos
Pero, ¿Cómo será la verdadera estructura de análisis
sintáctico usada por el compilador escrita por
ejemplo en lenguaje C o Java?
Aunque no existe una respuesta definitiva a
esto, se podría decir que con una declaración de datos
por ejemplo en lenguaje C se podría expresar el árbol
sintáctico abstracto.

Si retomamos nuestro ejemplo de expresiones

aritméticas simples, podrían ser determinados de
diversas maneras mediante estructuras de datos del
lenguaje C, las cuales se mostraran a continuación:
 Á rboles sintá cticos abstractos
• Primera forma mediante enumeraciones:

typedef enum {Plus,Minus,Times} OpKind;

typedef enum {OpK,ConstK} ExpKind;
typedef struct streenode
{ ExpKind kind;
OpKind op;
struct streenode *lchild,*rchild;
int val;
} STreeNode;
typedef STreeNode *SyntaxTree;
Á rboles sintá cticos
abstractos
• Segunda forma mediante uniones:
typedef enum {Plus,Minus,Times} OpKind;
typedef enum {OpK,ConstK} ExpKind;
typedef struct streenode
{ ExpKind kind;
struct streenode *lchild,*rchild;
union {
OpKind op;
int val; } attribute;
} STreeNode;
typedef STreeNode *SyntaxTree;
Á rboles sintá cticos
abstractos
En cuanto a Java, aunque al igual que con lenguaje C no
existe una respuesta definitiva a esto, se podría decir que se
puede aprovechar las características orientadas a objetos
de este lenguaje para crear una jerarquía de clases que
permitan elaborar un árbol sintáctico abstracto que sea
flexible a la hora de su procesamiento por parte de
funciones posteriores del compilador.

Si retomamos nuestro ejemplo de expresiones

aritméticas simples, una de las muchas jerarquías de clases
posible podría ser:
Á rboles sintá cticos
abstractos
Á rboles sintá cticos
abstractos
• Y su implementación
luciría como:
 Á rboles sintá cticos abstractos
Ejemplos:
(1) Considere la gramática para las sentencias if simplificadas:
sentencia  sent-if | otro
sent-if  if (exp) sentencia | if (exp) sentencia else
sentencia exp  0 | 1
¿Cuál será el árbol de análisis gramatical para la cadena if (0) otro else otro?
 Á rboles sintá cticos
abstractos
(2) Considere la gramática para las sentencias if simplificadas usando la
cadena vacía:
sentencia  sent-if | otro
sent-if  if (exp) sentencia parte-
else parte-else  else sentencia | Ɛ
exp  0 | 1

¿Cuál será el árbol de

análisis gramatical para
la cadena:
if (0) otro else otro?
 Á rboles sintá cticos
abstractos
(3) ¿Como se podría llevar a cabo un árbol sintáctico abstracto para la cadena if (0)
otro else otro ?
Se debería desechar todo, excepto las tres estructuras subordinadas de la
sentencia if: la expresión de prueba, la parte de acción (parte “then”) y la parte
alternativa (parte “else”).
Usando los tokens if y otro como etiquetas para distinguir la clase del nodo de
De este modo el árbol sentencia en el árbol sintáctico, y un ejemplo de su declaración en c seria:
sintáctico abstracto sería:
typedef enum {ExpK, StmtK} NodeKind;
typedef enum {Zero, One} ExpKind;
typedef enum {IfK, OtherK} StmtKind;
typedef struct streenode
{ NodeKind kind;
ExpKind ekind;
StmtKind skind;
struct streenode *test,*thenpart,*elsepart;
int val;
} STreeNode;
typedef STreeNode *SyntaxTree;
Ejercicio
• Considere la gramática de una secuencia de sentencias separadas
por signos de punto y coma:

secuencia-sent  sent ; secuencia-sent | sent

sent  s

Dada la cadena s ; s ; s se debe:

1. Hallar el árbol de análisis gramatical para esta cadena con la

gramática mostrada.
2. Hallar un posible árbol sintáctico para la cadena.
 Hijos de extrema izquierda y
hermanos a la derecha
• Imaginemos que en el ejercicio anterior, una solución posible fuese
unir todos los nodos en una secuencia con solamente un nodo,
obteniendo:

• El problema con esto es que podemos tener un número arbitrario

de hijos y es difícil tomar precauciones al respecto en una
declaración de tipos de datos.
 Hijos de extrema izquierda
y hermanos a la derecha
La solución es utilizar la representación de estructura de
datos de hijo de extrema izquierda y hermanos a la derecha para un
árbol.

En esta se representa un único vinculo entre el padre y el hijo

de extrema izquierda, y luego los hijos se vinculan entre si de
izquierda a derecha en una lista enlazada, denominándose estos
vínculos entre hermanos.
Clave agrupación
 Notaciones extendidas
• Las construcciones repetitivas y opcionales son muy comunes en el
mundo de los lenguajes de programación. Por lo tanto, la notación
BNF se extiende en ocasiones con el fin de incluir estas situaciones.

• Esta nueva notación extendida recibe el nombre de BNF extendida

o EBNF (por las siglas del término en inglés).
EBNF
• Hasta ahora en la notación Backus-Naur Form (BNF)
• Los metasímbolos son | → ε

• En la notación extendida BNF (EBNF)

• Los metasímbolos son […] y {…} (opcional y repetición)

• Debido a la existencia de estos nuevos metasímbolos, se

puede eliminar el uso de ε
EBNF
• La notación de repetición de EBNF, se expresa mediante el uso
de llaves {…}

• Es como el símbolo * en las expresiones regulares. Por ejemplo:

- Reemplazar repeticiones solamente recursivas por la izquierda:

exp → exp + term | term
se convierte en:
exp → term { + term }
EBNF
• El problema con cualquier notación de repetición es que ocultan cómo se
construye el árbol de análisis gramatical. Por ejemplo:

secuencia-sent→ sent ; secuencia-sent | sent

sent→ s

• Se convertiría con notación EBNF en:

secuencia-sent→ {sent ; } sent (recursiva por derecha)
secuencia-sent→ sent {; sent } (recursiva por izquierda)

• Otros problemas pueden surgir con la asociatividad.

• Se debe tener cuidado al construir reglas, como:

exp → exp + term | exp - term | term
no es lo mismo que:
exp → term { + term } | term { - term }
 EBNF
• Las construcciones opcionales en EBNF se representan entre […].

• Su significado en opcional como el símbolo ? de las expresiones regulares.

Por ejemplo:
exp → term ‘|’ exp | term
se convierte en:
exp → term [ ‘|’ exp ]
o
if-sent→ if ( exp ) sent | if ( exp ) sent else sent
se convierte en:
if-sent → if ( exp ) sent [ else sent ]
Ejemplo simple en EBNF
exp → term { sumop term }
sumop → + | -
term → factor { mulop factor }
mulop → *
factor → ( exp ) | numero
Diagramas de sintaxis
• Es la representación grafica para simbolizar de manera visual
las reglas EBNF. Por ejemplo la regla gramatical
factor → ( exp ) | número
Se escribe como un diagrama de sintaxis de la siguiente manera:
Diagramas de sintaxis
• Las construcciones de repetición tales como:
A→ {B}
Se representa como:

• Las construcciones opcionales tales como:

A→ [B]
Se representa como:
 Diagramas de
sintaxis
• Algunas de las reglas EBNF mostradas anteriormente se pueden
representar como:
• exp → term { sumop term }
• factor → ( exp ) | número
Ejemplo Diagrama de
sintaxis:
• Considere la gramática:
sentencia  sent-if | otro
sent-if  if (exp) sentencia
| if (exp) sentencia else sentencia
exp  0 | 1

Y su representación EBNF:
sentencia  sent-if | otro
sent-if  if (exp) sentencia [ else sentencia ]
exp  0 | 1
¿Cuál será su diagrama de sintaxis?
Ejemplo Diagrama de
sintaxis:
• Solución: