sdsdd

33

Ing. Fco. Ríos Acosta

Gramáticas

friosam@prodigy.net.mx

II
GRAMÁTICAS.

2.1 INTRODUCCIÓN A LAS GRAMÁTICAS

.......................

34

2.2 ESTRUCTURAS DE LAS GRAMÁTICAS

.......................

37

2.3 CLASIFICACIÓN DE LAS GRAMÁTICAS

.......................

41

2.4 REPRESENTACIÓN DE GRAMÁTICAS

.......................

44

2.5 EJERCICIOS PROPUESTOS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

33

34

Ing. Fco. Ríos Acosta

Gramáticas

friosam@prodigy.net.mx

Palabras clave : gramáticas, clasificación de gramáticas. Gramáticas de contexto libre.Lenguajes y
autómatas. Derivaciones, lenguaje generado.

2.1 INTRODUCCIÓN A LAS GRAMÁTICAS.
En la sección 1.3 se mostró como las primeras fases de análisisen un proceso de
compilación interactúan para efectuar ciertas tareas sobre el programa fuente. El
analizador léxico que tiene de entrada al programa fuente, identifica a los tokens y los
envía al analizador sintáctico, fig 2.1.

Programa
Fuente

ANALIZADOR

ANALIZADOR

LÉXICO

SINTÁCTICO

Árbol de
reconocimiento
(árbol de parse)

tokens

Fig 2.1 Análisis léxico y análisissintáctico de un programa.
¿ Cuántos tokens envía el analizador léxico al analizador sintáctico ?; los que requiera el
propio analizador sintáctico para el reconocimiento de la sintáxis de una instrucción. La
tarea fundamental del análisis sintáctico es recibir los tokens que juntos (concatenados)
constituyen en escencia, a una instrucción. De acuerdo a ciertas reglas de sintáxis para
cadainstrucción , decide si éstas -las instrucciones-, están bien construidas; es decir,
respetan y cumplen dichas reglas de sintáxis.
Las gramáticas consisten de un conjunto de reglas, que nos permiten especificar
formalmente la sintáxis de las instrucciones de un lenguaje de programación.

Expresiones regulares
Gramáticas

LyA

34

= especificación de tokens.

= especificación de sintáxisde instrucciones.

35

Ing. Fco. Ríos Acosta

friosam@prodigy.net.mx

Gramáticas

Los programas analizadores sintácticos que se basan en gramáticas para reconocer las
instrucciones residentes en el programa fuente se denominan Parser’s (reconocedores).
Las dos clases de parser más comunes son :
• Parser Descendente ( Top Down )
• Parser Ascendente ( Bottom Up )
INSTRUCCIONESEspecificación
Reconocimiento
Gramáticas

1. Parser Descendente
( Top Down )
2. Parser Ascendente
( Bottom Up )

Fig. 2.2 Especificación y reconocimiento de instrucciones.
Veamos con más detalle el fin de una gramática. Hemos dicho que una gramática se
utiliza para especificar de manera formal, la sintáxis de una instrucción ( o de varias ) .
El uso de una gramática le permite a unreconocedor ( Parser ), saber si una instrucción
está bien construida. Si no está adecuadamente construida, el reconocedor lo hará saber
mediante el envío de un mensaje “error de sintáxis” .
Supongamos la instrucción scanf que en lenguaje C es usada para leer datos desde el
teclado. En la figura 2.3 se muestran algunas posibles formas en las que puede ser
encontrada en un programa fuente, lainstrucción scanf.
1)
2)
3)
4)
5)

scanf (“%d”,&iNum);
scanf (“%f”,pfNum);
scanf (“%s %d”,sNom,&iTen);
scanf (“%c”,&asCar[i]);
scanf (“%d %f %d”,piEnt1,pfReal,piEnt2);
.....

Fig 2.3 Algunas instancias de la instrucción scanf.

35

36

Ing. Fco. Ríos Acosta

friosam@prodigy.net.mx

Gramáticas

Podemos llegar a ciertas conclusiones hechándole un vistazo a la fig. 2.3. Entre lascuestiones que mas nos interesan, están :
1. Las n instancias son un conjunto de tokens concatenados. La instancia 1 tiene 8
tokens debidamente concatenados :

scanf

Palabra reservada

(

Separador

”%d”

CteLit

,

Separador

&

Operador de Dirección

iNum

Identificador

)

Separador

;

Terminador de Instrucción

2. Las n instancias de la instrucción...