Procesadores de Lenguaje: Práctica Anual
Ingeniería en Informática 4º C
Facultad de Informática UCM (2009-2010)

1ª Entrega

Grupo: <Número asignado al grupo>
Miembros: <En orden alfabético por primer apellido y separados por comas>

Introducción
Muy breve descripción del contenido de la memoria y de su estructura.
Se recomienda crear un índice para acceder directamente a cada una de las secciones, numerar las páginas, etc.

0. Descripción del lenguaje fuente
En esta sección se debe describir informalmente cómo es el lenguaje de programación de alto nivel que se va a procesar. En este apartado basta con copiar las características que os proponemos a continuación (salvo las restricciones contextuales que se llevarán al punto 4.1).

Características que debe tener el lenguaje definido:
•	Los programas constarán de una sección de declaraciones y de una sección de instrucciones, separadas mediante el símbolo &
•	La sección de declaraciones constará de una secuencia de una o más declaraciones, separadas entre sí por el símbolo ; 
•	El lenguaje distingue cadenas según estén escritas con letras mayúsculas o minúsculas, tanto si son palabras reservadas (que se escriben siempre en minúsculas) como si son identificadores de variables
•	Es decir, aunque dos identificadores tengan las mismas letras, se consideran distintos si no coinciden en mayúsculas y minúsculas
•	Cada declaración constará de una variable, seguida del símbolo : y a continuación el nombre de un tipo
•	Los identificadores de las variables comienzan necesariamente por una letra, seguida de cero o más letras y dígitos 
•	En la sección de declaraciones no podrá haber variables duplicadas
•	El tipo podrá ser boolean (valores booleanos true y false), character (caracteres alfanuméricos), natural (números naturales), integer (números enteros con signo) y float (números reales)
•	La sección de instrucciones constará de una secuencia de una o más instrucciones, separadas por el símbolo ;
•	El lenguaje sólo tendrá tres tipos de instrucciones: instrucciones de asignación, instrucciones de lectura e instrucciones de escritura
•	Una instrucción de asignación consta de una variable, seguida de los símbolos := y a continuación una expresión
•	Las expresiones usarán los siguientes operadores: <, >, <=, >=, =, =/=, +, -, *, /, %, and, or, not, - (unario), <<, >>, (float), (int), (nat),  (char) y ||
•	El menor nivel de prioridad (nivel 0) es el de los operadores de comparación < (menor que), > (mayor que), <= (menor o igual que), >= (mayor o igual que), = (igual) y =/= (distinto): 
•	Todos estos operadores son binarios infijos y no asocian 
•	Es posible comparar entre sí valores numéricos (natural con natural, natural con entero, natural con real, entero con natural, entero con entero, entero con real, real con natural, real con entero, real con real), caracteres (según la ordenación del estándar de caracteres usado en la implementación, por ejemplo UNICODE) y booleanos (true se considera mayor que false)
•	El resultado de una comparación es un valor booleano (true cuando se cumple la comparación, false cuando no se cumple)
•	El siguiente nivel de prioridad (nivel 1) es el de los operadores aritméticos + (suma) y - (resta), así como el del operador lógico or
•	Todos ellos son operadores binarios infijos que asocian a izquierdas
•	+ y - operaran sobre valores numéricos. El resultado será un valor real (siempre y cuando alguno de los operandos sea real), un valor entero (siempre y cuando no haya operandos reales y algún operando sea entero) o un valor natural (sólo cuando los dos operandos sea naturales)
•	or opera sobre valores booleanos. El resultado será el o lógico de los operandos
•	El siguiente nivel de prioridad (nivel 2) es el de los operadores aritméticos * (multiplicación), / (división) y % (módulo), así como el operador lógico and
•	Todos ellos son operadores binarios infijos que asocian a izquierdas
•	* y / operan sobre valores numéricos. El resultado será un valor real (siempre y cuando alguno de los operandos sea real), un valor entero (siempre y cuando no haya operandos reales y algún operando sea entero) o un valor natural (sólo cuando los dos operandos sea naturales). En el primer caso, la división funcionará como división real. En los dos últimos casos, la división funcionará como división entera
•	En la operación módulo % el primer operando puede ser entero o natural, pero el segundo operando sólo puede ser natural. El resultado de a % b será el resto de la división de a entre b. El tipo del resultado será el mismo que el del primer operando
•	Por último, and opera únicamente sobre valores booleanos. El resultado será el y lógico de los operandos
•	El siguiente nivel de prioridad (nivel 3) es el de los operadores de desplazamiento << y >>
•	Ambos son operadores binarios infijos que asocian a derechas
•	Operan únicamente sobre valores naturales. Por un lado a << b es el natural resultante de desplazar b bits hacia la izquierda en la representación binaria de a. Por otro lado a >> b es el natural resultante de desplazar b bit hacia la derecha en la representación binaria de a  
•	El mayor nivel de prioridad (nivel 4) es el del operador lógico not, el - unario, los operadores de conversión (float), (int), (nat) y (char), y el operador con estructura sintáctica valor absoluto delimitado por dos símbolos de barra vertical |
•	Todos son operadores unarios prefijos, salvo el valor absoluto que sitúa al operando dentro de sus dos barras verticales 
•	El operador negación lógica not asocia, y opera sobre valores booleanos, siendo el resultado la negación lógica de su operando 
•	El operador – unario también asocia, opera sobre valores numéricos y el resultado es su operando cambiado de signo. Este resultado será real si el tipo del operando es real, y entero en otro caso
•	Los operadores de conversión no asocian
•	(float) a devuelve el propio a si es real. Si a es entero o natural el resultado es a convertido a real (añadiendo un único 0 en la parte decimal). Si a es un carácter el resultado es el código de dicho carácter convertido a real
•	(int) a devuelve el propio a si es entero, Si a es real el resultado es la parte entera de a. Si a es natural el resultado es a convertido a entero (con signo positivo). Si a es un carácter el resultado es el código de dicho carácter convertido a entero
•	(nat) a devuelve el propio a si es natural. No admite operandos reales o enteros. Si a es un carácter el resultado es el código de dicho carácter
•	(char) a.devuelve el propio a si es un carácter. Si a es natural el resultado es el carácter cuyo código es a. No admite operandos reales o enteros
•	El operador valor absoluto está formado por el símbolo de barra vertical | seguido de una expresión, seguida otra vez del símbolo de barra vertical |. El resultado es el valor absoluto de la expresión, de tipo real si la expresión evalúa a un número real, o natural si la expresión evalúa a un número entero o natural. No admite expresiones que evalúen a booleano o carácter
•	Como expresiones básicas, que podrán ser combinadas mediante los operadores anteriores, se consideran las siguientes:
•	Literales naturales. Secuencias de uno o más dígitos, no admitiéndose ceros a la izquierda. Téngase en cuenta que las expresiones enteras se pueden formar con literales naturales y el – unario
•	Literales reales. Secuencia formada por una parte entera, seguida de una de estas tres cosas: una parte decimal, una parte exponencial, o una parte decimal seguida de una parte exponencial. La parte entera tiene la misma estructura que un literal natural. La parte decimal está formada por el símbolo . seguido de uno o más dígitos, no admitiéndose ceros a la derecha (salvo si se trata de un único cero, como por ejemplo 2.0). La parte exponencial está formada por el símbolo E o el símbolo e, seguido opcionalmente del símbolo -, y seguido obligatoriamente de la misma estructura que tiene un literal natural
•	Literales booleanos. Con valores true y false
•	Literales carácter. Un símbolo de comilla simple ' seguido de un carácter alfanumérico, seguido otra vez del símbolo de comilla simple '
•	Variables, que han debido ser convenientemente declaradas en la sección de declaraciones
•	En las expresiones es posible utilizar paréntesis para alterar la forma en la que se aplican los operadores sobre los operandos
•	Una instrucción de asignación debe cumplir además estas condiciones: 
•	La variable en la parte izquierda debe haber sido declarada
•	A una variable de tipo real es posible asignarle un valor real, entero o natural (produciéndose automáticamente la correspondiente conversión), pero no un carácter
•	A una variable de tipo entero es posible asignarle un valor entero o natural (produciéndose automáticamente la correspondiente conversión), pero no un valor real o un carácter
•	A una variable de tipo natural únicamente es posible asignarle un valor natural
•	A una variable de tipo carácter únicamente es posible asignarle un valor de tipo carácter
•	A una variable de tipo booleano únicamente es posible asignarle un valor de tipo booleano
•	Una instrucción de lectura tiene la forma in(v) donde v es una variable. Su efecto es leer un valor del tipo de la variable v por la entrada estándar del usuario y almacenar en la variable v el valor leído
•	Una instrucción de escritura tiene la forma out(exp), donde exp es una expresión. Su efecto es escribir por la salida estándar del usuario el valor de exp   
•	El lenguaje admite comentarios de línea. Dichos comentarios comienzan con el símbolo # y se extienden hasta el fin de la línea

