Analyse syntaxique et interprétation

21.1 Introduction et motivation

Comment une machine comprend-elle "3 + 4 * 2" et répond 11 (et non 14) ? C'est le travail d'un interpréteur, et c'est l'occasion d'un projet qui rassemble presque tout le livre. Le traitement se fait en trois étapes, une véritable chaîne de montage :

L'analyse lexicale (lexing) découpe la chaîne (chapitre 6) en lexèmes (nombres, opérateurs, parenthèses) ; l'analyse syntaxique (parsing) les organise en un arbre de syntaxe (un type somme récursif, chapitre 3) qui respecte les priorités ; l'évaluation parcourt cet arbre (comme au chapitre 3). Le parser s'écrit par descente récursive — un bel usage de la récursion mutuelle (chapitre 1).

21.2 Analyse lexicale

Un lexème est une unité de sens. Pour l'arithmétique, on en a six :

type lexeme = Nombre of int | Plus | Moins | Fois | ParenG | ParenD

L'analyseur lexical parcourt la chaîne, ignore les espaces, reconnaît les opérateurs et les parenthèses, et regroupe les chiffres consécutifs en un nombre.