Journal [Letlang] Écrire un compilateur en Rust (partie 2)

Sommaire

• • Introduction
  • Les différents types de parser
  • Au travail
    • Implémenter le lexer
    • Implémenter la grammaire
  • Conclusion

Bonjour Nal :)

Je suis inspiré en ce moment, du coup je continue ma série sur l'écriture d'un compilateur en Rust. Si tu es intéressé par les précédents articles, les voici :

• Partie 0 : Présentation du langage
• Partie 1 : Générer du code Rust à partir d'un AST

Dans cette partie, je vais te présenter mes dernières découvertes concernant le parser.

Introduction

Tout d'abord, c'est quoi un parser ?

Google Translate traduit le terme par analyseur. Voilà bonne journée, à demain.

…

Non, en vrai, c'est pas suffisant comme explication. Dans le domaine des langages de programmation, le parser est la partie du compilateur ou interpréteur qui va traduire le texte en AST.

Cela est fait en plusieurs étapes :

1. On transforme le flux de caractères en flux de token :

const a := 42;

devient

KEYWORD_CONST IDENTIFIER(a) OPERATOR_ASSIGN INTEGER(42) STATEMENT_END

Différentes méthodes sont possibles, une souvent utilisée est basée sur les expressions régulières (les regex sont nos amies, stop regex hate).

Si on rencontre une chaîne de caractère qui n'est reconnue par aucun token, on a alors une erreur de syntaxe.

Chaque token est accompagné d'information indiquant OÙ dans la chaine de caractère initiale il se trouve.

2. On analyse le flux de token à l'aide d'une grammaire:

Les règles de grammaires définissent quels sont les pattern de token que l'on doit rencontrer. Par exemple :

• Déclaration de constante : KEYWORD_CONST IDENTIFIER OPERATOR_ASSIGN EXPRESSION STATEMENT_END
• Importation de module : KEYWORD_IMPORT STRING_LITERAL STATEMENT_END
• Exportation de symbole : KEYWORD_EXPORT IDENTIFIER+ STATEMENT_END (le + signifiant 1 ou plus)

Si on rencontre un pattern qui n'est défini par aucune règle de grammaire, alors il y a une erreur grammaticale (unexpected token blabla).

Le résultat de cette étape est très souvent un AST annoté des informations suivantes : nom de fichier, ligne, colonne.

3. On parcours l'AST pour vérifier qu'il est bien formé :

Un petit exemple en Rust :

const good: i64 = 21 * 2;
const bad: i64 = 42 + some_function();

Le compilateur ne va pas apprécier la seconde ligne. En effet, bien que valide au niveau de la syntaxe et de la grammaire, ce n'est pas valide d'un point de vue sémantique : on ne peut pas appeler de fonction non constante lorsque l'on déclare une constante ou une variable statique.

C'est donc à cette étape (qui elle même peut être découpée en plusieurs phases) que l'on va pouvoir vérifier les règles sémantiques, soit :

• inférence de type (on ajoute des métadonnées aux noeuds de l'AST)
• vérification des types
• rust a le bound-checking / borrow-checker / … pour assurer la viabilité de l'accès à la mémoire
• et tout ce que tu peux imaginer (exemple : si on est samedi, les if sont interdit)

Pour ma part, je prévois d'interdire les récursions qui ne sont pas Tail Call. L'idée étant de traduire la récursion en itération lors de la compilation, pour permettre d'avoir de la récursion infinie (pas d'erreur du type Maximum Depth Exceeded).

Les différents types de parser

Il existe différents types de parser, sujet très largement couvert en Computer Science et dans de nombreux ouvrages littéraires que je n'ai pas lu.

On retrouve par exemple :

• les Parser Combinators :
  • un parser est une fonction qui accepte une chaîne de caractères et retourne une structure
  • un combinator est une fonction qui accepte des parsers et retourne un nouveau parser
• les Parsing Expression Grammar (PEG pour les intimes) :
  • On commence par les règles de haut niveau, et on descend jusqu'à rencontrer une erreur
• les Left to right, Rightmost derivation (LR pour les intimes) :
  • On commence par les règles de plus bas niveau, et on remonte jusqu'à obtenir la structure finale

NB : Merci de me corriger si j'ai dit des bêtises.

En programmation fonctionnelle, les Parser Combinator sont très appréciés. Moi je les aime pas, car la gestion des espaces ( [ \t\n\f] ) est particulièrement pénible a implémenter. Si cela t'intéresse, en Rust je ne peux que te recommander nom.

Parmi les PEG parser, on retrouvera beaucoup des Packrat Parser, très souvent basé sur une grammaire inspirée de BNF. Je trouve ces grammaires assez simple à implémenter, et en Rust je peux te recommander pest.

Le soucis que j'ai avec cette dernière, c'est encore une fois la gestion des espaces. Tout les espaces ne sont pas insignifiants dans un langage de programmation, exemple :

