ll1_parser.py

"""
Analyseur syntaxique LL(1) pour un mini-langage C

Grammaire du langage:
    <Programme> ::= main() {<liste_declarations><liste_instructions>}
    <liste_declarations> ::= <une_declaration><liste_declarations> | ε
    <une_declaration> ::= <type> id ;
    <liste_instructions> ::= <une_instruction><liste_instructions> | ε
    <une_instruction> ::= <affectation> | <test>
    <type> ::= int | float
    <affectation> ::= id = nombre ;
    <test> ::= if <condition> <instruction> else <instruction> ;
    <condition> ::= id <operateur> nombre
    <operateur> ::= < | > | =
"""

from enum import Enum
from dataclasses import dataclass


# Définition des types de jetons
class TokenType(Enum):
    MAIN = "main"
    LPAREN = "("
    RPAREN = ")"
    LBRACE = "{"
    RBRACE = "}"
    INT = "int"
    FLOAT = "float"
    IF = "if"
    ELSE = "else"
    ID = "id"
    NUMBER = "nombre"
    ASSIGN = "="
    SEMICOLON = ";"
    LT = "<"
    GT = ">"
    EQ = "="
    EOF = "$"


@dataclass
class Token:
    type: TokenType
    value: str
    position: int

    def __repr__(self):
        return f"Token({self.type.name}, '{self.value}')"


class Lexer:
    # Analyseur lexical
    def __init__(self, input_text):
        self.input = input_text
        self.position = 0
        self.tokens = []

    def tokenize(self):
        # Convertir le programme en jetons
        self.tokens = []
        self.position = 0

        while self.position < len(self.input):
            self._skip_whitespace()

            if self.position >= len(self.input):
                break

            # On essaie de matcher les différents types de jetons
            if self._match_keyword():
                continue
            elif self._match_identifier():
                continue
            elif self._match_number():
                continue
            elif self._match_symbol():
                continue
            else:
                raise SyntaxError(
                    f"Caractère inattendu à la position {self.position}: '{self.input[self.position]}'"
                )

        # Jeton de fin de fichier
        self.tokens.append(Token(TokenType.EOF, "$", self.position))
        return self.tokens

    def _skip_whitespace(self):
        # Ignorer les espaces
        while self.position < len(self.input) and self.input[self.position].isspace():
            self.position += 1

    def _match_keyword(self) -> bool:
        # Vérifier si c'est un mot-clé
        keywords = {
            "main": TokenType.MAIN,
            "int": TokenType.INT,
            "float": TokenType.FLOAT,
            "if": TokenType.IF,
            "else": TokenType.ELSE,
        }

        for keyword, token_type in keywords.items():
            if self.input[self.position :].startswith(keyword):
                # Vérifier que c'est pas juste le début d'un identifiant
                end_pos = self.position + len(keyword)
                if end_pos < len(self.input) and (
                    self.input[end_pos].isalnum() or self.input[end_pos] == "_"
                ):
                    return False

                self.tokens.append(Token(token_type, keyword, self.position))
                self.position += len(keyword)
                return True
        return False

    def _match_identifier(self):
        # Matcher un identifiant (variable)
        if not (
            self.input[self.position].isalpha() or self.input[self.position] == "_"
        ):
            return False

        start = self.position
        while self.position < len(self.input) and (
            self.input[self.position].isalnum() or self.input[self.position] == "_"
        ):
            self.position += 1

        value = self.input[start : self.position]
        self.tokens.append(Token(TokenType.ID, value, start))
        return True

    def _match_number(self):
        # Matcher un nombre
        if not self.input[self.position].isdigit():
            return False

        start = self.position
        while self.position < len(self.input) and (
            self.input[self.position].isdigit() or self.input[self.position] == "."
        ):
            self.position += 1

        value = self.input[start : self.position]
        self.tokens.append(Token(TokenType.NUMBER, value, start))
        return True

    def _match_symbol(self):
        # Matcher les symboles et opérateurs
        symbols = {
            "(": TokenType.LPAREN,
            ")": TokenType.RPAREN,
            "{": TokenType.LBRACE,
            "}": TokenType.RBRACE,
            "=": TokenType.ASSIGN,
            ";": TokenType.SEMICOLON,
            "<": TokenType.LT,
            ">": TokenType.GT,
        }

        char = self.input[self.position]
        if char in symbols:
            self.tokens.append(Token(symbols[char], char, self.position))
            self.position += 1
            return True
        return False


