Gestion Système d'Information

AMMAIRES - AUTOMATES

page 1

LesMathématiques.net

INTRODUCTION

Un compilateur est un utilitaire de traduction permettant, à partir d'un programme écrit dans un langage de "haut niveau" ou, du moins, compréhensible par un programmeur humain (C/C++, Pascal, Algol, FORTRAN, assembleur, ...), de vérifier la syntaxe du programme de départ, puis de produire un fichier en un langage de niveau plus bas, par exemple un fichier en code objet, exécutable par le système d'exploitation. Le premier langage de haut niveau qui a été écrit est le FORTRAN (« Mathematical FORmula TRANslating System ») ; son compilateur a été conçu et écrit dans les années 1954-57 par une équipe de pionniers super-programmeurs conduite par John W. Backus. Son écriture, soit 25 000 lignes de code machine enregistrées sur bande magnétique, a nécessité un travail équivalent à 18 hommes-années, bien plus important que ce que le projet initial prévoyait ; mais la direction d'IBM, dont dépendait ce projet, a eu l'intelligence de laisser le groupe libre de poursuivre son effort comme il l'entendait. Coup d'essai, coup de maître : le langage FORTRAN I a eu un succès énorme, et son compilateur a gardé durant vingt ans le record d'optimisation du code objet produit. Plus tard, le compilateur du PASCAL a été écrit en auto-amorçage : conçu « à la main » pour 60% environ du langage, le reste a été produit par ce qui était déjà compilé. De nombreux autres compilateurs ont suivi (par exemple YACC, "Yet Another Compiler of Compiler"). Durant les mêmes années 1955-65, des linguistes, philosophes et mathématiciens ont défriché la partie théorique en proposant une description et une classification des langages et des grammaires, pour les diverses langues naturellement utilisées puis pour les langages de programmation. Parmi eux, citons le linguiste Noam Chomsky, le mathématicien logicien Stephen Kleene, l'informaticienne Sheila Greibach, dont nous reverrons les noms dans ce cours.

1. Les tâches d’analyse d’un compilateur.

Les premières tâches d'un compilateur sont de faire : • l’analyse lexicale : reconnaître les éléments constitutifs de la chaîne entrée, c’est-àdire du code source, et en dresser la liste. • l’analyse syntaxique : vérifier la conformité avec les règles de constitution du code. Par exemple, l'expression (A+B)) = C est syntaxiquement incorrecte (parenthèses…). • l’analyse sémantique : analyser le sens et fixer une interprétation. Par exemple dans « si A alors si B alors C sinon D » , choisir à quel si se rapporte le sinon. Dans ce qui suit, nous nous occuperons essentiellement de l'analyse syntaxique.

2. La notion de grammaire et d’analyse syntaxique.

Considérons, par exemple, la phrase suivante : LE VIEUX CHAT ATTRAPE LE PETIT RAT Le but est de construire une grammaire qui permette de produire cette phrase.

M.P. Muller - LANGAGES - GRAMMAIRES - AUTOMATES

page 2

LesMathématiques.net Il faut tout d’abord préciser les « ingrédients » nécessaires : ce sera l’alphabet des symboles ou lexique. Dans notre cas, nous pouvons prendre comme alphabet l’ensemble Σ = {LE, VIEUX, PETIT, CHAT, RAT, ATTRAPE} ( il contient ici six symboles). Noter que le terme « alphabet » n’a pas ici le sens habituel A, B, C,…. : en fait, l’alphabet contient les « briques de base » avec lesquelles on peut former… tout ce qu’on veut pouvoir former ! Dans un langage de programmation par exemple, les mots réservés, balises, etc… comme program, real, , , … sont dans l’alphabet de symboles. Voyons maintenant comment ces symboles sont assemblés. Dans la structure de la phrase, on peut distinguer : • un groupe sujet • un verbe • un groupe complément d’objet (CO) Les groupes sujet et CO sont eux-mêmes des groupes nominaux : un groupe nominal est formé d'un article suivi d'un nom, lui-même précédé ou suivi d'adjectifs. Voici un exemple de (petite) grammaire pouvant produire notre phrase ; elle a onze règles de grammaire (on dit aussi de production, ou de réécriture) : 1 . 2. 3. 4. 5. 6. 7. 9. LE CHAT RAT VIEUX PETIT ATTRAPE

8 . 10. 11.

