Krc · compilateur d'un langage en coréen

Du fichier .kr au fichier objet, en sept étapes

Chaque fichier passe par compile (src/main.rs). Chaque étape prend la sortie de la précédente. L'exemple ci-dessous est suivi d'étape en étape avec la vraie sortie du compilateur.

Exemple suivi : demo.kr
정수를 반환하는 더하다(정수 가, 정수 나) {
    (가 + 나)를 반환해요.
}

정수를 반환하는 main() {
    합은 3과 4를 더한 값이에요.
    합을 반환해요.
}
  1. Lexer
  2. Pre-parser
  3. Parser LR(1)
  4. Post-parser
  5. Converter
  6. Codegen
  7. Encodeur et ELF
1

Lexer

src/lexer/ · tokenize
texte source→LexerToken + Span
  • Découpe en HangulWord, LatinWord, Int, Float, Str, Punctuation, Operator, Eof. Saute les commentaires.
  • Les positions (Span) sont en octets.
  • Ne connaît ni mot-clé ni particule : 합은 reste un seul mot.

Erreurs : chaîne ou commentaire non terminé, jamo isolé, caractère inattendu, entier trop grand.

La ligne suivie
HangulWord(합은) Int(3) HangulWord(과)
Int(4) HangulWord(를) HangulWord(더한)
HangulWord(값이에요) Punctuation(.)
2

Pre-parser

src/parser/preparser/ · pre_parse
LexerToken→ParserToken + warnings
  • Classe et découpe les mots coréens : mot-clé, type, booléen, compteur, forme verbale, particule.
  • declared_verbs : l'infinitif de chaque verbe du fichier, pour qu'un appel placé avant la définition soit lu comme un verbe.
  • declared_names : les noms déclarés (결과는, paramètres), avec leur scope.
  • tokenize_names : un mot devient Name, ou Name + particule. Le nom le plus long gagne.

Erreurs : UnknownIdentifier, AmbiguousName. Warning : verbe sans (.

Point fragile

Le découpage dépend des déclarations, comme les typedef du C. Les déclarations sont devinées par des heuristiques sur une suite plate de tokens. Les issues #17, #18, #21 et #47 touchent cette étape.

La ligne suivie
Name(합) Particle(Topic)
Int(3) Particle(With)
Int(4) Particle(Object)
Verb { 더하다, Adnominal }
Keyword(Value) Particle(ItIs) Dot
3

Parser LR(1)

src/parser/cfg/ · Parser::new(RULES), parse
ParserToken→arbre de dérivation (TreeNode)
  • La grammaire est dans rules.rs. La table LR(1) est construite au démarrage, avec les ensembles FIRST (environ 4 s en debug, 0,5 s en release).
  • Ne regarde que la sorte du token (Name, Verb::Seo…), jamais sa valeur.
  • La terminaison des verbes (Da, Seo, Yo, Adnominal, Go) structure la phrase : 11 règles en dépendent.

Erreur : syntax error: unexpected <token>. L'option --tree affiche l'arbre.

Règle qui reconnaît « 3과 4를 더한 값 »
DeclarationValue =>
    Arguments
    Verb::Adnominal
    Keyword::Value
4

Post-parser

src/parser/postparser/ · convert_to_ast_tree
arbre de dérivation→AST (Program, Function, Statement, Expr)
  • Une fonction par non-terminal.
  • Refuse ce que la grammaire accepte mais que l'AST ne peut pas représenter : 부호 없는 소수, 짧은 논리, 반환해요 sans valeur ou avec deux valeurs, compteur incohérent (두 정수 가와 나와 다를).
  • Affiche l'AST sur stdout.
AST affiché
fn main() -> int {
    let 합 = 더하다(3, 4)
    return 합
}
5

Converter

src/converter/ · Converter::convert
AST→IR
  • L'analyse sémantique : scopes, types, expressions, instructions, signatures.
  • Noms de fonction décorés par les types des paramètres (더하다$int$int). Une fonction 외부 a un nom latin.
  • IR : variables numérotées et instructions Copy, Unary, Binary, Cast, Zero, Call, Label, Jump, JumpIfNot, Return.

Erreurs : UnknownVariable, AlreadyDeclared, SameSignature, MissingReturn, NoMain, NotInteger, BreakOutOfLoop…

IR affichée
fn main() -> int
    var v0: int
    var v1: int
    // let 합 = 더하다(3, 4)
    v0 = call 더하다$int$int(3ls, 4ls)
    v1 = v0
    // return 합
    return v1
6

Codegen

src/codegen/ · generate
IR→instructions x86-64 + sections
  • Chaque variable a sa case sur la pile. Pas encore d'allocation de registres (#8).
  • Pour chaque fonction : prologue, traduction de chaque instruction IR, épilogue.
  • Les chaînes vont dans .rodata, les fonctions dans .text. Une fonction 외부 devient un symbole non défini.
main désassemblé (extrait)
push rbp
mov  rbp, rsp
sub  rsp, 0x10
mov  rdi, 0x3
mov  rsi, 0x4
call 더하다$int$int
mov  [rbp-0x8], rax
...
ret
7

Encodeur x86-64 et ELF

src/elf/instructions/ · src/elf/file/
instructions→demo.o→a.out (avec -x)
  • Un assembleur maison : préfixes, REX, ModRM, SIB, déplacements et relocations.
  • Un écrivain ELF maison : sections, table des chaînes, symboles, relocations. Ni as ni nasm.
  • Avec plusieurs fichiers, un seul contient main. L'option -x appelle gcc pour lier, ce qui apporte la libc (printf).
Octets encodés (début de main)
48 55          push rbp
48 8b ec       mov rbp, rsp
48 83 ec 10    sub rsp, 0x10
e8 00 00 00 00 call (relocation)