Introduction
La définition et la mise au point d'outils d'analyse lexicale et
syntaxique ont été un important domaine de la recherche en
informatique. Ce travail a abouti à la réalisation des générateurs
d'analyseurs lexicaux et syntaxiques lex et yacc dont camllex et camlyacc, que nous présentons dans ce chapitre, sont
les dignes héritiers. Ces deux outils sont les outils rois du domaine,
cependant, d'autres, plus simples, comme les flots ou la bibliothèque
d'analyse des expressions rationnelles (ou expressions
régulières) Str sont suffisants pour des application
ne nécessitant pas une analyse puissante.
La nécessité de tels outils s'est essentiellement fait sentir dans
le domaine de la compilation des langages de programmation
évolués, mais d'autres applications peuvent mettre en oeuvre
avec profit de tels outils : les systèmes de bases de données qui
offrent la possibilité de formuler des requêtes, les tableurs qui
définissent le contenu de certaines cases comme résultat de
l'évaluation d'une formule. En un mot, toute application dont
l'interaction avec l'utilisateur se fait au moyen d'un
langage met en oeuvre les analyses lexicale et syntaxique.
À un niveau plus modeste, il est fréquent d'utiliser un format ASCII
pour stocker des données : fichiers de configurations systèmes,
données d'une feuille de calcul. Là encore, l'exploitation de ces
données nécessite une phase d'analyse lexicale et
une phase d'analyse syntaxique.
Dans les cas simples comme dans les cas compliqués, le problème que
doit résoudre l'analyse lexicale et syntaxique est la transformation
d'un flot linéaire de caractères en une donnée à la structure
plus riche : une suite de mots, une structure d'enregistrements,
l'arbre de syntaxe abstraite d'un programme, etc.
Tout langage possède un vocabulaire (le lexique) et une grammaire
permettant d'assembler correctement les éléments du vocabulaire
(la syntaxe). Pour qu'une machine, ou un programme, soit capable de
traiter correctement un langage, celui-ci doit obéir à des
règles lexicales et syntaxiques très précises. Une machine n'a
pas << l'esprit de finesse >> requis pour prendre une décision
face à l'ambiguïté des langues naturelles. Il convient donc de
s'adresser à elle selon des règles clairement fixées ne
souffrant pas d'exception. Aussi, les notions de lexique et de syntaxe
ont-elles reçues des définitions formelles que nous
présentons brièvement dans ce chapitre avant d'en montrer les
applications.