Evolution des compilateurs et parseurs

Le nom "compilateur" semble avoir été inventé en 1952 par Grace Hopper. C'est vers cette époque qu'est implémenté pour la première fois ce qui peut être considéré comme un parseur. Cependant le compilateur de Grace Hopper n'a rien à voir avec ce qu'on appelle maintenant un compilateur: un outil qui convertit un langage dans un autre, généralement de plus bas niveau. Les assembleurs existaient avant les compilateurs, mais un assembleur est seulement une représentation textuelle du code binaire, la traduction se fait avec une simple table de correspondance.

Compilateur meta-circulaire (1951)

Corrado Böhm décrit dans une thèse un programme qui traduit un langage compasé d'assignement et expression en code machine. Meta-circulaire signifie que le compilateur est écrit dans le langage qu'il compile.

Autocode (1952)

C'est un ensemble de macro instructions qui sont traduites en langage machine. Il n'y a pas de technique particulière derrière cet outil.

IT (1956)

Le Carnegie Institute de Technology fait connaître le compilateur IT fonctionnant sur IBM 650. Le langage comporte des expressions arithmétique mais pas de précédence sur les opérateurs.

Hiérarchie de Chomsky et grammaire non contextuelle (1956)

Dans une monographie publiée en 1956, Chomsky présente la structure d'un vrai compilateur:

A la même époque, il invente le contexte de grammaire non-contextuelle: elle est composée de règles ou x se définit par un groupe d'élement, et x est indépendant du contexte où il apparaît. Une telle grammaire s'écrit facilement en BNF, un format qui apparaîtra plus tard.

Fortran (1957)

Le premier langage de évolué, créé par John Backus n'utilise pas la structure de Chomsky, ou une technique particulière, mais traite les programmes ligne par ligne. Pour obtenir la précédence, il utilise une astuce, il entoure les parties de l'expression autour d'un opérateur avec des paires de parenthèses dont le nombre dénote leur importance, et la décortication des expressions aboutit à la précédence de la multiplication sur l'addition.
La plupart des constructs de Fortran ne sont apparus que dans les versions suivantes.

Lisp (1958)

Le premier compilateur Lisp n'est pas plus élaboré que le compilateur Fortran, puisque le programmeur doit lui-même ajouter des parenthèses pour lui indiquer comment transformer le code.

BNF (1958)

John Backus et Peter Naur utilisent une notation originale qu'ils utiliseront pour décrire la grammaire du language Algol 58: La forme de Backus-Naur, ou BNF.

Exemple de grammaire BNF:

<ifelse> ::= <if> [ { else <if> } ]

<if> ::= if "(" <condition> ")" ( <instruction> | "{" { <insttuction> } "}" ) 

Précédence (1959)

Une implémentation théorique de la précédence des opérateurs est démontrée par Samuelson et Bauer par l'utilisation d'une pile.

Algol (1960)

Le premier langage structuré basé sur une grammaire décrite en BNF. La description d'un parseur ALGOL est publié par Ned Irons.
Algo 60 comporte des blocs d'instructions et supporte la récursivité, des concepts nouveaux alors. Il comporte aussi des tableaux dynamiques, C et Pascal ont donc été des régressions sur ce plan.

Parseur récursif descendant (1961)

Peter Lucas et Ned Irons tous deux décrivent un parseur descendant récursift. Celui-ci par d'une règle initiale qui fait référence à d'autres régles et interprète ainsi le langage en suivant la hiérarchie de leur compostion. En outre une règle peut faire référence à elle-même et être récursive comme c'est le cas dans la description BNF ci-dessus quand une instruction, qui est partie de la règle "if", est aussi une règle "if".

Algorithme Shutting-Yard de Dijkstra (1961)

A partir d'une expression artithmétique avec parenthèses ou non (et donc par reconnaissance de la précédence), cet algorithme produit un arbre syntaxique abstrait.Il utilise une pile et produit une notation infixe (dite polonaise) ou un opérateur suit une paire d'opérandes avec ceux de plus grande priorité arrivant en fin de chaîne.

