Parser
Un parseur construit un AST à partir d'une séquence de jetons selon des règles grammaticales, en deux familles : descendante (descente récursive/LL) et ascendante (LR/LALR).
Objectif
Structurer les jetons en un arbre de syntaxe — le cœur des compilateurs et des outils d'analyse.
Mécanisme
LL(k) : de gauche à droite, dérivation la plus à gauche, k jetons d'anticipation. LR(k) : de gauche à droite, dérivation la plus à droite. Descente récursive : écrite à la main, une fonction par non-terminal. PEG utilise le choix ordonné et le retour arrière.
Cas d’usage
- Implémentation de compilateurs
- Analyse de formats de données
- Langages dédiés (DSL)