El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

En aquest tema, aprendrem a construir un compilador simple per a un subconjunt del llenguatge ALGOL. Aquest procés ens ajudarà a entendre millor com funcionen els compiladors i ens proporcionarà una base sòlida per a projectes més complexos en el futur.

Objectius del Tema

Comprendre els components bàsics d'un compilador.
Aprendre a analitzar sintàcticament un codi font.
Generar codi intermedi.
Implementar un compilador simple per a ALGOL.

Components d'un Compilador

Un compilador típic es compon de diverses fases, cadascuna amb una funció específica:

Anàlisi Lèxica (Lexer): Converteix el codi font en una seqüència de tokens.
Anàlisi Sintàctica (Parser): Construeix un arbre sintàctic a partir dels tokens.
Anàlisi Semàntica: Verifica la correcció semàntica de l'arbre sintàctic.
Generació de Codi Intermedi: Converteix l'arbre sintàctic en una representació intermèdia.
Optimització de Codi: Millora el codi intermedi per a una execució més eficient.
Generació de Codi Final: Converteix el codi intermedi en codi màquina o bytecode.

Anàlisi Lèxica

L'anàlisi lèxica és el primer pas en la construcció d'un compilador. El lexer llegeix el codi font i el divideix en tokens, que són les unitats lèxiques bàsiques del llenguatge.

Exemple de Lexer en Pseudocodi

function lexer(input):
    tokens = []
    i = 0
    while i < length(input):
        if is_whitespace(input[i]):
            i = i + 1
        else if is_digit(input[i]):
            num = ""
            while i < length(input) and is_digit(input[i]):
                num = num + input[i]
                i = i + 1
            tokens.append(Token("NUMBER", num))
        else if is_letter(input[i]):
            ident = ""
            while i < length(input) and is_letter(input[i]):
                ident = ident + input[i]
                i = i + 1
            tokens.append(Token("IDENTIFIER", ident))
        else:
            tokens.append(Token("SYMBOL", input[i]))
            i = i + 1
    return tokens

Exercici Pràctic

Implementa un lexer per a ALGOL que reconegui números, identificadors i símbols.

class Token:
    def __init__(self, type, value):
        self.type = type
        self.value = value

def lexer(input):
    tokens = []
    i = 0
    while i < len(input):
        if input[i].isspace():
            i += 1
        elif input[i].isdigit():
            num = ""
            while i < len(input) and input[i].isdigit():
                num += input[i]
                i += 1
            tokens.append(Token("NUMBER", num))
        elif input[i].isalpha():
            ident = ""
            while i < len(input) and input[i].isalpha():
                ident += input[i]
                i += 1
            tokens.append(Token("IDENTIFIER", ident))
        else:
            tokens.append(Token("SYMBOL", input[i]))
            i += 1
    return tokens

# Prova del lexer
input_code = "x = 10 + 20"
tokens = lexer(input_code)
for token in tokens:
    print(f"Type: {token.type}, Value: {token.value}")

Anàlisi Sintàctica

L'anàlisi sintàctica pren els tokens generats pel lexer i construeix un arbre sintàctic que representa l'estructura del programa.

Exemple de Parser en Pseudocodi

function parser(tokens):
    def parse_expression():
        token = tokens.pop(0)
        if token.type == "NUMBER":
            return NumberNode(token.value)
        elif token.type == "IDENTIFIER":
            return IdentifierNode(token.value)
        elif token.type == "SYMBOL" and token.value == "(":
            expr = parse_expression()
            match(")")
            return expr
        else:
            raise SyntaxError("Unexpected token: " + token.value)

    def match(expected):
        token = tokens.pop(0)
        if token.value != expected:
            raise SyntaxError("Expected " + expected + " but got " + token.value)

    return parse_expression()

Exercici Pràctic

Implementa un parser per a expressions aritmètiques simples en ALGOL.

class Node:
    pass

class NumberNode(Node):
    def __init__(self, value):
        self.value = value

class IdentifierNode(Node):
    def __init__(self, value):
        self.value = value

def parser(tokens):
    def parse_expression():
        token = tokens.pop(0)
        if token.type == "NUMBER":
            return NumberNode(token.value)
        elif token.type == "IDENTIFIER":
            return IdentifierNode(token.value)
        elif token.type == "SYMBOL" and token.value == "(":
            expr = parse_expression()
            match(")")
            return expr
        else:
            raise SyntaxError("Unexpected token: " + token.value)

    def match(expected):
        token = tokens.pop(0)
        if token.value != expected:
            raise SyntaxError("Expected " + expected + " but got " + token.value)

    return parse_expression()

# Prova del parser
tokens = lexer("x = 10 + 20")
ast = parser(tokens)
print(ast)

Generació de Codi Intermedi

La generació de codi intermedi converteix l'arbre sintàctic en una representació intermèdia que és més fàcil d'optimitzar i traduir a codi màquina.

Exemple de Generació de Codi Intermedi en Pseudocodi

function generate_code(node):
    if node is NumberNode:
        return "PUSH " + node.value
    elif node is IdentifierNode:
        return "LOAD " + node.value
    else:
        raise ValueError("Unknown node type: " + type(node))

Exercici Pràctic

Implementa la generació de codi intermedi per a expressions aritmètiques simples.

def generate_code(node):
    if isinstance(node, NumberNode):
        return f"PUSH {node.value}"
    elif isinstance(node, IdentifierNode):
        return f"LOAD {node.value}"
    else:
        raise ValueError("Unknown node type: " + type(node))

# Prova de la generació de codi intermedi
code = generate_code(ast)
print(code)

Resum

En aquest tema, hem après els components bàsics d'un compilador i hem implementat un lexer, un parser i un generador de codi intermedi per a un subconjunt simple d'ALGOL. Aquestes eines ens proporcionen una base sòlida per a la construcció de compiladors més complexos en el futur.

Exercicis Addicionals

Extensió del Lexer: Modifica el lexer per reconèixer operadors aritmètics (+, -, *, /) i parèntesis.
Extensió del Parser: Modifica el parser per manejar operacions aritmètiques i expressions amb parèntesis.
Generació de Codi Final: Implementa una fase de generació de codi final que converteixi el codi intermedi en codi màquina o bytecode.

Solucions als Exercicis

Extensió del Lexer

def lexer(input):
    tokens = []
    i = 0
    while i < len(input):
        if input[i].isspace():
            i += 1
        elif input[i].isdigit():
            num = ""
            while i < len(input) and input[i].isdigit():
                num += input[i]
                i += 1
            tokens.append(Token("NUMBER", num))
        elif input[i].isalpha():
            ident = ""
            while i < len(input) and input[i].isalpha():
                ident += input[i]
                i += 1
            tokens.append(Token("IDENTIFIER", ident))
        elif input[i] in "+-*/()":
            tokens.append(Token("SYMBOL", input[i]))
            i += 1
        else:
            raise ValueError("Unknown character: " + input[i])
    return tokens

Extensió del Parser

class BinaryOpNode(Node):
    def __init__(self, left, op, right):
        self.left = left
        self.op = op
        self.right = right

def parser(tokens):
    def parse_expression():
        left = parse_term()
        while tokens and tokens[0].value in "+-":
            op = tokens.pop(0).value
            right = parse_term()
            left = BinaryOpNode(left, op, right)
        return left

    def parse_term():
        left = parse_factor()
        while tokens and tokens[0].value in "*/":
            op = tokens.pop(0).value
            right = parse_factor()
            left = BinaryOpNode(left, op, right)
        return left

    def parse_factor():
        token = tokens.pop(0)
        if token.type == "NUMBER":
            return NumberNode(token.value)
        elif token.type == "IDENTIFIER":
            return IdentifierNode(token.value)
        elif token.type == "SYMBOL" and token.value == "(":
            expr = parse_expression()
            match(")")
            return expr
        else:
            raise SyntaxError("Unexpected token: " + token.value)

    def match(expected):
        token = tokens.pop(0)
        if token.value != expected:
            raise SyntaxError("Expected " + expected + " but got " + token.value)

    return parse_expression()

Generació de Codi Final

def generate_code(node):
    if isinstance(node, NumberNode):
        return f"PUSH {node.value}"
    elif isinstance(node, IdentifierNode):
        return f"LOAD {node.value}"
    elif isinstance(node, BinaryOpNode):
        left_code = generate_code(node.left)
        right_code = generate_code(node.right)
        return f"{left_code}\n{right_code}\n{node.op.upper()}"
    else:
        raise ValueError("Unknown node type: " + type(node))

# Prova de la generació de codi final
tokens = lexer("x = 10 + 20 * (30 - 40)")
ast = parser(tokens)
code = generate_code(ast)
print(code)

Amb aquests exercicis i solucions, hauríeu de tenir una comprensió sòlida de com construir un compilador simple per a ALGOL.

Construcció d'un Compilador Simple

Objectius del Tema

Components d'un Compilador

Anàlisi Lèxica

Exemple de Lexer en Pseudocodi

Exercici Pràctic

Anàlisi Sintàctica

Exemple de Parser en Pseudocodi

Exercici Pràctic

Generació de Codi Intermedi

Exemple de Generació de Codi Intermedi en Pseudocodi

Exercici Pràctic

Resum

Exercicis Addicionals

Solucions als Exercicis

Extensió del Lexer

Extensió del Parser

Generació de Codi Final

Curs de Programació en ALGOL

Mòdul 1: Introducció a ALGOL

Mòdul 2: Sintaxi i Estructura Bàsica

Mòdul 3: Estructures de Control

Mòdul 4: Funcions i Procediments

Mòdul 5: Estructures de Dades

Mòdul 6: Temes Avançats

Mòdul 7: Aplicacions Pràctiques

Mòdul 8: Lectures i Recursos Addicionals