Ejemplo de programa en el lenguaje definido:

# Programa de ejemplo
cantidad: float;
euros: integer;
centimos: float
&
in(cantidad);
euros := (int)cantidad;
centimos := cantidad – euros;
out(euros);
out('.');
out(centimos);
out((char)10)  # Código del carácter salto de línea

1. Definición léxica del lenguaje 
Especificación formal del léxico del lenguaje (a veces llamado microsintaxis) utilizando definiciones regulares.

2. Definición sintáctica del lenguaje 
Especificación formal de los aspectos sintácticos del lenguaje. 

2.1. Descripción de los operadores 
Enumeración de los operadores del lenguaje, especificando su aridad, su asociatividad y su prioridad.

2.2. Formalización de la sintaxis 
Formalización de la sintaxis del lenguaje utilizando una gramática incontextual. Dicha gramática debe representar de manera natural las prioridades y la asociatividad de los operadores.

3. Estructura y construcción de la tabla de símbolos 
Deberá contemplarse tanto los aspectos necesarios para comprobar las restricciones contextuales, como los necesarios para llevar a cabo la traducción.

3.1. Estructura de la tabla de símbolos 
Descripción de las operaciones de la tabla de símbolos definiendo la cabecera de dichas operaciones, así como describiendo informalmente su cometido, incluyendo el propósito de cada uno de sus parámetros.

