Irene Peligros Florindo, Elena Recio Álvarez Grupo605
[email protected] [email protected]
Práctica PRIMERA - Parser Descendente Recursivo
En esta práctica se desarrolla el diseño de un traductor que convierte expresiones en un
lenguaje simple en notación prefija a su equivalente notación infija mediante un parser
descendente recursivo.
1. Análisis de rd_lex( )
El Analizador Léxico rd_lex() lee la entrada carácter a carácter, ignorando los espacios en
blanco y los saltos de línea. En caso de leer un salto de línea se incrementa el contador
line_counter para proporcionar información más precisa si aparece un error.
Identifica los siguientes elementos léxicos:
- Reconocimiento de números (T_NUMBER): Identifica secuencias de números que
almacena en tokens.number y son devueltos en el token T_NUMBER.
- Reconocimiento de variables (T_VARIABLE): Identifica variables, formadas por
una letra seguida opcionalmente de un dígito. Se asigna el nombre de la variable a
tokens.variable_name y se devuelve el token T_VARIABLE.
- Reconocimiento de operadores aritméticos (T_OPERATOR): Identifica
operadores aritméticos (+, -, *, /). Se asigna a tokens.token_val el valor del operador
correspondiente y se devuelve el token T_OPERATOR.
- Reconocimiento de otros símbolos: si encuentra un carácter que no es ninguno
de los tipos mencionados, lo devuelve como un “literal”, que se almacena en la
variable token.token. Esto incluye caracteres como paréntesis, el signo de
asignación (‘=’), o cualquier otro símbolo no reconocido por los casos anteriores.
2. Análisis de la gramática
2.1. Gramática inicial
La gramática inicial se corresponde con la representación de la sintaxis de las expresiones
aritméticas en notación prefija siguiendo las especificaciones iniciales.
Axioma ::= Expresión “\n”
Expresion ::= “(“ Operador Parametro Parametro “)” | Numero
Parametro ::= Expresion
Operador :: “+” | “-” | “*” | “/”
Numero ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”
Aspectos que se han tenido que ir modificando a lo largo del desarrollo de la gramática
inicial:
- En la definición de Parámetro, se indica que éste podrá ser bien una Expresion o
un Numero. Inicialmente se propuso:
Parametro ::= Expresion | Numero
Sin embargo, la gramática no sería LL(1), ya que se produciría ambigüedad en
Numero al poder derivarse de dos formas distintas en la misma posición, a través de
Parametro o a través de Expresión.
1
Irene Peligros Florindo, Elena Recio Álvarez Grupo605
[email protected] [email protected]
- En el enunciado se especifica que Numero será un entero de uno o más dígitos que
se tratará como un Token. Inicialmente distinguimos las siguientes reglas para poder
representar lo que se pide:
Numero ::= Digito Numero | λ
Digito ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”
Sin embargo, a la hora de introducir nuestra gramática en la herramienta JFLAP, se
producía un error que tenía que ver con el símbolo λ. Se tuvo que modificar
únicamente con la regla:
Numero ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”
En el código del parser se tiene en cuenta lo exigido en el enunciado y se pueden
representar números de más de un dígito.
Tras introducir la gramática inicial en JFLAP, seleccionamos la opción <Build LL(1) Parse
Table> para de esta forma obtener entre otros los conjuntos PRIMERO(FIRST) y
SIGUIENTE(FOLLOW).
2.2. Gramática final completa
Una vez diseñada la gramática inicial y validada como LL(1), se procedió a completarla con
las especificaciones extendidas definidas en el enunciado, obteniendo la gramática final:
Axioma ::= Expresion “\n”
Expresion ::= “(“ R “)” | Numero | Variable
R ::= Operador Parametro Parametro | = Variable Parametro
Operador :: “+” | “-” | “*” | “/”
Parametro ::= Expresion
Variable ::= Letra Numero
Letra ::= a | b | … | z | A | B | … | Z
Numero ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”
2
Irene Peligros Florindo, Elena Recio Álvarez Grupo605
[email protected] [email protected]
Aspectos que se han tenido que ir modificando a lo largo del desarrollo de la gramática final:
- En el enunciado se añade la siguiente regla a partir de la definición de Variable:
Expresion ::= (Operador Parametro Parametro) | (= Variable Parametro )
Al añadir la última regla, la gramática ya no es LL(1), al haber dos producciones que
comienzan con “(“. El parser no podrá decidir qué producción tomar sin mirar más de
un token, lo cual rompe la propiedad LL(1). La solución es introducir la regla R:
R ::= Operador Parametro Parametro | = Variable Parametro
- Un último error surgió durante la elaboración de la gramática. Se indica que
Variable consistirá en una letra (mayúscula o minúscula) seguida opcionalmente de
un dígito. A la hora de introducir la siguiente producción en JFLAP:
Letra ::= a | b | … | z | A | B | … | Z
Ocurre un error, ya que considera las letras mayúsculas como No Terminales, los
cuáles no tendrían sus reglas de producción definidas a continuación. Es por ello por
lo que a la hora de analizar la gramática en JFLAP se ha omitido la posibilidad de
que Letra pueda ser mayúscula. Sin embargo, en el código del parser sí que se
implementa dicha posibilidad.
Tras introducir la gramática final en JFLAP, seleccionamos la opción <Build LL(1) Parse
Table> para de esta forma obtener entre otros los conjuntos PRIMERO(FIRST) y
SIGUIENTE(FOLLOW).
2.3. Niveles léxico y sintáctico
Nivel léxico
El nivel léxico está representado por las reglas que definen los caracteres individuales y
cómo se agrupan los tokens. Estos elementos forman la base del análisis léxico, que agrupa
caracteres en tokens como operadores, variables y números.
Operador :: “+” | “-” | “*” | “/”
Letra ::= a | b | … | z | A | B | … | Z
Numero ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”
Nivel sintáctico
El nivel sintáctico describe cómo los tokens se combinan para formar expresiones válidas.
En esta gramática, el resto de expresiones conforman el dicho nivel.
3
Irene Peligros Florindo, Elena Recio Álvarez Grupo605
[email protected] [email protected]
A continuación se muestra el Diagrama Sintáctico que representa la gramática diseñada:
4
Irene Peligros Florindo, Elena Recio Álvarez Grupo605
[email protected] [email protected]
3. Resumen del diseño del parser
A partir de la gramática final, se pasa al desarrollo de un parser descendente recursivo que
reconozca expresiones en notación prefija, incorporando semántica de traducción para
generar la expresión equivalente en notación infija.
Los errores sintácticos se tratan con la función rd_syntax_error(). En el caso de invocar esta
función, se imprime un mensaje en el que se indica el número de línea en el que se produce
el error, junto con la comparación de los valores esperados y los recibidos.
void rd_syntax_error (int expected, int token, char *output) {
fprintf (stderr, “ERROR in line %d”, line_counter);
fprintf (stderr, output, expected, token);
exit(0);
}
La función main se limita a llamar al parser dentro de un bucle controlado por flagMultiple
(siempre es 1 a menos que se produzca un error). Inicializa el análisis mediante la función
ParseAxiom(), la cual introduce la producción del axioma
int main (int argc, char **argv){
int flagMultiple = 1;
if (argc >= 2) {
if (strcmp (“-s”, argv[1] == 0){
flagMultiple = 0;
}
}
rd_lex ();
do{
ParseAxiom();
} while (flagMultiple);
exit(0);
}
La función ParseAxiom() da comienzo a las reglas de producción introduciendo
ParseExpresion() . Se corresponde con la primera regla de la gramática:
Axioma ::= Expresion “\n”
Comprueba que termine con un salto de línea mediante MatchSymbol(). Éste comprueba si
el token actual se corresponde con el pasado por argumento (en caso contrario se llama al
mensaje de error para terminar).
void ParseAxiom () { ///Axioma ::= Expresion\n
ParseExpresion ();
if (tokens.token == \n) {
MatchSymbol(‘\n’);
printf(“\n”);
} else {
rd_syntax_error(-1, tokens.token, “”--Unexpected token
(Expected: %d=None, Read:%d) at end of Parsing\n”);
}
}
5
Irene Peligros Florindo, Elena Recio Álvarez Grupo605
[email protected] [email protected]
La función ParseExpresion() incluye las reglas de producción de la gramática:
Expresion ::= “(“ R “)” | Numero | Variable
Primero se analiza si se trata de una expresión entre paréntesis, o si se corresponde con las
reglas de producción que dan un número o una variable. Para estas últimas producciones
alternativas se invoca la función ParseRestoExpresion(), al tratarse dos producciones y no
poder abordarlas con un único else que las diferencie de la función ParseR().
void ParseExpresion () {
///Expresion ::= (R)
if (tokens.token == ‘(’){
MatchSymbol(‘(’);
ParseR();
MatchSymbol(‘)’);
} else { // Expresion ::= Numero | Variable
ParseRestoExpresion();
}
}
La función ParseR() desarrolla las reglas de producción asociadas a R:
R ::= Operador Parametro Parametro | = Variable Parametro
En caso de que se trate de la primera regla, llamará a la función ParseOperador(), y en el
caso de ser la segunda, usa la función genérica MatchSymbol() para comprobar que el
lexema leído es el símbolo de asignación. A continuación se traduce la expresión a forma
infija, con la correcta posición de los paréntesis, variables y resto de parámetros.
void ParseR () {
//R::= Operador Parametro Parametro
if (tokens.token == T_OPERATOR){
ParseOperador();
} else if { //R::= = Variable Parametro
MatchSymbol(‘=’);
printf(“(“);
printf(“%s = “, tokens.variable_name);
MatchSymbol(T_VARIABLE);
ParseExpresion();
printf(“)”);
}
}
ParseRestoExpresion() recoge las otras dos posibles producciones de Expresion que dan
una Variable (se imprime de forma infija) o un Numero.
void ParseRestoExpresion () {
//Expresion::= Numero
if (tokens.token == T_NUMBER){
MatchSymbol(T_NUMBER);
} else if {
//Expresion ::= Variable
printf(“%s”, tokens.variable_name);
MatchSymbol(T_VARIABLE);
}
}
6
Irene Peligros Florindo, Elena Recio Álvarez Grupo605
[email protected] [email protected]
La función ParseOperador() primero emplea la función genérica MatchSymbol() para
comprobar que el token se corresponde con un operador. A continuación comienza la
traducción a una expresión en notación infija. Inicia con la apertura del paréntesis para
poder distinguir operaciones encadenadas, y hace una llamada a ParseExpresion() para
procesar el primer operando. Luego imprime el operando matemático y vuelve a llamar a la
función ParseExpresion() para procesar el segundo operando. Por último, cierra con un
paréntesis para completar la notación infija.
void ParseOperador () {
//Operador::= “+” | “-” | “*” | “/”
MatchSymbol(T_OPERATOR);
printf(“(“);
ParseExpresion();
printf(“ %c “, tokens.token_val);
ParseExpresion();
printf(“)”);
}
Como se puede observar en el código, no se incluye la siguiente regla de la gramática:
Parametro ::= Expresion
Esto se debe a que dicha regla ya está implícitamente manejada dentro de la función
ParseExpresion(). No se incluye ya que su única función sería llamar a ParseExpresion(), lo
cual sería redundante.
4. Pruebas de traducción y evaluaciones realizadas
En este apartado se muestran algunos ejemplos de pruebas que se han realizado para
comprobar el código.
En el fichero drLL.txt se incluyen pruebas (todas pasadas con éxito) que abordan las
propuestas en el enunciado junto con algunas adicionales que contemplan las posibles
expresiones en notación prefija que recibe el parser y traduce a notación infija.
Algunas de ellas son:
Código recibido Código devuelto Comentarios
A A Prueba con una sola variable
z7 Z7 Variable con letra y número
(+ A 122) (A + 122) Expresión simple con operador
(* (+ A 2) (- B 3)) ((A + 2) * (B - 3))
Expresiones con operadores
(/ (- (* A B) C) 2) (((A * B) - C) / 2) anidados
(= a (= b (= c3 (+ 2 3)))) ( a = (b = (c3 = (2 + 3))) Expresión con asignaciones
(= A (* (+ B (- C (A = (((B + (C - D))
D)) (/ E F))) * (E / F)))) Expresiones complejas con
asignaciones y operadores
anidados
= r (- (+ (= s (+ 2 (r = (((s = (2 + 3))
3)) 4) 5) + 4) - 5))
7
Irene Peligros Florindo, Elena Recio Álvarez Grupo605
[email protected] [email protected]
Al introducir una expresión que producirá error, se devuelve un mensaje del tipo:
ERROR in line 19 -- Unexpected Token (Expected: -1=None, Read:1001) at end
of Parsing
En el fichero drLL.txt no se contemplan casos que sabemos que van a producir dicho error
ya que al introducirse en el parser éste finaliza.
Es por ello por lo que analizaremos individualmente algunos casos que deben dar error:
Este código produce un error ya que la variable tan sólo puede estar seguida
(opcionalmente) de un único número
A879
El siguiente código también producirá un error y se paralizará el análisis de las líneas
siguientes al tratarse de una expresión que nuestro parser identifica como sintácticamente
inválida
(((* 3 2)))
El código no contempla los signos unarios - y + como parte de nuestra gramático (ni a nivel
sintáctico ni léxico). Es por ello por lo que la siguiente entrada producirá un error
-1
