TP01 : Un Parser pour l’EBNF

Pour illustrer la technique de l’analyse récursive, considérons un parseur pour l’EBNF, dont la syntaxe est à nouveau résumée ici.

syntax = {production}.
production = identifier "=" expression "." .
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string |
         "(" expression ")" | "[" expression "]" | "{" expression "}".

Pour ce cours, nous écrirons notre compilateur en Python et nous appliquerons les bonnes pratiques de développement logiciel avec cet environnement.

Installation de Python

Nous programmerons notre compilateur en Python. Si ce n’est pas encore fait, installez Python sur votre machine.

Nous appliquerons aussi les bonnes pratiques et, pour cela, nous utiliserons les outils suivants :

• Uv pour gérer les dépendances de notre projet
• Ruff pour l’analyse statique du code
• Pyright et Mypy pour l’analyse de type statique
• pytest pour les tests unitaires
• Sphinx pour la documentation
• Black pour le formatage du code
• Reuse pour vérifier la conformité de votre projet avec les licences open source

Pour le code, nous appliquerons les principes des pythonistas, nous suivrons les recommandations de la PEP8 et nous utiliserons les outils suivants :

• Typer pour la gestion des commandes
• Rich pour l’affichage des résultats
• Dataclasses pour la gestion des données
• Loguru pour la gestion des logs

Vous pouvez installer ces outils sur votre machine ou utiliser le devcontainer fourni.

Configuration de l’environnement de développement

Commencez par créer un nouvreau dossier pour votre projet (par exemple ebnf-compiler) et ouvrez ce dossier dans votre éditeur de code préféré (par exemple, Visual Studio Code).

Installation “native”

Si vous choisissez une installation native (sans passer par un devcontainer), Assurez-vous d’avoir les outils suivants installés sur votre machine :

