El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Construcción de un Compilador Simple

Siguiente ►
►

En este módulo, aprenderemos a construir un compilador simple para un subconjunto del lenguaje ALGOL. Este ejercicio te permitirá comprender los conceptos fundamentales de la compilación, incluyendo el análisis léxico, el análisis sintáctico, la generación de código intermedio y la generación de código final.

Objetivos del Módulo

  • Comprender los componentes básicos de un compilador.
  • Implementar un analizador léxico (lexer).
  • Implementar un analizador sintáctico (parser).
  • Generar código intermedio.
  • Generar código final ejecutable.

  1. Componentes Básicos de un Compilador

Un compilador típico se compone de varias fases:

  1. Análisis Léxico (Lexer): Convierte el código fuente en una secuencia de tokens.
  2. Análisis Sintáctico (Parser): Convierte la secuencia de tokens en una estructura de datos (generalmente un árbol de sintaxis abstracta, AST).
  3. Análisis Semántico: Verifica la semántica del programa (por ejemplo, tipos de datos).
  4. Generación de Código Intermedio: Convierte el AST en una representación intermedia.
  5. Optimización de Código: Mejora el código intermedio para hacerlo más eficiente.
  6. Generación de Código Final: Convierte el código intermedio en código máquina o bytecode.

  1. Implementación del Analizador Léxico (Lexer)

El analizador léxico toma el código fuente y lo divide en tokens. Un token es una secuencia de caracteres que representa una unidad léxica, como una palabra clave, un identificador, un operador, etc.

Ejemplo de Código para el Lexer

import re

# Definición de tokens
token_specification = [
    ('NUMBER',   r'\d+(\.\d*)?'),  # Números enteros o decimales
    ('ASSIGN',   r':='),           # Operador de asignación
    ('END',      r';'),            # Fin de la instrucción
    ('ID',       r'[A-Za-z]+'),    # Identificadores
    ('OP',       r'[+\-*/]'),      # Operadores aritméticos
    ('NEWLINE',  r'\n'),           # Nueva línea
    ('SKIP',     r'[ \t]+'),       # Espacios y tabulaciones
    ('MISMATCH', r'.'),            # Cualquier otro carácter
]

# Compilación de las expresiones regulares
token_re = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)
get_token = re.compile(token_re).match

# Función para generar tokens
def tokenize(code):
    line_num = 1
    line_start = 0
    mo = get_token(code)
    while mo is not None:
        kind = mo.lastgroup
        value = mo.group(kind)
        if kind == 'NEWLINE':
            line_start = mo.end()
            line_num += 1
        elif kind == 'SKIP':
            pass
        elif kind == 'MISMATCH':
            raise RuntimeError(f'{value!r} inesperado en la línea {line_num}')
        else:
            yield kind, value
        mo = get_token(code, mo.end())
    if mo is None:
        raise RuntimeError(f'Error de tokenización en la línea {line_num}')

# Ejemplo de uso
code = 'x := 10 + 20;'
tokens = list(tokenize(code))
print(tokens)

Explicación del Código

  • Definición de tokens: Se define una lista de tuplas donde cada tupla contiene el nombre del token y su expresión regular correspondiente.
  • Compilación de expresiones regulares: Se combinan todas las expresiones regulares en una sola expresión.
  • Función tokenize: Esta función toma el código fuente y genera una secuencia de tokens. Utiliza la expresión regular compilada para encontrar coincidencias en el código fuente.

  1. Implementación del Analizador Sintáctico (Parser)

El analizador sintáctico toma la secuencia de tokens generada por el lexer y construye un árbol de sintaxis abstracta (AST).

Ejemplo de Código para el Parser

class ASTNode:
    def __init__(self, type, value=None):
        self.type = type
        self.value = value
        self.children = []

    def add_child(self, node):
        self.children.append(node)

def parse(tokens):
    def parse_expression(index):
        token_type, token_value = tokens[index]
        if token_type == 'NUMBER':
            node = ASTNode('NUMBER', token_value)
            return node, index + 1
        elif token_type == 'ID':
            node = ASTNode('ID', token_value)
            return node, index + 1
        elif token_type == 'OP':
            node = ASTNode('OP', token_value)
            return node, index + 1
        else:
            raise SyntaxError(f'Token inesperado: {token_value}')

    def parse_statement(index):
        node = ASTNode('STATEMENT')
        left_node, index = parse_expression(index)
        node.add_child(left_node)
        token_type, token_value = tokens[index]
        if token_type == 'ASSIGN':
            assign_node = ASTNode('ASSIGN', token_value)
            node.add_child(assign_node)
            index += 1
            right_node, index = parse_expression(index)
            node.add_child(right_node)
        else:
            raise SyntaxError(f'Token inesperado: {token_value}')
        return node, index

    ast, index = parse_statement(0)
    return ast

# Ejemplo de uso
tokens = [('ID', 'x'), ('ASSIGN', ':='), ('NUMBER', '10'), ('OP', '+'), ('NUMBER', '20'), ('END', ';')]
ast = parse(tokens)
print(ast.type, [child.type for child in ast.children])

Explicación del Código

  • Clase ASTNode: Representa un nodo en el árbol de sintaxis abstracta. Cada nodo tiene un tipo, un valor opcional y una lista de hijos.
  • Función parse_expression: Analiza una expresión y devuelve un nodo del AST y el índice del siguiente token.
  • Función parse_statement: Analiza una sentencia y devuelve un nodo del AST y el índice del siguiente token.
  • Función parse: Inicia el análisis sintáctico y devuelve el AST completo.

  1. Generación de Código Intermedio

El código intermedio es una representación del programa que es más fácil de optimizar y traducir a código máquina.

Ejemplo de Código para la Generación de Código Intermedio

def generate_intermediate_code(ast):
    if ast.type == 'STATEMENT':
        left_code = generate_intermediate_code(ast.children[0])
        right_code = generate_intermediate_code(ast.children[2])
        return f'{left_code} := {right_code}'
    elif ast.type == 'NUMBER':
        return ast.value
    elif ast.type == 'ID':
        return ast.value
    elif ast.type == 'OP':
        left_code = generate_intermediate_code(ast.children[0])
        right_code = generate_intermediate_code(ast.children[1])
        return f'{left_code} {ast.value} {right_code}'

# Ejemplo de uso
intermediate_code = generate_intermediate_code(ast)
print(intermediate_code)

Explicación del Código

  • Función generate_intermediate_code: Toma el AST y genera una representación intermedia del código. La función es recursiva y maneja diferentes tipos de nodos del AST.

  1. Generación de Código Final

La generación de código final convierte el código intermedio en código máquina o bytecode que puede ser ejecutado por una máquina virtual o un procesador.

Ejemplo de Código para la Generación de Código Final

def generate_final_code(intermediate_code):
    # Este es un ejemplo simplificado que simplemente devuelve el código intermedio
    return intermediate_code

# Ejemplo de uso
final_code = generate_final_code(intermediate_code)
print(final_code)

Explicación del Código

  • Función generate_final_code: En este ejemplo simplificado, la función simplemente devuelve el código intermedio. En un compilador real, esta función convertiría el código intermedio en código máquina o bytecode.

Ejercicio Práctico

Ejercicio

Implementa un compilador simple para un subconjunto del lenguaje ALGOL que soporte asignaciones y operaciones aritméticas básicas. El compilador debe incluir las siguientes fases:

  1. Análisis Léxico
  2. Análisis Sintáctico
  3. Generación de Código Intermedio
  4. Generación de Código Final

Solución

# Implementación completa del compilador

# Análisis Léxico
import re

token_specification = [
    ('NUMBER',   r'\d+(\.\d*)?'),
    ('ASSIGN',   r':='),
    ('END',      r';'),
    ('ID',       r'[A-Za-z]+'),
    ('OP',       r'[+\-*/]'),
    ('NEWLINE',  r'\n'),
    ('SKIP',     r'[ \t]+'),
    ('MISMATCH', r'.'),
]

token_re = '|'.join('(?P<%s>%s)' % pair for pair in token_specification)
get_token = re.compile(token_re).match

def tokenize(code):
    line_num = 1
    line_start = 0
    mo = get_token(code)
    while mo is not None:
        kind = mo.lastgroup
        value = mo.group(kind)
        if kind == 'NEWLINE':
            line_start = mo.end()
            line_num += 1
        elif kind == 'SKIP':
            pass
        elif kind == 'MISMATCH':
            raise RuntimeError(f'{value!r} inesperado en la línea {line_num}')
        else:
            yield kind, value
        mo = get_token(code, mo.end())
    if mo is None:
        raise RuntimeError(f'Error de tokenización en la línea {line_num}')

# Análisis Sintáctico
class ASTNode:
    def __init__(self, type, value=None):
        self.type = type
        self.value = value
        self.children = []

    def add_child(self, node):
        self.children.append(node)

def parse(tokens):
    def parse_expression(index):
        token_type, token_value = tokens[index]
        if token_type == 'NUMBER':
            node = ASTNode('NUMBER', token_value)
            return node, index + 1
        elif token_type == 'ID':
            node = ASTNode('ID', token_value)
            return node, index + 1
        elif token_type == 'OP':
            node = ASTNode('OP', token_value)
            return node, index + 1
        else:
            raise SyntaxError(f'Token inesperado: {token_value}')

    def parse_statement(index):
        node = ASTNode('STATEMENT')
        left_node, index = parse_expression(index)
        node.add_child(left_node)
        token_type, token_value = tokens[index]
        if token_type == 'ASSIGN':
            assign_node = ASTNode('ASSIGN', token_value)
            node.add_child(assign_node)
            index += 1
            right_node, index = parse_expression(index)
            node.add_child(right_node)
        else:
            raise SyntaxError(f'Token inesperado: {token_value}')
        return node, index

    ast, index = parse_statement(0)
    return ast

# Generación de Código Intermedio
def generate_intermediate_code(ast):
    if ast.type == 'STATEMENT':
        left_code = generate_intermediate_code(ast.children[0])
        right_code = generate_intermediate_code(ast.children[2])
        return f'{left_code} := {right_code}'
    elif ast.type == 'NUMBER':
        return ast.value
    elif ast.type == 'ID':
        return ast.value
    elif ast.type == 'OP':
        left_code = generate_intermediate_code(ast.children[0])
        right_code = generate_intermediate_code(ast.children[1])
        return f'{left_code} {ast.value} {right_code}'

# Generación de Código Final
def generate_final_code(intermediate_code):
    return intermediate_code

# Ejemplo de uso
code = 'x := 10 + 20;'
tokens = list(tokenize(code))
ast = parse(tokens)
intermediate_code = generate_intermediate_code(ast)
final_code = generate_final_code(intermediate_code)
print(final_code)

Explicación del Ejercicio

  • Análisis Léxico: Se tokeniza el código fuente.
  • Análisis Sintáctico: Se construye el AST a partir de los tokens.
  • Generación de Código Intermedio: Se genera una representación intermedia del código.
  • Generación de Código Final: Se genera el código final a partir del código intermedio.

Conclusión

En este módulo, hemos construido un compilador simple para un subconjunto del lenguaje ALGOL. Hemos cubierto las fases principales de un compilador: análisis léxico, análisis sintáctico, generación de código intermedio y generación de código final. Este ejercicio te proporciona una base sólida para comprender cómo funcionan los compiladores y te prepara para explorar temas más avanzados en la compilación.

En el próximo módulo, aplicaremos estos conocimientos para implementar algoritmos más complejos y explorar estudios de caso y proyectos prácticos.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados