Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Générateurs de compilateurs Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informat

Générateurs de compilateurs Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) www.zegour.uuuq.com email: d_zegour@esi.dz Générateurs de compilateurs Introduction Yacc Lex Coco/R Fonctionnement des générateurs de compilateurs Ils génèrent les parties d’un compilateur à partir d’une spécification concise (Parties générées : scanner, analyseur syntaxico-sémantique, générateur de code , ...) Générateur De compilateurs Spécification du scanner Ex. grammaire régulière) générateur scanner scanner Spécification sémantique (Ex. grammaire d’attribut) générateur de l’analyseur Analyseur Classes utilisateur • Table des symboles • Générateur de code • Programme principal • ... compilateur & éditeur de liens compilateur généré Exemples Yacc générateur d’analyseur syntaxique et sémantique pour C et Java Lex générateur de scanner pour C, Java et C# Coco/R générateur de scanner et d’analyseur pour Java, C#, Modula-2, Oberon, ... ... Générateurs de compilateurs Introduction Yacc Lex Coco/R Yacc - Yet another compiler compiler 1975 développé aux laboratoires Bell ( ensemble avec C et Unix) • Génère des analyseurs LALR(1) • À l’origine sous Unix, Aujourd'hui aussi sous Windows, Linux • A l’origine pour C, Aujourd'hui pour Java Histoire Utilisation sample.y Yacc parser.java javac parser.class Versions actuelles Bison version GNU de Yacc http://www.gnu.org/software/bison/bison.html Byacc Berkeley Yacc http://byaccj.sourceforge.net/ Nous décrivons ici la version de Java Langage d’entrée pour Yacc Format général %{package Java et les lignes ‘import’ %} Déclarations Yacc (unités, règles de précédence des opérateurs, ...) %% productions %% Déclarations Java (champs, méthodes) class parser { ... public void yyparse() { ... parser ... } } Traduit vers Yacc — Productions et actions sémantiques Productions Grammar = {Production}. Production = NT ":" Alternative {"|" Alternative} ";" Alternative = {NT | T} [SemAction]. SemAction = "{" ... arbitrary Java statements ... "}". NT = ident. T = ident | charConst. Exemple expr: term { $$ = $1; } | expr '+' term { $$.ival = $1.ival + $3.ival; } ; Actions Sémantiques • Peuvent contenir des instructions Java • Peuvent apparaître seulement à la fin d’une alternative • Les attributs sont dénotés par des noms spéciaux: $$ attribut du coté gauche NTS $i attribut du i-ème symbole du coté droit ($1 = attr. du premier symbole, $2 = attr. du second symbole, ...) Yacc — Attributs Pour les symboles terminaux • Sont délivrés par le scanner (scanner développé manuellement ou généré avec Lex) • Chaque unité lexicale a un attribut de type parserval class parserval { int ival; // token value if the token should have an int attribute double dval; // token value if the token should have a double attribute String sval; // token value, e.g. for ident and string Object obj; // token value for more complex tokens parserval(int val) {...} // constructors parserval(double val) {...} parserval(String val) {...} parserval(Obj val) {...} } • Le scanner retourne les attributs dans la variable globale yylval Scanner yylval = new parserval(n); Accès dans une action sémantique { ... $1.ival ... } Pour les symboles non terminaux • Chaque NTS a un attribut $$ de type parserval ( valeurs plus complexes rangées dans $$.obj) • Chaque affectation à $$ empile l’attribut du NTS dans une pile d’attributs. Les accès à $1, $2 se font en dépilant les attributs de la pile Yacc — Variables et Méthodes Java Sont déclarées après le second %% %{ ... imports ... %} ... Unités ... %% ... Productions ... %% ... Déclarations Java ... • Deviennent des champs et des méthodes pour l’analyseur • Peuvent être utilisées dans les actions sémantiques Au moins les méthodes suivantes doivent être implémentées dans les déclarations Java void yyerror(String msg) {...} Pour afficher les messages d’erreur int yylex() {...} Scanner (retourne les codes des unités et remplit yylval) public static void main(String[] arg) { ... initializations for yylex ... yyparse(); } Programme principal Exemple: Compilateur pour les expressions arithmétiques /* declaration of all tokens which are not strings */ %token number %% /* productions: first NTS is the start symbol */ input: expr { System.out.println($1.ival); } ; expr: term { $$ = $1; } | expr '+' term { $$.ival = $1.ival + $3.ival; } ; term: factor { $$ = $1; } | term '*' factor { $$.ival = $1.ival * $3.ival; } ; factor: number { $$ = $1; } | '(' expr ')' { $$ = $2; } ; %% int yylex() {...} void yyerror(string msg) {...} public static void main(String[] arg) {...} Conventions de codage des unités • eof == 0 • Code des unités ‘caractère’ : leurs valeurs Ascii (Par exemple '+' == 43) • YYERRCODE == 256 • Autres unités sont numérotées consécutivement commençant par 257 (Par exemple. nombre == 257); elles peuvent être accédées dans les productions et dans yylex() utilisant leur nom déclaré. Yacc — Précédence des opérateurs La grammaire suivante spécifie explicitement la précédence des opérateurs expr: term | expr '+' term ; term: factor | term '*' factor ; factor: number | '(' expr ')' ; • '*' a une précédence sur '+' • Les opérateurs sont associatifs à gauche: a*b*c == (a*b)*c On peut aussi l’exprimer comme suit en Yacc: %token number %left '+' %left '*' %% input: expr { System.out.println($1.ival); } ; expr: number { $$ = $1; } | expr '+' expr { $$.ival = $1.ival + $3.ival; } | expr '*' expr { $$.ival = $1.ival * $3.ival; } | '(' expr ')' { $$ = $2; } %% ... • %left : l’opérateur est associatif gauche a+b+c == (a+b)+c • Les opérateurs sont déclarés en ordre ascendant de priorité: '*' a une précédence sur '+' • Cette grammaire ne spécifie aucune précédence d’opérateurs • La précédence est spécifiée par %left ou %right Yacc — Traitement des erreurs Les alternatives ‘error’ Pour certains NTS (EX: Instructions, Expression, ...) l’utilisateur doit spécifier Les alternatives ‘error’ A: ... | ... | error  {...} ;  ... Séquence quelconque de symboles T et NT Signification: S’il existe une erreur dans A l’analyseur effectue les actions suivantes: • Il dépile des états de la pile jusqu’à l’obtention d’un état dans lequel une action ‘décaler’ avec l’unité error est valide • ‘Décaler’ error • Il saute les unités d’entrée jusqu’à ce qu’il détecte une séquence d’unités qui peut être réduite à  ( le sommet de pile contient alors : error ) • Il réduit error  à A et exécute l’action sémantique correspondante Exemple Statement = ... | error ';' ; Saute tout jusqu’au prochain ';' Générateurs de compilateurs Introduction Yacc Lex Coco/R Lex — Générateur de scanner 1975 développé aux laboratoires Bell • génère un scanner en forme de DFA • A l’origine un outil de Unix, aujourd'hui aussi pour Windows • A l’origine pour C, Aujourd’hui aussi pour Java • Coopère généralement avec Yacc Histoire Versions actuelles flex version GNU de Lex (pour C) http://www.gnu.org/software/flex/ JLex version Java avec légère différence dans la syntaxe d’entrée; incompatible avec Bison ou Byacc http://www.cs.princeton.edu/~appel/modern/java/JLex/ CsLex version C# , dérivé de JLex http://www.cybercom.net/~zbrad/DotNet/Lex Utilisation sample.l Lex sample.yy.c C-Compiler sample.o sample.y Yacc sample.tab.c include Nous decrivons ici la version C Exemple de description Lex %{ ... e.g. include directives for token numbers exported by the parser ... %} /* macros */ delim [ \t\n] /* blank, tab, eol */ ws {delim}+ /* {...} ... use of a macro */ letter [A-Za-z] digit [0-9] id {letter} ({letter} | {digit})* number {digit}+ %% /* token declarations described as regular expressions */ {ws} {} /* no action */ if { return IF; } /* constants like IF are imported from the parser */ then { return THEN;} else { return ELSE; } {id} { yylval = storeId(yytext, yyleng); return ID; } {number} { yylval = convert(yytext, yyleng); return number; } < { return yytext[0]; } > { return yytext[0]; } . {} /* . denotes any character */ %% /* semantic routines */ int storeId(char* text, int len) {...} int convert(char* text, int len) {...} Scanner généré La spécification du scanner est convertie en une fonction int yylex() {...} qui est incluse dans l’analyseur yylex() retourne aussi les attributs d’unités comme variables globales int yylval; /* attribute if the token has a numeric value */ char* yytext; /* token text (attribute of ident, string, ...) */ int yyleng; /* lengh of the token text */ int yylineno; /* line number of the token */ L’analyseur déclare (et exporte) les codes des unités %token IF %token THEN ... Expressions régulières dans Lex Éléments des expressions régulières abc la chaîne "abc"; tout caractère sauf ()[]{}*+?|^$.\ dénote lui-même . Tout caractère sauf \n (fin de ligne) x* 0 ou plusieurs répétitions de x x+ 1 ou plusieurs répétitions de x x? 0 ou 1 occurrence de x ( occurrence optionnelle) (...|...) pour grouper des alternatives [...] ensemble de tous les caractères entre les crochets (Ex. [A-Za-z0-9$]) {...} Utilise d’une macro ^ ligne début $ ligne fin \udddd caractère en Unicode Générateurs de compilateurs Introduction Yacc Lex Coco/R Coco/R – Compilateur de compilateur / Descente Récursive 1980 développé à l’université de Linz (Rechenberg, Mössenböck) • génère un scanner et un analyseur à partir d’une grammaire uploads/Management/ esi-generateurs-compilateurs.pdf