Automatas

Pr´cticas Compiladores YACC a
Este material no es obligatorio para la pr´ctica. a Grupos de Kostadin Koruchev. A quien se refiere: A los alumnos que por una u otra raz´n no han o podido asistir en clase. Esto son los ejercicios que se han hecho en clase. Los ejemplos est´n ampliados en respeto con lo que se dio en clase. a Contenido: Los ejercicios que se hicieron en clase con explicaciones yunos 4-5 problemas m´s. a Como utilizarlo: En clase los ejercicios se dan uno tras otro y no se proporciona la soluci´n antes de que los alumnos resuelven el problema. Esto o es claramente imposible con un material en papel. El grado de manejo de la pr´ctica depende del esfuerzo de cada alumno. Por tanto una simple lectura a del material no ofrece mucho manejo de yacc. El procedimiento correcto es elsiguiente: Leer con cuidado el material. Cuando hay que escribir un programa, intentar de escribirlo utilizando el material de referencia proporcionado en clase y la informaci´n en “info yacc”. Ocultar el resto de este manual con o una hoja. Despu´s de resolver el problema, comparar con la soluci´n que se e o proporciona. Los puntos donde hay que parar de leer y hacer el ejercicio est´n maracados con ***************************** El final de la secci´n, donde se proporciona la soluci´n del problema, se o o da con —————————–

1

Pr´ctica 1. Introducci´n a yacc a o

Yacc es una herramienta para construcci´n de analizadores sint´cticos de o a lenguajes del tipo LR(1) (LALR).

1.1

Concepto:

Consideramos el lenguaje: -> S -> B -> D -> S ( B ) ( B ) D b D NIL 1

(1)Construimos la tabla SLR de an´lisis: a ( b ) D B $ S --------------------------------------------------------------0 1 3 10 1 2 3 D->NIL 5 8 2 2 3 D->NIL 5 6 3 3 D->NIL 4 4 D->bD 5 B->D 6 7 7 B->(B) 8 9 9 S->(B) 10 ACCEPT ---------------------------------------------------------------Observaci´n: 1. La tabla se construye utilizando un algoritmo bien o conocido y no es necesario hacerla a mano. 2. Lasdecisiones(acciones) en el lenguaje pueden hacerse s´lo al reducir una regla. Es preciso entonces al o hacer la reducci´n, incluir las acciones. En yacc esto se escribe as´ o ı:

1.2
S

Formato fichero entrada yacc
: ’(’ B ’)’ { acci´n; } o

donde acci´n representa sentencias en C, S - s´ o ımbolo no terminal, (B) - la sentencia que se reduce a S. Con muchas reglas del mismo s´ ımbolo noterminal: B : ’(’ B ’)’ | ’d’ D

Yacc construye la tabla de an´lisis y ejecuta el trozo de programa {acci´n; a o }, antes de reducir los s´ ımbolos. Tambi´n maneja la pila del aut´mata LR e o (de s´ ımbolos y estados). Los s´ ımbolos terminales con un car´cter pueden a sustituirse con el c´digo (ASCII) del mismo, si esto es que devuelve del o analizador morfol´gico. Al encontrar un error sint´ctico,el analizador llama o a a yyerror(). El c´digo de yacc se incluye en manera parecida de lex entre o %%. Problema: 2

Escribir el lenguaje (1) en formato yacc. Compilar con yacc. Soluci´n: o ***************************** %% S : B : | D : | %% —————————– ’(’ B ’)’ ’(’ B ’)’ D ’b’ D /* NIL */ { { { { { printf(" printf(" printf(" printf(" printf(" S->(B)\n");} B->(B)\n");} B->D\n");} D->’b’ D\n");}D->NIL\n");}

1.3

yyerror(); main(); yylex();

El usuario tiene que proporcionar las funciones yyerror(), main() y yylex(). El funcionamiento de yylex() es el mismo que proporciona lex. yyerror() sirve para escribir los errores en stderr. main() invoca yyparse(). yyparse() es la funci´n que se genera a partir de las definiciones de la gram´tica y las o a acciones. Es decir, todo entre %% y%% es yyparse(). Devuelve un entero igual a 0 si el an´lisis ha terminado con exito y 1 si el an´lisis ha terminado a a con error. /* ANALIZADOR MORFOLOGICO */ int yylex() { char ch=getchar(); if (ch==’(’ || ch==’b’ || ch==’)’) return ch; return 0; } /* manejo de errores y main -- omitidos en los demas ejemplos */ void yyerror(a) { printf(a);} int main() { return yyparse();}

1.4

Valor...