TP05 : Un Parser pour Oberon-0
La prochaine étape dans la construction de notre compilateur est d’écrire un parser pour le langage Oberon-0.
Grammaire de Oberon-0 simplifiée
Afin d’obtenir le plus rapidement possible un compilateur fonctionnel, nous allons commencer par une version très simplifiée de la grammaire d’Oberon-0, que nous allons progressivement enrichir au fil des TP suivants.
Voici la grammaire que nous allons utiliser pour ce TP :
oberon0-a.ebnf
ident = letter {letter | digit}.
integer = digit {digit}.
number = integer.
factor = ident [ActualParameters] | number | "(" expression ")" .
term = factor {("*" | "DIV" | "MOD" ) factor}.
SimpleExpression = ["+"|"-"] term {("+"|"-") term}.
expression = SimpleExpression.
assignment = ident ":=" expression.
ActualParameters = "(" [expression {"," expression}] ")" .
ProcedureCall = ident [ActualParameters].
statement = [assignment | ProcedureCall].
StatementSequence = statement {";" statement}.
IdentList = ident {"," ident}.
type = ident.
ProcedureHeading = "PROCEDURE" ident ["*"].
ProcedureBody = declarations ["BEGIN" StatementSequence] "END" ident.
ProcedureDeclaration = ProcedureHeading ";" ProcedureBody.
declarations =
["VAR" {IdentList ":" type ";"}]
{ProcedureDeclaration ";"}.
module =
"MODULE" ident ";"
declarations
"END" ident "." .
Cette grammaire simplifiée nous permet de considérer les exemples suivants:
print42.mod
(*
SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
SPDX-License-Identifier: MIT
*)
MODULE Test;
PROCEDURE Print42*;
BEGIN
WriteInt(42, 5);
WriteLn;
END Print42;
END Test.
printx.mod
(*
SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
SPDX-License-Identifier: MIT
*)
MODULE Test;
PROCEDURE Print2X*;
VAR x, y : INTEGER;
BEGIN
OpenInput;
ReadInt(x);
WriteInt(2 * x, 5);
WriteLn;
END Print2X;
END Test.
add.mod
(*
SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
SPDX-License-Identifier: MIT
*)
MODULE Test;
PROCEDURE Add*;
VAR x, y, z: INTEGER;
BEGIN
OpenInput;
ReadInt(x);
ReadInt(y);
z := x + y;
WriteInt(z, 5);
WriteLn;
END Add;
END Test.
Arbre de syntaxe abstraite (AST) - Partie 1
Contrairement aux compilateurs de Niklaus Wirth, nous allons construire un compilateur à plusieurs passes, et nous allons donc construire un arbre de syntaxe abstraite (AST) à partir du code source
Voici comment vous pouvez commencer l’implémentation de l’AST en Python:
src/oberon0_compiler/ast.py
# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: MIT
"""
Oberon-0 Abstract Syntax Tree
"""
from dataclasses import dataclass
from . import sym_table as SYM
from .scanner import Position, Scanner
actual_scanner: Scanner | None = None
@dataclass
class Node:
position: Position
def __str__(self) -> str:
return ""
@dataclass
class VariableDeclaration(Node):
symbol: SYM.LocalVariable | SYM.GlobalVariable
def __str__(self) -> str:
return f"VAR {self.symbol.name}: {self.symbol.type_};"
@dataclass
class Declarations(Node):
var_declarations: list[VariableDeclaration]
procedure_declarations: list["ProcedureDeclaration"]
def __str__(self) -> str:
v = "\n".join(str(d) for d in self.var_declarations)
p = "\n".join(str(d) for d in self.procedure_declarations)
return "\n".join([i for i in [v, p] if i])
@dataclass
class ProcedureDeclaration(Node):
symbol: SYM.ProcedureDefinition
exported: bool
declarations: Declarations
body: StatementSequence
def __str__(self) -> str:
e = "*" if self.exported else ""
decl = str(self.declarations)
body = str(self.body)
res = f"PROCEDURE {self.symbol.name}{e};"
if decl:
res += "\n" + decl
if body:
res += "\nBEGIN\n" + body
return res + f"\nEND {self.symbol.name}"
@dataclass
class Assignment(Statement):
symbol: SYM.Symbol
expression: Expression
def __str__(self) -> str:
lhs = f"{self.symbol.name}"
rhs = f"{self.expression}"
return f"{lhs} := {rhs}"
@dataclass
class Term(Node):
factor: Factor
mulop_factors: list[tuple[str, Factor]]
def __str__(self) -> str:
mulop = "".join(f" {op} {f}" for op, f in self.mulop_factors)
return f"{self.factor}{mulop}"
@dataclass
class Ident(Factor):
symbol: SYM.Variable
def __str__(self) -> str:
return self.symbol.name
@dataclass
class Number(Factor):
value: int
def __str__(self) -> str:
return str(self.value)
@dataclass
class Module(Node):
ident: str
declarations: Declarations
def __str__(self) -> str:
decl = str(self.declarations)
res = f"MODULE {self.ident};"
if decl:
res += "\n" + decl
return res + f"\nEND {self.ident}."
Notez l’utilisation de @dataclass et de __str__ pour faciliter l’affichage de l’AST.
La table des symboles (symbol table)
Dans l’AST, les identifiants ne sont pas représentés par des chaînes de caractères (str), mais par des symboles1.
Un symbole est une instance de la classe SYM.Symbol, qui contient des informations sur l’identifiant, comme son nom, son type, etc.
Ces symboles sont créés et gérés par la table des symboles. Cette structure de données permet de:
- associer des informations à chaque identifiant (nom, type, etc.)
- retrouver rapidement les informations associées à un identifiant (par exemple, pour vérifier que les types sont corrects)
- gérer la portée (scope) des identifiants (par exemple, les variables locales d’une procédure ne sont pas accessibles en dehors de cette procédure)
- assurer que les identifiants sont uniques dans leur portée (par exemple, on ne peut pas déclarer deux variables avec le même nom dans la même procédure)
Voici une implémentation possible (mais incomplète)de la table des symboles:
src/oberon0_compiler/sym_table.py
# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: MIT
"""
Oberon-2 Symbol Table
"""
from dataclasses import dataclass, field
import wasm_gen as W # noqa
from loguru import logger
@dataclass
class Symbol:
name: str
@dataclass
class Type(Symbol):
index: int
size: int
@dataclass
class Variable(Symbol):
type_: Type
@dataclass
class LocalVariable(Variable):
offset: int
@dataclass
class GlobalVariable(Variable):
offset: int
@dataclass
class FormalParameter(Variable):
index: int
by_ref: bool
@dataclass
class ProcedureDefinition(Symbol):
exported: bool
stack_size: int
@dataclass
class SystemCall(Symbol):
index: int
params: list[FormalParameter]
return_type: Type | None = None
@dataclass
class Scope:
level: int
symbols: dict[str, Symbol] = field(default_factory=dict)
def add(self, symbol: Symbol) -> None:
if symbol.name in self.symbols:
raise KeyError(
f"Symbol {symbol.name} already defined in scope {self.level}"
)
self.symbols[symbol.name] = symbol
def find(self, name: str, class_: type) -> Symbol | None:
logger.debug(f"Looking for {name} at level {self.level}")
if name in self.symbols:
s = self.symbols[name]
logger.debug(f"Found {s}")
if isinstance(s, class_):
return s
return None
@dataclass
class SymbolTable:
scopes: list[Scope] = field(default_factory=list)
def current_level(self) -> int:
return len(self.scopes) - 1
def current_scope(self) -> Scope:
return self.scopes[-1]
def new_scope(self) -> None:
level = len(self.scopes)
logger.debug(f"New scope at level {level}")
self.scopes.append(Scope(level=level))
def close_scope(self) -> None:
if len(self.scopes) == 0:
raise IndexError("No scope to close")
logger.debug(f"Closing scope at level {self.current_level()}")
for s in self.scopes[-1].symbols.values():
logger.debug(f"> {s}")
self.scopes.pop()
def add(self, symbol: Symbol) -> None:
scope = self.current_scope()
scope.add(symbol)
def find(
self,
name: str,
class_: type = Symbol,
min_level: int = 0,
max_level: int | None = None,
) -> Symbol | None:
for scope in reversed(self.scopes[min_level:max_level]):
s = scope.find(name, class_)
if s is not None:
return s
logger.debug(f"Symbol {name} not found")
return None
Arbre de syntaxe abstraite (AST) - Partie 2
Complétez maintenant l’implémentation de l’AST en ajoutant les nœuds manquants, comme les assignations, les déclarations de variables, les procédures, etc.
Le parser
Implémemntez maintenant le parser pour le langage Oberon-0 en utilisant la grammaire simplifiée que nous avons définie plus haut. Le parser doit construire un AST à partir du code source.
Voici comment vous pouvez commencer l’implémentation du parser:
src/oberon0_compiler/parser.py
# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: MIT
"""
Oberon-0 parser
"""
import typing
from dataclasses import dataclass, field
import wasm_gen as W # noqa
from loguru import logger
from . import ast, systemcalls, types
from . import sym_table as SYM
from .scanner import Position, Scanner
from .token import Token
class ParserError(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 Parser:
scanner: Scanner
sym_table: SYM.SymbolTable = field(default_factory=SYM.SymbolTable)
@typing.no_type_check
def check_sym(self, expected: Token):
if self.scanner.sym != expected:
raise ParserError(
f"Expected '{expected}', but got '{self.scanner.sym}'",
self.scanner.position(),
)
def factor(self) -> ast.Factor:
logger.debug("parsing factor")
# TODO(Student): Implement parsing of factors
def term(self) -> ast.Term:
logger.debug("parsing term")
# TODO(Student): Implement parsing of terms
def expression(self) -> ast.Expression:
logger.debug("parsing expression")
# TODO(Student): Implement parsing of expressions
# TODO(Student): Implement the rest of the parsing functions (statement, statement_sequence, declarations, etc.)
def add_types(self) -> None:
self.sym_table.add(types.integer)
self.sym_table.add(types.boolean)
def add_system_calls(self) -> None:
self.sym_table.add(systemcalls.OpenInput)
self.sym_table.add(systemcalls.ReadInt)
self.sym_table.add(systemcalls.eot)
self.sym_table.add(systemcalls.WriteChar)
self.sym_table.add(systemcalls.WriteInt)
self.sym_table.add(systemcalls.WriteLn)
def module(self) -> ast.Module:
logger.debug("parsing module")
self.check_sym(Token.MODULE)
self.scanner.get_next_symbol()
self.check_sym(Token.IDENT)
name = self.scanner.value
self.scanner.get_next_symbol()
self.check_sym(Token.SEMICOLON)
self.scanner.get_next_symbol()
self.sym_table.new_scope()
self.add_types()
self.add_system_calls()
d = self.declarations(global_=True)
self.scanner.get_next_symbol()
self.check_sym(Token.IDENT)
self.sym_table.close_scope()
if self.scanner.value != name:
raise ParserError(
f"Expected '{name}', but got '{self.scanner.value}'",
self.scanner.position(),
)
self.scanner.get_next_symbol()
self.check_sym(Token.PERIOD)
self.scanner.get_next_symbol()
self.check_sym(Token.EOF)
return ast.Module(position=self.scanner.position(), ident=name, declarations=d)
def parse(self) -> ast.Module:
logger.debug("Parsing")
ast.actual_scanner = self.scanner
self.scanner.get_next_symbol()
return self.module()
Notez les méthodes add_types2 et add_system_calls, qui ajoutent les types de base et les procédures système à la table des symboles avant de commencer le parsing. Voici comment ces symboles sont implémentés:
src/oberon0_compiler/types.py
# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: MIT
"""
Oberon-0 types
"""
from . import sym_table as SYM
types = [
SYM.Type(name=name, index=i, size=size)
for i, (name, size) in enumerate([("INTEGER", 4), ("BOOLEAN", 4)])
]
integer = types[0]
boolean = types[1]
src/oberon0_compiler/systemcalls.py
# SPDX-FileCopyrightText: 2026 Jacques Supcik <jacques.supcik@hefr.ch>
#
# SPDX-License-Identifier: MIT
"""
Oberon-0 System Calls
"""
from . import sym_table as SYM
from .types import integer
system_calls = [
SYM.SystemCall(name=name, index=i, params=params, return_type=return_type)
for i, (name, params, return_type) in enumerate(
[
("OpenInput", [], None),
(
"ReadInt",
[SYM.FormalParameter(name="var", index=0, type_=integer, by_ref=True)],
None,
),
("eot", [], integer),
(
"WriteChar",
[SYM.FormalParameter(name="c", index=0, type_=integer, by_ref=False)],
None,
),
(
"WriteInt",
[
SYM.FormalParameter(name="n", index=0, type_=integer, by_ref=False),
SYM.FormalParameter(name="w", index=1, type_=integer, by_ref=False),
],
None,
),
("WriteLn", [], None),
]
)
]
OpenInput = system_calls[0]
ReadInt = system_calls[1]
eot = system_calls[2]
WriteChar = system_calls[3]
WriteInt = system_calls[4]
WriteLn = system_calls[5]
Modifiez le programme principal de votre compilateur (src/oberon0_compiler/__init__.py) pour utiliser le parser que vous venez d’implémenter et testez avec les exemples de modules que nous avons définis plus haut.
Implémentez aussi une fonction d’affichage de l’AST pour pouvoir visualiser le résultat du parsing.
Tests unitaires
Implémentez des tests unitaires pour votre parser afin de vérifier qu’il fonctionne correctement avec les différents éléments de la grammaire. Vous pouvez utiliser les exemples de modules que nous avons définis plus haut comme cas de test.