class LL1Parser:
    # Analyseur syntaxique LL(1) avec automate à pile

    # Les non-terminaux de la grammaire
    PROGRAMME = "<Programme>"
    LISTE_DECLARATIONS = "<liste_declarations>"
    UNE_DECLARATION = "<une_declaration>"
    LISTE_INSTRUCTIONS = "<liste_instructions>"
    UNE_INSTRUCTION = "<une_instruction>"
    TYPE = "<type>"
    AFFECTATION = "<affectation>"
    TEST = "<test>"
    CONDITION = "<condition>"
    OPERATEUR = "<operateur>"
    EPSILON = "ε"

    def __init__(self, tokens):
        self.tokens = tokens
        self.current = 0
        self.stack = []
        self.derivations = []  # pour stocker les règles appliquées

    def parse(self):
        # Méthode principale d'analyse LL(1)
        # On initialise la pile avec EOF et le symbole de départ
        self.stack = [TokenType.EOF, self.PROGRAMME]
        self.derivations = []
        self.current = 0

        while self.stack:
            top = self.stack.pop()
            current_token = self.tokens[self.current]

            # Si on a un terminal
            if isinstance(top, TokenType):
                if top == current_token.type:
                    if top != TokenType.EOF:
                        self.current += 1
                    continue
                else:
                    raise SyntaxError(
                        f"Attendu {top.name}, obtenu {current_token.type.name} à la position {current_token.position}"
                    )

            # Sinon c'est un non-terminal, on l'expanse
            elif isinstance(top, str) and top.startswith("<"):
                production = self._get_production(top, current_token)
                if production is None:
                    raise SyntaxError(
                        f"Aucune règle de production pour {top} avec lookahead {current_token.type.name}"
                    )

                self.derivations.append(
                    f"{top} -> {' '.join(str(p) for p in production)}"
                )

                # On empile la production en ordre inverse
                for symbol in reversed(production):
                    if symbol != self.EPSILON:
                        self.stack.append(symbol)

        return True, self.derivations

    def _get_production(self, non_terminal, lookahead):
        # Table d'analyse LL(1)
        # Retourne la production à appliquer selon le non-terminal et le lookahead

        if non_terminal == self.PROGRAMME:
            if lookahead.type == TokenType.MAIN:
                return [
                    TokenType.MAIN,
                    TokenType.LPAREN,
                    TokenType.RPAREN,
                    TokenType.LBRACE,
                    self.LISTE_DECLARATIONS,
                    self.LISTE_INSTRUCTIONS,
                    TokenType.RBRACE,
                ]

        elif non_terminal == self.LISTE_DECLARATIONS:
            if lookahead.type in [TokenType.INT, TokenType.FLOAT]:
                return [self.UNE_DECLARATION, self.LISTE_DECLARATIONS]
            elif lookahead.type in [TokenType.ID, TokenType.IF, TokenType.RBRACE]:
                return [self.EPSILON]

        elif non_terminal == self.UNE_DECLARATION:
            if lookahead.type in [TokenType.INT, TokenType.FLOAT]:
                return [self.TYPE, TokenType.ID, TokenType.SEMICOLON]

        elif non_terminal == self.LISTE_INSTRUCTIONS:
            if lookahead.type in [TokenType.ID, TokenType.IF]:
                return [self.UNE_INSTRUCTION, self.LISTE_INSTRUCTIONS]
            elif lookahead.type == TokenType.RBRACE:
                return [self.EPSILON]

        elif non_terminal == self.UNE_INSTRUCTION:
            if lookahead.type == TokenType.ID:
                return [self.AFFECTATION]
            elif lookahead.type == TokenType.IF:
                return [self.TEST]

        elif non_terminal == self.TYPE:
            if lookahead.type == TokenType.INT:
                return [TokenType.INT]
            elif lookahead.type == TokenType.FLOAT:
                return [TokenType.FLOAT]

        elif non_terminal == self.AFFECTATION:
            if lookahead.type == TokenType.ID:
                return [
                    TokenType.ID,
                    TokenType.ASSIGN,
                    TokenType.NUMBER,
                    TokenType.SEMICOLON,
                ]

        elif non_terminal == self.TEST:
            if lookahead.type == TokenType.IF:
                return [
                    TokenType.IF,
                    self.CONDITION,
                    self.UNE_INSTRUCTION,
                    TokenType.ELSE,
                    self.UNE_INSTRUCTION,
                    TokenType.SEMICOLON,
                ]

        elif non_terminal == self.CONDITION:
            if lookahead.type == TokenType.ID:
                return [TokenType.ID, self.OPERATEUR, TokenType.NUMBER]

        elif non_terminal == self.OPERATEUR:
            if lookahead.type == TokenType.LT:
                return [TokenType.LT]
            elif lookahead.type == TokenType.GT:
                return [TokenType.GT]
            elif lookahead.type == TokenType.ASSIGN:
                return [TokenType.ASSIGN]

        return None


