Points clé analyse syntaxique – PF, Info4

Toujours bien suivre les trois étapes suivantes :

• écrire la grammaire et la laisser en commentaire ;
• écrire un analyseur pur basé sur analist et le tester ;
• enfin, décorer le programme précedent avec des arguments supplémentaires pour obtenir un analyseur informatif basé sur ranalist.

Cela vaut aussi bien pour les programmes basés sur le style

let analyseur : ... =
  let l = auxiliaire1 l in
  let l = auxiliaire2 l in
  let l = auxiliaire3 l in
  etc.

que pour les programmes basés sur des combinateurs comme

let analyseur : ... =
  auxiliaire1 -->  auxiliaire2 --> auxiliaire3
  etc.

Commencer par transformer une grammaire récursive à gauche en un grammaire récursive à droite.

Par exemple un non-terminal R qui répète X au moins une fois avec un séparateur ','

R ::= R ',' X | X

s'exprimera plutôt :

R ::= X ',' R | X

ou plutôt, en factorisant X :

R ::= X S
S ::= ',' X S | ε

Attention, l'analyseur informatif qui en découle doit être programmé en respectant l'associativité à gauche qui est initialement prévue pour le séparateur (',' ci-dessus). À cet effet on programmera l'aspirateur pour X comme un programme qui prend un argument supplémentaire transportant le contenu informatif de la séquence déjà parcourue – on peut le voir comme un accumulateur.

Ce petit morceau de code est à placer au début de la définition d'un analyseur lorsqu'il est récursif.

À cet effet p_NonTerminal ++> est généralement suivi de fun x -> ... où x capture le résultat rendu par p_NonTerminal .

Considérons un membre droit de règle de grammaire A B C traduit en analist par une composition séquentielle.

p_A --> p_B --> p_C

La version ranalist est obtenue en remplaçant --> par ++> fun selon le mécanisme décrit précédemment :

p_A ++> fun a -> p_B ++> fun b -> p_C fun c -> code_final

À l'endroit de code_final, on a la visibilité de a, b et c et on peut donc fabriquer une expression f a b c qui sera l'information retournée (par exemple un AST fait avec les sous-AST a, b et c). Mais on ne peut pas écrire simplement

p_A ++> fun a -> p_B ++> fun b -> p_C ++> fun c -> f a b c

car il faut retourner non seulement f a b c mais aussi la liste restant après aspiration successive d'un A par p_A, d'un B par p_B et d'un C par p_C. C'est d'ailleurs signalé au niveau du typage OCaml.

D'un point de vue grammatical on ajoute en fait un ε supplémentaire, ce qui revient à remplacer le membre droit A B C par A B C ε. Rien de gênant car ε est élément neutre. Dans le code avec analist, cela serait traduit par :

p_A --> p_B --> p_C --> epsilon

Et dans le code avec ranalist :

p_A ++> fun a -> p_B ++> fun b -> p_C ++> fun c -> epsilon_res (f a b c)

Ainsi tout va bien, vérifiez en passant que les exigences du typage sont satisfaites.