3.2. Construcción de la tabla de símbolos 
Formalización de la construcción de la tabla de símbolos mediante una gramática de atributos.

3.2.1 Funciones semánticas 
Descripción, si procede, de las funciones semánticas adicionales utilizadas en la especificación. Para cada función debe indicarse explícitamente su cabecera, así como informalmente su cometido, incluyendo el propósito de cada uno de sus parámetros. 

Esta sección puede dejarse vacía si no se van a usar funciones semánticas adicionales.    

3.2.2 Atributos semánticos 
Para cada categoría sintáctica relevante en este procesamiento deben enumerarse sus atributos semánticos, indicando si son heredados o sintetizados, y describiendo informalmente su propósito.

3.2.3 Gramática de atributos 
Gramática de atributos que formaliza la construcción de la tabla de símbolos.

4. Especificación de las restricciones contextuales 

4.1. Descripción informal de las restricciones contextuales 
Enumeración y descripción informal de las restricciones contextuales del lenguaje. En este apartado basta con copiar las restricciones contextuales que os proponemos al principio de la plantilla, cuando describimos las características del lenguaje.

4.2. Funciones semánticas 
Descripción, si procede, de las funciones semánticas adicionales utilizadas en la especificación. Para cada función debe indicarse explícitamente su cabecera, así como informalmente su cometido, incluyendo el propósito de cada uno de sus parámetros. 

Esta sección puede dejarse vacía si no se van a usar funciones semánticas adicionales.

4.3. Atributos semánticos 
Para cada categoría sintáctica relevante en este procesamiento deben enumerarse sus atributos semánticos, indicando si son heredados o sintetizados, y describiendo informalmente su propósito.

4.4. Gramática de atributos 
Gramática de atributos que formaliza la comprobación de las restricciones contextuales.

5. Especificación de la traducción

5.1. Lenguaje objeto y máquina virtual 
Explicar cómo es el lenguaje objeto y cómo es la arquitectura de la máquina P capaz de ejecutarlo (tipos de celdas según tipos primitivos, etc.), su comportamiento interno y todo su repertorio de instrucciones (mostrando su sintaxis y una descripción informal de su semántica).

5.1.1.  Arquitectura 

5.1.2.  Comportamiento interno

5.1.3.  Repertorio de instrucciones

5.2. Funciones semánticas 
Descripción, si procede, de las funciones semánticas adicionales utilizadas en la especificación. Para cada función debe indicarse explícitamente su cabecera, así como informalmente su cometido, incluyendo el propósito de cada uno de sus parámetros. 

Esta sección puede dejarse vacía si no se van a usar funciones semánticas adicionales.

5.3. Atributos semánticos 
Para cada categoría sintáctica relevante en este procesamiento deben enumerarse sus atributos semánticos, indicando si son heredados o sintetizados, y describiendo informalmente su propósito.

5.4. Gramática de atributos 
Gramática de atributos que formaliza la traducción.

6. Diseño del analizador léxico 
Diagrama de transición que caracterice el diseño del analizador léxico. La implementación del analizador léxico debe estar guiada por este diseño.

7. Acondicionamiento de las gramáticas de atributos 
Transformaciones realizadas sobre las gramáticas de atributos para permitir la traducción predictivo-recursiva. 

Únicamente deben incluirse la transformación de las producciones que se ven afectadas. Si alguna de las gramáticas no necesitan acondicionamiento, dejar el correspondiente subapartado en blanco.