• Python 3.10 ou supérieur (https://www.python.org/)
• Uv (https://docs.astral.sh/uv/)

Installation avec devcontainer

Si vous préférez utiliser un devcontainer, vous pouvez installer la commande devcontainer et taper la commande suivante dans votre terminal :

devcontainer templates apply --workspace-folder . \
  --template-id ghcr.io/heia-fr/cc-devcontainer/coco:latest

Cette commande crée la structure suivante :

.
├── .devcontainer
└── .zshrc

Création du projet

Dans le dossier créé précédemment, initialisez un nouveau projet Python avec la commande uv init.

Cette commande crée la structure suivante :

.
├── .git
├── .gitignore
├── .python-version
├── main.py
├── pyproject.toml
└── README.md

Editez le fichier pyproject.toml pour ajouter une description à votre projet et pour ajouter une licence (par exemple, MIT):

pyproject.toml

[project]
name = "ebnf-compiler"
version = "0.1.0"
description = "EBNF Compiler: A tool for parsing and compiling EBNF grammars."
readme = "README.md"
requires-python = ">=3.12"
license = "MIT"
dependencies = []

Ajoutez les dépendances que nous allons utiliser pour notre projet :

uv add typer loguru rich
uv add --dev black ruff pyright pre-commit reuse

Implémentation du compilateur

Crez maintenant un dossier pour votre package. Nous vous recommandons d’utiliser le dossier src/ebnf_compiler pour votre code source, mais vous pouvez choisir un autre nom si vous le souhaitez.

Ajoutez le fichiers suivants à votre projet :

src/ebnf_compiler/tokens.py

# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: Apache-2.0 OR MIT

"""
EBNF Tokens
"""

from enum import Enum, auto


class Token(Enum):
    IDENT = auto()
    LITERAL = auto()
    LPAREN = auto()
    LBRAK = auto()
    LBRACE = auto()
    BAR = auto()
    EQL = auto()
    RPAREN = auto()
    RBRAK = auto()
    RBRACE = auto()
    PERIOD = auto()
    OTHER = auto()
    EOF = auto()

Ce fichier contient les tokens que nous allons utiliser pour notre scanner.

Note

Étudiez l’utilisation de Enum pour déclarer les tokens en Python.

Ajoutez maintenant un scanner pour analyser les fichiers EBNF. Voici une proposition de code pour la classe Scanner :

src/ebnf_compiler/scanner.py

# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: Apache-2.0 OR MIT

"""
EBNF Scanner
"""

import typing
from dataclasses import dataclass
from pathlib import Path

import typer
from loguru import logger
from rich import print
from rich.console import Console

from .tokens import Token

console = Console()


@dataclass
class Scanner:
    eof: bool = False
    sym: Token | None = None  # Next Symbol
    value: str = ""

    _ch: str = ""
    _file_name: Path | None = None
    _text: typing.TextIO | None = None
    _text_line: str = ""
    _line_no: int = 0
    _col_no: int = 0

    token_map: typing.ClassVar[dict[str, Token]] = {
        "=": Token.EQL,
        "(": Token.LPAREN,
        ")": Token.RPAREN,
        "[": Token.LBRAK,
        "]": Token.RBRAK,
        "{": Token.LBRACE,
        "}": Token.RBRACE,
        "|": Token.BAR,
        ".": Token.PERIOD,
    }

    def init(self, f: typing.TextIO) -> None:
        self._text = f
        self.get_next_char()

    def open(self, file_name: Path) -> None:
        logger.debug(f"Opening {file_name}")
        self._file_name = file_name
        try:
            f = self._file_name.open("r")
            self.init(f)
        except Exception:
            print(f"[bold red]Error: Source file '{file_name}' not found[/bold red]")
            raise typer.Exit(code=1) from None

    def print_error(self, msg: str):
        console.print(
            f"Error: {msg}"
            f"(File {self._file_name}, Line {self._line_no}, Column {self._col_no})"
        )

    def skip_space(self) -> None:
        while self._ch.isspace():
            self.get_next_char()

    def get_next_char(self) -> None:
        if self._text is None:
            raise Exception("Scanner not initialized")
        while not self.eof and self._text_line == "":
            self._text_line = self._text.readline()
            self._line_no += 1
            self._col_no = 0
            if self._text_line == "":
                self.eof = True
                break
            self._text_line = self._text_line.rstrip()
        if self.eof:
            self._ch = ""
        else:
            assert self._text_line != ""
            self._ch = self._text_line[0]
            self._text_line = self._text_line[1:]
            self._col_no += 1

    def get_next_symbol(self):
        self.skip_space()
        if self._ch.isalpha():
            self.sym = Token.IDENT
            self.value = self._ch
            self.get_next_char()
            while self._ch.isalpha():
                self.value += self._ch
                self.get_next_char()

        elif self._ch == '"':
            self.sym = Token.LITERAL
            self.value = ""
            self.get_next_char()
            while not self.eof and self._ch != '"':
                self.value += self._ch
                self.get_next_char()
            if self.eof:
                self.print_error("Unterminated literal")
                return
            self.get_next_char()
        elif self._ch == "":
            self.sym = Token.EOF
            self.value = ""
        elif self._ch in self.token_map:
            self.sym = self.token_map[self._ch]
            self.value = self._ch
            self.get_next_char()
        else:
            self.sym = Token.OTHER
            self.value = self._ch
            self.get_next_char()
        logger.info(f"Token: {self.sym}, Value: {self.value}")

Note

Étudiez l’utilisation de dataclass pour déclarer la classe Scanner et l’utilisation de loguru pour gérer les logs. Le module rich est utilisé pour afficher les résultats de manière plus agréable.

Typer sera expliqué plus tard. Ici il est juste utilisé pour quitter le programme en cas d’erreur.

Ajoutez le parser :

src/ebnf_compiler/parser.py

# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: Apache-2.0 OR MIT

"""
EBNF Parser
"""

from dataclasses import dataclass

from loguru import logger

from .scanner import Scanner
from .tokens import Token


@dataclass
class Parser:
    scanner: Scanner
    has_error: bool = False

    def raise_error(self, msg: str) -> None:
        self.has_error = True
        self.scanner.print_error(msg)
        raise Exception(msg)

    def raise_expected_error(self, expected: Token):
        self.raise_error(f"Expected '{expected}', but got '{self.scanner.sym}'")

    def factor(self) -> None:
        logger.debug("Factor")
        sym = self.scanner.sym
        if sym == Token.IDENT:
            self.scanner.get_next_symbol()
        elif sym == Token.LITERAL:
            self.scanner.get_next_symbol()
        elif sym == Token.LPAREN:
            self.scanner.get_next_symbol()
            self.expression()
            if self.scanner.sym != Token.RPAREN:
                self.raise_expected_error(Token.RPAREN)
            self.scanner.get_next_symbol()
        elif sym == Token.LBRAK:
            self.scanner.get_next_symbol()
            self.expression()
            if self.scanner.sym != Token.RBRAK:
                self.raise_expected_error(Token.RBRAK)
            self.scanner.get_next_symbol()
        elif sym == Token.LBRACE:
            self.scanner.get_next_symbol()
            self.expression()
            if self.scanner.sym != Token.RBRACE:
                self.raise_expected_error(Token.RBRACE)
            self.scanner.get_next_symbol()
        else:
            self.raise_error(
                f"Expected identifier, literal, (', '['. or '{{' got {sym}"
            )
            raise Exception("Unexpected symbol")

    def term(self) -> None:
        logger.debug("Term")
        self.factor()

        while self.scanner.sym in (
            Token.IDENT,
            Token.LITERAL,
            Token.LPAREN,
            Token.LBRAK,
            Token.LBRACE,
        ):
            self.factor()

    def expression(self) -> None:
        logger.debug("Expression")
        self.term()
        while self.scanner.sym == Token.BAR:
            self.scanner.get_next_symbol()
            self.term()

    def production(self) -> None:
        logger.debug("Production")
        if self.scanner.sym != Token.IDENT:
            self.raise_expected_error(Token.IDENT)
        self.scanner.get_next_symbol()
        if self.scanner.sym != Token.EQL:
            self.raise_expected_error(Token.EQL)
        self.scanner.get_next_symbol()
        self.expression()
        if self.scanner.sym != Token.PERIOD:
            self.raise_expected_error(Token.PERIOD)
        self.scanner.get_next_symbol()

    def syntax(self) -> None:
        logger.debug("Syntax")
        while self.scanner.sym != Token.EOF:
            if self.scanner.sym != Token.IDENT:
                self.raise_expected_error(Token.IDENT)
            self.production()

    def parse(self) -> None:
        logger.debug("Parsing")
        self.scanner.get_next_symbol()
        self.syntax()

Note

Étudiez la méthode de recursive descent parsing utilisée dans le parser.

Terminez l’implémentation du parser en ajoutant le fichier __init__.py :

src/ebnf_compiler/__init__.py

# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: Apache-2.0 OR MIT

"""
EBNF Compiler
"""

import sys
from dataclasses import dataclass
from pathlib import Path
from typing import Annotated

import typer
from loguru import logger
from rich.console import Console

from .parser import Parser
from .scanner import Scanner

console = Console()
app = typer.Typer()


@dataclass
class Compiler:
    scanner: Scanner
    parser: Parser

    def compile(self) -> None:
        try:
            self.parser.parse()
        except Exception as e:
            print(f"{e}")


@app.command()
def main(
    source: Annotated[Path, typer.Argument()],
    debug: bool = False,
) -> None:

    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)
    compiler.compile()


if __name__ == "__main__":
    app()

Note

Étudiez l’utilisation de Typer pour gérer les commandes de votre programme.’

Nous sommes maintenant (presque) prêts à analyser un fichier EBNF.

Éditez le fichier pyproject.toml pour ajouter les lignes suivantes :

pyproject.toml

[build-system]
requires = ["uv_build>=0.10.1,<0.11.0"]
build-backend = "uv_build"

[tool.pyright]
venvPath = "."
venv = ".venv"

[project.scripts]
ebnf-compiler = "ebnf_compiler:app"

Créez un dossier examples à la racine de votre projet et ajoutez un fichier basic.ebnf avec le contenu suivant :

examples/basic.ebnf

ident = letter { letter | digit }.
number = digit { digit }.
digit = "0" | "1" | "2" | "3".

Mettez à jour votre environnement virtuel de python:

uv sync

Testez votre compilateur avec la commande suivante :

uv run ebnf-compiler examples/basic.ebnf

Vous pouvez aussi ajouter l’option --debug pour afficher plus de logs de votre programme :

uv run ebnf-compiler --debug examples/basic.ebnf

Tests unitaires

Comme pour tous les projets logiciels, il est important d’écrire des tests unitaires pour votre code.

Ahoutez les dépendances nécessaires pour les tests unitaires :

uv add --dev pytest

Créez un dossier tests à la racine de votre projet et ajoutez un fichier test_simple.py avec le contenu suivant :

tests/test_simple.py

import io
import sys

from loguru import logger

from ebnf_compiler.parser import Parser
from ebnf_compiler.scanner import Scanner

SRC = """
syntax = {production}.
production = identifier "=" expression "." .
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".
"""


def test_simple():
    logger.remove()
    logger.add(sys.stdout, level="INFO")

    scanner = Scanner()
    source = io.StringIO(SRC)
    scanner.init(source)
    parser = Parser(scanner=scanner)

    parser.parse()

Testez maintenant avec la commande suivante :

uv run pytest

Documentation

Tout comme les tests unitaires, il est important d’écrire une bonne documentation pour votre projet.

Ajoutez les dépendances nécessaires pour la documentation :

uv add --dev sphinx sphinx_design furo

créez un dossier docs à la racine de votre projet et dans ce dossier, exécutez la commande suivante pour initialiser la documentation :

cd docs
uv run sphinx-quickstart

Remplacez le contenu du fichier docs/conf.py par le contenu suivant :

docs/conf.py

# Configuration file for the Sphinx documentation builder.
#
# For the full list of built-in configuration values, see the documentation:
# https://www.sphinx-doc.org/en/master/usage/configuration.html

# -- Path setup --------------------------------------------------------------
# If extensions (or modules to document with autodoc) are in another directory,
# add these directories to sys.path here.

# -- Project information -----------------------------------------------------
# https://www.sphinx-doc.org/en/master/usage/configuration.html#project-information

project = "EBNF Compiler"
copyright = "2026, Jacques Supcik"
author = "Jacques Supcik"
release = "0.1.0"

# -- General configuration ---------------------------------------------------
# https://www.sphinx-doc.org/en/master/usage/configuration.html#general-configuration

extensions = [
    "sphinx.ext.autodoc",
    "sphinx.ext.napoleon",
    "sphinx.ext.viewcode",
    "sphinx_design",
]

templates_path = ["_templates"]
exclude_patterns = ["_build", "Thumbs.db", ".DS_Store"]


# -- Options for HTML output -------------------------------------------------
# https://www.sphinx-doc.org/en/master/usage/configuration.html#options-for-html-output

html_theme = "furo"
html_static_path = ["_static"]

# Furo theme options
html_theme_options = {
    "light_css_variables": {
        "color-brand-primary": "#0071c5",
        "color-brand-content": "#0071c5",
    },
}

Remplacez le contenu du fichier docs/index.rst par le contenu suivant :

docs/index.rst

.. EBNF Compiler documentation master file, created by
   sphinx-quickstart on Mon Feb 16 13:49:30 2026.
   You can adapt this file completely to your liking, but it should at least
   contain the root `toctree` directive.

EBNF Compiler
=============

A tool for parsing and compiling Extended Backus-Naur Form (EBNF) grammars.

.. grid:: 1 2 2 2
    :gutter: 2

    .. grid-item-card:: 📚 Module Documentation
        :link-type: ref
        :link: modules-section

        Explore the API documentation and module reference.

    .. grid-item-card:: 🔍 API Reference
        :link: genindex

        Complete index of all classes, functions, and variables.


.. toctree::
   :maxdepth: 2
   :hidden:

.. _modules-section:

Modules
=======

.. toctree::
   :maxdepth: 3

.. automodule:: ebnf_compiler
   :members:
   :undoc-members:
   :show-inheritance:

.. automodule:: ebnf_compiler.scanner
   :members:
   :undoc-members:
   :show-inheritance:

.. automodule:: ebnf_compiler.parser
   :members:
   :undoc-members:
   :show-inheritance:

.. automodule:: ebnf_compiler.tokens
   :members:
   :undoc-members:
   :show-inheritance:

Indices and tables
==================

* :ref:`genindex`
* :ref:`modindex`
* :ref:`search`

Générez la documentation avec la commande suivante :

cd docs
uv run make html

Note pour les machines Windows

Sur Windows, si vous n’avez pas installé la commande make, vous pouvez utiliser la commande suivante à la place :

cd docs
uv run ./make.bat html

Votre documentation est maintenant disponible dans le dossier docs/_build/html. Ouvrez le fichier index.html dans votre navigateur pour voir le résultat.

Analyse statique du code

Une autre bonne pratique est d’utiliser des outils d’analyse statique du code pour détecter les erreurs potentielles dans votre code avant même de l’exécuter. Pour Python, nous utiliserons les outils suivants :

• Ruff pour l’analyse statique du code
• Pyright et Mypy pour l’analyse de type statique
• Black pour le formatage du code
• Reuse pour vérifier la conformité de votre projet avec les licences open source

Pour simplifier l’utilisation de ces outils, nous allons utiliser pre-commit pour les exécuter automatiquement avant chaque commit.

Ajoutez le fichier de configuration de pre-commit à la racine de votre projet avec le contenu suivant :

.pre-commit-config.yaml

repos:
  - repo: https://github.com/pre-commit/pre-commit-hooks
    rev: v2.3.0
    hooks:
      - id: check-yaml
      - id: end-of-file-fixer
      - id: trailing-whitespace
  - repo: https://github.com/psf/black
    rev: 26.1.0
    hooks:
      - id: black
  - repo: https://github.com/astral-sh/ruff-pre-commit
    rev: v0.15.0
    hooks:
      - id: ruff-check
  - repo: https://github.com/RobertCraigie/pyright-python
    rev: v1.1.408
    hooks:
      - id: pyright
  - repo: https://github.com/pre-commit/mirrors-mypy
    rev: v1.19.1
    hooks:
      - id: mypy
  - repo: https://github.com/fsfe/reuse-tool
    rev: v6.2.0
    hooks:
      - id: reuse

Vérifiez que votre code est conforme aux règles définies par pre-commit avec la commande suivante :

uv run pre-commit run --all-files

Si ce n’est pas le cas suivez les indications données par pre-commit pour corriger les erreurs.

CI/CD

Vous avez maintenant un projet Python avec une bonne structure, des tests unitaires, une documentation et une analyse statique du code. Il est temps de mettre en place un pipeline de CI/CD pour automatiser les tests et la génération de la documentation à chaque commit.

À faire

Mettez en place un pipeline de CI/CD avec Gitlab ou Github pour :

• Valider le code avec pre-commit (et d’autres outils d’analyse statique du code si vous le souhaitez)
• automatiser les tests
• générer la documentation
• Publier la documentation sur GitHub Pages ou GitLab Pages
• Publier votre projet dans une Release GitHub ou GitLab (optionnel)

Gestion des commentaires en EBFN

Le programme actuel ne gère pas les commentaires dans les fichiers EBNF.

À faire

Ajoutez la gestion des commentaires dans votre scanner pour permettre l’utilisation de commentaires dans les fichiers EBNF.

Attention

Les commentaires en EBNF sont similaires à ceux de Pascal et peuvent être imbriqués!

Testez avec le fichier examples/ebnf.ebnf avec le contenu suivant :

examples/ebnf.ebnf

(*
   SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
   SPDX-License-Identifier: Apache-2.0 OR MIT
*)

syntax = {production}.
production = identifier "=" expression "." .
expression = term {"|" term}.
term = factor {factor}.
factor = identifier | string | "(" expression ")" | "[" expression "]" | "{" expression "}".

Testez encore avec le fichier examples/oberon0.ebnf avec le contenu suivant :

examples/oberon0.ebnf

(*
   SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
   SPDX-License-Identifier: Apache-2.0 OR MIT
*)

ident = letter {letter | digit}.
integer = digit {digit}.
selector = {"[" expression "]"}.
number = integer.
factor = ident (ActualParameters  | selector) | number | "(" expression ")" | "~" factor.
term = factor {("*" | "DIV" | "MOD" | "&") factor}.
SimpleExpression = ["+"|"-"] term {("+"|"-" | "OR") term}.
expression = SimpleExpression
    [("=" | "#" | "<" | "<=" | ">" | ">=") SimpleExpression].
assignment = ident selector ":=" expression.
ActualParameters = "(" [expression {"," expression}] ")" .
ProcedureCall = ident selector [ActualParameters].
IfStatement = "IF" expression "THEN" StatementSequence
    {"ELSIF" expression "THEN" StatementSequence}
    ["ELSE" StatementSequence] "END".
WhileStatement = "WHILE" expression "DO" StatementSequence "END".
RepeatStatement = "REPEAT" StatementSequence "UNTIL" expression.
statement = [assignment | ProcedureCall | IfStatement | WhileStatement | RepeatStatement].
StatementSequence = statement {";" statement}.
IdentList = ident {"," ident}.
ArrayType = "ARRAY" expression "OF" type.
type = ident | ArrayType.
FPSection = ["VAR"] IdentList ":" type.
FormalParameters = "(" [FPSection {";" FPSection}] ")".
ProcedureHeading = "PROCEDURE" ident [FormalParameters].
ProcedureBody = declarations ["BEGIN" StatementSequence] "END" ident.
ProcedureDeclaration = ProcedureHeading ";" ProcedureBody.
declarations = ["CONST" {ident "=" expression ";"}]
    ["TYPE" {ident "=" type ";"}]
    ["VAR" {IdentList ":" type ";"}]
    {ProcedureDeclaration ";"}.
module = "MODULE" ident ";" declarations
    ["BEGIN" StatementSequence] "END" ident "." .

Conclusion

Félicitations, vous avez écrit votre premier compilateur en Python et vous avez appris à utiliser quelques bonnes pratiques de développement logiciel.

Ce dépôt git doit vous servir d’exemple pour vos projets en Python. Si, plus tard, vous souhaitez mettre votre projet en Open Source et maintenir une communauté autour de votre projet, je vous recommande l’article How to Become an Open Source Project Maintainer.