TP07 : Implémentation de la grammaire complète pour Oberon-0
Complétez votre code pour implémenter la grammaire complète d’Oberon-0:
ident = letter {letter | digit}.
integer = digit {digit}.
number = integer.
factor = ident (ActualParameters) |
number | "(" expression ")" | "~" factor.
term = factor {("*" | "DIV" | "MOD" | "&") factor}.
SimpleExpression = ["+"|"-"] term {("+"|"-" | "OR") term}.
expression = SimpleExpression
[("=" | "#" | "<" | "<=" | ">" | ">=") SimpleExpression].
assignment = ident ":=" expression.
ActualParameters = "(" [expression {"," expression}] ")" .
ProcedureCall = ident [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}.
type = ident.
FPSection = ["VAR"] IdentList ":" type.
FormalParameters = "(" [FPSection {";" FPSection}] ")".
ProcedureHeading = "PROCEDURE" ident ["*"] [FormalParameters].
ProcedureBody = declarations ["BEGIN" StatementSequence] "END" ident.
ProcedureDeclaration = ProcedureHeading ";" ProcedureBody.
declarations =
["CONST" {ident "=" expression ";"}]
["VAR" {IdentList ":" type ";"}]
{ProcedureDeclaration ";"}.
module = "MODULE" ident ";" declarations "END" ident "." .
Commencez par implémenter les instructions de contrôle de flux (if, while, etc.), puis les procédures et les fonctions.
Le scanner ne devrait pas nécessiter de modifications, mais vous devrez probablement ajouter des noeuds à l’AST, compléter le parser pour construire ces noeuds, et compléter le générateur de code pour générer le code WebAssembly correspondant.
Passe séparée pour la vérification des types
En implémentant toutes les fonctionnalités du langage, vous remarquerez que la génération de code devient plus complexe, car il faut gérer de nombreux cas différents (par exemple, les appels de procédures, les expressions, les instructions de contrôle de flux, etc.). Il faut aussi s’assurer que les types sont corrects (par exemple, on ne peut pas additionner un entier et un booléen), ce qui peut nécessiter de faire des vérifications de types pendant la génération de code. Afin d’alléger le générateur de code, vous pouvez implémenter une passe séparée pour la vérification des types, qui parcourt l’AST après le parsing et vérifie que les types sont corrects1.
Implémentez cette passe de vérification des types dans le fichier src/oberon0_compiler/type_checker.py et modifiez le programme principal de votre compilateur pour l’appeler après le parsing et avant la génération de code.
Voici à quoi pourrait ressembler l’implémentation de la classe TypeChecker:
# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: MIT
"""
Oberon-2 WASM Type Checker
"""
from dataclasses import dataclass
from loguru import logger
from rich.console import Console
from . import ast, types
from . import sym_table as SYM
from .scanner import Position
console = Console()
class TypeCheckError(Exception):
def __init__(self, message: str, position: Position) -> None:
super().__init__(message)
self.position = position
def __str__(self) -> str:
p = self.position
return (
f"{self.args[0]} (File {p.file_name}, Line {p.line_no}, Column {p.col_no})"
)
@dataclass
class TypeChecker:
def ensure(self, node: ast.Node, condition: bool, message: str) -> None:
if not condition:
raise TypeCheckError(message, node.position)
def factor(self, f: ast.Factor) -> SYM.Type | None:
pass
...
def term(self, t: ast.Term) -> SYM.Type:
f1_type = self.factor(t.factor)
assert f1_type is not None
for op, f in t.mulop_factors:
f2_type = self.factor(f)
self.ensure(t, f1_type == f2_type, "Type mismatch")
if op == "*":
self.ensure(
t, f1_type == types.integer, "Type mismatch : expected INTEGER"
)
elif op == "DIV":
self.ensure(
t, f1_type == types.integer, "Type mismatch : expected INTEGER"
)
elif op == "MOD":
self.ensure(
t, f1_type == types.integer, "Type mismatch : expected INTEGER"
)
elif op == "&":
self.ensure(
t, f1_type == types.boolean, "Type mismatch : expected BOOLEAN"
)
else:
raise TypeCheckError(f"Unknown mulop: {op}", t.position)
return f1_type
def check(self, ast_: ast.Module) -> None:
self.ensure(ast_, isinstance(ast_, ast.Module), "Module expected")
d = ast_.declarations
for p in d.procedure_declarations:
self.procedure(p)
logger.debug("Type checking completed successfully")
Notez que les fonction qui représentent les noeuds de l’AST (comme factor, term, etc.) retrournet maintenant le type de l’expression correspondante.
Tests finaux
Testez votre compilateur avec les exemples suivants:
(*
SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
SPDX-License-Identifier: MIT
*)
MODULE PrintOddNumbers;
PROCEDURE Run*;
VAR i, max: INTEGER;
BEGIN
OpenInput;
ReadInt(max);
i := 1;
WHILE i < max DO
WriteInt(i, 5);
WriteLn;
i := i + 2;
END;
END Run;
END PrintOddNumbers.
> oberon0-rt run print_odd_numbers.wasm Run 7
1
3
5
(*
SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
SPDX-License-Identifier: MIT
*)
MODULE FooBar;
PROCEDURE FooBar*;
VAR i, n: INTEGER;
BEGIN OpenInput; ReadInt(n);
i := 1;
WHILE i <= n DO
IF (i MOD 5 = 0) & (i MOD 7 = 0) THEN
WriteChar(70); WriteChar(111); WriteChar(111);
WriteChar(66); WriteChar(97); WriteChar(114); WriteLn;
ELSIF i MOD 5 = 0 THEN
WriteChar(70); WriteChar(111); WriteChar(111); WriteLn;
ELSIF i MOD 7 = 0 THEN
WriteChar(66); WriteChar(97); WriteChar(114); WriteLn;
ELSE
WriteInt(i, 4); WriteLn;
END ;
i := i + 1;
END ;
END FooBar;
END FooBar.
> oberon0-rt run foobar.wasm FooBar 36
1
2
3
4
Foo
6
Bar
8
9
Foo
11
12
13
Bar
Foo
16
17
18
19
Foo
Bar
22
23
24
Foo
26
27
Bar
29
Foo
31
32
33
34
FooBar
36
(*
SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
SPDX-License-Identifier: MIT
*)
MODULE Samples;
PROCEDURE Multiply*;
VAR x, y, z: INTEGER;
BEGIN OpenInput; ReadInt(x); ReadInt(y); z := 0;
WHILE x > 0 DO
IF x MOD 2 = 1 THEN z := z + y END ;
y := 2*y; x := x DIV 2
END ;
WriteInt(x, 4); WriteInt(y, 4); WriteInt(z, 6); WriteLn
END Multiply;
PROCEDURE Divide*;
VAR x, y, r, q, w: INTEGER;
BEGIN OpenInput; ReadInt(x); ReadInt(y); r := x; q := 0; w := y;
WHILE w <= r DO w := 2*w END ;
WHILE w > y DO
q := 2*q; w := w DIV 2;
IF w <= r THEN r := r - w; q := q + 1 END
END ;
WriteInt(x, 4); WriteInt(y, 4); WriteInt(q, 4); WriteInt(r, 4); WriteLn
END Divide;
PROCEDURE Sum*;
VAR n, s: INTEGER;
BEGIN OpenInput; s:= 0;
WHILE ~eot() DO ReadInt(n); WriteInt(n, 10); s := s + n END ;
WriteInt(s, 10); WriteLn;
END Sum;
END Samples.
> oberon0-rt run sample.wasm Multiply 7 5
0 40 35
> oberon0-rt run sample.wasm Divide 1700 3
1700 3 566 2
> oberon0-rt run sample.wasm Sum 3 4 5 6 7
3 4 5 6 7 25
(*
SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
SPDX-License-Identifier: MIT
*)
MODULE Test;
CONST x = 21 * 2;
y = 2 * x + 1;
PROCEDURE Say42*;
BEGIN
WriteInt(x, 5);
WriteLn;
WriteInt(y, 5);
WriteLn;
END Say42;
END Test.
> oberon0-rt run const.wasm Say42
42
85
Conclusion
Si vous êtes arrivés jusqu’ici, félicitations ! Vous avez implémenté un compilateur complet pour un langage de programmation simple (mais non trivial) et vous avez appris beaucoup de choses sur la construction de compilateurs, les langages de programmation, et le WebAssembly.
Si vous souhaitez aller plus loin, vous pouvez essayer d’ajouter des fonctionnalités supplémentaires à votre compilateur, comme la gestion des tableaux, des enregistrements (records), des pointeurs, etc. Vous pouvez aussi essayer d’implémenter un langage de programmation plus complexe que Oberon-0, ou d’implémenter un compilateur pour un langage de programmation existant (comme C, Java, Python, etc.) vers WebAssembly.
Vous pouvez aussi étudier le projet llvm pour voir comment les compilateurs professionnels sont implémentés. Pour terminer, vous pouvez étudier les différentes optimisations que les compilateurs peuvent faire pour améliorer les performances du code généré, comme l’inlining, la vectorisation, la parallélisation, etc. La vidéo de Keith Randall à GopherCon 2017 sur la génération de meilleur code machine avec SSA est aussi très intéressante pour comprendre comment les compilateurs modernes optimisent le code généré.
-
Cette passe peut aussi annoter l’AST avec des informations de type, ce qui peut faciliter la génération de code. ↩