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
edu.red"/ 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 |