Par Richard A. Sevenich mailto:rsevenic@penguin.sirti.org
par Richard A. Sevenich, Département d'Informatique, Université Washington Est, le 25 mars 1999.
Traditionnellement, dans le monde UNIX, il y a deux outils complémentaires de construction de compilateur qui sont disponibles:
Ces outils sont disponibles librement dans le monde GNU/Linux, habituellement gratuits, dans certains cas sous license GPL. Il faut noter que l'analyse lexicale et syntaxique sont deux des tâches de base à réaliser par un traducteur de langage. Un lexer et un parser construits avec les outils ci-dessus n'accomplissent pas automatiquement une troisième tâche cruciale, la génération de code cible. Cependant, ces outils fournissent au programmeur des possibilités de greffe faciles pour incorporer la génération de code cible.
Plus loin dans cette série d'article j'espère faire l'introduction de deux de ces outils, JFlex et CUP, en mettant en place un cours d'initiation. Je m'assurerais du concours de plusieurs étudiants comme co-auteurs du cours de conception de compilateurs. Finalement, j'espère convaincre ceux qui ne sont pas familiers avec ces outils qu'ils sont très pratiques. J'ai choisi JFlex et CUP parce qu'ils produisent du code java et il est grand temps pour moi d'apprendre un peu java. Cette ignorance de java me fournira aussi un bouc émissaire si je fais quelque chose d'idiot - je peux faire retomber le blâme sur cette ignorance.
Ce premier article fournira la base pour la série. Le prochain article, qui devrait suivre assez rapidement, montrera comment/où obtenir ces outils, donnera un scénario d'installation très particulier, et produira une application simple comme exemple de développement. Un troisième article donnera un exemple pratique du monde réel (décrit plus bas). Si le troisième article devient trop lourd, il pourra être découpé en plusieurs parties.
L'Analyseur Lexical (c-à-d 'lexer' ou 'scanner')
La traduction de langage convertit un code source écrit dans certain langage en un code cible dans un autre langage. Le compilateur "traditionnel" peut convertir le code source en langage assembleur ou même en code machine - bien que les prochains articles dans cette série se concentreront sur d'autres cibles que celles-là. La première tâche d'un traducteur de langage est voisin de l'examination d'une rédaction anglaise pour s'assurer que les mots sont écrits correctement. Le lexer accomplit ce travail sur notre code source en reconnaissant une série de symboles continus comme valide ou invalides, par exemple le lexer pourrait :
Le lexer est analogue à un contrôleur d'orthographe pour code source.
Un utilitaire comme JFlex construit un lexer à partir d'un fichier de spécifications que le programmeur écrit pour définir les 'mots' (les tokens lexicaux, token lexical = unité lexicale) dans le langage désiré. Disons que le programmeur définit un nouveau langage appelé pronto et écrit un fichier 'pronto.flex' qui définit les tokens lexicaux valides pour pronto. Alors l'opération sur la ligne de commande 'JFlex pronto.flex' produira une version java d'un analyseur lexical, disons "Lexer.java".
Dans son utilisation la plus rudimentaire, le lexer indique simplement que le fichier source est seulement constitué de tokens valides ou non - il retourne un booléen. La famille de lexers dont on parle est conçue pour faire plus et, en particulier, peut coopérer avec des parsers (analyseurs syntaxiques décrits plus bas). Dans une application typique le lexer est en fait appelé par le parser et le lexer peut réaliser les tâches suivantes :
Le premier des trois de la liste ci-dessus permet au lexer de supporter la tâche centrale du parser, l'analyse syntaxique. Les deux autres sont particulièrement utiles pour aider le parser dans la génération finale du code cible.
L'Analyseur Syntaxique (c-à-d le parser)
Si l'on continue l'analogie commencée dans la section précédente, tout comme le lexer contrôle l'orthographe des mots, le parser examine le code source pour s'assurer que les 'mots' sont arrangés en des constructions grammaticales valides. Par exemple, pour certains nouveaux langage de programmeurs le lexer peut passer ces six tokens valides au parser:
{ if + while ] } - le lexer se soucie seulement de la validité des tokens, pas de leur arrangement. Cependant, le parser voit l'arrangement '{ if + while ] }' comme invalide. Tout comme le lexer est un contrôleur d'orthographe de code source, le parseur est un analyseur grammatical.
[A noter: ceux qui s'intéressent aux compilateurs s'apercevront que le lexer contrôle en fait la validité du code source à partir des spécifications très simples d'une 'grammaire régulière' et que le parser contrôle le code source à partir de spécifications moins simples d'une 'grammaire non contextuelle' - comme définie dans la hiérarchie de Chomsky. Les livres classiques de conception de compilateurs discutent à souhait de la théorie.]
Un utilitaire tel que CUP construit un parser à partir d'un
fichier de spécifications écrit par le programmeur pour
définir la structure syntaxique dans le langage désiré. Pour le
nouveau langage fictif appelé pronto, le programmeur
pourrait créer le fichier de spécifications pronto.cup.
Alors l'opération sur la ligne de commande
java java_cup.Main < pronto.cup produira plusieurs fichiers dont l'un est
la version java de l'analyseur syntaxique désiré, parser.java.
Dans son uilisation la plus primaire, le parser indique que le fichier source est soit grammaticalement correct soit le contraire - à nouveau, un booléen. La famille des parsers dont on parle peut effectuer des tâches supplémentaires - toutes les fois qu'une construction grammaticale correcte est trouvée, exécuter n'importe quel code que le programmeur daigne encoder. Cette astuce (NDT: hook, aussi crochet, dans le jargon des programmeurs) est typiquement utilisée pour gérer la génération de code cible dans deux styles d'exécution:
Langages Spécifiques pour Application
Les outils de construction de compilateurs dont on parle peuvent être utilisés pour développer un traducteur de langage complet par exemple pour le C, le Pascal, le FORTRAN, le Perl, etc. Cela pourrait inclure des projets de développement majeurs. Je parlerais ici des traducteurs pour les 'Langages Spécifiques pour Application', typiquement un projet plus modeste, mais déjà assez utile. Je définirais un 'Langage Spécifique pour Application' (LSA) opérationnel, par le biais de deux exemples.
Exemple 1 - Un langage de contrôle industriel généraliste
Disons que Fred travaille pour une compagnie qui produit des contrôleurs industriels, qui sont pilotés par un ordinateur. Lorsque Fred est engagé, la compagnie a déjà développé et déployé un langage de contrôle à but généraliste puissant reposant sur une machine à état parallèle généraliste. Cependant, les clients doivent devenir programmeurs pour utiliser le contrôleur, or ils sont ingénieur chimiste, ingénieur en mécanique, techniciens etc. et n'ont ni le désir ni le temps d'apprendre un nouveau langage générique. Le produit est vraiment générique, utile dans beaucoup d'industries spécialisées - automobile, pétrole, scieries, contrôle de satellite etc.
Fred a été embauché pour créer une interface au langage pour chacun des crénaux exploitables. Dans chaque cas, l'interface doit être adaptée à la terminologie utilisée par le client et facile d'utilisation. L'interface pourra être du style 'remplir les blancs', une interface graphique utilisateur (GUI), n'importe quoi. Les interfaces sont en fait de nouveaux langages avec tous le même langage cible (le langage de contrôle générique). Chaque interface est un exemple de LSA. En utilisant les outils de construction de compilateurs (par exemple JFlex et CUP), Fred capitalise plusieurs bénéfices dont:
Exemple 2 - un logiciel générique de prise de décision basé sur la Logique Floue
Il a été prouvé que la Logique Floue était très utile, pas seulement dans son rôle traditionnel dans les contrôles industriels, mais aussi dans le rôle de prise de décisions. Elle peut être utilisée pour jouer à la bourse (et perdre de l'argent plus élégamment ?), pour choisir parmi les recherches d'une entreprise ou les stratégies marketing, pour aider dans la prédiction des avalanches etc.
Supposons qu'un alter-ego de Fred, Sally, a programmé un logiciel générique de prise de décisions basé sur la Logique Floue. Pour l'appliquer à différents problèmes il est initialisé à partir de différents fichiers de données appropriés. Sally commercialise ce produit dans différents crénaux, mais trouve le client final un fardeau qui prend son temps. Le problème est en fait inhérent à la manière dont la Logique Floue fonctionne. Le client est l'expert dans le domaine de son problème particulier. Un modèle de Logique Floue est initialisé en incorporant l'expertise de l'utilisateur. L'utilisateur gagne plus d'expertise au fur et à mesure que le modèle est utilisé et veut constamment tirer le maximum du modèle. Le noeud du problème de Sally est que le fichier d'initialisation qui doit être préparé doit être programmé avec beaucoup de précaution. Les clients ne sont pas programmeurs et font facilement des erreurs (la plupart syntaxiques) en préparant de tels fichiers de données. Ils rencontrent toujours des problèmes, appellent Sally à l'aide, et s'attendent à ce qu'elle le fasse dans un court délai. Elle doit répondre au mieux pour maintenir sa réputation et son succès financier.
Sa solution est de faire une interface 'pour les nuls' qui automatisera les fichiers de données d'initialisation. L'interface est adaptée à la terminologie du client et à son domaine de problèmes. L'interface est un LSA avec le fichier de données d'initialisation comme langage cible. Le traducteur peut être écrit à l'aide des outils de construction de compilateurs, comme l'a fait Fred pour le scénario de contrôle industriel. Le traducteur garantit que le contenu lexical et syntaxique du fichier de données est correct.
Si l'interface est définie intelligemment le client la trouvera utile. A noter que le client est l'expert sur le problème sémantique, là où le programmeur (Sally) est la plus faible. Le client résoudra le problème sémantique, et le traducteur LSA évitera les problèmes lexicaux et syntaxiques relatifs au fichier de données d'initialisation.
Résultat
Les deux exemples précédents ont un point commun évident. Il faudrait insister sur le fait que pour la conception de l'interface, Fred et Sally doivent intéragir de façon importante avec le client spécialiste. Après tout, le LSA doit être utile à un programmeur débutant qui, en même temps, a l'expertise du domaine des problèmes. Si cette interaction échoue, le LSA ne sera pas correctement accepté et pourra échouer dans le marché attendu.
L'exemple de la Logique Floue est, en fait, le projet de cours de la classe de conception de compilateur de quatrième - en supposant que Sally ne réussira pas avant nous.
Copyright 1999, Richard A. Sevenich - Publié dans le numéro 39 de la Linux Gazette, avril 1999
Adaptation française : Frédéric Gacquer (Neuronnexion)