LLLLaaaannnnggggaaaaggggeeeessss,,,, GGGGrrrraaaammmmmmmmaaaaiiiirrrreeeessss,,,, AAAAnnnnaaaallllyyyysssseeeessss,,,, CCCCoooommmmppppiiiillllaaaattttiiiioooonnnn UUUUnnnneeee iiiinnnnttttrrrroooodddduuuuccccttttiiiioooonnnn CCCCoooouuuurrrrssss////TTTTDDDD////TTTTPPPP Jacques Rouillard Illustration de couverture : voir note 2 page 16 Table des Matières 1 GRAMMAIRES ET CLASSIFICATIONS [COURS/TD].......................................................................5 1.1 DÉFINITION...........................................................................................................................................5 1.2 NOTATION............................................................................................................................................5 1.3 CLASSIFICATION...................................................................................................................................6 1.4 EXERCICES............................................................................................................................................8 2 PREMIER, SUIVANT [COURS/TD]......................................................................................................11 2.1 PREMIER.............................................................................................................................................11 2.2 SUIVANT.............................................................................................................................................11 2.3 EXERCICES..........................................................................................................................................12 3 ANALYSE PAR LA DROITE, PAR LA GAUCHE [COURS]............................................................13 4 EXPRESSIONS RÉGULIÈRES: ANALYSE PAR AUTOMATE D'ÉTATS FINIS [COURS/TD]..15 4.1 NOTATIONS.........................................................................................................................................15 4.2 AUTOMATES DÉTERMINISTES..............................................................................................................15 4.3 AUTOMATES NON DÉTERMINISTES......................................................................................................16 4.4 RENDRE DÉTERMINISTE UN AUTOMATE À ÉTATS FINIS NON DÉTERMINISTE........................................16 4.5 EXERCICES :........................................................................................................................................22 5 GRAMMAIRES HORS CONTEXTE: ANALYSE DESCENDANTE LL [COURS/TP]...................23 5.1 DÉFINITION.........................................................................................................................................23 5.2 ÉCRIRE UN INTERPRÉTEUR LL1 EN C..................................................................................................24 5.3 FAIRE FACILEMENT UN GÉNÉRATEUR D’INTERPRÉTEURS LL1............................................................27 6 GRAMMAIRES HORS CONTEXTE: ANALYSE ASCENDANTE LR [COURS]...........................29 6.1 DÉFINITION.........................................................................................................................................29 6.2 ALGORITHME D'ANALYSE SLR 1........................................................................................................31 6.3 LEX/FLEX ET YACC/BISON/BYACC.......................................................................................................38 6.4 LEX....................................................................................................................................................39 6.5 YACC................................................................................................................................................41 7 FAIRE UN INTERPRÉTEUR EN LEX/YACC [TP]............................................................................43 8 TRANSFORMER L’INTERPRÉTEUR EN COMPILATEUR [TP]...................................................45 8.1 STRUCTURE DES FICHIERS...................................................................................................................46 8.2 NOTION D’INSTRUCTIONS...................................................................................................................48 8.3 LES SOUS-PROGRAMMES.....................................................................................................................54 8.4 COMPLICATIONS.................................................................................................................................59 9 TABLE DES SYMBOLES [TP]...............................................................................................................61 9.1 LA LISTE CHAÎNÉE...............................................................................................................................61 9.2 L’ARBRE.............................................................................................................................................62 9.3 LA TABLE DE LISTES...........................................................................................................................62 10 GÉNÉRATION DE CODE POUR LE PROCESSEUR DÉVELOPPÉ EN VHDL [TP]....................65 11 ANNEXES..................................................................................................................................................67 11.1 LEX POUR C........................................................................................................................................67 11.2 YACC POUR C.....................................................................................................................................69 12 INDEX........................................................................................................................................................75 13 TABLE DES FIGURES............................................................................................................................77 Jacques Rouillard 1 Grammaires et classifications [cours/TD] 1.1 Définition Pour définir une grammaire, nous allons utiliser des quadruplets. {Vt, Vn, Ax, R}. • Vt est le vocabulaire terminal, c'est-à-dire la liste des mots qui apparaissent dans le langage. En informatique, cela peut être des mots «figés » comme if ou return. Ou des mots porteurs de valeur, comme 123 (c’est un mot, un entier portant la valeur 123) ou Toto (c’est un identificateur symbolisant quelque chose). En Français, ce sont les mots du dictionnaire. Figure 1 Dictionnaire • Vn est la liste des concepts du langage, ceux qui se définissent les uns les autres. On dira « non-terminal ». Ainsi en Français, la notion de « groupe nominal » peut être définie comme « article adjectif substantif» (le beau garçon) ou « article substantif » (la fleur) etc. En C, l’instruction_if peut être définie (très sommairement et entre autres) par « if ( expression ) instruction ; ». En Français, ce sont donc les concepts définis dans une grammaire. Figure 2 Grammaire • R est l’ensemble des règles qui définissent les éléments de Vn en fonction des éléments de Vn+Vt. On voit ci-dessus que l’instruction_if est définie par des mots réservés, éléments de Vt « (« if », « ( » , « ) », « ; ») et des éléments de Vn (« expression », « instruction »). La règle vide est appelée e. • Ax est l’axiome, la règle particulière par laquelle on entre dans le langage. Par exemple « programme ». En Français, c'est la désignation de l'entrée du texte que l'on va lire. On voit que le travail de définition est essentiellement dans la rédaction des règles, impliquant la liste de Vn. On voit aussi que le même langage peut être décrit par une infinité de grammaires différentes. Inversement, la plupart des langages sont infinis (acceptent une infinité de phrases), mais l’infinité de grammaires qui peuvent décrire chaque langage sont, chacune, finie. Cela est vrai en Français comme en informatique : quiconque a des enfants scolarisés voit que l’enfant apprend le Français avec des concepts qui n’existaient pas 10 ans avant. Or c’est (en principe) la même langue. Les règles peuvent donner à la grammaire des propriétés, suivant (entre autres) • qu’elle est définie récursivement ou non. • que la définition d’une règle dépende de son contexte. Par exemple, en C, l'instruction break n'est pas acceptée partout. 1.2 Notation On écrit une règle en décrivant deux parties: la gauche est la partie définie, la droite est la partie définissante. On utilise la flèche "→" en général et le symbole "::=" dans la notation 5 Jacques Rouillard dite BNF que l'on emploie généralement pour les grammaires hors contexte, ou simplement ":" dans le formalisme de yacc qui est utilisé par la majorité des outils. On dira qu'une règle est dérivée quand on remplace sa partie gauche par sa partie droite, et réduite quand on remplace la partie droite par sa partie gauche. Par exemple, soit la règle Achille → héros au pied léger (πόδας ὠκὺς Ἀχιλλεύς) On la dérive quand on dit "J'ai vu Achille, un héros au pied léger". On la réduit quand on dit: "Arrive le héros au pied léger, j'ai nommé Achille." 1.3 Classification Les grammaires sont classées (classification dite de Chomsky-Schützenberger 1), de 0 -très général- à 4 -très restrictif-. Chaque classe est incluse dans la précédente (inclusion stricte). Dans les exemples suivants, les lettres grecques représentent des séquences d’éléments de vocabulaire, terminal, non-terminal ou séquence quelconque des deux. Les minuscules des éléments du vocabulaire terminal (les mots), les majuscules des éléments du vocabulaire non terminal (les noms des règles). • Type 4 parfois mentionné et d'usage quasi-nul, pour lequel chaque non-terminal est défini comme étant exactement un et un seul terminal. • Type 3 : les grammaires régulières, que l’on peut reconnaître avec un automate d’états finis (sans pile). Les règles sont ou peuvent se ramener à des formes pour lesquelles la partie gauche est un non-terminal unique, et la partie droite commence ou se termine par un terminal. A → aB (ou A → Ba) et A→ a ; dans le premier cas on la dit linéaire droite, dans le second cas linéaire gauche. Exemple, la description de la règle « ENTIER » qui acceptera tous les entiers composés de plusieurs chiffres, où « chiffre » est ici vu comme un élément terminal : ENTIER → chiffre ENTIER ENTIER → chiffre L’entier 123 se dérivera ainsi (on met entre parenthèse la portion de la phrase qu’on a substituée, et en gras souligné celle qu’on va dériver) : ENTIER (1ENTIER) 1(2ENTIER) 12(3) 1 Noam Chomsky (USA, 1928-) est un professeur de linguistique qui s'est illustré par ses travaux sur les grammaires, les langages naturels et la psychologie cognitive. Par ailleurs il est connu comme anarcho-libertaire, et émet des critiques politiques virulentes contre les engagements de son pays. C'est un auteur très souvent cité dans beaucoup de domaines. Marcel-Paul Schützenberger (France, 1920-1996), double doctorat en médecine – généticien, épidémiologiste- et en mathématiques, domaine dans lequel il s'est fait connaître par ses travaux en théorie des langages et des systèmes combinatoires. Par ailleurs il a développé des arguments âprement controversés contre le darwinisme. Il a inspiré le Dr. Schütz de "Et on tuera tous les affreux" de Boris Vian, qui était son ami. 6 Jacques Rouillard • Type 2 : les grammaires hors contexte, que l’on peut reconnaître avec un automate à pile non déterministe (des entrées peuvent activer plusieurs mouvements de l'automate). Les règles acceptées sont telles que l’élément non terminal est défini de façon univoque : A → g . Donc ici la partie gauche est toujours un non-terminal unique, la partie droite est quelconque. Exemple, un palindrome formé de 0 et de 1 (éventuellement vide) PALIND → 1 PALIND 1 PALIND → 0 PALIND 0 PALIND → e Le palindrome 101101 va se dériver ainsi (on met entre parenthèse la portion de la phrase qu’on a substituée, et en gras souligné celle qu’on va dériver) : PALIND (1PALIND1) 1(0PALIND0)1 10(1PALIND1)01 101(e eee )101 101101 • Type 1 : les grammaires contextuelles, reconnaissables par une machine de Turing linéairement bornée (son ruban a une longueur bornée) non déterministe. On s’autorise des définitions dans lesquelles l’élément à définir est « encadré » d'un côté, de l'autre ou des deux par un contexte.a Ab → bga . Exemple, une grammaire acceptant N « a » puis N « b » puis N « c », N étant quelconque mais le même dans les trois cas. S → aSBC S → abC CB → BC aB → ab bB → bb bC → bc cC → cc On voit ici que les phrases abc, aabbcc et aaabbbccc peuvent se dériver ainsi (on met entre parenthèse la portion de la phrase qu’on a substituée, et en gras souligné celle qu’on va dériver) : abc : S (abC) a(bc) aabbcc : S (aSBC) a(abC)BC aab(BC)C aa(bb)CC aab(bc)C aabb(cc) aaabbbccc : S (aSBC) a(aSBC)BC aa(abC)BCBC aaabCB(BC)C aaab(BC)BCC aaabB(BC)CC aaa(bb)BCCC aaab(bb)CCC aaabb(bc)CC aaabbb(cc)C aaabbbc(cc) • Type 0 : toutes les grammaires dites récursivement énumérables reconnaissables par une machine de Turing ; hélas si la reconnaissance se fait en un temps fini, la non- reconnaissance peut demander un temps infini avant d’être diagnostiquée. On s’autorise des règles de définition dans lesquelles la partie droite (définissante) et la partie gauche (définie) sont des phrases de même nature. a → b . Pas d’exemple simple. Là-dessus, il existe des classes intermédiaires remarquables, par exemple entre 2 et 3 : les langages reconnaissables par des automates à pile déterministes (pour chaque entrée, un seul mouvement est possible). Les générateurs d’analyseurs ne s’attaquent concrètement qu’aux grammaires de types 2 et 3 et intermédiaires. • Le type 3 est parfaitement adapté pour faire des grammaires reconnaissant les mots d’un langage : l’exemple donné supra (NOMBRE) l’illustre très bien. On peut décrire ainsi ce qu’est un entier (une succession de chiffres), un identificateur (une lettre suivie d’une succession de chiffres ou de lettres), ou, plus long, un réel (une succession de chiffre, un point décimal, puis une succession de chiffres, puis optionnellement une partie exposant avec un signe optionnel, etc etc.) Ce qu’on ne peut pas faire, c’est décrire des symboles « symétriques » nécessitant des règles 7 Jacques Rouillard récursives (on ne peut pas exiger que les identificateurs soient des palindromes ni vérifier l’équilibre de parenthèses.) On utilisera l’outil LEX ou son clone FLEX. • Les types 2 et 2.5 sont bien adaptés à l’analyse des langages informatiques modernes. On peut y décrire des constructions récursives (une boucle peut en contenir d’autres) ou symétriques par paires (parenthèses ouvrantes et fermantes en nombre égal). On ne peut pas y décrire des structures dépendant du contexte, par exemple exiger que dans N paires de parenthèses se trouvent N points (((…))). C’est l’exemple proposé plus haut avec abc comme terminaux, qui est de type 1. On utilisera l’outil YACC ou ses clones BYACC ou BISON. 1.4 Exercices • X → l'homme qui a vu X → l'homme qui a vu X TOTO → c'est X l'ours et qui n'a pas eu peur. L'axiome est TOTO. Quelles sont les phrases du langage? • Soit la grammaire : A → B y B → x B → ε L’axiome est A, les mots sont x et y. Quelles sont les phrases de ce langage ? • Même question : A → B y B → x B B → ε • Même question : A → B y B B → x B B → ε • Aller sur le site : http://cui.unige.ch/db-research/Enseignement/analyseinfo/Ada95/BNFindex.html Déterminer si l’on peut mettre une clause use paquetage dans la zone déclarative d’une procédure procedure P is use pck; begin null ; end; 8 Jacques Rouillard • Soit la grammaire: expression → terme '+' terme expression → terme ‘-' terme expression → terme '*' terme expression → terme '/' terme expression → terme terme → entier terme → '(' expression ')' Accepte-t-elle une expression comme 2+3? Accepte-t-elle une expression comme 2+(3+4)? Accepte-t-elle une expression comme 2+3+4 ? Si non, que faire pour qu’elle l’accepte ? Si ou quand oui, sera-t-on content avec l’analyse de 2+3*4, sachant qu’on ne peut faire « quelque chose » pour calculer qu’en fin de chaque ligne, quand les opérandes sont calculés ? Si non que faire ? 9