Analyseur LL(1) pour un Mini-Langage C

Ce projet implémente un analyseur syntaxique LL(1) pour une version simplifiée du langage C en Python. L'analyseur utilise un automate à pile avec une méthode descendante de type LL(1).

Grammaire

L'analyseur implémente la grammaire LL(1) suivante :

<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> <une_instruction> else <une_instruction> ;
<condition> ::= id <operateur> nombre
<operateur> ::= < | > | =

Remarque : id et nombre sont des terminaux (identifiants et nombres respectivement).

Vérification LL(1)

Cette grammaire est LL(1) car :

1. Pas de récursivité gauche : Toutes les productions sont récursives à droite ou non-récursives
2. Ensembles FIRST disjoints : Pour chaque non-terminal avec plusieurs productions, les ensembles FIRST ne se chevauchent pas
3. Lookahead déterministe : Chaque production peut être déterminée de manière unique par un seul jeton de lookahead

Ensembles FIRST et FOLLOW clés :

• FIRST(<type>) = {int, float}
• FIRST(<une_instruction>) = {id, if}
• FIRST(<operateur>) = {<, >, =}
• FOLLOW(<liste_declarations>) = {id, if, }}
• FOLLOW(<liste_instructions>) = {}}

Architecture

L'analyseur est composé de trois composants principaux :

1. Analyseur Lexical (classe Lexer)

• Tokenise la chaîne d'entrée en un flux de jetons
• Reconnaît les mots-clés (main, int, float, if, else)
• Identifie les symboles ((, ), {, }, =, ;, <, >)
• Extrait les identifiants et les nombres

2. Analyseur Syntaxique (classe LL1Parser)

• Implémente l'algorithme d'analyse LL(1) en utilisant un automate à pile
• Utilise une table d'analyse pour déterminer quelle production appliquer
• Maintient une pile pour l'analyse
• Retourne un arbre de dérivation (liste des règles de grammaire appliquées)

3. Programmes de Test

• Plusieurs programmes de test sont intégrés dans le code comme variables
• Facile d'ajouter de nouveaux programmes de test

Utilisation

Exécution de l'Analyseur

python3 ll1_parser.py

Ceci exécutera tous les programmes de test prédéfinis et affichera :

• Le flux de jetons
• L'arbre de dérivation (règles de grammaire appliquées)
• Le statut de succès/échec

Ajout de Nouveaux Programmes de Test

Pour tester un nouveau programme, ajoutez simplement une nouvelle variable dans la section de test :

# Votre nouveau programme de test
NOUVEAU_PROGRAMME_TEST = """
main() {
    int mavariable;
    mavariable = 42;
}
"""

# Ajoutez-le à la liste des tests
test_programs = [
    # ... tests existants ...
    ("Mon Nouveau Test", NOUVEAU_PROGRAMME_TEST),
]

Test d'un Programme Unique

Vous pouvez également utiliser l'analyseur de manière programmatique :

from ll1_parser import parse_program

programme = """
main() {
    int x;
    x = 10;
}
"""

succes, derivations = parse_program(programme)

Exemple de Sortie

Pour le programme d'entrée :

main() {
    int x;
    x = 10;
}

L'analyseur produit :

Jetons :

Token(MAIN, 'main')
Token(LPAREN, '(')
Token(RPAREN, ')')
Token(LBRACE, '{')
Token(INT, 'int')
Token(ID, 'x')
Token(SEMICOLON, ';')
Token(ID, 'x')
Token(ASSIGN, '=')
Token(NUMBER, '10')
Token(SEMICOLON, ';')
Token(RBRACE, '}')
Token(EOF, '$')

Arbre de Dérivation :

1. <Programme> -> main ( ) { <liste_declarations> <liste_instructions> }
2. <liste_declarations> -> <une_declaration> <liste_declarations>
3. <une_declaration> -> <type> id ;
4. <type> -> int
5. <liste_declarations> -> ε
6. <liste_instructions> -> <une_instruction> <liste_instructions>
7. <une_instruction> -> <affectation>
8. <affectation> -> id = nombre ;
9. <liste_instructions> -> ε

Cas de Test Inclus

1. Test 1 : Programme simple avec déclarations et affectations
2. Test 2 : Programme avec instruction if-else
3. Test 3 : Programme valide minimal (vide)
4. Test 4 : Programme avec seulement des déclarations
5. Test 5 : Programme avec instructions if-else imbriquées
6. Test 6 : Programme complexe avec plusieurs fonctionnalités

Règles de Grammaire

L'analyseur applique strictement la grammaire :

• Tous les programmes doivent commencer par main() { et se terminer par }
• Les déclarations doivent venir avant les instructions
• Toutes les instructions doivent se terminer par ;
• Les conditions dans if-else doivent comparer un identifiant avec un nombre (pas deux identifiants)
• Les instructions if-else doivent avoir les deux branches

Gestion des Erreurs

L'analyseur fournit des messages d'erreur clairs :

• Erreurs lexicales : Caractères inconnus ou jetons invalides
• Erreurs syntaxiques : Jetons inattendus, points-virgules manquants, etc.

Exemple d'erreur :

✗ Syntax error: Expected NUMBER, got ID at position 94

Détails d'Implémentation

• Code propre : Bien structuré avec docstrings et annotations de type
• Conception modulaire : Composants analyseur lexical et syntaxique séparés
• Facile à étendre : L'ajout de nouvelles règles de grammaire ou de cas de test est simple
• Sortie complète : Affiche à la fois le flux de jetons et l'arbre de dérivation pour le débogage

Auteur

Créé pour le projet du cours de Compilation.