7.1. Acondicionamiento de la gramática para la construcción de la tabla de símbolos  

7.2. Acondicionamiento de la gramática para la comprobación de las Restricciones Contextuales 

7.3. Acondicionamiento de la gramática para la traducción 

8. Esquema de traducción orientado a las gramáticas de atributos 
Esquema de traducción en el que se muestre, mediante acciones semánticas, los lugares en los que deben evaluarse las distintas ecuaciones contempladas en todas las gramáticas de atributos: la de construcción de la tabla de símbolos, la de comprobación de las restricciones contextuales y la de especificación de la traducción. 

El recorrido del árbol será el realizado por un analizador predictivo-recursivo.

9. Esquema de traducción orientado al traductor predictivo – recursivo 
Esquema de traducción en el que se haga explícito los parámetros utilizados para representar los atributos, así como en los que se muestre la implementación de las ecuaciones semánticas como asignaciones a dichos parámetros.

9.1. Variables globales 
Descripción y propósito de las variables globales usadas. 

Si no se usan variables globales, dejar este apartado en blanco.

9.2. Nuevas operaciones y transformación de ecuaciones semánticas 
En caso de introducir nuevas operaciones (por ejemplo: el procedimiento “emite”), deben describirse aquí. 

Debe describirse, así mismo, qué ecuaciones semánticas se ven transformadas y cómo (por ejemplo: la generación de código se implementa emitiendo la última instrucción).

9.3. Esquema  de traducción 

10. Formato de representación del código P 
Deberá describirse el formato de archivo aceptado por el intérprete de la máquina P, llamado código a pila (código P). Se valorará la eficiencia de dicho formato (por ejemplo: uso de bytecode binario en lugar de texto).

11 Notas sobre la implementación  
Descripción de la implementación realizada.

Deberán implementarse dos programas separados:
1.	Traductor del lenguaje fuente a código de una máquina P. Este programa funcionará en modo línea de comandos, tomando dos argumentos: el nombre del archivo que contiene el programa fuente y el nombre del archivo donde se va a generar el código objeto. El resultado dependerá de si el programa fuente es o no correcto:
•	Si es correcto, se generará el archivo con el código objeto
•	Si no es correcto, se mostrará por pantalla un listado de errores y no se generará ningún archivo
o	Cada error estará precedido por los números de fila y de columna que identifican el punto exacto en el programa fuente en el que se ha producido el error
o	La ejecución del programa se interrumpe en el momento en que se encuentra el primer error sintáctico. El resto de los errores (léxicos y de violación de restricciones contextuales) no interrumpen la ejecución del traductor
2.	Intérprete trivial capaz de simular el comportamiento de la máquina P. Este programa también funcionará en modo línea de comandos, tomando como argumento el archivo donde está el código P a ejecutar, así como un valor que indicará si la ejecución debe ser en modo normal o en modo traza. El resultado será la ejecución de dicho código:
•	En modo normal el único resultado visible será el producido por las instrucciones específicas de lectura/escritura
•	En modo traza el intérprete mostrará una traza por la consola de comandos con los distintos pasos de ejecución. En cada paso el intérprete debe: 
1.	Mostrar el contenido de la pila de ejecución y de las celdas relevantes en la memoria de datos
2.	Esperar a que el usuario pulse una tecla para proseguir la ejecución
3.	Mostrar la instrucción a ejecutar y ejecutarla, avanzando al siguiente paso

Deberán entregarse un conjunto de archivos conteniendo los casos de prueba (programas de ejemplo) utilizados en la validación de la implementación, incluyendo tanto casos correctos como incorrectos, para demostrar que los programas implementados son capaces de detectar y tratar todos los tipos de errores posibles de una forma adecuada a los requisitos mencionados anteriormente.

11.1. Descripción de archivos 
Enumeración de los archivos con el código fuente de la implementación, y descripción de lo que contiene cada archivo. 

El código en sí deberá estar adecuadamente comentado, pero NO se incluirá en la memoria de la práctica. Aquí sólo debe describirse someramente qué contiene cada archivo.

11.2. Otras notas 
Otras notas sobre la implementación que se consideren pertinentes (por ejemplo: diagramas de clase UML describiendo la arquitectura del sistema).

Conclusiones
Qué se ha conseguido y qué se ha dejado pendiente para más adelante.

Referencias bibliográficas
Libros, artículos y otras fuentes de información utilizadas (por ejemplo páginas web).

Apéndices 
Sólo si alguno fuese necesario… y en ningún caso se trata de copiar aquí el código de las aplicaciones desarrolladas ni nada similar.