def parse_program(program):
    # Fonction pour analyser un programme complet
    print("\n" + "=" * 60)
    print("Analyse du programme:")
    print("=" * 60)
    print(program)
    print(f"{'=' * 60}\n")

    try:
        # Analyse lexicale
        lexer = Lexer(program)
        tokens = lexer.tokenize()

        print("Jetons:")
        for token in tokens:
            print(f"  {token}")
        print()

        # Maintenant l'analyse syntaxique
        parser = LL1Parser(tokens)
        success, derivations = parser.parse()

        print("Arbre de dérivation (règles de grammaire appliquées):")
        for i, derivation in enumerate(derivations, 1):
            print(f"  {i}. {derivation}")

        print("\n✓ Analyse réussie!\n")
        return True, derivations

    except SyntaxError as e:
        print(f"\n✗ Erreur de syntaxe: {e}\n")
        return False, []


# ==================================================
# Programmes de test
# ==================================================

# Test 1: Programme simple avec déclarations et affectations
TEST_PROGRAM_1 = """
main() {
    int x;
    float y;
    x = 10;
    y = 3.14;
}
"""

# Test 2: Programme avec instruction if-else
TEST_PROGRAM_2 = """
main() {
    int a;
    a = 5;
    if a > 3 x = 1; else x = 0;;
}
"""

# Test 3: Programme valide minimal
TEST_PROGRAM_3 = """
main() {
}
"""

# Test 4: Programme avec seulement des déclarations
TEST_PROGRAM_4 = """
main() {
    int x;
    int y;
    float z;
}
"""

# Test 5: Programme avec if-else imbriqués
TEST_PROGRAM_5 = """
main() {
    int x;
    x = 10;
    if x < 5 y = 1; else if x > 8 y = 2; else y = 3;;;
}
"""

# Test 6: Programme complexe
TEST_PROGRAM_6 = """
main() {
    int a;
    int b;
    float c;
    a = 10;
    b = 20;
    c = 3.14;
    if a < b c = 1.0; else c = 2.0;;
}
"""


if __name__ == "__main__":
    # Lancer tous les tests
    test_programs = [
        ("Test 1: Simple program", TEST_PROGRAM_1),
        ("Test 2: If-else statement", TEST_PROGRAM_2),
        ("Test 3: Minimal program", TEST_PROGRAM_3),
        ("Test 4: Only declarations", TEST_PROGRAM_4),
        ("Test 5: Nested if-else", TEST_PROGRAM_5),
        ("Test 6: Complex program", TEST_PROGRAM_6),
    ]

    results = []
    for name, program in test_programs:
        print("\n" + "#" * 60)
        print(f"# {name}")
        print("#" * 60)
        success, derivations = parse_program(program)
        results.append((name, success))

    # Résumé
    print("\n" + "=" * 60)
    print("RÉSUMÉ")
    print("=" * 60)
    for name, success in results:
        status = "✓ RÉUSSI" if success else "✗ ÉCHOUÉ"
        print(f"{status} - {name}")
    print("=" * 60 + "\n")