• GOOD : const a = 42;
• GOOD : const a=42;
• BAD : consta=42;

Et donc, en utilisant pest, je dois désactiver le "skip" des espaces, et ajouter moi même la règle partout dans la grammaire. Bref, même soucis qu'avec les Parser Combinator.

Au final, les LR(1) parser sont très utilisés dans l'implémentation de langage de programmation. Tu as sûrement entendu parler des vénérables lex et yacc, c'est parce qu'ils permettent de produire des grammaires LR(k).

Côté Rust, j'ai ainsi découvert LALRPOP et Logos. On va regarder ça ensemble de suite :)

Au travail

Tout d'abord, préparons notre projet en ajoutant à Cargo.toml :

[package]
# ...
build = "build.rs"

[build-dependencies]
lalrpop = "0.19.7"

[dependencies]
lalrpop-util = "0.19.7"
regex = "1"
logos = "0.12.0"

Et dans build.rs :

extern crate lalrpop;

fn main() {
  lalrpop::process_root().unwrap();
}

---

LALRPOP s'inspire de lex et yacc. On a un Lexer (pour transformer le flux de caractères en flux de token), et une grammaire qui pour chaque règle va y associer un bout de code Rust (qu'on utilisera pour créer l'AST).

Le lexer par défaut ignore tout les espaces, mais il est possible de fournir un lexer fait maison. Ils fournissent d'ailleurs un exemple de parser pour le langage whitespace, l'opposé de ce que fait donc le lexer par défault :P

C'est là que Logos intervient. Il permet de définir le pattern de nos tokens et il va lui même s'occupe de transformer notre chaine de caractères en chaîne de token. Le tout en gérant correctement les espaces et autres séparateurs. Petit exemple:

use logos::Logos;

#[derive(Logos, Clone, Debug, PartialEq)]
pub enum Token {
  #[regex(r"[_a-zA-Z][_0-9a-zA-Z]*", |lex| lex.slice().parse())]
  Identifier(String),

  #[token("const")]
  Const,

  #[error]
  Error,  // requis pour tout les tokens invalides
}

Ici je définis 2 tokens, const et un identifier. Tu remarqueras que la regex de Identifier est capable de parser const. Logos résous cela de 2 manières :

• les #[token()] ont priorité sur les #[regex()]
• les tokens les plus longs ont priorité sur les tokens les plus court

Ce deuxième point est très important :

• const a donne [Const, Identifier("a")]
• consta donne [Identifier("consta")]

Je complète donc mon enumeration avec l'ensemble des tokens de mon langage, et je teste :

let tokens: Vec<_> = Token::lexer("const a := 42;").spanned().collect();
assert_eq!(
  tokens,
  &[
    (Token::StatementConst, 0..5),
    (Token::Identifier(String::from("a")), 6..7),
    (Token::OperatorAssign, 8..10),
    (Token::IntegerBase10(42), 11..13),
    (Token::StatementSeparator, 13..14),
  ]
);

Bingo! Je peux passer à la suite :)

Implémenter le lexer

LALRPOP demande à ce que le lexer implémente le trait Iterator, et lui retourne à chaque itération un Result avec le tuple (start_location, token, end_location). C'est donc ce que l'on va faire pour intégrer le tokenizer Logos à LALRPOP.

Commençons par importer tout ce qui va nous être utile :

use logos::{Logos, SpannedIter};  // on importe le trait Logos

use crate::core::errors::{ParseResult, ParseError}; // ma propre structure Result/Error
use crate::parser::tokens::Token; // l'enum créée précédemment

Comme dit précédemment, le Lexer va implémenter le trait Iterator, voici donc les items de notre itérateur :

pub type Spanned<Tok, Loc> = ParseResult<(Loc, Tok, Loc)>;

Notre Lexer va utiliser notre tokenizer Logos en entrée pour générer la liste des tokens :

pub struct Lexer<'input> {
  filename: String,
  token_stream: SpannedIter<'input, Token>
}

impl<'input> Lexer<'input> {
  pub fn new(filename: &String, input: &'input str) -> Self {
    Self {
      filename: filename.clone(),
      token_stream: Token::lexer(input).spanned(),
    }
  }
}

Ce qui va grandement simplifier l'écriture de l'itérateur :

impl<'input> Iterator for Lexer<'input> {
  type Item = Spanned<Token, usize>;

  fn next(&mut self) -> Option<Self::Item> {
    match self.token_stream.next() {
      None => {
        None // on est a la fin du stream
      },
      Some((token, span)) => {
        match token {
          Token::Error => {
            Some(Err(ParseError::new(
              format!(
                "[{}][{}:{}]: unexpected token",
                self.filename, span.start, span.end
              )
            )))
          },
          _ => Some(Ok((span.start, token, span.end)))
        }
      }
    }
  }
}

Et juste comme ça, l'étape 1 de notre parseur, à savoir l'analyse lexicale, est faite.

Implémenter la grammaire

