PDF de programación - Análisis sintáctico - Gramáticas libres de contexto

Procesadores de Lenguajes

Ingeniería Técnica superior de Ingeniería Informática

Departamento de Lenguajes y Sistemas informáticos

Análisis sintáctico
Gramáticas libres de contexto

Javier Vélez Reyes
[email protected]
Departamento de Lenguajes Y Sistemas Informáticos
UNED

Análisis sintáctico. Gramáticas libres de contexto
Objetivos

Objetivos

› Conocer los lenguajes libres de contexto
› Conocer las responsabilidades del analizador sintáctico
› Aprender a utilizar gramáticas libres de contexto

› Aprender a diseñar gramáticas libres de contexto
› Aprender a reconocer y resolver fuentes de ambigüedad
› Aprender a eliminar la recursividad por la izquierda
› Aprender a factorizar por la izquierda

› Conocer el uso y tipos de derivaciones y árboles sintácticos
› Conocer la representación de lenguajes mediante diagramas de sintaxis
› Presentar los diferentes tipos de autómatas utilizados para construir analizadores sintácticos
› Discutir los diferentes tipos de analizadores sintácticos

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Índice

Índice
›
› Gramáticas libres de contexto

Introducción

› Notación BNF y EBNF
› Derivación gramatical
› Árboles sintácticos
›
Limpieza gramatical

› Ambigüedad gramatical
› Recursividad por la izquierda
› Factorización por la izquierda

› Diagramas de sintaxis
› Autómatas a pila deterministas
› Bibliografía

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Introducción

Análisis sintáctico

La fase de análisis sintáctico tiene por objetivo solicitar tokens al analizador léxico y
construir una representación arborescente de todo el código fuente. Este proceso se
encuentra dirigido por el conocimiento gramatical que del lenguaje tiene el analizador
sintáctico

Foco de atención

analizador

nuevos

va
El
pidiendo
al
analizador léxico para construir
un árbol del programa fuente

sintáctico
tokens

SWhile

WHILE E DO S

E >

E

