Examen: Lo que debes saber

Temas

Traducción de programas. Conceptos generales: código máquina, lenguaje ensamblador, lenguaje de alto nivel, programa fuente y programa objeto (destino). Fases de traducción: análisis léxico, análisis sintáctico, análisis semántico, y generación de código. Tipos de procesadores de lenguajes y ejemplos representativos de cada uno: intérprete, compilador, preprocesador, ensamblador, compilador cruzado, transpilador, máquina virtual (interpretación y compilación Just-In-Time de bytecode/código intermedio) y compilador self-hosting (auto-alojado). Desarrollo de un compilador incremental utilizando el enfoque de “rebanadas verticales”.
Análisis léxico. Concepto de token. Expresiones regulares y sus operadores. Módulo re de Python. Funciones re.search, re.match, re.fullmatch, re.split, re.findall, re.finditer y re.sub. Banderas de opción para expresiones regulares. Tipo Match y sus operaciones más comunes.
Análisis sintáctico. Conceptos generales de gramáticas libres de contexto. Gramáticas de tipo PEG (Parsing Expression Grammar). Construcción de parsers usando el paquete Arpeggio para Python, incluyendo: definición de la gramática (incluyendo soporte para comentarios), creación del árbol de parseo, manejo de errores sintácticos y recorrido del árbol de parseo usando el patrón de visitante.
Análisis semántico. Conceptos generales de análisis semántico: detección de errores a tiempo de compilación y a tiempo de ejecución. Concepto de tabla de símbolos y su función durante el análisis semántico. Definición de un visitante para recorrer el árbol de parseo de Arpeggio y efectuar el análisis semántico.
Generación de código. La plataforma WebAssembly (WASM), sus ventajas y desventajas. Funcionamiento general de una máquina de pila. Directivas e instrucciones de WASM: funciones, manejo de variables y parámetros, operaciones aritméticas, comparaciones y control de flujo para condiciones y ciclos. Uso del paquete wasmtime de Python para traducir programas en el formato textual de WASM a su formato binario y ejecutar el código resultante. Definición de un visitante para recorrer el árbol de parseo de Arpeggio y realizar la generación de código en el formato textual WASM.

Artículos permitidos durante el examen

Pluma, lápiz, borrador, sacapuntas.

Acordeón personal de estudio con las siguientes características:

Debe ser uno de los siguientes:
- Tarjeta o ficha de trabajo de \(5 \times 8\) pulgadas (\(12.7 \times 20.32\) cm).
- Media hoja tamaño carta (\(13.97 \times 21.59\) cm).
Debe estar escritas a mano. No se permiten tarjetas/hojas impresas elaboradas en computadora.
Está permitido escribir en ambos lados de la tarjeta/hoja.
Debe incluir matrícula y nombre completo en la esquina superior izquierda de ambos lados de la tarjeta/hoja.
No hay restricciones sobre el contenido específico escrito en la tarjeta/hoja.

NOTA 1: Una vez iniciado el examen, no se permite compartir ningún artículo con alguien más.

NOTA 2: No está permitido usar teléfono celular, calculadora, tableta, computadora o cualquier otro dispositivo electrónico.

Preguntas ejemplo

¿Cuál es la diferencia entre código máquina y lenguaje ensamblador?
¿Cuál es la diferencia entre un compilador tradicional y un transpilador? Proporciona un ejemplo de un transpilador.
Explica qué es un compilador de tipo self-hosting y menciona un ejemplo.
Explica brevemente para qué sirven los paquetes de Python arpeggio y wasmtime utilizados en clase.
¿Cuál es el propósito del analizador semántico en un compilador?

¿Qué imprime en la salida estándar el siguiente código de Python?

import re

cadena = '''
    BRILLA, LUCE, RATITA ALADA,
    ¿EN QUE ESTARAS TAN ATAREADA?

    POR ENCIMA DEL UNIVERSO VUELA
    COMO UNA BANDEJA DE TETERAS.
    BRILLA, LUCE...
    UN MURCIELAGO PASO
    NO SE DONDE SE ESCONDIO.
'''

for palabra in re.findall(r'\w+', cadena):
    if re.search('O', palabra):
        print(palabra)

¿Qué imprime en la salida estándar el siguiente código de Python?

import re

cadena = 'EL ESPEJO INDICA UN OSO AMOROSO EN EL INFIERNO'
resultado = re.sub(r'\b([AEIOU])(\w+)([AEIOU])\b', r'\3\2\1',
    cadena)
print(resultado)

