Arbre de syntaxe abstraite (AST)

Actuellement, notre compilateur est capable de vérifier la syntaxe d’une grammaire EBNF, mais il ne produit rien.

Premières phases d'un compilateur

Le but d’un compilateur est de transformer un programme écrit dans un langage source en un programme équivalent dans un langage cible. Traditionnellement, les compilateurs de Niklaus Wirth génèrent le code au fur et à mesure de l’analyse syntaxique. Cela signifie que le code est généré directement à partir des règles de la grammaire. Cette approche rend le compilateur très rapide et très économe en mémoire. Cependant, elle peut rendre le compilateur plus difficile à maintenir et à étendre.

Les ordinateurs actuels sont suffisamment puissants pour permettre une approche plus flexible. Au lieu de générer directement le code, le compilateur construit une représentation intermédiaire du programme sous la forme d’un arbre de syntaxe abstraite (AST pour Abstract Syntax Tree).

Phases d'un compilateur

Pour l’arbre de syntaxe abstraite de l’EBNF, nous pouvons définir les classes suivantes :

classDiagram

    class Option {
        expr: Expression
    }

    class Literal {
        value: str
    }

    class Expression {
        terms: list[Term]
        paren: bool = False
    }

    class Identifier {
        value: str
    }

    class Syntax {
        production: list[Production]
    }

    class Node {
    }

    class Repetition {
        expr: Expression
    }

    class Production {
        identifier: Identifier
        expression: Expression
    }

    class Term {
        factors: list[Factor]
    }

    class Factor {
    }

    Term ..> Factor
    Expression ..> Term
    Option ..> Expression
    Repetition ..> Expression
    Production ..> Expression
    Production ..> Identifier
    Syntax ..> Production

    Node <|-- Production
    Node <|-- Syntax
    Node <|-- Term
    Node <|-- Factor
    Factor <|-- Option
    Factor <|-- Literal
    Factor <|-- Expression
    Factor <|-- Identifier
    Factor <|-- Repetition

Nous implémentons ces classes dans le fichier ebnf_compiler/ast.py à l’aide de la bibliothèque standard dataclasses:

ebnf_compiler/ast.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: Apache-2.0 OR MIT

"""
EBNF Abstract Syntax Tree
"""

from dataclasses import dataclass


@dataclass
class Node:
    pass


@dataclass
class Factor(Node):
    pass


@dataclass
class Term(Node):
    factors: list[Factor]


@dataclass
class Identifier(Factor):
    value: str


@dataclass
class Literal(Factor):
    value: str


@dataclass
class Expression(Factor):
    terms: list[Term]
    paren: bool = False


@dataclass
class Option(Factor):
    expr: Expression


@dataclass
class Repetition(Factor):
    expr: Expression


@dataclass
class Production(Node):
    identifier: Identifier
    expression: Expression


@dataclass
class Syntax(Node):
    production: list[Production]

À faire

  • Modifiez le parser pour qu’il construise et retourne un AST.
  • Vous pouvez afficher l’AST à l’aide de la bibliothèque rich pour le rendre plus lisible. Par exemple, vous pouvez utiliser la classe Pretty de rich pour afficher l’AST de manière structurée.

Ajoutez une méthode rich à chaque classe de l’AST pour sérialiser l’AST de manière lisible. Utilisez la bibliothèque rich pour colorer les différentes parties de l’AST.

Par exemple, la classe Production pourrait être modifiée comme suit :

ebnf_compiler/ast.py
@dataclass
class Production(Node):
    identifier: Identifier
    expression: Expression

    def rich(self) -> str:
        return (
            f"[yellow]{self.identifier.rich()}[/yellow] [cyan]=[/cyan] "
            f"{self.expression.rich()}[cyan].[/cyan]"
        )

À faire

Modifiez le compilateur pour qu’il affiche l’AST après l’analyse syntaxique.

Testez avec le cli suivant :

ebnf_compiler/__init____.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
@app.command(context_settings={"ignore_unknown_options": True})
def main(
    source: Annotated[Path, typer.Argument()],
    debug: bool = False,
    show_tree: bool = False,
):

    logger.remove()
    if debug:
        logger.add(sys.stdout, level="DEBUG")
    else:
        logger.add(sys.stdout, level="INFO")

    scanner = Scanner()
    scanner.open(source)
    parser = Parser(scanner=scanner)

    compiler = Compiler(scanner=scanner, parser=parser)
    ast_ = compiler.ast()

    if ast_ is None:
        console.print("[red]Compilation failed[/red]")
        return
    elif show_tree:
        console.print(Panel(Pretty(ast_, indent_size=2), title="Syntax Tree"))
    else:
        console.print(Panel(ast_.rich(), title="Code"))

Nous pouvons maintenant faire des opérations sur cet AST.

À faire

Modifiez votre compilateur pour qu’il analyse l’AST et en fasse l’inventaire de tous les symboles terminaux et non terminaux de la grammaire. Votre programme de doit pas avoir besoin de modifier les classes de l’AST pour faire cela. Testez avec plusieurs grammaires EBNF.

Avec la grammaire d’Oberon0, vous devriez trouver les symboles suivants :

Terminal Symbols
- digit
- letter

Non-terminal Symbols
- ActualParameters
- ArrayType
- assignment
- declarations
- expression
- factor
- FormalParameters
- FPSection
- ident
- IdentList
- IfStatement
- integer
- module
- number
- ProcedureBody
- ProcedureCall
- ProcedureDeclaration
- ProcedureHeading
- RepeatStatement
- selector
- SimpleExpression
- statement
- StatementSequence
- term
- type
- WhileStatement

Faites un dépôt dans le Gitlab de l’école avec votre code. Ajoutez les fichiers de CI/CD pour que votre code soit automatiquement testé et analysé à chaque commit.

Étudiez le dépôt https://gitlab.forge.hefr.ch/coco/ebnf-compiler. Il contient une implémentation complète d’un compilateur pour l’EBNF. Vous pouvez vous en inspirer pour votre propre implémentation.

Étudiez plus précisément l’utilisation des outils suivants: