1. No category

Procesamiento de Lenguajes (PL)
Curso 2014/2015
Pr´
actica 1: analizador descendente recursivo
Fecha y m´
etodo de entrega
La pr´
actica debe realizarse de forma individual, como las dem´as pr´acticas de la asignatura, y debe entregarse a
trav´es del servidor de pr´
acticas del DLSI antes de las 23:59 del 6 de marzo de 2015.
Al servidor de pr´
acticas del DLSI se puede acceder de dos maneras:
Desde la web del DLSI (http://www.dlsi.ua.es), en el apartado “Entrega de pr´acticas”
Desde la URL http://pracdlsi.dlsi.ua.es
Una vez en el servidor, se debe elegir la asignatura PL y seguir las instrucciones.
Descripci´
on de la pr´
actica
La pr´
actica consiste en implementar un analizador sint´actico descendente recursivo, como se ha estudiado en la
clase de teor´ıa, utilizando Java como lenguaje fuente.
Como subprograma del analizador sint´
atico ser´a necesario realizar un analizador l´exico, que ser´a utilizado en la
pr´
actica 2. Adem´
as, el analizador l´exico y sint´
actico ser´an la base de la pr´actica 3.
Analizador l´
exico
El analizador l´exico debe reconocer los siguientes componentes l´exicos:
Token
pari
pard
mulop
addop
relop
pyc
dosp
coma
asig
var
real
integer
program
begin
end
function
if
then
else
endif
while
do
writeln
nentero
id
nreal
´ n regular
Expresio
(
)
’*’|’/’|’div’
’+’|’-’
’<’|’>’|’<=’|’>=’|’=’|’<>’
;
:
,
:=
var
real
integer
program
begin
end
function
if
then
else
endif
while
do
writeln
[0-9]+
[a-zA-Z][a-zA-Z0-9]*
[0-9]+\.[0-9]+
Cadena a mostrar
(
)
* / div
+< > <= >= = <>
;
:
,
:=
’var’
’real’
’integer’
’program’
’begin’
’end’
’function’
’if’
’then’
’else’
’endif’
’while’
’do’
’writeln’
numero entero
identificador
numero real
PL, 2014/2015
2
Ten en cuenta las siguientes cuestiones:
1. Debes dise˜
nar el diagrama de transiciones en papel, tal y como se ha estudiado en clase de teor´ıa. Para esta
pr´
actica no es necesario que pongas las palabras reservadas en el diagrama (saldr´ıan much´ısimos estados),
puedes tratar las palabras reservadas como identificadores en el diagrama, y justo antes de devolver el token,
comprobar si el identificador coincide con alguna de las palabras reservadas para devolver el token asociado en
vez del token del identificador.
2. El lenguaje es sensible a may´
usculas, es decir, “BeGin” es un identificador y “begin” es la palabra reservada
begin.1
3. El analizador l´exico debe ignorar los espacios en blanco, tabuladores y saltos de l´ınea (excepto para contar
columnas y filas, en cuyo caso el tabulador se contar´a como un u
´nico caracter). Debe leer el fichero car´acter a
car´
acter, hasta completar un token. En ning´
un caso debe leer el fichero completo en memoria, ni leer m´
as de
una vez el fichero.
4. En caso de que alg´
un car´
acter de la entrada no pueda formar parte de un token, se debe emitir el siguiente
error:
Error lexico (f,c): caracter ’a’ incorrecto
donde f es la fila, c es la columna, y a es el car´acter incorrecto. Cuando se encuentre un error, el programa
debe terminar con System.exit(-1)
Si el car´
acter incorrecto es el que representa el final del fichero, entonces el mensaje debe ser:
Error lexico: fin de fichero inesperado
5. El analizador l´exico tambi´en debe ignorar los comentarios, que comenzar´an por “(*” y se extender´an (posiblemente a lo largo de varias l´ıneas) hasta que aparezca la secuencia “*)”. No se permiten comentarios anidados,
es decir, el primer “*)” cierra el primer “(*”. Si se termina el fichero en mitad de un comentario se debe emitir
el error de fin de fichero inesperado.
6. En los programas que se utilizar´
an para probar las pr´acticas solamente habr´a caracteres del c´odigo ASCII, es
decir, no habr´
a acentos ni ~
n ni otros caracteres extra˜
nos.
7. El analizador l´exico se debe implementar con dos clases en Java:
La clase Token, que tendr´
a los tipos de token de la especificaci´on, tal y como se ha explicado en la clase de
teor´ıa. El m´etodo toString debe devolver para cada token la cadena que aparece en la tercera columna
de la tabla anterior.
La clase AnalizadorLexico, que debe implementar al menos el m´etodo siguienteToken, que leer´
a caracteres de la entrada hasta formar un token y lo devolver´a.
8. Utiliza la clase RandomAccessFile para acceder al fichero de entrada, usando el m´etodo readByte() o read()
para leer caracteres. El m´etodo readChar() lee caracteres Unicode y no sirve para leer caracteres ASCII.
1 El lenguaje Pascal, en el que se basa el lenguaje fuente de esta pr´
actica, no es sensible a may´
usculas (case insensitive), por lo que
ambas cadenas ser´ıan la palabra reservada begin.
PL, 2014/2015
3
Analizador sint´
actico
La gram´
atica que debe utilizarse como base para dise˜
nar el analizador sint´actico es la siguiente:
S
Vsp
Vsp
Unsp
Unsp
LV
LV
V
Lid
Lid
Tipo
Tipo
Bloque
SInstr
SInstrp
SInstrp
Instr
Instr
Instr
Instr
Instr
Instr
E
E
Expr
Expr
Term
Term
Factor
Factor
Factor
Factor
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→
program id pyc Vsp Bloque
Vsp Unsp
Unsp
function id dosp Tipo pyc Vsp Bloque pyc
var LV
LV V
V
id Lid dosp Tipo pyc
coma id Lid
integer
real
begin SInstr end
Instr SInstrp
pyc Instr SInstrp
Bloque
id asig E
if E then Instr endif
if E then Instr else Instr endif
while E do Instr
writeln pari E pard
Expr relop Expr
Expr
Expr addop Term
Term
Term mulop Factor
Factor
id
nentero
nreal
pari Expr pard
Ten en cuenta las siguientes cuestiones:
1. Para probar el analizador sint´
actico necesitas el analizador l´exico de la pr´actica funcionando correctamente.
2. Calcula los conjuntos de predicci´
on y comprueba que la gram´atica resultante es LL(1). Antes de ponerte a ello,
debes eliminar la recursividad por la izquierda y los factores comunes por la izquierda.
3. En caso de que el analizador encuentre un error, se debe emitir el siguiente mensaje:
Error sintactico (f,c): encontrado ’token’, esperaba ...
donde f es la fila, c es la columna (del primer car´acter del token), y token es el lexema del token incorrecto,
y despu´es de esperaba debe aparecer una lista con los tokens que se esperaba, mostrando para cada token la
cadena que aparece en la tercera columna de la tabla de los componentes l´exicos. Como en el analizador l´exico,
si aparece alg´
un error se debe terminar la ejecuci´on con System.exit(-1)
Ejemplo:
Error sintactico (4,5): encontrado ’hola’, esperaba ) ; + -
PL, 2014/2015
4
Los tokens esperados deben aparecer en el mismo orden que en la tabla de los componentes l´exicos.
Si el token encontrado es el final del fichero, el mensaje de error debe ser:
Error sintactico: encontrado fin de fichero, esperaba ...
4. El analizador sint´
actico se debe implementar en una clase en Java, denominada AnalizadorSintacticoDR, que
tendr´
a al menos los m´etodos/funciones asociados a los no terminales de la gram´atica.
5. Se publicar´
a un script para comprobar que el analizador sint´actico funciona razonablemente bien. Se recomienda
utilizar un m´etodo privado para acumular los n´
umeros de regla, y un atributo booleano (flag) en la parte privada
de la clase que permita mostrar o no los n´
umeros de las reglas que ha ido aplicando el analizador sint´actico, de
forma que se pueda reutilizar f´
acilmente el c´
odigo para la pr´actica 3. Por ejemplo, ante este fichero de entrada
(y suponiendo que el atributo booleano est´
a a true):
program uno;
var a:integer;
begin
a := 7+3
end
la salida del analizador deber´ıa ser:
1 2 6 7 10 12 13 9 4 15 16 20 26 29 32 36 34 30 32 36 34 31 28 18
Los n´
umeros de las reglas se corresponden con la gram´atica obtenida eliminando la recursividad por la izquierda
(RI) y los factores comunes por la izquierda (FCI), no con la gram´atica descrita anteriormente. Para que los
n´
umeros sean comunes (y la autocorrecci´
on autom´atica funcione bien), las reglas nuevas resultantes de eliminar
dichas caracter´ısticas no LL(1) se colocar´
an en el mismo lugar que las originales, desplazando hacia abajo las
siguientes reglas. Por ejemplo, al eliminar la recursividad por la izquierda de las reglas de Vsp se reemplazar´ıan
las reglas 2 y 3 de la gram´
atica original por 3 nuevas reglas, que tendr´ıan los n´
umeros 2, 3 y 4; por tanto, las
reglas de Unsp pasar´ıan a tener los n´
umeros 5 y 6 (en vez de 4 y 5), y as´ı sucesivamente.
6. Los n´
umeros de regla se deben ir acumulando (utilizando un atributo privado de tipo StringBuilder, y un
m´etodo privado), y cuando el an´
alisis termine con ´exito, en el m´etodo .comprobarFinFichero(), se imprimir´
an
los n´
umeros de regla. Si se produce alg´
un error l´exico o sint´actico, no saldr´a ning´
un n´
umero de regla.
7. La pr´
actica debe tener varias clases en Java:
La clase plp1, que tendr´
a solamente el siguiente programa principal (y los import necesarios):
class plp1 {
public static void main(String[] args) {
if (args.length == 1)
{
try {
RandomAccessFile entrada = new RandomAccessFile(args[0],"r");
AnalizadorLexico al = new AnalizadorLexico(entrada);
AnalizadorSintacticoDR asdr = new AnalizadorSintacticoDR(al);
asdr.S(); // simbolo inicial de la gramatica
asdr.comprobarFinFichero();
}
catch (FileNotFoundException e) {
System.out.println("Error, fichero no encontrado: " + args[0]);
}
catch (IOException e) {
}
}
else System.out.println("Error, uso: java plp1 <nomfichero>");
}
}
PL, 2014/2015
5
La clase AnalizadorSintacticoDR, que tendr´a los m´etodos/funciones asociados a los no terminales del
analizador sint´
actico, que imprimir´
an las reglas que van aplicando (seg´
un el valor del atributo booleano
mencionado anteriormente).
Las clases Token y AnalizadorLexico del analizador l´exico