Parseur LR (1965) et LALR (1971)

Inventé par Donald Knuth, un parseur LR lit une grammaire non contextuelle de la partie gauche vers la partie droite.

On peut avoir un parseur SLR (Simple Left-Right) inventé en 1969 par Frank DeRemer, ou LALR (Look-Ahead Left-Right) imaginé par le même en 1971. Dans le second cas tente une correspondance entre la règle de grammaire et l'instruction du code source et en cas d'échec, on revient au premier élement et tente une alternative. Un message d'erreur est émis quand aucune alternative ne correspond.
On écrit LR(k) ou k désigne le nombre de "lookaheads", de niveaux que l'analyseur explore dans le code source avant de décider qu'une règle s'applique pour une instruction.

En 1968, Donald Knuth améliore le concept d'attribut synthétique de Iron (1968) avec les attributs hérités. Alors que les attributs synthétiques définissent un noeud à partir des noeuds inférieurs, on a un attribut hérité quand un noeud utilise au contraire les attributs du noeud parent.

Parseur LL (1968) et LR

Imaginé par Lewis and Stearns, le principe LL s'applique à une grammaire conçue pour être analysée par un parseur simplifié et que l'on puisse écrire à la main.

Un parseur LL analyse une instruction de gauche et droite et du haut vers le bas, il construit une représentation de l'instruction en remplaçant chaque noeud par le groupe de noeud qui le définissent.

Un parseur LR analyse une instruction de gauche à droite également, mais du bas vers le haut, autrement dit il considère les noeuds terminaux et les combine pour retrouver le noeud de plus haut niveau.

Algorithme CYK (1960+)

Conçu pour parser des grammaires non contextuelles, utilisant l'analyse ascendante et la programmation dynamique, il se montre efficace dans des cas de figures spécifiques, mais les autres méthodes le dépassent dans la moyenne des cas.

Parseur de Earley (1970)

Jay Earley a inventé un algorithme en 1968 capable d'analyser la plupart des grammaires non contextuelles, qu'il a simplifié en 1970. Cependant il était lent à l'exécution et d'autres techniques se sont imposées pour les compilateurs populaires. Une version plus rapide en a été trouvée plus tard.

Parseur GLR (1974)

Un parseur GLR (Generalized LR), est une extension de LR pour des grammaires ambigues comme celle de C. Un algorithme qui l'implémenté a été décrit par Bernard Lang, et amélioré depuis 1974.
Les langages C, C++, etc... sont parsés par une version de cet algorithme par la plupart des compilateurs.

Yacc (1975)

Basé sur LALR, c'est le premier générateur automatique de parseur, réalisé par Stephen Johnson chez ATT pour Unix.
Le compilateur C passe passe alors d'un simple parseur récursif descendant à LALR. Mais Yacc ne sera disponible pour le public qu'en 1979.

Yacc a été utilisé par GCC, puis pour Awk, R, Ruby, etc...

GCC et CLang

GCC a longtemps utilisé Yacc, mais en 2004, les compilateurs C et Objective-C remplacent Yacc par un parseur descendant récursif écrit manuellement. Il procure un gain de vitesse minimal de 1.5%. Le compilateur C++ a suivi.
CLang utilise un parseur similaire pour tous les langages.

ANTLR (1989)

Basé sur un algorithme LL(k), ANTLR, créé par Terence Parr est sans doute l'outil de génération de parseur le plus utilisé. La version 4 qui se dit ALL(k), et qui est une combinaison de LL(k) et GLR, fonctionne soit avec des listeners ou des visiteurs, et permet d'analyser pratiquement toute grammaire. L'écriture d'un compilateur devient beaucoup plus simple et dans la version listener, facilite aussi les multiples langages cibles.

Voir aussi:

Auteur: Denis Sureau, créateur des langages Scriptol et Cryonie.