Escribe una expresión regular que permita reconocer fechas válidas usando el formato YYYY-MM-DD definido en el estándar ISO 8601. Se debe consider lo siguiente para procurar que la gran mayoría de las fechas reconocidas sean válidas (aunque no necesariamente todas):
- El año YYYY pueder ir del 0000 al 9999.
- En el mes MM el primer dígito debe ser 0 o 1. Si el primer dígito es 0, el segundo debe ser cualquier dígito del 1 al 9. Si el el primer dígito es 1, el segundo dígito debe ser 0, 1 o 2.
- En el día DD el primer dígito debe ser 0, 1, 2 o 3. Si el primer dígito es 0, el segundo debe ser cualquier dígito del 1 al 9. Si el el primer dígito es 1 o 2, el segundo dígito debe ser cualquier dígito del 0 al 9. Si el el primer dígito es 3, el segundo dígito debe ser 0 o 1.
Así, por ejemplo, las siguientes fechas deben ser reconocidas por la expresión regular:
- 2023-04-28
- 1521-08-13
- 9999-12-31
Sin embargo, las siguientes fechas deben ser rechazadas:
- 0000-00-00
- 2023-04-32
- 1998-13-15

Se tiene la siguiente gramática PEG:

foo    =  bar baz quz? EOF
bar    =  (corge / grault)*
baz    =  (garply / waldo / fred)+
quz    =  plugh / thud
corge  =  'a'
grault =  'b'
garply =  'c'
waldo  =  'd'
fred   =  'e'
plugh  =  'f'
thud   =  'g'

Suponiendo que la producción raíz es foo, dibuja el árbol de parseo (parse tree) que se genera al reconocer la siguiente cadena de entrada:

abcedg

Escribe un módulo completo en WebAssembly text format (WAT) que contenga una función exportada llamada average. Dicha función debe recibir como entrada tres argumentos de tipo f64 (punto flotante de 64 bits) y debe devolver un valor de tipo f64 con el promedio aritmético de los tres valores de entrada.

Por ejemplo, average(1.25, 5.25, -14.0) debe devolver -2.5.

Se tiene la siguiente definición de módulo en WebAssembly text format (WAT).

(module
  (func
    (export "mystery")
    (param $n i32)
    (result i32)
    (local $a i32)
    (local $b i32)
    i32.const 0
    local.set $a
    i32.const 1
    local.set $b
    loop
        local.get $b
        local.get $b
        local.get $a
        i32.add
        local.set $b
        local.set $a
        local.get $n
        i32.const 1
        i32.sub
        local.set $n
        local.get $n
        br_if 0
    end
    local.get $a
  )
)

¿Qué valor devuelve la función mystery al ser invocada con cada uno de los valores (parámetro n) indicados a continuación?

mystery(1)
mystery(2)
mystery(5)
mystery(7)

Se tiene el siguiente programa de Python que utiliza el paquete Arpeggio para implementar un pequeño compilador de un lenguaje cuya sintaxis está definida en la gramática contenida en la variable PEG. El código convierte el contenido de la variable codigo_fuente a un módulo completo de WebAssembly en formato textual (WAT) y lo imprime en la salida estándar. Indica la salida completa (el código WAT) de este programa al momento de correrlo.

import arpeggio
import arpeggio.cleanpeg

codigo_fuente = '1-222-33-4'

PEG = '''
    inicio     = uno dos* tres+ cuatro? EOF
    uno        = '1'
    dos        = '2'
    tres       = '3'
    cuatro     = '4'
    comentario = '-'
'''

class ExamVisitor(arpeggio.PTNodeVisitor):

    TEMPLATE = '''
(module
    (func
    (export "inicio")
    (result i64)
{}  )
)
'''

    def visit_inicio(self, node, children):
        return ExamVisitor.TEMPLATE.format(''.join(children))

    def visit_uno(self, node, children):
        return '    i64.const 1\n'

    def visit_dos(self, node, children):
        return ('    i64.const 2\n'
                '    i64.mul\n')

    def visit_tres(self, node, children):
        return ('    i64.const 3\n'
                '    i64.mul\n')

    def visit_cuatro(self, node, children):
        return ('    i64.const 4\n'
                '    i64.mul\n')

if __name__ == '__main__':
    try:
        parser = arpeggio.cleanpeg.ParserPEG(PEG, 'inicio',
            'comentario')
        resultado = arpeggio.visit_parse_tree(
            parser.parse(codigo_fuente), ExamVisitor())
        print(resultado)
    except arpeggio.NoMatch as e:
        print(e)