__________________________ SYNTEX 2.0 (d) rateur de Compilateur (C) J.F. LE TENO __________________________ S O M M A I R E 1/ Pr sentation 2/ Syntaxe 3/ Interface Utilisateur 4/ Ecrire grammaire LL(1) 5/ Copyright enregistrement logiciel Merci Alix ALIX pour les "moteurs". ------------- sentation ------------- Syntex est un G rateur de Compilateur bas sur un article d'Alix Alix paru dans les num ros 29, 31 et 35 de Pascalissime, et dont il reprend en grande partie les "moteurs". A partir d'un fichier texte contenant la grammaire du langage pour lequel on veut crire un compilateur, il g re le corps de l'analyseur syntaxique. La grammaire source doit crite avec la notation BNF (Backus-Naur Form) dans un fichier texte. Elle doit tre de la classe LL(1) pour tre compilable par d scente r cursive sans rebroussement, avec un seul symbole d'avance - comme celle du Pascal, par exemple -. ` Syntex implante alors en (Turbo) Pascal le corps d'un analyseur syntaxique pr dictif r cursif. + !! Attention !! Dans sa version actuelle, Syntex ne v rifie *PAS* que la grammaire est non contextuelle, non ambig e et LL(1). De plus, il n'effectue aucune correction, ni optimisation du texte source (traitement des r cursions gauche, factorisation gauche, limination des productions cycliques ou vides) ] Seul le squelette de l'analyseur lexical est produit. Il est donc n cessaire de l' crire. | Seul le squelette de la proc dure de traitement des erreurs syntaxiques est produit. Il est donc n cessaire de l' crire. O L'analyse s mantique est rer dans le corps de l'analyseur syntaxique. Retour Sommaire ---------------------------- Syntaxe BNF - Fichiers .Grm ---------------------------- Les fichiers contenant les descriptions grammaticales ont pour extension Grm. La syntaxe utilis e pour d crire la grammaire est d e de la notation de Backus-Naur (BNF). Le signe est utilis pour --------------------------------------------------------------------------- = s parer la d finition de son texte. | s parer les alternatives. [ ] encadrer les parties de d finition qui peuvent tre pr sentes z ro ou une fois. accolades encadrer les parties de d finition qui peuvent tre pr sentes z ro ou plusieurs fois. . termine une d finition (tableau des m ta-symboles BNF) La priorit est laiss e aux m tasymboles Crochets et Accolades sur le symbole |. e Afin de reconna tre les terminaux dans l'arbre syntaxique, Syntex impose les deux r gles suivantes: La liste des symboles de ponctuation, ie de tous les terminaux qui ne sont pas alphanum riques, doit tre donn e en d but du fichier .Grm, en pla ant les symboles entre guillemets. Les terminaux qui ne sont pas des symboles de ponctuation doivent d buter par une majuscule. Ce qui interdit galement l'usage des majuscules pour la d signation des noeuds non-terminaux. L'ordre dans lequel les r gles de syntaxes sont pr es dans le fichier est indiff rent; Dans le fichier TEST.GRM elles sont pr es par ordre de d rivation; elles peuvent tout aussi bien tre pr es dans le d sordre. A noter qu'une production peut s' tendre sur plusieurs lignes. Syntex accepte les commentaires dans les fichiers .Grm, condition de les placer entre '@'. + Voir les fichiers GRM fournis en exemple. Remarque tout fait personnelle: quel plaisir de voir que l'on peut crire automatiquement une partie importante de ce qui a crit la main! (Note personnelle (encore!): J'y suis particuli rement sensible pour m' tre 'coltin la main l' criture de l'interpr teur de WIZZ, un petit programme de trac de fonctions math matiques - en tenant compte du domaine de d finition - et de calcul scientifique. C' tait un tr s bon exercice p dagogique pour moi, mais comme toujours dans ce genre d'exercices, les vertues disparaissent rapidement d s qu'on l'a fait une fois. FdNote) Retour Sommaire ------------------------------------ Interface Utilisateur - release 2.0 ------------------------------------ Elle s'est consid rablement am e - voir la Version History - gr l'utilisation de Turbo Vision. L'utilisation est maintenant "intuitive" - comme on dit, histoire de rire un bon coup -, et l'aide est accessible en ligne par la touche F1. N Editer Debuggage Windows Fichier Generer Option Retour Sommaire Retour Sommaire File|New --------- Ouvre une nouvelle fen tre d' dition. File|Open ---------- Affiche la boite de s lection de fichier positionn e par d faut sur les fichiers d'extension GRM. File|Save ---------- Sauve le contenu de l' diteur courant dans un fichier, en passant ventuellement par la boite de s lection de fichier si le fichier n'est pas encore nomm File|Save As ------------- Sauve le contenu de l' diteur courant dans un fichier, en passant par la boite de s lection de fichier. File|Save All -------------- Sauve le contenu de tous les diteurs ouverts et ayant modifi Retour Sommaire Retour Sommaire Generate|Generate ------------------ re le corps de l'analyseur syntaxique correspondant la grammaire contenue dans la fen tre d' dition courante. f Le nom de l'analyseur reprend celui du fichier .GRM dont il descend, et lui ajoute l'extension .PAS. & Generate|Options ----------------- Permet de sp cifier si le code Pascal produit doit tre format comme un Programme ou comme une Unit Par d fault, c'est un Programme qui est g Generate|Make -------------- Permet de compiler le code Pascal produit par Generate afin de v rifier qu'il 'tourne' - afin ventuellement de modifier la grammaire. Retour Sommaire Debug|Syntax Tree ------------------ Affiche l'arbre syntaxique de la derni re grammaire analys Les branches peuvent tre d velopp es ou r duites afin de faciliter l'analyse de la structure de l'arbre. $ Debug|Key Words ---------------- Affiche la liste des mots-clef - les terminaux - de la derni re grammaire analys Debug|Ponctuation ------------------ Affiche le liste des caract res de ponctuation d finis dans la derni re grammaire analys Retour Sommaire Options|Video -------------- Passe de l'affichage sur 25 lignes l'affichage 43 lignes (EGA) ou 50 lignes (VGA). . Options|Save Desktop --------------------- Sauvegarde la configuration du bureau - fen tre ouvertes et param tres s lectionn s - sur disque. M ** Cette option n'est pas impl e sur cette version non enregistr e. ** . Options|Load Desktop --------------------- Restaure la configuration du bureau - fen tre ouvertes et param tres s lectionn s - pr alablement sauv e sur le disque. M ** Cette option n'est pas impl e sur cette version non enregistr e. ** Retour Sommaire Retour Sommaire ----------------------------------- Comment crire une grammaire LL(1) ----------------------------------- a. Survol structure compilateur b. L'analyse syntaxique descente cursive symbole vision c. Grammaire LL(1) d. Premier e. Corrections f. Consid rations diverses Retour Sommaire a/ Survol de la structure d'un compilateur ------------------------------------------- Un compilateur est un programme qui, partir d'un texte source crit dans un langage donn , produit une traduction. Il doit donc lire le texte source, v rifier qu'il est correct, et le traduire. Ces fonctions sont r parties entre diff rents modules. La lecture du source est effectu e par l'analyseur lexical, dont le r le est de d couper le source en unit lexicales correspondant au langage utilis - en mots -. } Vient ensuite l'analyseur syntaxique, qui a pour r le de v rifier que les suites d'unit s lexicales produites par l'analyseur lexical - les phrases -sont "grammaticalement" correctes, par rapport la grammaire du langage utilis . C'est g ralement l'analyseur syntaxique qui, au fur et mesure de ses besoins, demande l'analyseur lexical de lui fournir des unit s lexicales. Puis l'analyseur s mantique entre en jeux pour v rifier ces phrases grammaticalement correctes ont un "sens". Il lui revient en g ral de traiter les aspects contextuels du langage qui ne peuvent tre trait s par la grammaire qui, comme son nom l'indique, est non contextuelle. Parmi ces aspects contextuels, citons le contr le de type, l'existence et la visibilit des identificateurs, etc. Enfin, le dernier module produit la traduction. Cette phase peut tre trait e de fa ons bien diff rentes, avec production d'un code interm diaire, ou non, etc. Cette derni re phase, fortement d pendante de la machine d stination, est appell e la partie finale d'un compilateur, par opposition aux phases d'analyse (lexicale, syntaxique, et s mantique) qui sont regroup es sous le terme de partie frontale. Syntex est donc une machine fabriquer des analyseurs syntaxiques, ie des v rificateurs de correction grammaticale, partir d'une description de la grammaire souhait Il existe bien videmment plusieurs approches pour pratiquer une analyse syntaxique, de m me qu'il existe plusieurs types de grammaires. De plus, certains types de grammaires n cessitent l'utilisation de certaines approches, et r ciproquement. Dans le cas de Syntex, l'analyse syntaxique se fait par descente r cursive sur des grammaires de la classe LL(1). Voyons donc tout cela en d tail. Retour Sommaire b/ L'analyse syntaxique par descente r cursive avec un symbole de pr vision ---------------------------------------------------------------------------- Les Production - r gles de grammaire - contenues dans un fichier .Grm sont en fait des sch mas qu'une phrase doit suivre pour tre correcte vis vis de cette grammaire. Certains ments de ces sch mas sont eux-m crits dans le fichier .GRM comme des sch mas: ce sont des symboles non terminaux. D'autres de donne lieu aucun d veloppement: ce sont les symboles terminaux. \ velopper chacun de ces sch mas au sein d'une production s'appelle d river la production. D'autre part, certaines de ces productions tant r cursives, ou imbriqu es, il est n cessaire de disposer d'un point d'entrer unique, appel Axiome. L'ensemble des productions forme un Arbre Syntaxique (celui que construit Syntex) dont l'axiome est la racine. Les branches sont constitu es des productions, et les feuilles des symboles terminaux. L'analyse syntaxique descendante consiste rifier qu'une phrase est en tout point conforme aux productions; pour cela on v rifie d'abord que l'axiome est v , puis au fur et mesure que l'on avance dans la phrase, on d rive - d veloppe - les productions qui doivent tre mises en jeu, en fonction du symbole de pr vision. On "descend" ainsi dans l'arbre syntaxique, de la racine vers les feuilles (en informatique, une structure d'arbre a toujours la t te en bas). Une analyse syntaxique descendante proc de ainsi: Pour un symbole donn partir de la position courante dans l'arbre syntaxique, on d veloppe au maximum les productions possibles pour trouver le premier terminal. ^ Si le symbole et le terminal correspondent, on lis le symbole suivant dans la phrase, sinon, on parcourt les ventuelles alternatives de la production pour comparer le symbole avec les terminaux des alternatives, jusqu' trouver une correspondance, ou jusqu' puisement des terminaux possibles partir de cette position dans l'arbre syntaxique. y Si aucune correspondance n'est trouv e entre le symbole et les terminaux possibles, deux strat gies sont envisageables: h soit on rebrousse chemin jusqu' l'embranchement pr dent, pour essayer d' ventuelles alternatives, % soit on d clare qu'il y a erreur. Syntex impl mente la deuxi me alternative, qui correspond un analyseur pr dictif sans rebroussement avec un symbole de pr vision. Ce choix implique que la grammaire ait des propri s particuli res, que nous d taillerons plus loin. Retour Sommaire c/ Grammaire LL(1) ------------------- Il est possible de construire automatiquement un analyseur syntaxique par descente recursive sans rebroussement et avec un seul symbole d'avance partir d'une grammaire appartenant la classe LL(1) - c'est ce que fait Syntex. Un tel analyseur syntaxique s'appelle analyseur pr dictif r cursif, que nous nous contenterons d'appeler par son petit nom - "analyseur pr dictif". LL(1) signifie "Left to right scanning - Leftmost derivation" (ie. parcours du source de Gauche droite - d rivation Gauche); le "1" indique que chaque tape ne n cessite que la conna ssance du symbole qui suit pour d cider de la suite - d'o le qualificatif de "pr dictif" -. b En pr sence d'une production A, Syntex part la recherche des terminaux correspondants cette expression apr rivation, afin de d terminer la prochaine production invoquer. Il parcourt galement chaque alternative, si toutefois il y en a. Il produit ainsi une liste de tous les premiers terminaux accessibles apr rivation de la production A. " Pourquoi les premiers seulement? Parce que c'est une propri des grammaires LL(1), de toujours permettre de d cider de la production suivante utiliser la "vue" de l'unique symbole de pr -vision produit la demande de l'analyseur syntaxique par l'analyseur lexical. Retour Sommaire d/ Premier jet --------------- Il existe une d finition de la classe LL(1) qui permet de v rifier si une grammaire donn e est bien LL(1). Une grammaire donn e est de la classe LL(1) si et seulement si, chaque fois qu'elle contient une production de la forme A = B | C, k 1. Pour tout terminal a, B et C ne peuvent se d river tous les deux en a; ie. "partant de deux endroits diff rents, on doit aboutir deux destinations diff rentes". En effet, comme l'on d cide du traitement effectuer en fonction de la nature de la destination atteinte, on ne saurait plus s'il faut faire un traitement B ou un traitement C, il y a ambigu 2. B et C ne doivent pas tous les deux aboutir la cha ne vide; c'est dire que "l'un au moins des deux chemins doit aboutir quelque part". En effet, si B et C aboutissaient toutes les deux la cha ne vide, l'ambigu sur celle choisir pour le traitement r apparaitrait. 3. Si C aboutit la cha ne vide, B ne doit pas pouvoir aboutir un terminal que l'on peut trouver apr s A; ie on interdit des constructions du genre "if then then write('toto')" o l'on aurait la m me cha ne pour un identificateur et pour un mot cl , car l'analyseur syntaxique aurait le risque de "brancher" sur la mauvaise production, et de refuser une construction qui est pourtant correcte. ~ En pratique on ne v rifie pas syst matiquement que la d finition est respect e, mais on proc de en r digeant un premier jet pour sa grammaire, puis on effectue les corrections. Cette deuxi thode ne garantit pas que le r sultat soit dans la classe LL(1), car elle ne v rifie pas que la grammaire n'est ni ambig e ni contextuelle, mais elle fonctionne dans la majorit des cas. p Inspirez-vous des fichiers .Grm fournis en exemples pour voir le style adopter dans votre prose personnelle. Retour Sommaire e/ Corrections --------------- On peut effectuer deux types de corrections: des corrections sur la grammaire, et des corrections sur le code produit. Afin que la grammaire soit effectivement adapt la construction automatique d'un analyseur pr dictif, ses productions doivent viter certaines constructions, dont voici la liste. La R cursion Gauche: Une production est r cursive gauche lorsqu'elle est de la forme A = Aa, o 'A' est le nom de la production, et 'a' une cha ne quelconque situ droite de la production - la "suite de la production". On constate que la production A commence par s'appeler elle-m me. " Comment le probl me survient-il? L'analyseur syntaxique appelle l'analyseur lexical, et re oit en r ponse une unit lexicale. Supposons alors que pour traiter cette unit lexicale, il faille faire appel la production A. A appelle son tour la production A, qui est son premier terme, et cela sans passer l'unit lexicale suivante, puisque seul l'appel d'un ment terminal de la grammaire provoque la demande d'une nouvelle unit lexicale. L'analyseur syntaxique boucle alors r cursivement ind finiment sur la production A. Probl me. # Eliminer une r cursivit diate gauche revient transformer A = Aa|b en A = bA' et A' = [aA']. Il arrive parfois que la r cursivit gauche n'apparaisse qu'apr s avoir d une production au moins deux fois; ce dernier cas doit tre trait globalement - nous n'en dirons pas plus. # La non Factorisation Gauche: h Certaines productions peuvent tre de la forme A = BC | BD, o 'B','C', et 'D' sont des non terminaux. : Au cours de son fonctionnement l'anayseur syntaxique est amen traiter la production A, ayant sa disposition une unit lexicale relevant de la production B. Le probl me vient alors de ce qu'il lui est impossible de d cider " la seule vue de l'unit lexicale" - le "1" de "LL(1)", quelle alternative choisir. M Factoriser gauche consiste remplacer A = BC|BD par A = BA' et A' = C|D. Les cycles: z Une grammaire contient un cycle si une production A peut se trouver d e en A, apr ventuellement plusieurs tapes. Les productions vides: + Une production vide est de la forme A = . Concernant le code produit, la souplesse - relative - de Syntex par rapport la d finition stricte des grammaires LL(1) permet de g rer du code pour des grammaires "presque" LL(1), quitte faire quelques modifications par la suite sur le code lui-m Retour Sommaire f/ Consid rations diverses --------------------------- Lorsque Syntex cherche les premiers terminaux d'une expression accessibles par d rivation, si ces terminaux pr sentent des alternatives inclues dans un m tasymbole, seul le premier terminal de la premi re alternative est pris en compte. Notons que cette limitation n'est pas impos e par les grammaires LL(1) ni par la m thode d'analyse pr dictive r cursive. Cette difficult est facile contourner en retouchant l rement le code produit par Syntex. [ Syntex est lui-m me un compilateur, qui traduit le texte contenu dans le fichier .Grm en un programme TPascal plac dans un fichier .Pas. L'option "MakeTree" correspond ainsi la fonction d'analyse lexicale et syntaxique du texte source, alors que l'option "Generate" regroupe, elle, les fonctions d'analyse s mantique et de production de code. Bien que Syntex accepte l'imbrication des m tasymboles [] et Accolades sur une seule production, la phase de g ration de code partir de l'arbre syntaxique ne les traite pas. Il est alors n cessaire de passer par des sous-productions traitant ces imbrications. Syntex n'est pas - pour le moment (?) - un g rateur d'analyseur lexical, et seul le corps de cette proc dure est g automatiquement. Cependant, et bien qu'une structure proc durale base d'appels r cursifs soit un peut de la grosse artillerie - on passe plus traditionnellement par des automates construits partir d'expressions r res -, il est tout fait possible d'en passer par l pour certaines parties d'analyse lexicale; la grammaire Pascal des nombres r els donn e au chapitre /3 en est un exemple. Retour Sommaire -------------------------- SYNTEX rateur de Compilateur -- Release 2.0 (d) -------------------------- (C) J.F. Le T CompuServe ID 100346,3212 -------------------------- Ce programme n'est PAS dans le 'domaine public', et aussi g nial ou aussi nul qu'il puisse vous para tre, il repr sente un investissement personnel certain en temps et en sueur. Je n'exige en retour le versement d'aucune licence, mais j'appr cierais grandement un signe de vie - de solidarit , de reconnaissance ?!... - de votre part, si toutefois vous d cidez d'utiliser ce logiciel. Sentez-vous donc libre de m'envoyer ce qui vous semble bon (chocolat, coup de fil, mat riel inutilis , carte postale, quelques sous, ...) - cela fera office d'enregistrement; ceux d'entre vous qui ont d programm comprendront ... Je me ferais alors un plaisir de mettre les sources votre disposition, et je serais galement heureux de recevoir toute critique, tout conseil ou suggestion sur Syntex 2.0. L'Auteur. Retour Sommaire