35
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 )
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 un reconocedor ( 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, la instrucció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
37
Gramáticas
2.2 ESTRUCTURA DE LAS GRAMÁTICAS.
Una gramática consiste de 4 componentes, y es denotada por G = (VT,VN, S, F)
donde :
VT Es el conjunto de símbolos terminales a partir de los cuales las cadenas son
formadas. Si la gramática es usada para denotar un lenguaje de programación , entonces
los tokens son los símbolos terminales.
VN Es el conjunto de símbolos no terminales , también llamados variables sintácticas.
Las variables sintácticas denotan un conjunto de cadenas. Los símbolos no terminales
definen conjuntos de cadenas que ayudan a definir el lenguaje generado por la
gramática.
S Es un símbolo no terminal de la gramática que es distinguido como símbolo de
inicio. El conjunto de cadenas que este símbolo de inicio denota, es el lenguaje definido
por la gramática G.
F Es el conjunto de producciones o reglas gramaticales. Las producciones de una
gramática especifican la manera en que los tokens ( terminales ) y las variables
sintácticas ( no terminales ) pueden ser combinados para formar cadenas.
Ejemplo 2.1 Dada la siguiente gramática :
R
R
R
R
P
P
read
readln
read (P)
readln (P)
P, id
id
Encuentra sus componentes VT, VN,, S y F.
Usemos la siguiente convención de notación :
• Las letras mayúsculas servirán para denotar variables sintácticas (Símbolos no
terminales).
• El lado izquierdo de la primera producción es el símbolo de inicio.
• Si A a1 , A a2, . . . A aK son producciones teniendo a la no
terminal A en el lado izquierdo, podemos escribir A a1 ?a2 ?. . . ?aK ? donde
a1, a2, . . . ,aK se les llama las alternativas para A.
37
39
Gramáticas
39
9)
10)
11)
F
F
F
num
(E)
-E
La gramática G = (VT,VN, S, F) tiene los siguientes componentes :
VT = { id, :=, ; , +, – , * , / , num, ( , ) }
VN = { A,E,T,F }
S = A
Usando la convención de notación (3), la gramática puede representarse como :
A
E
T
F
id := E;
E+T ? E-T ? T
T*F ? T/F ? F
id ? num ? (E) ? -E
Ejemplo 2.3 Veamos una gramática que nos genera el lenguaje de todos los
números enteros pares :
N
N
K
K
L
L
L
L
P
P
P
P
P
Z
Z
…
…
Z
D
KP
L
KD
Z
2
4
6
8
0
2
4
6
8
1
2
9
0
Monografias.com"/
br
40
Gramáticas
D
D
…
…
D
1
2
9
VT = { 0, 1, 2…, 9 }
Los dígitos del 0-9.
VN = { N, K, L, Z, D, P }
S=N
La gramática con la agrupación de las alternativas para cada variable sintáctica es :
N
K
P
KP ? L
KD? Z
0 ? 2? 4 ? 6 ? 8
L
D
Z
2 ? 4 ? 6 ? 8
0 ? 1? … ?9
1 ?2 ? .
Página siguiente  |