- Le point de départ s’appelle l'axiome. Dans notre exemple, c’est . - Les variables sont les « ingrédients » qui peuvent encore être remplacés par d’autres (, , , etc…). - Les règles 1 à 5 sont des règles syntaxiques (la première règle concerne toujours l’axiome). Les règles 6 à 11 sont des règles complètement terminales (ou : lexicales). - Le langage engendré par la grammaire est l'ensemble de toutes les phrases que l'on peut produire à partir de l’axiome en utilisant des règles de grammaire, une phrase étant une chaîne de symboles.

M.P. Muller - LANGAGES - GRAMMAIRES - AUTOMATES

page 3

LesMathématiques.net Voici maintenant quelques exemples de phrases « grammaticalement correctes », c'est-àdire des chaînes de symboles que l'on peut produire à partir de l'axiome, en utilisant les règles précédentes : LE RAT ATTRAPE LE PETIT CHAT LE CHAT ATTRAPE LE VIEUX CHAT On peut associer à chaque phrase ainsi produite un arbre de dérivation où figurent les variables auxquelles on a appliqué des règles de grammaire. Nous avons ajouté aux nœuds de cet arbre de dérivation, pour faciliter la compréhension, les numéros des règles qui ont été appliquées aux variables. Un arbre de dérivation pour la phrase LE RAT ATTRAPE LE PETIT CHAT est représenté dans la figure suivante.

1

2

11

3

4

5

6

8

6

10

7

LE

RAT

ATTRAPE

LE

PETIT

CHAT

M.P. Muller - LANGAGES - GRAMMAIRES - AUTOMATES

page 4

LesMathématiques.net

LANGAGES – LANGAGES REGULIERS 1. Définitions.

L’alphabet des symboles est un ensemble fini. On le notera en général Σ , dans la suite du cours. Exemple 1. Σ = { LE, CHAT, ..., VIEUX, ...} cf. l’introduction. Exemple 2. Σ ={0, l, 2, ...., 9, +, *, -, / , (, ) }. Cet alphabet permet d'écrire les expressions arithmétiques sur les nombres entiers, avec les quatre opérations et les parenthèses. Anticipons un peu : le premier problème sera de pouvoir distinguer si une expression est « correctement écrite » ; par exemple, 2*(31-6)+8 est correcte, mais 2(31-6)+8 ou encore (21+)*4 ne le sont pas. Le deuxième problème sera, pour une expression correctement écrite, de la calculer selon les règles de l’art, c'est-à-dire de respecter les priorités (donner la priorité à la multiplication sur l'addition, calculer d'abord ce qui est entre parenthèses, ...). Une chaîne est une suite finie de symboles. La longueur d'une chaîne est le nombre de ses symboles. Exemples. LE LE CHAT est une chaîne de longueur 3 sur l’alphabet de l’exemple 1. Les expressions arithmétiques (correctes ou non !) sont des chaînes sur l'alphabet de l’exemple 2. La chaîne vide, notée λ , ne contient aucun symbole ; sa longueur est nulle. On verra qu'elle est particulièrement utile ! Σn est l’ensemble de toutes les chaînes de longueur n. Σ0 = { λ } , par convention. Attention, cet ensemble Σ0 n’est pas vide : il contient la chaîne vide. Σ* est la réunion des Σn pour n ≥ 0. C'est donc l'ensemble de toutes les chaînes, chaîne vide comprise. Σ+ est la réunion des Σn pour n > 0 . On peut concaténer des chaînes de symboles, c’est-à-dire les « coller » les unes derrière les autres, de la même façon que plusieurs textes peuvent être assemblés les uns derrière les autres pour former un nouveau texte. Si u et v sont deux chaînes de symboles, leur concaténation sera notée u.v ou plus simplement uv . Un langage sur Σ est un sous-ensemble de Σ*. Exemples. Sur l’alphabet Σ = {a, b, c, d}, les ensembles suivants sont des langages : • L1 = {ac, abbc} • l’ensemble L2 de toutes les chaînes qui commencent par a. • L’ensemble L3 de toutes les chaînes de longueur paire. Notation. Afin de faciliter la lecture, nous adopterons en général une notation a, b, c, … pour des symboles de Σ et u, v, w, x, … pour des chaînes de symboles.

page 5

M.P. Muller - LANGAGES - GRAMMAIRES - AUTOMATES

LesMathématiques.net

2. Opérations sur les langages.

Un alphabet