...
<DO, PR>
<), PD>
<b, ID>
<>, GT>
<a, ID>
<(, PI>
<WHILE, PR>

Analizador sintáctico



Tema 3

¿Cómo se especifica formalmente
un analizador sintáctico?
›
›
› Conversión entre formalismos

Formalismos
Tratamiento de formalismos

Temas 4 y 5



¿Cómo se implementa un
analizador sintáctico?

›
›
›

Estrategias análisis sintáctico
Tipos de gramáticas
Tipos de analizadores

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Introducción

Lenguajes libres de contexto

Desde una perspectiva sintáctica un lenguaje es una colección de construcciones sintácticas
bien formadas desde un alfabeto de entrada y correctamente combinadas entre sí de
acuerdo a una colección de reglas sintácticas

Ejemplo

Pascal

El lenguaje Pascal tiene unas normas de
carácter gramatical que definen su
naturaleza y expresividad. Visto de
manera extensiva, el
lenguaje Pascal
sería el conjunto infinito de todos los
posibles
correctos
escritos en sintaxis Pascal

códigos

fuente

uses
crt;
var
contador:integer;
begin
ClrScr;
for contador:=2 to 999 do
begin

Uses crt;
var
cantidad,cont,numero,s:integer;
begin
clrScr;
s:=0;
write('Cantidad:');
read(canditad);
for cont:=1 to cantidad do
begin
write('Numero ',cont,': ');
Read(numero);
s:=s+numero;
end;
write('Promedio:',s/cantidad:0:2);
readKey;
end;.

contador:=contador+1;
Write(contador,', ');
if contador>999 then
begin contador:=999;
end;

end;
ReadKey;
end.

…

Uses crt;
var
suma,numero,contador:integer;
begin
clrScr;
write('Numero: ');
readln(numero);
suma:=0;
for contador:=1 to numero do
begin
suma:=suma + contador;
end;
write('Suma: ',suma);
readKey;
end.

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Introducción

Especificación de lenguajes libres de contexto

Existen 3 diferentes maneras de definir formalmente un lenguaje de contexto libre. A lo
largo de esta sección estudiaremos cada una de ellas en detalle y veremos cómo se
puede pasar de cada una a las otras 2

›

Elementos

› Gramáticas libres de contexto
› Diagramas de sintaxis
›

Autómatas a pila

Gramáticas libres

de contexto

Lenguajes
libres de
contexto

Diagramas de

sintaxis

Autómatas

a pila

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Gramáticas libres de contexto

Especificación mediante gramáticas libres de contexto

De manera similar a como ocurre en los lenguajes regulares, los lenguajes libres de
contexto se pueden expresar mediante el uso de gramáticas libres de contexto. Su
definición es una extensión de las gramáticas regulares con reglas de producción
potencialmente más complejas

Definición de gramática libre de contexto
Una gramática libre de contexto es un conjunto de 4
elementos G = (T, N, S, P) donde:

T es un conjunto de símbolos terminales

›
› N es un conjunto de símbolos no terminales
›
›

S Є N axioma gramatical
P un conjunto de reglas de producción de la forma

1. A ::= X donde X es una secuencia de elementos en N U T
2. A ::= x donde x es una secuencia de elementos en T
3. A :: =

la cadena vacía

siendo

A veces T se elide, N se deduce de los antecedentes de las
reglas de P y se asume que el antecedente de la primera regla
es S con lo G sólo a través de P

Ejemplo

L = Lenguaje de operadores
Sea G = (T, N A, P) con

T = {+, -, *, /, n}
N = {E}
P = {

E ::= E + E
E ::= E - E
E ::= E * E
E ::= E / E
E ::= n

}

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Gramáticas libres de contexto

Especificación mediante gramáticas libres de contexto

De manera similar a como ocurre en los lenguajes regulares, los lenguajes libres de
contexto se pueden expresar mediante el uso de gramáticas libres de contexto. Su
definición es una extensión de las gramáticas regulares con reglas de producción
potencialmente más complejas

Notación

¿Cómo se escriben

las reglas?

Notación estándar

Las reglas se escriben como A → X.
Cada regla se escribe en una linea
distinta

E → E + E
E → E – E
E → id

Notación BNF

Las reglas se escriben como A ::= X.
Las reglas de un mismo antecedente
se escriben como A ::= X | Y | Z…
Cada regla con antecendente distinto
se escribe en una nueva línea

Notación EBNF

Se usa la notación BNF. Las reglas
recursivas se pueden esquematizar
con los meta-caracteres { y }

D ::= T L
T ::= int | bool | char
L ::= id , L | id

D ::= T L
T ::= int | bool | char
L ::= { id , } id



e
d
o
c
o
F

n
ó
i
c
n
e
t
a

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Gramáticas libres de contexto

Especificación mediante gramáticas libres de contexto

De manera similar a como ocurre en los lenguajes regulares, los lenguajes libres de
contexto se pueden expresar mediante el uso de gramáticas libres de contexto. Su
definición es una extensión de las gramáticas regulares con reglas de producción
potencialmente más complejas

Derivación gramatical
Se plantea el siguiente problema de decisión: Dado un lenguaje descrito a
través de una gramática G, L(G) determinar si la colección de terminales x
pertenece o no al lenguaje al mismo. Esto es ¿x Є L (G)?

2 + 3 * 5

Cadena de
derivación

L = Lenguaje de operadores
Sea G = (T, N A, P) con

T = {+, -, *, /, n}
N = {E}
P = {

axioma

asidero

(2) (3) (5)
E → E + E → n + E → n + E * E → n + n * E → n + n * n

Paso de
derivación

Forma
de frase

Frase

}

E ::= E + E
E ::= E - E
E ::= E * E
E ::= E / E
E ::= n

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Gramáticas libres de contexto

Especificación mediante gramáticas libres de contexto

De manera similar a como ocurre en los lenguajes regulares, los lenguajes libres de
contexto se pueden expresar mediante el uso de gramáticas libres de contexto. Su
definición es una extensión de las gramáticas regulares con reglas de producción
potencialmente más complejas

Derivación gramatical
Se plantea el siguiente problema de decisión: Dado un lenguaje descrito a
través de una gramática G, L(G) determinar si la colección de terminales x
pertenece o no al lenguaje al mismo. Esto es ¿x Є L (G)?

Frase Secuencia

de
que
lenguaje definido por la
pertenece al
gramática. Si x Є L (G), x es frase de L

terminales

Forma de
frase

de
que

terminales

no
Secuencia
terminales
una
colección de frases del lenguaje. Existe
una cadena de derivación que llega
hasta ella

representa

y

Axioma Forma de frase más abstracta que
representa a L (cualquier derivación de
Si x Є L (G) comienza por el axioma)

Paso de
derivación

Aplicación de una regla de producción
que transforma una forma de frase más
general en otra más especifica para x

Cadena de
derivación

Secuencia de pasos de derivación que
parten del axioma gramatical para
intentar alcanzar la frase analizada x.
Demostración de x Є L (G)

Asidero Parte izquierda de cualquier forma de
frase de x Є L (G) formada únicamente
por símbolos terminales

Javier Vélez Reyes [email protected]

Análisis sintáctico. Gramáticas libres de contexto
Gramáticas libres de contexto

Especificación mediante gramáticas libres de contexto

De manera similar a como ocurre en los lenguajes regulares, los lenguajes libres de
contexto se pueden expresar mediante el uso de gramáticas libres de contexto. Su
definición es una extensión de las gramáticas regulares con reglas de producción
potencialmente más complejas

Derivación gramatical
Se plantea el siguiente problema de decisión: Dado un lenguaje descrito a
través de una gramática G, L(G) determinar si la colección de terminales x
pertenece o no al lenguaje al mismo. Esto es ¿x Є L (G)?

¿ En qué orden se
aplican las reglas?

Left Most Derivation

En cada paso de derivación se
escoge el no terminal más a la
izquierda de la forma de frase a
derivar

Right Most Derivation

En cada paso de derivación se
escoge el no terminal más a la
derecha de la forma de frase a
derivar

E → E + E →