Cette étape va te rappeler votre expérience avec lex et yacc, ou pas si tu ne les as jamais utilisés.

On crée dans nos sources un fichier grammar.larlpop (c'est la que le build.rs entre en jeu, il va générer le module Rust qui correspond). Il va avoir une syntaxe très similaire à Rust. Voici son en-tête :

use lalrpop_util::{ParseError as GrammarError};

use crate::{
  ast,
  core::errors::ParseError,
  parser::tokens::Token,
};

grammar(unit_identifier: &String);

La dernière ligne indique les données en entrée que notre grammaire va utiliser. À l'avenir, il s'agira d'une structure contenant un peu plus d'information. En Letlang, chaque fichier de source va produire une unité de compilation, le unit_identifier sera un hash unique pour identifier cette unité de compilation. C'est tout ce dont j'ai besoin pour l'instant.

A la fin du fichier je vais ajouter les informations concernant le lexer que j'utilise :

extern {
  type Location = usize;
  type Error = ParseError;

  enum Token {
    "identifier" => Token::Identifier(_),
    // ...
    "int10" => Token::IntegerBase10(_),
    // ...
    "const" => Token::StatementConst,
    // ...
    ";" => Token::StatementSeparator,
    // ...
    ":=" => Token::OperatorAssign,
    // ...
  }
}

Maintenant, dès que je vais spécifier "identifier" dans ma grammaire, cela fera référence à mon token.

Ma règle de plus haut niveau sera Unit, correspondant à un fichier source :

pub Unit: Box<ast::Unit> = {
  <stmts:Statement*> => ast::Unit::new(unit_identifier.clone(), stmts)
}

Elle comprend un 0 ou plus Statement, et le code associé est la création du noeud de l'AST.

Je peux maintenant définir ma règle Statement :

Statement: Box<ast::Statement> = {
  "const" <i:"identifier"> ":=" <e:Expr> ";" =>? {
    match i {
      Token::Identifier(name) => Ok(ast::Statement::constant(name, e)),
      _ => Err(GrammarError::User {
        error: ParseError::new(format!("unexpected token: {:?}", i))
      })
    }
  },
  // ...
}

On a donc le pattern de token suivi à nouveau du code qui va produire le noeud de l'AST. Plusieurs choses :

• j'utilise =>? et non =>, pour produire un Result<_, _> au lieu de juste une valeur
• bien qu'il ne soit pas possible d'avoir autre chose que Token::Identifier, le compilateur ne sait pas le garantir, et si je refactor mon code, au moins j'aurais une erreur levée

Pour compléter mon exemple, voici la règle Expr :

Expr: Box<ast::expression::Expression> = {
  <n:"int10"> =>? {
    match n {
      Token::IntegerBase10(val) => {
        Ok(ast::expression::Expression::literal(
          ast::expression::Literal::int(val)
        ))
      },
      _ => Err(GrammarError::User {
        error: ParseError::new(format!("unexpected token: {:?}", n))
      })
    }
  },
  // ...
}

Oui, c'est un peu verbeux, je factoriserai le code plus tard, je préfère avoir quelque chose qui fonctionne d'abord.

Pour finaliser l'intégration de notre grammaire, dans le mod.rs du même dossier ou j'ai mis ma grammaire (src/parser/grammar.lalrpop) :

pub mod tokens; // contient le tokenizer Logos
pub mod lexer;  // contient le Lexer pour LALRPOP

lalrpop_mod!(pub grammar, "/parser/grammar.rs"); // pointe vers le module généré à partir de la grammaire

Une fois fait, on peut tester cela dans le main.rs :

use letlang::parser::{
  lexer::Lexer,
  grammar::UnitParser,
};

fn main() {
  let filename = String::from("main");
  let src = "const foo:=42;";

  let lexer = Lexer::new(&filename, src);
  let parser = UnitParser::new();
  let ast = parser.parse(&filename, lexer).unwrap();

  println!("{:?}", ast);
}

Et après exécution (j'ai fait le pretty print à la mano, car je suis sympa, enfin je crois) :

Unit {
  identifier: "main",
  statements: [
    ConstDecl(ConstDeclStatement {
      symbol_name: "foo",
      value: Literal(Integer(42))
    })
  ]
}

BOOM! L'AST a été généré! Je peux déjà le passer à mon compilateur qui va me générer le code Rust qui va bien. Bon en vrai je vais d'abord vérifier qu'il est correct sémantiquement, mais t'as compris le principe :)

Conclusion

LALRPOP et Logos sont une joyeuse découverte, qui va accélérer grandement l'écriture de la phase la plus pénible du compilateur : le parser.

C'est un couple de librairie à avoir dans son outillage pour peu que vous ayez à faire à des données textuelles (sisi, ça existe encore, tout n'est pas que JSON ou XML).

Je te remercie de m'avoir lu jusqu'au bout, voici une petite récompense :

Si tu as la recette…