Rust offre de très bons parseurs BNF, mais ils sont généralement pensés pour le backend. Avec la compilation en WebAssembly, ce n'est plus réellement un problème. Dans cet article, nous construisons les base d'un bac à sable interactif avec Leptos et Trunk pour debugger des BNF entièrement dans le navigateur.
Des regex...
Récemment, j’ai dû analyser des références bibliques dans le contenu de publications quotidiennes couvrant plus de 15 ans et des dizaines d’auteurs. Par exemple, « Jn 12.3-4 » désigne les versets 3 et 4 du 12ᵉ chapitre de l’évangile de Jean — mais « Joh 12.3,4 » ou « J12.3 et 4 » signifient la même chose, selon l’auteur.
Comme tout le monde, j’ai commencé par des regex. Beaucoup de regex. Comme celle-ci :
let main_regex = Regex::new(
r"(?:(?P<book>\d?[\wÉéèêîïâäàçôöûü]+)[ ]+)?(?P<verses>(?:(?:(?:\d+)[: ]+)?(?:(?:(?:\d+)-(?:\d+))|(?:\d+))(?:,|,[ ]|[ ]et[ ])?)+)"
)?;
let chapters_regex = Regex::new(
r"(?:(?P<chapter>\d+)[: ])(?P<verses>(?:(?:(?:(?:\d+)-(?:\d+))|(?:\d+))(?:,|,[ ]|[ ]et[ ]))*)(?P<last>(?:(?:(?:\d+)-(?:\d+))|(?:\d+))$)?",
)?;
let verse_range_regex = Regex::new(
r"(?:(?:(?:(?P<start>\d+)-(?P<end>\d+))|(?P<verse>\d+))(?:,|,[ ]|[ ]et[ ])?)"
)?;
... aux formes Backus–Naur
Fatigué de bricoler ce genre de monstres et ayant une patience très limitée pour déboguer ce genre de choses — même avec un bac à sable en ligne — j’ai exploré d’autres techniques.
Les formes Backus–Naur (BNF) en sont une. C’est une représentation formelle d’une grammaire (un ensemble de règles décrivant ce qui est un entrée valide ou non). Par exemple, un nombre pourrait être défini ainsi :
<number> ::= <digit> | <number> <digit>
<digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0'
C’est très formel, j’en conviens. On n’a pas les jolis raccourcis et plages de caractères des regex. En fait, au sens le plus strict, BNF décrit un ensemble plus vaste : les grammaires hors-contexte. (Mais en pratique, la plupart des implémentations de regex modernes disposent de fonctionnalités supplémentaires qui leur permettent de dépasser leur définition théorique).
L’avantage, c’est qu’on obtient une description expressive de ce à quoi une phrase doit ressembler pour respecter une grammaire. L’exemple précédent se lit ainsi :
Un chiffre est l’un des caractères 1, 2, 3, 4, 5, 6, 7, 8, 9 ou 0 Un nombre est soit un chiffre seul, soit un chiffre suivi de quelque chose qui est un nombre
Cette expressivité rend la BNF idéale pour décrire des spécifications formelles.
Analyseurs syntaxiques
Comme on peut s’en douter, il existe des analyseurs pour les BNF. J’ai utilisé par exemple la bibliothèque Rust bnf crate. Rust est particulièrement adapté à ce type de parsing.
Elle fonctionne bien, en construisant un arbre représentant le résultat de l’analyse. Dans l’exemple précédent, on obtiendrait :
<number> ::= <number> <digit>
├── <number> ::= <digit>
│ └── <digit> ::= "1"
│ └── "1"
└── <digit> ::= "2"
└── "2"
Côté frontend
Parfait, nous avons un moyen de décrire des grammaires, et un analyseur. Si seulement on pouvait avoir un petit bac à sable pour les tester ! On pourrait créer un petit serveur pour ça, et un frontend React…
Attendez ! Pourquoi ? Autant l’exécuter directement dans le navigateur !
Est-ce que ça marche ? Parfaitement !
Leptos et Trunk
Leptos est un framework web Rust, qui supporte le rendu côté serveur (SSR) et le rendu côté client (CSR, via Trunk). Pour commencer :
cargo install trunk
cargo init epigrammars
cd epigrammars
cargo add leptos --features=csr
cargo add bnf
rustup target add wasm32-unknown-unknown
Ensuite, on peut créer notre application :
ajoutons simplement deux zones de texte.
La réactivité est assurée avec des signals.
On les relie à prop:value et on:input:target sur les champs texte.
Dans notre vue, on affiche la saisie et la grammaire en dessous.
use leptos::prelude::*;
fn main() {
leptos::mount::mount_to_body(App)
}
const EXAMPLE_GRAMMAR: &str = r#"<number> ::= <digit> | <number> <digit>
<digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0'
"#;
#[component]
pub fn App() -> impl IntoView {
let (grammar, set_grammar) = signal(EXAMPLE_GRAMMAR.to_string());
let (input, set_input) = signal("12".to_string());
view! {
<div>
<h2>Grammaire</h2>
<textarea
on:input:target=move |ev| { set_grammar.set(ev.target().value()); }
prop:value=grammar />
</div>
<div>
<h2>Entrée</h2>
<textarea
on:input:target=move |ev| { set_input.set(ev.target().value()); }
prop:value=input />
</div>
<p>Entrée : {input}</p>
<p>Grammaire : {grammar}</p>
}
}
Pour l’instant, grammar est de type ReadSignal<String>.
On voudrait l’analyser en une structure de grammaire BNF,
et la mettre à jour si l’entrée change.
Pour dériver de nouveaux signals à partir d’existants,
et ne recalculer que si les valeurs changent,
on peut utiliser Memo :
let parsed_grammar: Memo<Result<Grammar, String>> = Memo::new(
move |_| match Grammar::from_str(&grammar.get()) {
Ok(grammar) => Ok(grammar),
Err(bnf::Error::ParseError(e)) => Err(format!("Grammaire invalide : {:}", e)),
Err(e) => Err(format!("Échec de l’analyse, erreur inconnue : {:#?}", e)),
}
);
Dans la fermeture de Memo, il faut récupérer la valeur courante
du signal dépendant (grammar.get()).
On peut alors dériver un autre signal avec l’analyse de l’entrée :
let output = Memo::new(move |_| match parsed_grammar.get() {
Ok(grammar) => {
let binding = input.get();
grammar
.parse_input(&binding)
.map(|output| format!("{}", output))
.collect::<Vec<_>>()
.join("\n")
}
Err(message) => message,
});
Et enfin, l’afficher :
<pre> {output} </pre>
Aller plus loin
Cet exemple très simple peut être amélioré, par exemple en ajoutant un composant récursif pour afficher les nœuds imbriqués, et des boutons pour choisir la règle de production avec laquelle analyser.
