Home

LE SYSTÈME SYNTAXTM MANUEL D`UTILISATION ET DE

1. E21 Grammaire xa so E 2 2 Listage des conflits avec l option path E 3 Sp cifications d une grammaire LALR 2 TABLE DES MATIERES E38 Grammaire 5 ts ee en oe E32 AGUIOTIS 2 002 Mare eat E X P Pot E 4 Un langage non d terministe EAI Grammaire 2 4 4 tod ee a Wee As E42 Actions E eS F Exemples de d finitions lexicales 1 2 F 3 D finition lexicale de PASCAL D finition lexicale d un langage commentaires imbriqu s F 2 1 Expressions r guli res F 2 2 Actions lexicales Actions lexicales r alisant une inclusion iii Table des figures 1 1 2 1 3 1 3 2 3 3 4 1 4 2 4 3 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 5 1 5 2 5 4 6 1 Sp cification de paragraphage 7 criture de terminaux non g n riques 10 Diagnostic de non conformit Shift Reduce 16 Grammaire d expressions 19 D sambig ation de la grammaire d expressions 19 D finition de classes 28 D finition de 32 Sp cification de repr sentation 33 Exemple d expression r guli re
2. lt X gt rU Reduce 9 D X derived from 1 lt Z gt lt A gt X lt T gt by lt Z gt gt lt A gt X lt T gt gt lt A gt t gt a D X t gt a D t gt a lt X gt e t ANNEXE E EXEMPLES DE GRAMMAIRES NON LALR 1 The grammar is not LR 1 First derivation lt Z gt gt lt A gt X lt T gt gt lt A gt t gt a D X t gt a lt p gt t gt lt X gt e t Second derivation lt Z gt gt lt E gt gt lt C gt lt X gt lt T gt gt a lt C gt t gt lt X gt Using the system disambiguating rules priority is given to reduction number 8 E 3 Sp cifications d une grammaire LALR 2 E 3 1 Grammaire Grammaire d ecole non LALR 1 mais LALR 2 du langage L e ca e cb e d ae c ae d gt 0 lt Z gt lt ca lt Z gt lt cb gt cb lt Z gt lt C gt 3 lt Z gt a lt B gt c 5 lt Z gt a lt C gt d lt E 1 lt cb gt lt E gt B E C E lt gt 5 lt gt lt gt s amp 1 regarde si le contexte droit contient c et ANNEXE E EXEMPLES DE GRAMMAIRES NON LALR 1 87 E 3 2 Actions include sxunix h include XNT_td h defines c_code to be 1 and a_code
3. 34 Utilisation de l op rateur 34 Utilisation de l op rateur 35 D finition d expression de pr dicats 39 Extrait de la sp cification lexicale de BNF 39 Exemple de sp cification des commentaires de OLGA 39 Utilisation de Vunion 42 Utilisation de clause Priority 43 Diagnostics de LECL sur des conflits 44 Cr ation d un arbre abstrait pour une liste 47 Exemple d arbre 48 Exemple d arbre abstrait 48 Acc s l arbre abstrait 50 Modification de la grammaire pour am liorer le rattrapage d erreur 54 Liste des tableaux 2 1 4 1 4 2 4 3 Conventions d criture des caract res dans les chaines 10 Tiessmots cl s de LECE aie es 25 Classes pr d finies pour le confort de l utilisateur 26 Classes pr d finies pour les caract res non imprimables 27 Chapitre 1 Introduction Le syst me SYNTAX regroupe un ensemble d outils dont le but premier est de faciliter la conception et la r alisation de traducteurs principalement mais non exclusivement dans le domaine de la compilation Ces outils permettent d une part la construction d analyseurs syntaxiques lexicographiques et s mantiques d autre part la com
4. QRESET INTEGER_ NUMBER ACTION QINCR AINTEGER NUMBER ACTION QDECR AINTEGER NUMBER ACTION QPUT SIMPLE REF ACTION MARK lt ACTION gt QRELEASE lt PREDICATE gt APREDICATE lt PREDICATE gt lt STATIC_PREDICATE gt lt PREDICATE gt lt DYNAMIC_PREDICATE gt lt STATIC_PREDICATE gt lt STATIC_PREDICATE gt amp TRUE EFALSE DYNAMIC PREDICATE 4PREDICATE NO DYNAMIC PREDICATE 15 FIRST COL DYNAMIC PREDICATE 15 LAST COL DYNAMIC PREDICATE EIS SET DYNAMIC PREDICATE 4INTEGER NUMBER LOWER TO UPPER UPPER TO LOWER ACTION ERASE SET RESET INCR DECR PUT MARK RELEASE IS_TRUE IS_FALSE IS_FIRST_COL SYNONYMS SYNONYMS LIST SYNONYMS LIST lt SYNONYMS_LIST gt lt SYNONYMS_LIST gt lt DENOTATION_LIST gt lt DENOTATION_LIST gt lt DENOTATION gt EIS RESET ION INH ION SYNONYMS SYNONYMS LIST SYNONYMS LIST DENOTATION LIST DENOTATION LIST DENOTATION LIST lt DENOTATION gt COL 24 SPACE IDENTIFIER ZINTEGER_NUMBER lt DENOTATION gt IS_LAST_COL IS_SET 7 IS RESET SYNONYM S lt DENOTATION gt DENOTATION S ID DENOTATION ANNEXE B SPECIFICATIONS
5. IDENTIFIER PREDICATE_NAME ASTRING LITERAL Synonyms OCTAL_CODE _ YINTEGER_NUMBER PREDICATE_NO ACTION_NO KEYWORD ACTION_KEYWORD PREDICATE_KEYWORD BOLD_LET BOLD_US BOLD_LET DARK_LET DARK US DARK LET Mark O amp True Erase DIGIT O amp True DIGIT SP HT EOL VT FF 2 2 EOL EOL Context All But Comments IDENT QGUpper Case Context 11 But 4 IDENTIFIER KEYWORD AINTEGER NUMBER amp IDENT OUpper Case Context All But YIDENTIFIER QUOTE 1 a n amp True EOL amp True n amp True Put EOL b amp True Put BS t amp True Put HT y amp True Put VT f amp True Put FF r amp True Put CR Mark OCTAL amp True OCTAL amp True OCTAL True 2 ANY QUOTE Context All But STRING_LITERAL OCTAL 4 IDENT Upper_Case DIGIT amp NUMBER NORMAL FORM Q NUMBER NORMAL FORM DARK_LET Upper Case Context All But YIDENTIFIER KEYWORD BOLD COMMERCIAL BOLD WORD Upper Case Context 11 But IDENTIFIER DARK AMPERSAND DARK WORD Upper Case Context 11 But IDENTIFIER Priority Shift gt Reduce ANNEXE B SPECIFICATIONS DU LANGAGE LECL EOF END_OF_FILE 01 Is Same Letter 02 nnn gt char B 3 Actions lexicales 73 Ceci est le codage en langage C des actions il n y a pas de pr dicat associ
6. SXVOID more_scan_act bnf_scan_act code act_no int code int act_no switch code case OPEN coords struct span sxalloc rules_no rule_slice sizeof struct span 1 if more scan act NULL scan act code act no return ANNEXE A SPECIFICATIONS DU LANGAGE BNF 63 case CLOSE if more_scan_act NULL more_scan_act code act no if coords NULL sxfree coords 1 return case INIT if more_scan_act NULL more_scan_act code act no register SHORT sxsrcmngr current_char while EOF if c 2 lt amp amp sxsrcmngr source_coord column 1 coords xprod 1 head sxsrcmngr source_coord line return else c sxnext_char fprintf sxstderr n tThis text is not a grammar See you later n SXEXIT 3 case FINAL if more_scan_act NULL more_scan_act code act no return case ACTION switch act no register SHORT 1 coords xprod tail line sxsrcmngr source_coord line coords xprod tail column sxsrcmngr source_coord column if more_scan_act NULL more scan act code act_no ANNEXE A SPECIFICATIONS DU LANGAGE BNF 64 sxsrcomngr current char while c EOF if c 2 lt amp amp sxsrcmngr source_coord column 1 1 if xprod gt rules_no coords struct span sxrealloc coords 1 rules_no ru
7. lt PRIORITY_KIND gt lt PRIORITY_KIND gt REDUCE gt REDUCE REDUCE gt SHIFT SHIFT gt REDUCE lt PRIORITY_KIND gt gt PRIORITY KIND S REDUCE REDUCE REDUCE SHIFT 5 REDUCE 77 CONTEXT RESTRICTED CONTEXT RESTRICTED CONTEXT lt REF LIST UNBOUNDED CONTEXT lt REF LIST gt UNBOUNDED_RESTRICTED_CONTEXT lt VOID gt lt CONTEXT gt CONTEXT lt TOKEN_REF_LIST gt lt CONTEXT gt CONTEXT ALL BUT lt TOKEN_REF_LIST gt lt CONTEXT gt CONTEXT ALL VOID lt CONTEXT gt UNBOUNDED CONTEXT lt CONTEXT gt UNBOUNDED CONTEXT ALL BUT lt CONTEXT gt UNBOUNDED CONTEXT ALL lt VOID gt UNBOUNDED_RESTRICTED_CONTEXT ANNEXE B SPECIFICATIONS DU LANGAGE LECL 69 lt TOKEN_REF_LIST gt lt TOKEN_REF_LIST gt lt TOKEN_REF_LIST gt lt TOKEN_REF gt lt TOKEN_REF gt lt TOKEN_REF gt lt TOKEN_NAME gt lt VOID gt lt TOKEN_NAME gt lt TOKEN_NAME gt COMMENTS lt TOKEN_NAME gt EOF lt TOKEN_NAME gt INCLUDE lt TOKEN_NAME gt AIDENTIFIER lt TOKEN_NAME gt lt TOKEN_NAME gt _ YSTRING_LITERAL lt COMPONENT_NAME_REF gt 4IDENTIFIER REGULAR lt REGULAR_EXPRESSION gt EXPRESSIONS lt ALTERNATIVE gt lt ALTERNATIVE gt lt ALTERNATIVE gt lt SEQUENCE gt lt ALTERNATIVE gt lt SEQUENCE gt lt SEQUENCE gt SEQ
8. 4 L utilisation de pr dicats permet d influer sur l analyse et en particulier de faire intervenir des notions qui n appartiennent pas la classe LALR 1 Ces notions peuvent tre purement syntaxiques utilisation du contexte gauche vel droit sur une longueur ventuellement non born e ou m me s mantiques utilisation d informations calcul es par les actions syn taxiques Les pr dicats peuvent repr senter le seul moyen utilisable pour r soudre des conflits voir l exemple du langage non d terministe en pages 87 et suivantes Ils ont cependant pour inconv nient de ne r soudre les conflits que de mani re dynamique Ils ne se substituent donc pas aux autres pos sibilit s num r es ci dessus 3 3 1 Le langage PRIO Les tables mentionn es ci dessus sont construites par l ex cution pr alable du module PRIO voir la documentation en ligne man prio sur des sp cifications de priorit s crites par l utilisateur et rassembl es dans un fichier de nom nom du langage prio Une sp cification crite dans le langage PRIO contient deux parties chacune tant optionnelle une partie a ot l on donne les priorit s des op rateurs une partie b o l on donne les priorit s des r gles de la grammaire a Cette partie d finit pour chaque symbole cit en g n ral un terminal de la grammaire son type d associativit gauche droit non associatif et sa priorit relative Cette liste est or
9. Il y a dix types diff rents de productions de Floyd Evans Test Scan Reduce Stack Goto test n de NT bloc n de T bloc test x adresse n de T bloc test n de NT bloc n de T bloc test adresse n de T bloc test n de r duction adresse test z n de r duction non terminal test n de r duction adresse test n de r duction non terminal test Halt test Error Remarque Afin de faciliter l exploitation manuelle de l automate le code des NT tables est pr sent dans le listage successivement sous deux formes 1 La premi re partie organis e comme on l a pr sent ci dessus regroupe s quentiellement les instructions de chaque NT bloc Cette pr sentation CHAPITRE 3 CSYNT CONSTRUCTION DE L ANALYSEUR SYNTAXIQUE23 n est exploit e que lorsque le sommet de pile apres cr tage repr sente un num ro de NT bloc et le champ Goto de l instruction sp cifie un non terminal 2 Dans la seconde pr sentation qui elle est exhaustive les instructions sont rep r es par leur num ro et sont ex cut es inconditionnellement c est la partie qui doit tre utilis e lorsque le champ Goto d une instruction Reduce est Goton ou lorsque le sommet de pile apr s cr tage est une adresse 3 6 Mise en uvre Se reporter la documentation en ligne man bnf Chapitre 4 LECL Construction de l Analyseur Lexical LECL est le constructeur lexic
10. Si l on est en visite h rit e le fr re de gauche s il existe peut tre acc d par LEFT plut t que par sxbrother VISITED VISITED gt position 1 En visite synth tis e le fils le plus droite peut tre acc d par LAST ELEM plut t que par sxson VISITED VISITED gt degree 5 2 2 3 Mise en uvre L valuation des attributs est r alis e par des instructions qui sont ins rer dans la trame engendr e par SEMAT Cette trame comporte essentiellement la d finition de deux proc dures nom du langage pi pour les attributs h rit s nom du langage pd pour les attributs synth tis s Ces deux proc dures sont constitu es principalement par des instructions switch le choix tant fait sur le nom du n ud p re puis la position du fils visit pour la passe h rit e le nom du noeud visit pour la passe synth tis e L ent te d une telle trame est constitu e par les d clarations de constantes repr sentant les noms de noeud Chaque nom de constante est form par le nom du n ud suffix par n Par exemple au noeud de nom OBJ et de code interne 3 est associ e la d finition define OBJ_n 3 Les deux proc dures nom du langage pi et nom du langage pd sont pas s es en param tre sxsmp qui r alise une passe haut bas gauche droite sur l arbre param tre Chaque fois qu un noeud est visit en h rit sxsmp appelle CHAPITRE 5 LA SEMANTIQUE DANS SYNTAX 51 nom
11. case FINAL return case ACTION switch action_no struct sxsource_coord source_coord case 0 Call From Level 0 llev scanner Swap of the scanner local variables sxsvar llev_svar sxsvar sxsvar hlev_svar source_coord sxsrcmngr source_coord sxplocals SXP_tables scanit Quick Scanner Call hlev_svar sxsvar sxsvar llev_svar if sxsrcmngr current_char sxput_error source coord sComment not closed sxsvar sxtables gt err_titles 2 ANNEXE EXEMPLES DE DEFINITIONS LEXICALES 92 return case 1 Call From Level Greater Than 0 hlev scanner sxsvar is already correct source_coord sxsrcmngr source_coord sxplocals SXP_tables scanit Quick Scanner Call if sxsrcmngr current_char sxput_error source coord sSub Comment not closed sxsvar sxtables err titles 2 return default fputs The function llev_sact is out of date with respect to its specification n sxstderr abort On trouvera ci dessous le r sultat de l ex cution d un petit texte source erron 1 2 2 2 3 2 texti llev line 1 Column 9 Error Sub Comment not closed 1 2 2 2 3 2 texti llev line 1 column 1 Error Comment not closed F 3 Actions lexicales r alisant une inclusion include sxunix h VOID your scan act entry act no int entry act no 1 switch entry case OPEN case CLOSE case INIT case FINAL s
12. cette signification d pend galement de l environnement posi tionnement du caract re un num ro de colonne donn occurrence dans une portion de texte donn e et cetera En g n ral ce genre de situation ne peut que difficilement se d crire de facon purement syntaxique Afin de r soudre ce probl me LECL permet d influer sur l analyse lexicale par l interm diaire de pr dicats Il est possible dans une expression r guli re quelconque d associer une occurrence d une classe de caract res quelconque un pr dicat syst me ou utili sateur Un nom de pr dicat commence par le caract re Lors de l analyse d un texte source un caract re t ne peut tre reconnu par le couple classe pr dicat que si t appartient classe et si pr dicat est vrai Dans une expression r guli re toute occurrence d un nom de classe n ayant pas de pr dicat associ peut tre consid r e comme tant associ e un pr dicat toujours vrai A chaque pr dicat autre qu un pr dicat statique voir ci dessous doit cor respondre une fonction valeur bool enne d finie par le syst me pour ce qui concerne les pr dicats pr d finis ou crite par l utilisateur ces fonctions sont ex cut es au cours de l analyse lexicale d un texte source Les pr dicats syst me Statiques Ces pr dicats contrairement aux autres sont valu s la cons truction et permettent de simplifier l criture des expressions r guli res il s ag
13. is replaced by Ne 40 XX1223 A 0 NH before Nit 1 18 replaced by 40 on 41 HH SMS Dont Delete 1 Dont Insert Forced Insertion NH 40 is forced before 1 NOM Global Key Terminals Validation Length 2 Followers Number lt 5 7 Zs is expected parameters array 1 Followers_Number of valid followers at detection point Detection Global recovery parameters none Restarting Parsing resumes on 5 parameters array 1 Validation Length of valid m followers at restarting point Halt Parsing stops on End Of File parameters none Abstract Ad errors and d warnings are reported parameters array 1 Titles_No of number of messages Annexe Exemples de grammaires non LALR 1 E 1 Une grammaire ambigtie On trouvera ci dessous une grammaire ambigiie illustrant le probl me du dangling else et les messages de non conformit mis par CSYNT dans le cas standard avec les options par d faut et dans le cas ou l option path est positionn e E 1 1 Grammaire lt Stmt gt lt If_Stmt gt 3 lt Stmt gt lt If_Stmt gt if cond lt Then_Part gt lt Else_Part gt lt Then_Part gt then lt Stmt gt lt Else_Part gt 3 lt Else_Part gt else lt Stmt gt 3 E 1 2 Listage des conflits E 1 2 1 option par d faut NOT L A LR 1 Shift Reduce conflict in state 6 on else between Shif
14. lors de la construction d un analyseur Fra 3 1 Exemple de diagnostic de non conformit Shift Reduce NON LALR 1 Le terminal t est en conflit dans l etat s en position reduce dans pi lt A gt alpha derivant de p2 lt B gt beta lt D gt gamma en position shift dans p3 lt C gt delta t lambda La signification de ce diagnostic est la suivante on vient de reconnaitre dans l tat s simultan ment alpha partie droite de p1 et delta d but de p3 et l on doit d cider s il faut effectuer la r duction p1 Reduce ou lire le symbole t Shift de p3 or l on a lt D gt omega lt A gt et t FIRST1 gamma La r solution du conflit devant se faire avec au plus un symbole en avance la vue de t ne permet donc pas de prendre de d cision d ot le message de non conformit On trouvera en annexe E 1 une grammaire ambig e illustrant le probl me du dangling else et en annexe E 1 2 1 les messages de non conformit produits par CSYNT Si les renseignements pr c dents ne suffisent pas comprendre les raisons d un conflit L option path du processeur CSYNT voir la documentation en ligne man csynt permet d obtenir des renseignements suppl mentaires Pour chaque tat s dans lequel un conflit est d tect CSYNT sort une chaine Xi Xi X o chaque X est un l ment du vocabulaire terminal ou non terminal telle que l tat s est atteint depuis l tat initial par transit
15. quelques exemples de possibilit s d criture de symboles terminaux non g n riques Fic 2 1 Exemples d criture de terminaux non g n riques Le terminal peut s crire Begin Begin fBegin Begin E 4 AND AND AND AND AND AND NA CHAPITRE 2 BNF LECTURE DES DEFINITIONS SYNTAXIQUES 11 La d finition de la grammaire se termine par la fin du fichier d entr e Remarques Les r gles dont la partie droite est vide sont d crites sous la forme naturelle lt A gt On peut inclure des commentaires dans la d finition de la grammaire ils d butent en colonne 1 par un caract re et se terminent par une fin de ligne Il est possible d associer de la s mantique chaque r gle de grammaire Sur ce point BNF est un langage ouvert au sens o il se contente uniquement d interpr ter les r gles de syntaxe d une description source BNF consid re comme d crivant de la s mantique et ce titre ne l interpr te pas tout le texte se trouvant avant le premier lt en colonne 1 marquant le d but de la premi re r gle de grammaire ainsi que les portions de texte situ es entre chaque marquant la fin d une r gle et le d but de la r gle suivante ou la fin du fichier d entr e Ce texte peut bien entendu tre utilis par un processeur associ BNF c est d ailleurs ainsi que sont implant s les constructeur
16. s La formalisation des notions d acc s la pile et de gestion de la pile em ploy es ci dessus est la notion de grammaire attribu e La description de cette technique demande trop de place pour figurer ici mais disons seulement qu elle permet d exprimer de facon purement d clarative tous les calculs dirig s par la syntaxe SYNTAX propose une forme restreinte de grammaires attribu es dans la quelle les valeurs des attributs sont calcul es de bas en haut de l arbre de d ri vation purement synth tis es Le calcul de ces valeurs peut tre d crit soit en C processeur TABC soit en PASCAL processeur TABACT Dans ce dernier cas plusieurs modules d interface inclus dans le syst me d ex cution permettent d acc der en PASCAL aux fonctionnalit s de la version C 1 3 4 Arbres abstraits Si le traitement s mantique d sir ne peut pas s effectuer en une passe au cours de l analyse syntaxique il faut construire un arbre repr sentant le texte source et susceptible d tre parcouru plusieurs fois SYNTAX propose une telle forme de traitement s mantique dans laquelle les arbres produits sont des arbres abstraits ce qui signifie qu ils ne contiennent pas d information purement synta xique comme les terminaux non g n riques et les productions simples De plus les notions du langage exprimant des listes sont effectivement repr sent es par des noeuds listes et non pas par des peignes La sp cification de ce traitement se
17. sentant des phrases de haut niveau du langage voir l exemple de la figure 6 1 FIG 6 1 Modification de la grammaire pour am liorer le rattrapage d erreur Consid rons les r gles suivantes LISTE DE DECL gt LISTE DE DECL gt lt DECL gt lt LISTE DE DECL gt lt DECL gt lt DECL gt DCL 414 Le est a priori d fini comme un terminal de rattrapage Mais si une erreur se produit en d but de d claration le se trouvant en fin de d claration ne pourra pas permettre de se r cup rer car il n est pas pr c d d un non terminal Pour permettre la r cup ration il faut transformer la grammaire par exemple de la facon suivante LISTE DE DECL gt LISTE DE DECL gt lt DECL gt lt LISTE DE DECL gt lt DECL gt lt DECL gt 4 DCL 41 i Remarque Avant d effectuer une r cup ration globale l analyseur regarde s il n existe qu un seul symbole pouvant suivre la partie du texte source d j analys e Si c est le cas il l ins re automatiquement et il repart sur ce symbole Il peut ainsi rajouter toute une s quence de symboles obligatoires 6 2 Traitement des erreurs lexicales Les erreurs lexicales tant plus rares que les erreurs syntaxiques la correction des erreurs est moins labor e Elle repose uniquement sur une correction locale et utilise le m me principe que dans l analyse syntaxique Mais seuls les mod les permettant l insertion le remplacement ou
18. ses fr res et ses fils Il est donc possible en un n ud donn de calculer un attribut de ce n ud en fonction d attributs d j calcul s des n uds voisins 5 2 2 2 Les outils Les outils n cessaires la r alisation de l analyse s mantique sont principa lement la structure des noeuds et les pointeurs qui permettent d y acc der ainsi que les proc dures de parcours de l arbre abstrait voir la documentation en ligne sur sxatc 3 et sxat_mngr 3 Tous les n uds de l arbre ont la m me structure et poss dent donc tous les attributs utilis s La macro VISITED s tend en un pointeur vers le n ud visit celui pour lequel on doit calculer des attributs Les relations suivantes qui font r f rence la figure 5 4 sont v rifi es B sxbrother VISITED 1 VISITED sxbrother VISITED VISITED gt position B sxbrother VISITED avec n VISITED gt father gt degree S sxson VISITED 1 S sxson VISITED 4 Sm sxson VISITED m avec m VISITED gt degree CHAPITRE 5 LA SEMANTIQUE DANS SYNTAX 50 Fic 5 4 Acc s l arbre abstrait Le sous arbre entourant le n ud visit a la structure suivante Quelques acc l rateurs peuvent tre utilis s dans certains cas pour am liorer la vitesse d acc s un noeud particulier On peut acc der au fr re de droite s il existe par VISITED gt brother plut t que par sxbrother VISITED VISITED gt position 1
19. tre plus labor s Mod le Interpr tation 1 0 X 1 23 oubli d un symbole 2 0 X 2 3 4 un symbole erron 3 0234 un symbole en trop 4 1023 interversion de deux symboles 5 X 1 2 3 4 symbole pr c dent erron 6 1234 symbole pr c dent en trop La longueur du plus long mod le sp cifie la longueur n des cha nes de la vue de ces mod les on remarquera que l on a la possibilit d effectuer des corrections impliquant le symbole qui pr c de le symbole sur lequel l erreur a t d tect e Les mod les utilis s ne doivent pas tre trop longs pour ne pas augmenter de mani re cons quente le temps d ex cution de la correction d erreur Il semble qu un bon compromis soit atteint pour une valeur de n voisine de 4 ou 5 SYNTAX comporte galement un m canisme assez g n ral de correction des fautes d orthographe sur les mots cl s Ce m canisme peut tre exploit lors de la tentative de correction d une erreur mettant en cause un terminal g n rique dont la d finition lexicale reconnait un ou plusieurs mots cl s Il permet de corriger les fautes simples tombant dans l une des quatre cat gories suivantes omission d un caract re ajout d un caract re remplacement d un caract re interversion de deux caract res Ce m canisme sera mis en oeuvre si l on fournit des mod les dans lesquels un num ro de symbole terminal est remplac par 5 Exemple 052 correction sur le symbole S1
20. a b indique que l unit lexicale laquelle elle est rattach e ne reconnait que les mots cl s qui n appartiennent pas la liste a b Remarque Pour des raisons de compatibilit avec les versions pr c dentes NOT et KEYWORD sont des mots cl s non r serv s de LECL Remarque Les unit s lexicales Comnents et Include ne permettent pas de d finir des mots cl s 4 1 4 Les synonymes Si cette rubrique est pr sente elle est introduite par le mot cl SYNONYMS Elle permet d associer une liste de synonymes chaque terminal du niveau syntaxique Deux synonymes sont deux symboles qui vont jouer exactement le m me r le du point de vue syntaxique ils auront le m me code interne mais qui ont des repr sentations diff rentes au niveau lexical La sp cification de synonymes utilis e essentiellement pour les mots cl s permet de diminuer le nombre des symboles terminaux de la grammaire synta xique ce qui diminue en cons quence la taille de l automate pile engendr par le constructeur syntaxique F1G 4 2 Exemple de d finition de synonymes Synonyms DECLARE DECL DCL PROCEDURE PROC POINTER PTR DECLARE est un terminal du niveau syntaxique tandis que DECL et DCL n en sont pas Cette d finition signifie que trouver DECL ou DCL dans un texte est quivalent y trouver DECLARE 4 1 5 La sp cification de repr sentation Cette derni re rubrique si elle es
21. classes Le vocabulaire terminal du niveau lexical est g n ralement un sous ensemble des caract res valides pour une machine donn e ASCII EBCDIC Cependant l utilisation directe et syst matique des caract res comme voca bulaire terminal des expressions r guli res peut tre malcommode pour l utilisateur engendrer un grand nombre d tats pour l automate d o l introduction de la notion de classe Une classe est un ensemble de caract res qui jouent un r le identique un moment donn Exemple Dans la d finition des identificateurs les lettres jouent un r le analogue d un point de vue lexical le fait important est d avoir une lettre et non de conna tre son nom Dans un identificateur l ensemble des lettres majuscules ou minuscules peut donc constituer une classe Il existe un certain nombre de classes pr d finies en LECL Le nom de ces CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL26 classes n est pas r serv l utilisateur peut donc les red finir s il le d sire La table 4 2 liste l ensemble des classes qui ont t pr d finies pour simplifier l cri ture des sp cifications LECL et la table 4 3 donne les noms qui sont associ s aux caract res non imprimables du code ASCII TAB 4 2 Classes pr d finies pour le confort de l utilisateur Nom Signification ANY Ensemble des caract res ASCII EOL ou NL Fin de ligne code octal 012 LETTER Les lettres majuscules et minuscu
22. correction sur le symbole ao 6 1 2 R cup ration globale Si aucune correction locale gouvern e par les mod les fournis ne peut pro duire une chaine valide l on tente une action globale permettant la reprise de l analyse CHAPITRE 6 LE TRAITEMENT DES ERREURS 54 Cette r cup ration globale utilise la liste de terminaux de rattrapage de Key_Terminals voir en 6 3 Lorsque la correction locale a chou le texte source est lu sans analyse jusqu rencontrer un des terminaux de rattrapage L analyseur regarde alors si la cha ne source de longueur p est donn par Validation length com mencant par ce terminal peut tre un suivant possible de l un des tats de la pile d analyse apr s transition sur un non terminal si oui l analyse repart de cet endroit et on d pile jusqu ce que l on puisse transiter sur ce non terminal partir du sommet de pile Tout se passe comme si la partie du texte non analys e plus ventuellement une portion du texte d j analys e tait consid r e comme une chaine d riv e de ce non terminal si non l analyseur recherche dans le texte source le prochain terminal de rattrapage et il recommence Cette description du m canisme de r cup ration globale sugg re qu il est pr f rable pour permettre une bonne r cup ration d erreurs que les terminaux de rattrapage choisis soient plac s dans la grammaire imm diatement apr s des non terminaux repr
23. d crit ci dessous pour traiter le langage en question Ce programme doit tre compil et li au syst me d ex cution pour former un analyseur com plet 1 2 Le Syst me d Ex cution SYNTAX ne produit pas directement un programme ex cutable mais un en semble de donn es C compiler et lier avec diff rents modules du syst me d ex cution Ces modules comprennent bien entendu un analyseur lexical et un analyseur syntaxique qui vont interpr ter les tables du langage analyser mais CHAPITRE 1 INTRODUCTION 5 aussi de nombreux modules utilitaires permettant de r aliser peu de frais un squelette de compilateur gestionnaire du texte source permettant en particulier de traiter les in cludes gestionnaire des messages d erreur permettant de les afficher au cours de l analyse et de les stocker pour les inclure dans le listage gestionnaire de cha nes de caract res permettant de stocker des textes de longueur quelconque de leur affecter un num ro unique et d y acc der facilement enchaineur de passes modules de traitement d erreur module de production du listage gestionnaire de chaines de bits destin es repr senter des ensembles Tous ces modules sont disponibles sous forme binaire dans une biblioth que manipulable par l diteur de liens et aussi sous forme source ce qui permet de les modifier pour les adapter des besoins particuliers 1 3 Le Traitement S
24. de la partie gauche Voir l exemple de la figure 5 1 Fic 5 1 Exemple de cr ation d arbre abstrait pour une liste Consid rons les r gles OBJECT LIST 0BJECT LIST lt OBJECT gt OBJECT LIST lt OBJECT gt OBJ_S lt OBJECT gt E WII OBJ Si dans un texte source la liste d objets contient trois objets l arbre syntaxique classique serait celui d crit en figure 5 2 En revanche l arbre abstrait engendr par le constructeur d arbre est celui de la figure 5 3 3 Il est possible de ne pas sp cifier de nom de noeud pour une r gle si cette r gle ne comporte qu un seul non terminal ou terminal g n rique en partie droite ventuellement accompagn de terminaux non g n riques Lorsque l analyseur syntaxique r duit une telle r gle il n apporte aucune modification l arbre en cours de construction Ces omissions permettent donc de condenser l arbre abstrait engendr 4 Enfin en cas d erreur syntaxique non corrigible voir en 6 1 2 le construc teur d arbres r unit tous les sous arbres d j construits et impliqu s dans ce rattrapage global sous un noeud de nom ERROR Remarque On peut donner le m me nom de noeud plusieurs r gles CHAPITRE 5 LA SEMANTIQUE DANS SYNTAX 48 Fic 5 2 Exemple d arbre syntaxique 5 3 Exemple d arbre abstrait CHAPITRE 5 LA SEMANTIQUE DANS SYNTAX 49 diff rentes si elles ont la m me arit c est dire les noeuds repr sentant les no
25. es la description lexicale de LECL include sxunix h VOID lecl scan act entry act no int entry act no switch entry case OPEN case CLOSE case INIT case FINAL return case ACTION switch act_no case 1 Dark Letter Check if sxsrcmngr current_char sxsvar lv_s token_string sxsvar lv ts_lgth 1 sxput_error sxsrcmngr Source coord SN A dark symbol must be built up with the same character sxsvar sxtables gt err_titles 1 Warning return case 2 nnn gt char register int val register char C 8 sxsvar lv s token string sxsvar lv mark index for val 209 st NUL val val lt lt 3 c 0 t val sxsvar lv ts lgth sxsvar lv mark index 1 sxsvar lv mark index 1 ANNEXE B SPECIFICATIONS DU LANGAGE LECL 74 return default break default fputs The function lecl_scan_act is out of date with respect to its specification n sxstderr abort B 4 Pr dicats syntaxiques Ceci est le codage en langage C des pr dicats syntaxiques il n y a pas d ac tion associ s la description syntaxique de LECL include sxunix h static int NOT_code KEYWORD_code int lecl_pars_act entry action_no int entry action_no switch entry case OPEN case CLOSE case FINAL return case INIT The keywords NOT and KEYWORD are not reserv
26. if cond then if cond lt Then_Part gt lt Else_Part gt else gt if cond then if cond lt Then_Part gt else Second derivation lt Stmt gt gt lt If_Stmt gt gt if cond lt Then_Part gt lt Else_Part gt gt if cond lt Then_Part gt gt if cond then lt Stmt gt gt if cond then lt If_Stmt gt gt if cond then if cond lt Then_Part gt lt Else_Part gt gt if cond then if cond lt Then_Part gt else ANNEXE E EXEMPLES DE GRAMMAIRES NON LALR 1 85 Using the system disambiguating rules priority is given to shift E 2 Une grammaire non LR 1 On trouvera ci dessous une grammaire non LR 1 et les messages de non conformit mis par CSYNT dans le cas ou l option path est positionn e E 2 1 Grammaire lt Z gt lt A gt X lt T gt lt Z gt lt B gt lt X gt lt T gt t lt B gt a lt E gt H XE lt C gt X lt T gt lt A gt lt D gt lt X gt lt C gt X lt gt lt X gt E 2 2 Listage des conflits avec l option path SAMPLE PATH from state 1 to 9 lt X gt NOT LALR 1 Reduce Reduce conflict in state 9 on between Reduce 8 lt C gt XY derived from 6 E lt C gt X lt T gt by lt Z gt gt lt E gt gt lt C gt lt X gt lt T gt gt C nan gt
27. inexploitable manuellement L utilisateur peut cependant avoir une id e de l automate pile engendr en utilisant l option floyd_evans voir la documentation en ligne man csynt qui permet d obtenir le listage de l automate sous une forme compr hensible 3 5 Listage de l automate engendr L automate pile engendr est partitionn en trois tables les T tables qui s occupent des transitions terminales les NT tables qui s occupent des transitions non terminales les Prdct tables qui s occupent du traitement des pr dicats Chacune de ces tables est partitionn e en blocs comprenant une s quence d instructions Chaque bloc est tiquet pour r f rence de la facon suivante T bloc Etq l CHAPITRE 3 CSYNT CONSTRUCTION DE L ANALYSEUR SYNTAXIQUE21 NT bloc State m Prdct bloc Prdct m chaque instruction est associ e une adresse nombre entier positif Une ins truction est form e d un doublet test action Le premier champ sert la s lection le second champ indique l action effectuer lorsque l instruction a t s lectionn e L analyse commence dans les T tables par activation d un T bloc dont l ti quette est pr cis e dans le listage Le symbole terminal sous la t te de lecture est le symbole fictif End 0f File Quand un bloc est activ une instruction et une seule de sa s quence est s lectionn e et ex cut e les instructions sont examin es l une apr s
28. l automate une action d analyse Shift ou Reduce sur ce terminal mais le pr dicat ventuel associ ce terminal n est pas encore ex cut Ceci signifie que la portion de grammaire 1 t Ei o amp 1 utilise le r sultat de 1 est erron e alors que 01 s t amp 1 est valide Attention dans cet exemple l expression portion de gram maire n implique pas que l action et le terminal tendu apparaissent dans la m me r gle Le traitement des erreurs voir le chapitre 6 et en particulier la phase de correction est d licat mettre en ceuvre en pr sence de pr dicats Lorsque le traitement des erreurs a d cid de remplacer la chaine source af par CHAPITRE 2 BNF LECTURE DES D FINITIONS SYNTAXIQUES 13 af une erreur t d tect e dans 8 il faut obligatoirement que soit un pr fixe correct d une sentence du langage Or 0 peut contenir des pr dicats qui peuvent s ex cuter diff remment dans le contexte de la correction des erreurs les actions ne sont pas ex cut es l environnement est diff rent et dans le contexte de l analyse normale et donc produire des r sultats diff rents Afin de ne pas construire une cha ne 8 qui risquerait d tre invalid e par l analyse normale le couple analyseur correcteur pourrait m me boucler ind finiment on a choisi de ne pas ex cuter les pr dicats de l utilisa teur au cours du rattrapage d erreur en supposant qu ils retournent
29. l autre jusqu en rencontrer une dont le test soit satisfait La derni re instruction d une s quence contient toujours un champ test valant Any ce qui assure une s lection inconditionnelle de cette instruction Le mode de s lection d pend de la table consid r e Une instruction d un T bloc est s lectionn e si et seulement si le symbole terminal sous la t te de lecture est celui du champ test Une instruction d un NT bloc est s lectionn e si et seulement si le symbole non terminal courant c est dire le non terminal en partie gauche de la production qui vient d tre reconnue et choisie est celui du champ test Une instruction d un Prdct bloc est s lectionn e si et seulement si la fonc tion utilisateur appel e avec le param tre test retourne vrai Lorsqu une instruction est s lectionn e l action sp cifi e par le deuxi me champ est ex cut e Il existe quatre types d actions Shift Reduce Halt et Error Chacun de ces types est d crit ci dessous L action Shift correspond au traitement d une transition terminale ou non terminale elle est cod e sur trois champs Scan Stack Goto Si le champ Scan contient le symbole terminal suivant du texte source est positionn sous la t te de lecture sinon ce champ est vide et aucune lecture n est effectu e Le champ Stack obligatoire contient une information qui est empil e sur la pile d analyse Ce peut tre soit un nombre ent
30. le courant Ainsi avec le mod le 0 X 1 X 3 41 d signe le premier X et 43 le second Dont Delete et Insert sont des ensembles de symboles sp cifi s par l utilisateur qui permettent d influer sur le m canisme g n ral qui vient d tre d crit afin de limiter les possibilit s de suppression ou d insertion de symboles forte connotation s mantique Il est en effet souvent dangeureux pour la suite de l analyse de supprimer ou d ins rer un symbole ouvrant qui n cessite que l on rencontre plus tard le symbole fermant correspondant La prise en compte de ces deux ensembles conduit une modification dynamique des priorit s respectives des diff rentes instances des mod les de correction Ils ont en effet la d finition suivante Lors d une tentative de correction une instance d un mod le qui implique la suppression d un symbole de Dont Delete ne sera choisie que s il n existe pas d instance d un mod le m me moins prioritaire qui ne n cessite ni la suppression d un l ment de Dont Delete ni l insertion d un l ment de Dont Insert De m me l insertion d un l ment de Dont Insert ne pourra avoir lieu que si aucun mod le ne permet de correction sans suppression d l ment de Dont Delete Pour le niveau lexical les l ments de ces ensembles sont des caract res pour le niveau syntaxique il s agit de symboles terminaux Terminals dans la sp cification destin e la r cup
31. les pr c dences sont identiques alors l asso ciativit est utilis e associativit gauche implique Reduce associativit droite implique Shift et non associativit implique erreur Si le conflit ne peut tre r solu malgr tout on applique les r gles par d faut La plus grande prudence est vivement conseill e dans l emploi des r gles de d sambig ation 3 4 Optimisation de l automate Les automates produits par le constructeur LALR 1 sont optimis s lors d une deuxi me phase nomm e OPTIM Les optimisations effectu es sont de deux ordres optimisations propres l analyse LR L automate est tout d abord par titionn en trois une partie qui traite les transitions terminales les T tables une autre s occupant des transitions non terminales les NT tables et une troisi me partie les Prdct tables qui g re le traitement des pr dicats Les automates correspondants sont r duits Les productions simples sans s mantique sont partiellement limin es cette limination peut tre to tale sur option voir la documentation en ligne man csynt les transi tions non terminales apr s r duction ne n cessitant pas la pile d analyse sont d tect es et les NT tables sont compact es techniques de repr sentation de matrices creuses Les T tables et les NT tables sont lin aris es de facon conserver un temps constant pour l acc s l information Cette forme des tables est bien videmment
32. lexicaux Ceci est le codage en langage C des actions et pr dicats associ s la des cription lexicale de BNF include sxunix h define rule slice 100 static struct span unsigned long head struct tail unsigned long line unsigned int column tail coords static int xprod rules_no static int current_rule_no int bnf_get_line_no rule_no int rule_no return rule_no gt xprod O coords rule_no head SXVOID bnf_skip_rule register struct tail tail_coord register unsigned long line register unsigned int column if current rule no gt xprod 5 current rule no 0 tail_coord amp coords current_rule_no tail line tail_coord gt line column tail_coord gt column while sxsrcmngr source_coord line lt line if sxnext_char EOF return ANNEXE A SPECIFICATIONS DU LANGAGE BNF 62 while sxsrcmngr source_coord column lt column if sxnext_char EOF return SXVOID bnf_found_bad_beginning_of_rule 1 struct sxsource coord less coord less_coord sxsrcmngr source coord less coord column 1 sxput error less coord Illegal occurrence of lt the head of a new grammar rule is assumed sxsvar sxtables gt err_titles 2 sxsrcpush n lt less coord static VOID gripe 1 fputs nThe function V bnf scan actNV is out of date with respect to its specification n sxstderr abort
33. mantique L utilit d un pur analyseur lexico syntaxique est faible Certes il peut tre utile de savoir si un programme est syntaxiquement correct avant de le sou mettre un compilateur a priori plus lent mais dans la plupart des cas il faut compl ter l analyse par un traitement s mantique SYNTAX propose plu sieurs m thodes pour crire un tel traitement d crites ci apr s Pour chacune d elles un unique fichier source contient la fois la grammaire du niveau syn taxique et la sp cification du traitement s mantique Cette sp cification se fait en ins rant du texte apr s chaque production de la grammaire Un unique pro cesseur traite la fois la grammaire avec des fonctionnalit s h rit es de BNF et la sp cification de la s mantique 1 3 1 Actions La m thode de plus bas niveau mais aussi la plus puissante est d associer un num ro d action chaque production et d crire une proc dure comportant un fragment de programme pour chacun de ces num ros Lors de chaque r duc tion l analyseur appellera cette proc dure en lui passant le num ro de l action associ e la production par laquelle on r duit Cette action pourra alors acc der la pile d analyse et effectuer un traitement appropri Cette forme de s mantique est la plus d licate utiliser et la plus fastidieuse manipuler mais c est aussi la plus puissante puisque tout y est permis On pourrait la consid rer comme le langage d assemb
34. par un num ro Lors de l ex cution d une action que ce soit une action pr d finie ou une action de l utilisateur le caract re suivant dans le texte source a toujours t lu mais n a pas encore t pleinement exploit il est donc accessible si besoin est par l interm diaire du module de gestion du texte source dans la structure sxsrcmngr voir la documentation en ligne man sxsrcmngr Actions pr d finies Les actions pr d finies par le syst me sont les sui vantes OLOWER CASE Passe en minuscule tous les caract res qui ont t conserv s depuis le d but de la reconnaissance de l unit lexicale courante QUPPER CASE Passe en majuscule tous les caract res qui ont t conserv s depuis le d but de la reconnaissance de l unit lexicale courante LOWER_TO_UPPER Passe en majuscule le dernier caract re conserv QUPPER TO LOWER Passe en minuscule le dernier caract re conserv PUT char Ins re le caract re char dans la cha ne conserv e MARK M morise la position courante dans la cha ne conserv e voir les actions ERASE et GRELEASE ERASE Supprime tous les caract res qui ont pu tre conserv s depuis le pr c dent dans la m me unit lexicale s il existe ou sinon depuis le d but de la reconnaissance de l unit lexicale courante RELEASE Repousse dans le source les caract res m moris s depuis le pr c dent dans la m me unit lexicale
35. pas tre en premi re colonne et variable num ro 2 non nulle CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL39 Fic 4 7 Exemple de d finition d expression de pr dicats Abbreviations amp COND amp Is First Col amp Is Reset 2 amp Is First Col amp Is Set 2 Tokens Comments amp COND EOL EOL 2 Dans les langages formatt s la signification d une unit lexicale peut d pendre de l emplacement de son occurrence dans une ligne Prenons comme exemple de sp cification celle de BNF dans laquelle on impose que les non terminaux de la partie gauche d une r gle commencent en co lonne 1 Ces symboles ALHS NON TERMINAL et les non terminaux de la partie droite NON TERMINAL peuvent se d crire comme en figure 4 8 o le pr dicat amp IS FIRST COL r pond vrai si et seulement si le caract re auquel il est associ ici se trouve en colonne 1 dans le cas contraire on consid re que le lt est le d butant de 4NON TERMINAL 4 8 Extrait de la sp cification lexicale de BNF LHS NON TERMINAL amp IS FIRST COL EOL gt amp TRUE NON TERMINAL lt EOL gt amp TRUE 3 Le m canisme des actions et des pr dicats augmente la puissance th orique de description des expressions r guli res il est possible de d crire des langages non r guliers par exemple des commentaires imbriqu s Supposons que les caract res et marquent respec
36. s il existe ou sinon depuis le d but de l unit lexicale courante Les actions suivantes permettent la gestion de compteurs num rot s par tir de 0 Ces compteurs peuvent tre test s par l interm diaire des pr dicats pr d finis amp Is_Set et amp Is Reset voir plus loin Ils sont galement manipu lables par des actions vel des pr dicats de l utilisateur voir la documentation CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL36 en ligne man sxscanner Ces compteurs sont initialis s z ro au d but de l analyse de tout texte source RESET Mise z ro du compteur num ro SET n Mise un du compteur num ro n INCR n Le compteur num ro n est incr ment de 1 DECR n Le compteur num ro n est d cr ment de 1 Actions de l utilisateur Les actions utilisateur sont d finies par l apparition de leur nom dans une expression r guli re caract re 07 suivi d un nombre entier positif ou nul A chacune de ces actions doit correspondre une portion de programme crite par l utilisateur r alisant la fonction d sir e Ces actions sont ex cut es au cours de l analyse lexicale d un texte source Exemple En Ada la casse majuscule ou minuscule des lettres compo sant un identificateur est indiff rente Le m me nom peut donc s crire tant t en majuscules tant t en minuscules ou en m langeant les deux types de capi talisation Il est possible de m moriser les identif
37. une classe et dont le r sultat est le compl mentaire de la classe op rande par rapport ANY 4 1 6 3 Les actions Afin de permettre l utilisateur d ex cuter au cours de l analyse lexicale des traitements qui se sp cifient mal ou ne peuvent pas se sp cifier par le formalisme des expressions r guli res il a t introduit des actions dans la des cription lexicale Ces actions peuvent tre consid r es comme le pendant des actions s mantiques du niveau syntaxique CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL35 Fic 4 6 Exemples d utilisation de l op rateur L expression r guli re d finissant une chaine peut s crire QUOTE QUOTE QUOTE QUOTE QUOTE L criture amp Is First Col voir en 4 1 6 4 a la signification amp Is First Col c est dire carac t re quelconque diff rent de lt qui se trouve en premi re colonne Tout nom d action commence par le caract re 9 Certaines actions d int r t g n ral sont pr d finies par le syst me LECL Ces actions pourraient pour la plupart tre crites tr s simplement par l utilisateur leur existence se justifie toutefois non seulement par des consid rations d efficacit mais encore par l am lioration qu elles peuvent apporter la clart de la sp cification elles portent en effet un nom significatif de leur fonction alors que les actions de l utilisateur ne peuvent tre r f renc es que
38. valides d unit s lexicales il est possible de d finir une unit lexicale comme tant d crite par plusieurs expressions r guli res Cette possibilit appel e union est introduite par le mot cl UNION et se termine par le mot cl END voir l exemple de la figure 4 10 On r f rence les membres d une union par une notation point e nom de l unit nom du composant Il peut y avoir des clauses mot cl voir en 4 1 3 1 post action voir en 4 1 6 3 contexte voir en 4 1 7 1 et priorit voir en 4 1 7 3 associ es chaque com posant de l union Par d faut chaque composant h rite les clauses s il y en de l unit lexicale qui sont sp cifi es apr s le End marquant la fin de l union Pour une clause donn e cet h ritage est inhib si pour un composant d une union cette clause a t red finie au niveau de ce composant Fic 4 10 Exemple d utilisation de l union Consid rons la d finition suivante extraite de la sp cification du langage Ada Comments Union blanks SP HT EOL ada 2 _ EOL End Cette d finition quivalente en ce qui concerne la reconnaissance des commen taires Comments SP HT EOL EOL EOL permet par exemple d interdire la deuxi me forme des commentaires de suivre Vop rateur moins en le d finissant par _ 3 Context 11 But Comments ada ce qui signifie que la pr sence des caract res en d but d une un
39. AGE BNF 60 T_HEADER NT_BODY OCTAL Abbreviations PRINT lt amp PRINT SP gt On nn H NUMBER NORMAL FORM Tokens Comments 4LHS_NON_TERMINAL ANON TERMINAL A TERMINAL XGENERIC TERMINAL ACTION PREDICATE n n Mark amp Erase DIGIT O amp True DIGIT SP HT VT FF ven qot NaN EOL nte nt EOL EOL EOL EOL Priority Shift gt Reduce Context All But Comments lt amp Ts_First_Col Set 0 NT BODY gt lt NT BODY gt PRINT T_HEADER PRINT QUOTE N NnNN EOL EOL n lt n Put EOL b Put BS t Put HT y QPut VT f Put FF r Put CR Mark OCTAL True OCTAL amp True OCTAL amp True 2 bnfrtv n EOL QUOTE Priority Shift gt Reduce Context Comments 4 LETTER _ LETTER DIGIT Priority Reduce gt Reduce Shift gt Reduce Context Comments NUMBER_NORMAL_FORM Context Comments amp NUMBER NORMAL FORM Context Comments amp Ts_ Set 0 Reset 0 Q1 ANNEXE A SPECIFICATIONS DU LANGAGE BNF 61 scan act INIT erases the source text from beginning until the d first laying at column 1 01 Skip the source text until the first lt laying at column 1 02 Convert octal code nnn to character A 3 Actions et pr dicats
40. CII et le code interne du premier caract re d un intervalle doit bien entendu tre inf rieur ou gal celui du second des classes nomm es d finies pr alablement comme op rateurs binaires infixes lunion ensembliste a diff rence ensembliste CHAPITRE 4 CONSTRUCTION DE L ANALYSEUR LEXICAL27 TAB 4 3 Classes pr d finies pour les caract res non imprimables Nom Code ASCII octal NUL 000 SoH 001 STX 002 ETX 003 EOT 004 ENQ 005 006 007 BS 010 Back Space HT 011 Horizontal Tabulation LF 012 Line Feed VT 013 Vertical Tabulation FF 014 Form Feed CR 015 Carriage Return 50 016 SI 017 DLE 020 DC1 021 DC2 022 DC3 023 DC4 024 NAK 025 SYN 026 ETB 027 CAN 030 EM 031 SUB 032 ESC 033 FS 034 GS 035 RS 036 US 037 SP 040 Space DEL 177 CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL28 Une classe est anonyme si sa d notation appara t directement l endroit de son utilisation par exemple dans une expression r guli re Tous les caract res licites doivent tre d finis Cette d finition peut tre explicite ou implicite Un caract re est d fini explicitement s il apparait dans une d finition de classe nomm e ou anonyme il est d fini implicitement s il intervient dans le nom d un terminal non g n rique du niveau syntaxique alors qu il n est pas explicitement d fini Tout caract re non d fini impl
41. DU LANGAGE LECL 71 lt DENOTATION gt STRING_LITERAL STRING_DENOTATION REPRESENTATION SPECIFICATION lt REPR_SPEC_LIST_OPTION gt INH lt REPR_SPEC_LIST_OPTION gt REPR SPEC LIST lt REPR_SPEC_LIST gt REPR SPEC LIST lt REPR_SPEC gt 77 lt REPR_SPEC_LIST gt lt REPR_SPEC gt REPR SPEC S lt REPR_SPEC gt lt COLLATING_LIST_REPR gt 515 lt REPR_SPEC gt lt BYTE_LENGTH_REPR gt 576 lt REPR_SPEC gt lt WORD_LENGTH_REPR gt 52 lt COLLATING_LIST_REPR gt FOR INTERNAL CODE USE lt COLLATING_LIST gt VS BYTE LENGTH REPR FOR BYTE USE INTEGER NUMBER BITS 7 BYTE LENGTH WORD LENGTH REPR FOR WORD USE INTEGER NUMBER BITS 7 WORD LENGTH COLLATING LIST COLLATING LIST lt COMPOSANT gt 77 lt COLLATING_LIST gt lt COMPOSANT gt COLLATING_S lt COMPOSANT gt lt CLASS_REF gt 27 lt COMPOSANT gt UNUSED NOT SPECIFIED lt COMPOSANT gt ZINTEGER_NUMBER UNUSED Xo B 2 D finition lexicale Classes OCTAL SOM su ie Abbreviations IDENT LETTER _ LETTER DIGIT DARK_LET LETTER BS 1 LETTER BOLD_LET LETTER BS 1 LETTER BOLD_US no BS my DARK_US BS n 5 BOLD COMMERCIAL AT QU BS Q DARK AMPERSAND amp BS amp ANNEXE B SPECIFICATIONS DU LANGAGE LECL 72 BOLD_WORD DARK_WORD NUMBER_NORMAL_FORM Tokens Comments
42. FINALISATIONS JR ijt Be od bnf_smp what sxtables_ptr int what struct sxtables sxtables_ptr switch what case OPEN smpopen sxtables_ptr break case ACTION smppass break 80 Annexe D Le fichier Titles gt Warning Nt Error Nt Scanner Local 1234 X123 X012 4 3 Dont Delete Dont Insert Global Detection parameter Keyword Eol Eof Halt Parser Local 082 P4 NO standard recor The invalid character 0 is deleted The invalid character 0 N is replaced by 40 The character 70 is inserted before 0 s is deleted character in error This unknown keyword is erased End Of Line End Of File Scanning stops on End Of File Misspelling of 1 which is replaced by the keyword 41 Misspelling of O NV before 1 which is replaced by the keyword gL nA NE TN ae aes DT is inserted before 1 is replaced by 41 is deleted 42 is inserted before 1 81 ANNEXE D LE FICHIER STANDARD 82 X01723 3 N 40 is inserted before O 1 UN MOM X 1 2 3 4 2 0 before 1 is replaced by 40 NAME MUS 1234 O before V 1 is deleted X234 f 0 1
43. ID LETTER LETTER DIGIT Reduce ID LETTER LETTER DIGIT detected on ANB DIGIT Priority is given to Shift 1_look_ahead Shift Reduce conflict in state 4 on DIGIT between Shift ANB DIGIT Reduce ANB DIGIT detected on ANB DIGIT Priority is given to Shift Le premier diagnostic signifie que si deux identificateurs se succ dent sans s parateur il est impossible de les distinguer de l occurrence d un seul Le trai tement par d faut est dans ce cas de consid rer que a un seul identificateur priorit est donn e a la chaine la plus longue CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL45 Le second et le troisi me ont des significations analogues identificateur suivi d un nombre et nombre suivi d un nombre Si l on veut viter ces messages il est possible de sp cifier en utilisant les clauses contexte qu un identificateur ou un nombre ne peut pas suivre imm diatement un identificateur et qu un nombre ne peut pas suivre un nombre LETTER LETTER DIGIT Context A11 But YID ANB NB DIGIT Context All But YNB La r solution de ces conflits peut galement tre obtenue sans diagnostic en utilisant les clauses priorit LETTER LETTER DIGIT Priority Shift gt Reduce 4NB DIGIT Priority Shift gt Reduce 4 1 8 Exemples de d finitions lexicales On trouvera en annexe les sp cifications LECL d
44. ION PRDCT OR 77 PRDCT ET EXPRESSION PRDCT NOT TOKEN S TOKEN TOKEN lt BODY TOKEN DEF LEXICAL UNIT NAME LEXICAL UNIT NAME LEXICAL UNIT NAME 2r EOF 77 COMMENTS INCLUDE ANNEXE B SPECIFICATIONS DU LANGAGE LECL END lt COMPONENT_LIST gt lt COMPONENT_LIST gt lt COMPONENT gt lt COMPONENT_LIST gt lt COMPONENT gt lt COMPONENT gt lt COMPONENT_DEF gt lt VOID gt lt COMPONENT gt lt COMPONENT_DEF gt COL 27 lt ENVIRONMENT_LIST gt lt COMPONENT_DEF gt lt COMPONENT_NAME gt COL 24 SPACE lt COMPONENT_NAME gt IDENTIFIER ENVIRONMENT LIST ENVIRONMENT LIST ENVIRONMENT ENVIRONMENT LIST ENVIRONMENT n n nen gt 68 B COMPONENTS S COMPONENT COMPONENT REGULAR EXPRESSION COMPONENT DEF COMPONENT NAME DEF ENVIRONMENT S NOT KEYWORD POST ACTION lt ENVIRONMENT gt YIDENTIFIER amp 1 IDENTIFIER amp 1 retourne VRAI ssi le premier identificateur est NOT et le second KEYWORD ENVIRONMENT YACTION_NO lt ENVIRONMENT gt lt PRIORITY gt lt ENVIRONMENT gt lt CONTEXT gt lt PRIORITY gt PRIORITY lt PRIORITY_KIND_LIST gt lt PRIORITY_KIND_LIST gt lt PRIORITY_KIND_LIST gt lt PRIORITY_KIND_LIST gt lt PRIORITY_KIND gt lt PRIORITY_KIND gt
45. IRST COL Vrai si et seulement si les caract res de la classe courante sont en premi re colonne amp IS LAST COL Vrai si et seulement si les caract res de la classe courante sont sur la derni re colonne d une ligne amp IS RESET Vrai si et seulement si le compteur num ro n est nul amp IS SET n Vrai si et seulement si le compteur num ro n est non nul Les pr dicats utilisateur Ils d signent soit une fonction bool enne de luti lisateur caract re amp suivi d un nombre entier positif ou nul soit un nom d ex pression bool enne caract re amp suivi d un identificateur Dans ce deuxi me cas l expression bool enne a d tre d finie au pr alable dans le paragraphe ABBREVIATIONS de la facon suivante o nom de l expression lt expression bool les op rateurs de expression bool sont la concat nation par juxtaposition op ration et l op rateur op ration ou l op rateur avec les pr c dences usuelles les op randes sont des pr dicats chaque pr dicat peut tre soit un pr dicat syst me dynamique soit un pr dicat utilisateur soit un nom d ex pression de pr dicats d fini pr alablement 66 72 op ration de compl mentation Exemples 1 La figure 4 7 sp cifie qu un commentaire commence par le caract re v rifiant la condition tre en premi re colonne et variable num ro 2 nulle ou ne
46. LE SYSTEME SYNTAX MANUEL D UTILISATION ET DE MISE EN UVRE SOUS UNE Pierre Boullier Philippe Deschamp INRIA Rocquencourt BP 105 18153 Le Chesnay Cedex France Mise jour de Ao t 1991 dition du 18 octobre 2007 Ce document permet l utilisation du syst me SYNTAX de production de traducteurs implant sous UNIX il d crit la version de distribution 3 5 de juillet 1988 Tous commentaires remarques questions et suggestions seront bien venus qu ils concernent le syst me lui m me ou le pr sent manuel s adresser l quipe Langages et Traducteurs de l INRIA par courrier ou par t l phone x au 33 1 39 63 56 05 par courrier lectronique 4 syntax minos inria fr liste de personnes ou directement aux auteurs Copyright 1988 INRIA Projet Langages et Traducteurs Autorisation est donn e toute personne de fabriquer ou distribuer des copies int grales et fid les de ce document sous toute forme que ce soit condition que le copyright et le pr sent alin a soient pr serv s afin de transmettre au r cipiendaire les m mes droits Autorisation est donn e de distribuer des versions modifi es de ce document ou d extraits de ce document aux m mes termes que ci dessus la condition suppl mentaire que les modifications Soient mises en vidence sign es et expliqu es Permission is granted to anyone to make or distribute verbatim copies of this document as received in any medium pro
47. MAT S mantique par arbre abstrait 5 2 1 Sp cification et construction de l arbre abstrait 5 2 2 R alisation de l analyseur s mantique RECOR Le traitement des erreurs 6 1 Traitement des erreurs syntaxiques 4 6 1 1 Correction locale ee 6 1 2 R cup ration globale 6 2 Traitement des erreurs lexicales 6 3 Le fichier standard recor TABLES C Production des tables d analyse en langage Analyse d un texte source SL Miseen uvre uo n n 8 4 Sp cifications du langage BNF A 1 D finition syntaxique A2 D finition lexicales i 20 0 up EE Actions et pr dicats lexicaux Sp cifications du langage LECL B 1 D finition syntaxique B 2 D finition 1 Actions lexicales B 4 Pr dicats syntaxiques Exemples li s la s mantique C 1 Le programme d actions s mantiques C 2 Trame de passes s mantiques D Le fichier standard recor Exemples de grammaires non LALR 1 Une grammaire ambig e ELL Grammaire E 1 2 Lisage des confits u u 2 22222 442 2 Une grammaire non LR 1
48. ON DE L ANALYSEUR SYNTAXIQUE18 4 Ins rer dans la grammaire des pr dicats vel des actions voir en 2 2 2 afin d aider la r solution des conflits Dans tous les cas sur un conflit avant de choisir un type de r solution il faut comprendre la raison profonde de ce conflit Cette tache peut ne pas tre facile voir le chapitre pr c dent et la documentation en ligne man csynt Chacune de ces m thodes a ses avantages et ses inconv nients 1 C est la m thode des purs et durs Outre le fait qu elle puisse tre d licate mettre en ceuvre elle a tendance loigner la grammaire de sa forme naturelle Il peut tre parfois pr f rable de d crire un sur langage le compl mentaire tant filtr par la s mantique 2 Par d faut le syst me donne priorit au Shift lors d un conflit Shift Reduce la r gle qui appara t la premi re dans la grammaire lors d un conflit Reduce Reduce 3 Lors de la d tection du premier conflit CSYNT cherche un fichier de nom nom du langage dt Si ce fichier existe il est cens contenir des tables produites par le module PRIO qui vont aider le constructeur CSYNT r soudre les conflits Voir ci dessous le format et la signification des sp cifications destin es PRIO L avantage de cette facon de proc der est la grande finesse possible pour la r solution des conflits l inconv nient en est que l on peut ne plus savoir quel est le langage reconnu
49. UENCE lt TERM gt lt SEQUENCE gt lt TERM gt lt TERM gt lt ITEM gt lt TERM gt lt ITEM gt lt ITEM gt lt ALTERNATIVE gt lt ITEM gt lt ALTERNATIVE gt lt ITEM gt lt ALTERNATIVE gt lt ITEM gt lt ALTERNATIVE gt lt ITEM gt lt ALTERNATIVE gt lt ITEM gt lt ALTERNATIVE gt lt ITEM gt lt ALTERNATIVE gt lt ITEM gt lt EXTENDED_CLASS_REF gt lt ITEM gt lt ACTION gt lt EXTENDED_CLASS_REF gt lt NOT_CLASS_REF gt lt PREDICATE gt lt EXTENDED_CLASS_REF gt lt NOT_CLASS_REF gt lt NOT_CLASS_REF gt lt CLASS_REF gt lt NOT_CLASS_REF gt lt CLASS_REF gt lt ACTION gt AACTION_NO lt ACTION gt QUPPER CASE ACTION QLOWER CASE TOKEN REF REF S COMPONENT REF COMPONENT NAME REF COMPONENT REF CONTEXT COMMENTS CONTEXT EOF CONTEXT NAME CONTEXT NAME CONTEXT NAME CONTEXT NAME COMPONENT REF REGULAR EXPRESSION ALTERNATIVE SEQUENCE ERASE EXPRESSION OPTION REF TRANS CLOSURE REF TRANS CLOSURE REF TRANS CLOSURE TRANS CLOSURE TRANS CLOSURE EXTENDED CLASS NOT UPPER CASE LOWER CASE ANNEXE B SPECIFICATIONS DU LANGAGE LECL 70 lt ACTION gt LOWER_TO_UPPER lt ACTION gt QUPPER TO LOWER ACTION QERASE ACTION QSET INTEGER_NUMBER ACTION
50. VIATION amp EXPRESSION ABBREVIATION gt ABBREVIATION_RE_NAME gt ABBREVIATION_PRDCT_NAME ANNEXE B SPECIFICATIONS DU LANGAGE LECL lt amp _EXPRESSION gt lt amp _OR gt lt amp _OR gt lt amp _ET gt lt amp _ET gt lt amp _TERM gt lt amp _TERM gt lt amp _TERM gt lt amp _TERM gt TOKENS lt amp _OR gt lt amp _OR gt lt amp _ET gt lt amp _ET gt lt amp _ET gt lt amp _TERM gt lt amp _TERM gt lt amp _OR gt 4PREDICATE_NAME lt DYNAMIC_PREDICATE gt lt DYNAMIC_PREDICATE gt lt TOKENS_LIST_OPTION gt INH lt TOKENS_LIST_OPTION gt lt TOKENS_LIST gt lt TOKENS_LIST gt lt TOKEN gt lt TOKEN gt lt TOKEN_DEF gt TOKENS TAB lt TOKENS_LIST gt lt TOKENS_LIST gt lt TOKEN gt lt TOKEN gt lt TOKEN_DEF gt lt VOID gt lt TOKEN_DEF gt COL 27 lt ENVIRONMENT_LIST gt lt LEXICAL_UNIT_NAME gt COL 24 SPACE lt LEXICAL_UNIT_NAME gt GENERIC_NAME lt LEXICAL_UNIT_NAME gt ASTRING_LITERAL lt LEXICAL_UNIT_NAME gt 4IDENTIFIER lt LEXICAL_UNIT_NAME gt EOF lt LEXICAL_UNIT_NAME gt COMMENTS lt LEXICAL_UNIT_NAME gt lt TOKEN_BODY gt lt TOKEN_BODY gt lt UNION gt INCLUDE lt REGULAR_EXPRESSION gt COL 14 lt UNION gt UNION lt COMPONENT_LIST gt 77 PRDCT EXPRESS
51. Y_S_n break case VOCABULARY_S_n VISITED gt name ACTION_n GENERIC_TERMINAL_n LHS_NON_TERMINAL_n NON_TERMINAL_n TERMINAL_n X_NON_TERMINAL_n X_TERMINAL_n break case X_NON_TERMINAL_n switch VISITED gt position case 1 VISITED gt name NON_TERMINAL_n break case 2 VISITED gt name PREDICATE n break 78 ANNEXE EXEMPLES LIES A LA SEMANTIQUE break case X_TERMINAL_n switch VISITED gt position case 1 VISITED gt name GENERIC_TERMINAL_n TERMINAL_n break case 2 VISITED gt name PREDICATE_n break break ZZZZ end bnf_pi static bnf_pd DERIVED switch VISITED gt name case ERROR n break case ACTION n break case BNF_n break case GENERIC TERMINAL n break case LHS NON TERMINAL n break case NON TERMINAL n break case PREDICATE n break case RULE_S_n break case TERMINAL n break 79 ANNEXE C EXEMPLES LIES A LA SEMANTIQUE case VOCABULARY_S_n break case X_NON_TERMINAL_n break case X_TERMINAL_n break ZZZZ end bnf_pd static smpopen sxtables_ptr struct sxtables sxtables_ptr sxatcvar atc_lv node_size sizeof struct bnf_node static smppass INITIALISATIONS PR Nc ATTRIBUTES EVALUATION sxsmp sxatcvar atc lv abstract tree root bnf pi bnf pd
52. al de SYNTAX Nombre de ses caract ristiques ont t emprunt es son pr d cesseur new 10cl mais il s en distingue notam ment par une plus grande facilit de description et une plus grande puissance de sp cification LECL a pour donn es d une part la description des unit s lexicales du lan gage sous forme d expressions r guli res fournie par l utilisateur et d autre part des informations extraites des tables produites par BNF nom du langage bt son r le est de produire un automate d tats finis capable d effectuer la recon naissance des terminaux du niveau syntaxique 4 1 M talangage lexical La sp cification d un analyseur lexical en LECL est un texte qui doit v rifier une certaine syntaxe Le langage LECL peut donc se d crire l aide du syst me SYNTAX voir l annexe Informellement le niveau lexical de LECL se d finit comme suit C est un langage non positionnel le placement d une unit lexicale dans une ligne est sans importance qui comporte des mots cl s r serv s Les mot cl s de LECL au nombre de 43 sont r pertori s dans la table 4 1 Les mots cl s commen ant par amp repr sentent les pr dicats syst me voir en 4 1 6 4 ceux commen ant par repr sentent les actions syst me voir en 4 1 6 3 L ensemble des caract res ASCII est licite Les identificateurs sont form s d une lettre suivie d un nombre quelconque ventuellement nul de lettres ou de c
53. antique produites par les diverses phases de la construc tion Il contient en outre si nom du langage comporte des mots cl s le texte en langage C de la fonction check keyword 57 Chapitre 8 Analyse d un texte source L analyse d un texte source est r alis e en une ou deux passes suivant le type de description s mantique choisi La premi re passe correspond l analyse lexicale et syntaxique du texte source L analyse lexicale est r alis e par l analyseur lexical ou scanner qui est un interpr teur de l automate d tats finis produit par LECL Le scanner lit le texte source par l interm diaire du source manager et remplit d une part la structure terminal token qui sera exploit e par l analyseur syntaxique et d autre part la string table table contenant les textes des unit s lexicales exploit e par l interm diaire du string manager L analyse syntaxique est r alis e par l analyseur syntaxique ou parser qui est un interpr teur de l automate pile produit par CSYNT Au cours de cette passe selon le type de s mantique choisi des appels des actions s mantiques sont effectu s ou bien un arbre abstrait est engendr Dans le cas on r alise la s mantique par arbre abstrait une deuxi me passe SEMANTIC PASS est effectu e Elle consiste uniquement ex cuter le programme semantic pass crit par l utilisateur Les analyseurs lexical et syntaxique contiennent galement des modules per
54. c ce terminal en entr e apr s que la pile ait t cr t e jusqu a cet tat L effet net de ce m canisme est d ignorer une partie de texte entourant le point d erreur ce qui est un pis aller mais permet d analyser la suite du texte Le rattrapage lexical consiste 4 d truire purement et simplement le caract re en erreur L action combin e des deux phases du traitement d erreur de SYNTAX est en pratique tr s satisfaisante et en tous cas incomparablement sup rieure celle de YACC 1 1 4 3 Sp cification du traitement d erreur Tous les aspects du traitement d erreur sont d crits s par ment de la gram maire qu il s agisse de l affichage de la correction locale ou du rattrapage global et ce aussi bien pour l analyse lexicale que pour l analyse syntaxique L auteur de cette description sp cifie en particulier les mod les de correction les termi naux cl s et les messages d erreur aucune partie de message n tant fabriqu e directement par SYNTAX ceci permet de les adapter par exemple la langue naturelle des utilisateurs ou leur niveau de comp tence Cette description est trait e par le processeur RECOR 1 1 5 Production des tables TABLES Ce dernier processeur lit les tables produites par les autres constructeurs et construit un programme C compos essentiellement de structures de donn es initialis es contenant toutes les informations n cessaires au syst me d ex cution de SvNTAX
55. contexte Cette clause contexte se termine par un point virgule et peut s crire de trois mani res diff rentes 1 Unbounded Context liste de suivants 2 Unbounded Context A11 3 Unbounded Context All But liste de suivants Dans le premier cas on indique explicitement la liste des suivants valides Dans le deuxi me cas on indique que les suivants valides sont ceux d duits de la grammaire syntaxique sans modification Le troisi me cas est analogue au pr c dent except que lis e de suivants est supprim e des suivants valides Les suivants s par s par des virgules peuvent tre un nom d unit lexicale identificateur ou chaine de caract res un nom d un composant d union voir ci dessous Ces contextes peuvent tre utilis s de deux facons pour r soudre des conflits 1 si le mot cl Unbounded est absent on est en mode 1 look ahead LECL essaie alors de r soudre les conflits la vue d un seul caract re en avance CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL42 2 si le mot cl Unbounded est pr sent LECL peut utiliser un nombre non born de caract res en avance Une r solution Unbounded sur une unit lexicale dont le contexte est directement donn par la grammaire du ni veau syntaxique et non modifi par une clause Context explicite doit tre introduite par Unbounded Context A11 4 1 7 2 Les unions Afin d augmenter la pr cision de la description des s quences
56. cor respondant aux non terminaux et aux terminaux g n riques de la partie droite deviennent les fils d un nouveau n ud repr sentant le non terminal de la partie gauche de la r gle Ce nouveau noeud porte le nom qui se trouve en fin de r gle un terminal g n rique correspond une feuille qui porte le m me nom que ce terminal Cependant dans le cas o ce terminal g n rique se trouve dans une r gle ne comportant pas d autres terminaux g n riques et aucun non terminal et que cette r gle est suivie par un nom de n ud alors la feuille qui correspond au terminal g n rique porte ce nom Les r gles de construction qui viennent d tre nonc es ne sont pas tout fait syst matiques Il existe quelques exceptions importantes 1 Lorsque l analyseur syntaxique reconnait une r gle ne comportant que des terminaux non g n riques ou une r gle vide il cr e une feuille dont le nom est le nom de n ud associ s il est sp cifi sinon VOID 2 Si le nom d un non terminal r cursif gauche se termine par 1 157 par RIGHT LIST s il est r cursif droite tous les l ments de la liste sont r unis sous un m me n ud Aucun nom de n ud ne doit suivre la les r gle s r cursive s d finissant ce non terminal Si la les r gle s d finissant ce non terminal et d butant ou finissant la r cursion est suivie d un nom de n ud le n ud liste cr portera ce nom sinon il porte le nom du non terminal
57. ction Ces mod les fournis la construction par l auteur de la grammaire peuvent sp cifier un nombre quelconque de suppressions d insertions vel de remplacements dans le texte source Si l une des parties de texte engendr es correspond l un de ces mod les la correction est accept e le nouveau texte vient remplacer l ancien et l analyse reprend De nombreux dispositifs annexes permettent l auteur de la sp cification de contr ler tr s finement le m canisme de correction correction de fautes d or thographe sur les mots cl s longueur de validation terminaux cl s ensembles CHAPITRE 1 INTRODUCTION 4 Don t Delete et Don t Insert possibilit d agir sur le terminal pr c dant l er reur Notons que l analyseur lexical b n ficie du m me m canisme de correction que l analyseur syntaxique Notons aussi que ce m canisme est totalement in d pendant de la grammaire et ne n cessite pas de modifier cette derni re 1 1 4 2 Rattrapage global Si la correction locale choue ce qui se produit dans moins de 20 des cas en pratique l analyseur doit tout de m me pouvoir analyser le reste du texte Ceci est possible grace au rattrapage global Pour qui est du rattrapage syntaxique le texte est lu sans analyse jusqu rencontrer un terminal cl tel qu il existe dans la pile un tat ayant une transition non terminale valide pouvant tre suivie du dit terminal L analyseur est ensuite red marr ave
58. donn e du moins prioritaire vers le plus prioritaire Ainsi CHAPITRE 3 CSYNT CONSTRUCTION DE L ANALYSEUR SYNTAXIQUE19 left left d crit la priorit et l associativit des quatre op rations arithm tiques usuelles L addition et la soustraction sont associatives gauche et sont moins prioritaires que la multiplication et la division qui sont elles aussi associatives gauche Le mot cl right est utilis pour d finir l associativit droite et le mot cl 4nonassoc est utilis pour d finir des op rations qui comme le LT de FORTRAN ne peuvent s associer avec elles m mes Ainsi A LT B LT C est ill gal en FORTRAN b En r gle g n rale une production prend la priorit et l associativit de son terminal le plus droite s il existe Il est possible de modifier cette r gle g n rale pour une production en crivant cette production et en la faisant suivre du mot cl prec suivi d un symbole La production prend alors la priorit et l associativit de ce symbole Ce symbole et donc sa priorit doit avoir t d fini dans la partie a Exemple Consid rons la grammaire de la figure 3 2 Cette grammaire est Fic 3 2 Grammaire d expressions lt EXPR gt lt EXPR gt lt gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt lt EXPR gt IDENT d
59. du langage_pi chaque fois qu un noeud est visit en synth tis sxsmp ap pelle nom du langage_pd On trouvera en annexe C 2 titre d exemple la passe s mantique produite automatiquement par SEMAT sur la grammaire syntaxique de BNF Remarques Il est possible de sp cifier que le prochain noeud visit sera node dans le sens kind INHERITED ou DERIVED en utilisant la macro sxat snv kind node Le module MIX voir la documentation en ligne man mix peut aider g rer les versions successives d une passe s mantique Chapitre 6 RECOR Le traitement des erreurs Pour tout langage nom du langage une sp cification destin e au traitement des erreurs doit tre d crite dans un fichier nom du langage recor En g n ral ce fichier sera construit par modifications de standard recor Une modification de la sp cification du traitement des erreurs ne n cessite que de r activer le module RECOR sans avoir repasser les autres phases de la construction 6 1 Traitement des erreurs syntaxiques Le traitement des erreurs dans le syst me SYNTAX se d compose en deux parties 1 une tentative de correction locale du programme source erron 2 si la tentative pr c dente choue r cup ration de l erreur d tect e au niveau global 6 1 1 Correction locale Supposons qu une erreur de syntaxe soit d tect e sur le symbole terminal Soit le texte source o est la portio
60. e expression r guli re plusieurs cas peuvent se produire L unit lexicale est EOF End Of File l analyseur lexical renvoie le code de EOF l analyseur syntaxique L unit lexicale est un terminal l analyseur lexical renvoie le code du terminal et m morise la chaine de caract res dans une table Cette table est manipulable par l interm diaire des proc dures du string manager voir la documentation en ligne man sxstr mngr L unit lexicale est COMMENTS les caract res composant cette unit sont accessibles s ils ont t conserv s par l interm diaire de la struc ture token voir la documentation en ligne man sxunix associ e l unit lexicale qui suit ces commentaires Exemple Dans la d finition syntaxique on trouve la r gle expression expression PLUS terme et au niveau lexical on trouve PLUS PLUS est un terminal du langage Lorsque l analyseur lexical reconnait la chaine il renvoie le code du terminal PLUS Remarque L unit lexicale EOF permet l utilisateur de pr ciser que ses fichiers se terminent par une certaine chaine de caract res Si l on ne men tionne pas EOF dans les unit s lexicales le syst me g n rera un EOF lors de la reconnaissance de la fin physique du fichier 4 1 3 1 Les mots cl s Par d finition un mot cl est un terminal non g n rique qui est reconnu par u
61. e correspondante et le pr dicat utilisateur num ro n a retourn vrai D un point de vue syntaxique si s amp r et t amp n sont des symboles tendus s amp m t amp n s t m n ainsi l on a end amp 9 amp 009 Remarques Il est indispensable que le codage des pr dicats soit r alis sans effet de bord les pr dicats sont cens s tre purs En effet une m me occurrence d un pr dicat peut donner lieu plusieurs ex cutions de la fonction qui l implante test du look ahead puis shift pour l explication de ces termes voir au chapitre 3 ou traitement des erreurs Si dans un tat donn pour un symbole X coexistent shift vel look ahead des occurrences tendues et des occurrences simples le syst me consid re que les occurrences simples de X dans cet tat sont en fait des occurrences tendues X amp Else le pr dicat fictif Else s valuant toujours en vrai L ordre d ex cution des pr dicats associ s un symbole n est pas sp cifi sinon que le pr dicat fictif amp Else est toujours ex cut en dernier Il faut donc que dans un tat donn les pr dicats associ s un m me terminal soient exclusifs les uns des autres Du fait du traitement des erreurs voir le chapitre 6 lors de l ex cution d une action l unit lexicale suivante est lue et test e pr dicat ventuel compris et l unit lexicale d apr s est lue et semi test e il existe dans
62. e pr ciser les suivants imm diats possibles des unit s lexicales et des commentaires On appelle suivants imm diats l ensemble des unit s lexicales pouvant suivre une unit lexicale donn e conform ment la grammaire du niveau syntaxique et aux clauses contextes Attention cette notion est d finie en terme d unit s lexicales et non en terme de terminaux du niveau syntaxique Exemple Supposons que le mot cl THEN puisse d apr s la grammaire suivre un nombre entier terminal g n rique 4integer et que ce mot cl soit reconnu par l unit lexicale identifier alors Aidentifier est un l ment des suivants imm diats de integer En l absence de clause contexte les suivants imm diats sont pour un commentaire toutes les unit s lexicales ainsi que les commen taires pour une unit lexicale les commentaires plus les unit s lexicales recon naissant les terminaux qui peuvent suivre d apr s la grammaire n importe quel terminal reconnu par cette unit lexicale La clause contexte si elle existe doit suivre C le marquant la fin de l expression r guli re laquelle elle s applique ou le marquant la fin de la clause Priority voir en 4 1 7 3 si elle est pr sente ou le marquant la fin de la sp cification d une post action voir en 4 1 6 3 ou le marquant la fin de la clause NOT KEYWORD ou le marquant la fin d une autre clause
63. e toute vidence ambigiie il est cependant possible de r soudre ais ment les conflits comme le montre la figure 3 3 La derni re r gle de cette sp cification Fic 3 3 D sambig ation de la grammaire d expressions left left lt EXPR gt lt EXPR gt Aprec indique que la priorit et l associativit de la production cit e donc du unaire sont celles de Les r gles de d sambigtiation sont utilis es par CSYNT de la facon suivante pour r soudre des conflits 1 On enregistre les pr c dences et associativit s des terminaux s il y en a 2 Une pr c dence et une associativit sont associ es chaque r gle de la grammaire ce sont la pr c dence et l associativit du symbole terminal le plus droite dans cette r gle s il existe Si la construction prec est CHAPITRE 3 CSYNT CONSTRUCTION DE L ANALYSEUR SYNTAXIQUE20 utilis e la valeur sp cifi e vient remplacer la valeur par d faut Certaines r gles de grammaire et certains terminaux peuvent donc ne pas avoir de priorit vel d associativit 3 Quand un conflit Shift Reduce ou Reduce Reduce se produit si le sym bole en conflit ou une r gle impliqu e dans un Reduce n a ni priorit ni associativit alors les r gles par d faut voir page 18 s appliquent et le conflit est signal 4 Sinon le conflit est r solu en faveur de l action Shift ou Reduce associ e la pr c dence la plus forte Si
64. ed NOT_code sxstrsave NOT KEYWORD_code sxstrsave KEYWORD return case PREDICATE switch action_no case 1 return sxget token sxplocals ptok_no gt string_table_entry NOT_code amp amp sxget token sxplocals ptok no 1 string table entry KEYWORD code default break break default break ANNEXE B SPECIFICATIONS DU LANGAGE LECL fputs The function lecl_pars_act is out of date with respect to its specification n sxstderr abort 75 Annexe C Exemples li s la s mantique C 1 programme d actions s mantiques On trouvera ci dessous la structure que doit respecter le programme utilisa teur codant les actions s mantiques include sxunix h static action action no int action no switch action no case 0 break case 1 break case 2 break default Message d erreur L action entry arg int entry struct sxtables arg switch entry case OPEN appele avant l analyse des textes source On prepare les donnees ne dependant que du langage source et non des textes source 76 ANNEXE EXEMPLES LIES A LA SEMANTIQUE 77 break case INIT appele avant l analyse d un texte bedi case ACTION appele a chaque reduction syntaxique action arg arg action no break case ERROR appele en cas d erreur de syntaxe non corrigible bresk case FINAL appele apres l analyse synta
65. es guillemets de d but et de fin peuvent tre limin s en ne conservant que les caract res utiles L utilisateur a la possibilit de sp cifier si un groupe de caract res doit tre ou non conserv par l analyseur lexical en faisant pr c der le facteur qui correspond ce groupe de l op rateur unaire Cette suppression doit tre coh rente c est dire que deux occurrences du m me caract re atteintes simultan ment lors d une analyse lexicale ne peuvent la fois tre conserv es et supprim es Fic 4 5 Exemples d utilisation de l op rateur Les deux expressions r guli res suivantes sont a priori licites QUOTE tout sauf quote QUOTE QUOTE QUOTE SP EOL tout sauf EOL EOL En revanche la description suivante est erron e QUOTE ftout sauf quote QUOTE QUOTE3 QUOTE En effet lors de la reconnaissance d une cha ne les occurrences 2 et 4 de QUOTE sont atteintes en parall les S agit il du guillemet de fin ou d un guillemet int rieur Seule la connaissance du symbole suivant va permettre d en d cider est donc erron dans ce cas de sp cifier simultan ment une suppression occur rence 4 et une m morisation occurrence 2 27 Attention L op rateur binaire utilis dans les classes diff rence en sembliste ne peut pas tre utilis dans les expressions r guli res 66 99 4 1 6 2 L op rateur C est un op rateur unaire dont l op rande est
66. fait en attachant des noms de noeud certaines productions La description est trait e par le processeur SEMAT Ce dernier produit outre des tables permettant un module du syst me d ex cution de construire l arbre au cours de l analyse syntaxique des squelettes de programmes C dans lesquels les actions effectuer sur chaque n ud visit peuvent tre ins r es Un autre module du syst me d ex cution permet de par courir ces arbres du haut en bas et de gauche droite on peut aussi program mer des parcours diff rents en appelant les actions associ es chaque n ud CHAPITRE 1 INTRODUCTION 7 1 1 Exemple de sp cification de paragraphage Voici un extrait d une grammaire de PASCAL bien pr sent e lt PROC DECL gt lt PROC HEAD gt lt BLOCK gt PROC HEAD procedure ID lt FORMALS x lt BLOCK gt lt DECL gt lt COMPOUND STMT gt lt COMPOUND STMT gt begin lt STMT gt end PARADIS produit automatiquement un paragrapheur a partir de la sp cification pr c dente ce paragrapheur est capable de transformer le texte suivant ProCedure TRuc begin instruction1 Instruction2 end 3 en la forme paragraph e suivante procedure TRUC begin INSTRUCTION1 INSTRUCTION2 end Des informations peuvent tre attach es chaque noeud Un autre module du syst me d ex cution produit une repr sentation semi graphique alphanum
67. finition lexicale d un langage commen taires imbriqu s Cette section pr sente une alternative la description des commentaires du langage OLGA pr sent e en figure 4 9 F 2 1 Expressions r guli res Dans la description du langage principal de niveau z ro 1lev lecl se contente de d tecter le d but d un commentaire ici et on appelle l action utilisateur 00 Comments Q0 90 ANNEXE EXEMPLES DE DEFINITIONS LEXICALES 91 Cette action appelle l analyseur lexical du langage hlev qui se charge de la reconnaissance d un niveau de commentaire un niveau quelconque la re connaissance d une accolade ouvrante induit l appel du niveau suivant par l interm diaire de l action 01 essentiellement identique l action 00 alors que la reconnaissance d une accolade fermante Y vue par le niveau courant comme une fin de fichier entraine le retour au niveau pr c dent Comments aren 01 Eof zy F 2 2 Actions lexicales include sxunix h extern struct sxtables hlev_tables Structures used to store the local variables of a given scanner static struct sxsvar llev_svar hlev_svar llev_sact entry action_no int entry int action_no switch entry case OPEN case CLOSE llev svar sxsvar sxsvar hlev svar llev_svar sxtables gt analyzers scanner entry amp hlev tables hlev_svar sxsvar sxsvar llev_svar return case INIT
68. hiffres pouvant tre pr c d s d un blanc soulign _ La capitalisation des lettres n a aucune influence sur la signification des identificateurs ou des mots cl s 24 CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL25 TAB 4 1 Les mots cl s de LECL amp FALSE 15 FIRST COL amp IS LAST COL amp IS RESET amp IS SET amp TRUE CDECR CERASE CINCR CLOWER_CASE LOWER_TO_UPPER MARK PUT RELEASE RESET SET UPPER_CASE UPPER_TO_LOWER ABBREVIATIONS ALL BITS BUT BYTE CLASSES CODE COMMENTS CONTEXT END END FILE EOF FOR INCLUDE INTERNAL PRIORITY REDUCE SHIFT SYNONYMS TOKENS UNBOUNDED UNION UNUSED USE WORD Certains identificateurs peuvent repr senter des terminaux du niveau syn taxique o la capitalisation est significative Si ces terminaux comportent des lettres minuscules il faut les repr senter comme des cha nes de carac t res entre guillemets en conservant la capitalisation utilis e dans BNF Un commentaire est introduit par deux signes moins et se termine la premi re fin de ligne rencontr e Les chaines de caract res sont repr sent es entre guillemets Ces guillemets d limitent un nombre strictement positif de caract res quel conques dont la convention de repr sentation est celle du langage C voir en page 10 La d finition syntaxique du langage est divis e en cinq parties Chacune de ces parties est optionnelle 4 1 1 Les
69. icateurs sous une forme nor male ne comportant par exemple que des lettres majuscules la transformation d un identificateur quelconque vers cette forme normale passage des minus cules en majuscules peut tre programm e en utilisant une action syst me Cette action peut soit passer une seule lettre de minuscule en majuscule ac tion LOWER TO UPPER soit transformer l ensemble de l identificateur action UPPER Suivant le cas on obtient la description LETTER LOWER_TO_UPPER LETTER LOWER_TO_UPPER DIGIT si la transformation se fait lettre apr s lettre ou LETTER LETTER DIGIT QGUPPER CASE si la transformation s effectue globalement Un autre exemple Certains langages de programmation sp cifient que seuls un certain nombre de caract res sont significatifs dans les identificateurs ou m me limitent leur taille La troncature ou la v rification n cessaires peuvent ais ment se r aliser l aide du m canisme des actions Une des originalit s de LECL est d utiliser les contextes droits sur une lon gueur ventuellement non born e pour d cider de l action ex cuter de la m me facon que le contexte droit sert la reconnaissance d une expression r guli re voir en 4 1 7 1 Exemple La d finition des deux unit s lexicales UL1 Q1 b c UL2 Q2 b est licite C est la vue des caract res ou 4 apr s un nombre non born de p qui d c
70. ichiers include permettant l acc s aux modules du sys t me d ex cution Le plus important est sxunix h qui est utilisable en C Il existe aussi des versions PASCAL disponibles dans des sous r pertoires sx lib contient les binaires des modules du syst me d ex cution r partis entre une biblioth que libsx a et quelques fichiers Ces derniers sont es sentiellement des versions de mise au point de modules existant dans la biblioth que en version de production La biblioth que peut tre li e dans un r pertoire standard pour permettre l utilisation de l option 1sx de l diteur de liens 14 1 sx src contient les sources de tous les modules du syst me d ex cution Leur disponibilit permet de les adapter tous les besoins Ada est une marque d pos e du Gouvernement des tats Unis d Am rique Ada Joint Program Office Chapitre 2 BNF Lecture des D finitions Syntaxiques 2 1 Fonction BNr lit la grammaire et la met sous forme interne pour utilisation ult rieure par d autres constructeurs tels CSYNT et LECL Il effectue galement des tests de coh rence sur la grammaire Chaque r gle doit tre unique Un non terminal quelconque doit tre productif c est dire doit conduire une chaine terminale ventuellement vide Un non terminal quelconque doit tre accessible depuis l axiome Aucun non terminal ne doit d river dans lui m me c est dire que 5 e
71. icitement ou explicitement est un caract re interdit dans le langage F1G 4 1 Exemple de d finition de classes Classes tout sauf EOL tout sauf quote printable ANY EOL ANY quote ANY 000 SP 177 4 1 2 Les abr viations Afin d viter l criture fastidieuse de sous expressions r guli res identiques il est possible de nommer de telles expressions et d utiliser ce nom dans une expres sion r guli re ult rieure Toute occurrence du nom d une expression r guli re est s mantiquement quivalente une occurrence parenth s e de l expression qu elle d note Cette rubrique d bute par le mot cl ABBREVIATIONS Une abr viation se d finit par un nom identificateur suivi du symbole suivi d une expression r guli re voir en 4 1 6 la d finition est termin e par un On peut galement d finir dans cette partie des expressions de pr dicats voir en 4 1 6 4 4 1 3 Les unit s lexicales La d finition lexicale se poursuit par la d finition des expressions r guli res qui permettent de reconnaitre les diff rentes unit s lexicales du langage Cette d finition d bute par le mot cl TOKENS Une d finition d unit lexicale s crit dans le cas le plus simple de la mani re suivante un nom d unit lexicale suivi du symbole suivi d une expres sion r guli re termin e par un ce peut tre ventuellement suivi d une sp cification de priori
72. idera de l ex cution de l action 1 ou 2 Remarque Bien entendu certaines des variables utilis es par l analyseur lexical sont accessibles et m me modifiables par l utilisateur en particulier depuis le programme codant ses actions et pr dicats voir en 4 2 et consulter la documentation en ligne man sxscanner CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL37 Post action Il est galement possible de sp cifier une action utilisateur Cette action si elle existe doit suivre C le marquant la fin de l expression r guli re laquelle elle s applique ou le marquant la fin de la clause Priority voir en 4 1 7 3 si elle est pr sente ou le marquant la fin de la clause KEYWORD ou le marquant la fin de la clause contexte Une telle action est appel e post action lors de l analyse lexicale apr s reconnaissance de l expression r guli re laquelle elle est attach e cette action sera ex cut e imm diatement avant le retour l analyseur syntaxique L utilisa teur a donc la possibilit d y modifier les informations calcul es par l analyseur lexical code interne du terminal reconnu informations stock es dans la string table et cetera 4 1 6 4 Les pr dicats Jusqu pr sent nous avons suppos que la signification d un caract re donn ne d pendait que de ce caract re Il existe cependant un certain nombre de situations o
73. ier n positif entre paren th ses soit un nombre entier n positif ou nul n signifie que n est le num ro d un NT bloc n signifie que n est l adresse d une instruction du NT bloc Cette ins truction apres une action Reduce pourra tre ex cut e inconditionnel lement Si n est nul cette adresse n est pas significative Le champ Goto obligatoire indique le prochain T bloc qui va tre activ Goto Etq L action Reduce correspond au traitement d une r duction elle est cod e sur quatre champs Scan Reduce Stack Goto Si le champ Scan contient le symbole terminal suivant du texte source est positionn sous la t te de lecture sinon ce champ est vide et aucune lecture n est effectu e Le champ Reduce contient un nombre entier positif p qui est le num ro de la r gle de grammaire qui vient d tre reconnue et choisie CHAPITRE 3 CSYNT CONSTRUCTION DE L ANALYSEUR SYNTAXIQUE22 Le champ Stack contient un certain nombre ventuellement nul de barres verticales qui indiquent le nombre dont la pile d analyse est cr t e Ce nombre est pour une instruction d un T bloc la longueur de la partie droite de la production p cette longueur diminu e de un pour un NT bloc Le champ Goto contient soit un non terminal nt sp cifi par Goto Branch Table lt nt gt Top Stack State soit une adresse n sp cifi e par Goto n Ce champ est in
74. ilit de modifier la chaine source voir en 4 1 6 1 et 4 1 6 3 pour obtenir une forme interne qui sera r ellement utilis e Ainsi les expressions r guli res DARK A A BS iBS DARK B BS bp iBS DARK LET DARK A DARK B permettent de d finir des lettres grasses dont la forme normale contient une lettre unique L expression r guli re CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL31 DARK WORD DARK LET DARK_US DARK LET DARK US iBS oy d crit un identificateur dont la forme externe est grasse et dont la forme normale est pur e Il serait alors agr able que la d finition KEYWORD Q DARK WORD permette automatiquement de reconna tre les mots cl s d signant les actions syst me et de g n rer la fonction check keyword Or du fait de la pr sence de l op rateur dans la d finition d une lettre grasse chaque lettre est r p t e au moins deux fois et ne correspond donc pas la forme normale bien que la forme interne obtenue apr s application de l op rateur soit la forme normale du mot cl Pour que l utilisation pr c dente soit possible la d finition des mots cl s a t l g rement modifi e Un mot cl est un terminal non g n rique qui soit est reconnu par une unit lexicale dont le nom est celui d un terminal g n rique ou non de la grammaire du niveau syntaxi que diff rent de ce
75. ion sur cette cha ne Cette cha ne permet de comprendre pourquoi les productions mises en jeu dans un conflit sont atteintes simultan ment Pour chaque terminal t en conflit dans un tat s outre les renseignements standards d crits pr c demment CSYNT sort pour chaque production pi lt A gt alpha impliqu e dans le conflit et pour chaque item p2 lt B gt beta D gamma responsable du contexte droit t t FIRST1 gamma une d rivation droite issue de l axiome lt S gt de la grammaire de la forme lt S gt delta lt B gt delta beta D gamma delta beta D t CHAPITRE 3 CSYNT CONSTRUCTION DE L ANALYSEUR SYNTAXIQUE17 delta beta omega lt A gt t delta beta omega alpha t qui montre le cheminement complet du terminal t depuis son apparition comme d butant de la chaine gamma jusqu son utilisation comme contexte droit de la production p1 L option path demande galement au constructeur CSYNT de rechercher certain cas d ambig it le cas g n ral est ind cidable Si d tecte une ambig it deux d rivations droites diff rentes menant la m me forme senten cielle sont galement produites On trouvera en annexe E 1 2 2 les messages de non conformit produits avec l option path sur l exemple de l annexe E 1 Pour un conflit donn si aucune ambig it a t d tect e l option path demande galement CSYNT de v rifier si la grammai
76. it lexicale n a pas la signification op rateur moins suivi d un d but de commentaire 4 1 7 3 Les priorit s Cette clause introduite par le mot cl PRIORITY doit suivre si elle est pr sente C le marquant la fin d une expression r guli re C ou le marquant la fin d une sp cification de post action ou le marquant la fin d une clause contexte ou le marquant la fin d une clause NOT KEYWORD Gu ou le marquant la fin d une autre clause PRIORITY CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICALA3 Elle est form e d une liste d au plus trois sp cifications de priorit s par es par des cette clause se termine par un Les possibilit s de sp cification de priorit sont les suivantes Reduce gt Reduce En cas de conflit 1 look ahead ou Unbounded la priorit est donn e l expression courante sur toute autre expression ne compor tant pas cette clause et reconnaissant un sous langage commun Reduce gt Shift En cas de conflit 1 look ahead ou Unbounded les chaines reconnues par l expression r guli re courante Reduce ont priorit sur les pr fixes stricts Shift de chaines reconnues soit par cette expression r guli re soit par d autres Shift gt Reduce En cas de conflit 1 look ahead ou Unbounded toute chaine reconnue par une expression Reduce comportant cette clause est aban donn e au profit des pr f
77. it des pr dicats amp TRUE et amp FALSE Le pr dicat amp TRUE a la signification suivante si au cours de la construction de l automate LECL se trouve en plusieurs endroits diff rents dans le graphe des tats non d terminisme et qu un de ces endroits au moins est une classe associ e au pr dicat amp TRUE alors le constructeur ne conserve que les endroits ainsi rep r s les autres tant consid r s comme des impasses Exemples CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL38 Les expressions r guli res de la figure 4 5 reconnaissant les chaines de caract res et les commentaires peuvent s crire QUOTE ANY QUOTE amp TRUE QUOTE QUOTE amp TRUE SP EOL ANY EOL amp TRUE La classe compos e ANY contient le caract re guillemet QUOTE appar tient ANY lorsqu un guillemet est reconnu l on se trouve en trois endroits diff rents dans l expression r guli re QUOTE ANY QUOTE TRUE QUOTE QUOTE amp TRUE 1 1 1 Selon la r gle pr c dente seuls les deux derniers emplacements sont conserv s Le guillemet est donc reconnu par QUOTE et non par ANY Sans utiliser de pr dicat amp TRUE les commentaires PL 1 peuvent tre reconnus par l expression r guli re ona p xn pepe Te ILE onm En utilisant le pr dicat amp TRUE on obtient l expression ci dessous nota blement plus simple et plus lisible x ANY amp TRUE Dynamiques 15 F
78. ixes stricts Shift d j reconnus s il y en a Les clauses priorit sont appliqu es successivement dans l ordre indiqu Fic 4 11 Exemples d utilisation de clause Priority On d finit les deux terminaux g n riques suivants IDENT LETTER LETTER DIGIT CDR C A D R Priority Reduce Reduce et l on suppose que leurs contextes sont identiques La chaine CADDR est reconnue par les deux expressions r guli res mais cause de la clause de priorit sera consid r e comme tant un CAR_CDR Notons que la cha ne CADDR1 sera consid r e comme tant un 4IDENT En revanche avec la description suivante IDENT LETTER _ LETTER DIGIT YNOMBRE DIGIT CAR CDR C A D R Priority Reduce gt Reduce Reduce gt Shift cette m me chaine source CADDR1 sera consid r e comme tant une suite YCAR_CDR YNOMBRE CADDR et 1 4 1 7 4 Principes de la r solution des conflits En cas de conflit LECL applique les r gles suivantes La pr sence d actions dans une expression r guli re ne doit pas a priori modifier le r sultat de l analyse Les d cisions se prennent sur les r ductions On d termine tout d abord le mode de r solution du conflit 1_ look ahead ou Unbounded une r solution est Unbounded si et seulement si toutes les unit s lexicales intervenant dans le conflit ont une clause Unbounded Context dans
79. l n est pas en g n ral possible pour LECL de conna tre la construction la forme interne d une cha ne r sultant de la recon naissance d une chaine source LECL est donc susceptible de rater la recon naissance de certains mots cl s Afin de pallier cette faiblesse et de permettre un contr le plus fin l utilisateur a la possibilit de modifier le comportement pr c dent en indiquant explicite ment si telle ou telle unit lexicale reconnait tel ou tel mot cl Pour ce faire il est possible d ins rer une clause mot cl apr s la d finition d une unit lexicale Cette clause sp cifie le comportement de cette unit lexicale vis vis des mots cl s Cette clause si elle est pr sente doit suivre CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL32 Gu le marquant la fin d une expression r guli re d finissant une unit lexicale C ou le marquant la fin d une sp cification de post action ou le marquant la fin d une clause contexte Elle peut avoir les formes suivantes NOT KEYWORD ALL indique qu en aucun cas l unit lexicale laquelle elle est rattach e ne peut reconnaitre de mot cl KEYWORD ALL indique que l unit lexicale laquelle elle est rattach e reconnait tous les mots cl s KEYWORD a b indique que l unit lexicale laquelle elle est rat tach e ne reconnait que les mots cl s de la liste a b KEYWORD ALL BUT
80. la suppression d un caract re sont CHAPITRE 6 LE TRAITEMENT DES ERREURS 55 autoris s L utilisateur a seulement la possibilit de modifier la longueur des mod les et l ordre dans lequel ils sont d finis dans la liste fournie par SYNTAX Mod le Interpr tation 1 1234 suppression 2 X 1 23 4 remplacement 3 X 0123 insertion Au niveau lexical il est impossible d agir sur le caract re pr c dent le carac t re en erreur 0 d signe donc le caract re en erreur 1 le caract re qui le suit etc Si aucun mod le ne s applique le caract re en erreur est supprim 6 3 Le fichier standard recor Ce fichier permet non seulement de sp cifier le traitement des erreurs des niveaux lexicographique et syntaxique et galement les textes des diagnostics qui seront produits Il est donc possible par exemple de d crire les messages en Fran ais Allemand ou patois La sp cification contenue dans standard recor est donn e en annexe D Le texte d un message est form d une s quence de cha nes de caract res les guillemets internes doivent tre pr c d s de V n n est un entier positif ou nul sera remplac par le n i me symbole de la cha ne source attention dans l analyseur lexical le caract re en erreur est le num ro 0 alors que dans l analyseur syntaxique le terminal en erreur est le num ro 1 sera remplac par le symbole correspondant au X ou au S d indice n dans le mod
81. lage du traitement s man tique Cette comparaison est d autant plus justifi e que pour l analyseur syn taxique tout traitement s mantique est constitu d actions appel es chaque r duction Cette forme de s mantique est trait e par le processeur SEMACT CHAPITRE 1 INTRODUCTION 6 1 3 2 Actions la YACC Cette forme de traitement s mantique est un peu plus structur e que la pr c dente en ce sens que les fragments de code implantant les actions sont crits directement apr s les productions sous forme de blocs C entre accolades Le processeur YAX produit lui m me les num ros d action et la proc dure corres pondante En outre les acc s la pile sont d guis s par l emploi d une notation h rit e de YACC dont YAX est fortement inspir La gestion de la pile est aussi effectu e automatiquement Il faut noter tout de m me une diff rence importante YAX n accepte pas contrairement YACC que de tels fragments de code soient ins r s au milieu des parties droites des productions SYNTAX propose un traducteur nomm Ysx transformant purement syn taxiquement une sp cification pour YACC en une sp cification pour YAx Les actions au milieu des productions sont correctement traduites en les attachant des non terminaux d rivant la cha ne vide produits automatiquement Une version de YAX avec des actions en Pascal est actuellement l tude 1 3 3 Attributs s mantiques purement synth tis
82. le cas contraire le mode est 1 look ahead Sil y a conflit pour le mode trouv LECL applique les priorit s utilisateur s il y en a Sil reste des conflits LECL applique alors les r gles de r solution par d faut il donne priorit l action Shift Action Reduce qui assure CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL44 la reconnaissance de la cha ne la plus longue l int rieur d une m me expression r guli re En cas d galit il donne priorit l action rencontr e en premier dans un parcours gauche droit de la grammaire lexicale et produit un diagnostic Exemple Consid rons le langage form par une liste d identificateurs 4ID et de nombres entiers ANB et qui a la d finition lexicale suivante Tokens Comments SP EOL ID LETTER LETTER DIGIT NB DIGIT LECL produit sur cette sp cification les diagnostics de la figure 4 12 Comme il n y a pas de clause Unbounded Context tous ces conflits sont trait s en mode 1 look ahead Fic 4 12 Exemple de diagnostics de LECL sur des conflits Warning Warning Warning 1 look ahead Shift Reduce conflict in state 3 on LETTER between Shift ID LETTER LETTER DIGIT Reduce ID LETTER LETTER DIGIT detected on ID LETTER LETTER DIGIT Priority is given to Shift 1_look_ahead Shift Reduce conflict in state 3 on DIGIT between Shift
83. le_slice sizeof struct span 1 coords xprod head sxsrcmngr source_coord line return else sxnext_char return case 2 nnn gt char register int val register char C s t s sxsvar lv s token string sxsvar lv mark index for val st 0 st NUL val val lt lt 3 c 0 t val sxsvar lv ts lgth sxsvar lv mark index 1 sxsvar lv mark index 1 return default gripe Annexe B Sp cifications du langage LECL B 1 D finition syntaxique Ceci est la grammaire de LECL voir le chapitre 4 Les cha nes de carac t res suivant une r gle de grammaire a la droite du sont une sp cifi cation d arbre abstrait destin e SEMAT voir en 5 2 Les commandes entre tildes sp cifient un paragrapheur du langage LECL et doivent tre ignor es du point de vue strictement grammatical cf paradis 1 et le rapport INRIA N 455 intitul Paradis un Syst me de Paragraphage Dirig par la Syntaxe Novembre 1985 lt LECL_GRAMMAR gt lt CLASSES_LIST_OPTION gt lt ABBREVIATIONS_LIST_OPTION gt lt TOKENS_LIST_OPTION gt lt SYNONYMS_LIST_OPTION gt lt REPR_SPEC_LIST_OPTION gt PROGRAM_ROOT_LECL CLASSES lt CLASSES_LIST_OPTION gt INH lt CLASSES_LIST_OPTION gt CLASSES TAB CLASSES LIST 65 ANNEXE B SPECIFICATIONS DU LANGAGE LECL lt CLASSES_LIST g
84. les LOWER Les lettres minuscules UPPER Les lettres majuscules DIGIT Les chiffres d cimaux QUOTE Caract re Code octal 042 A Bb Z 22 Une classe est nomm e si l ensemble des caract res qui la composent a recu un nom Cette d finition est l objet de la premi re partie d un source LECL dans laquelle on d finit les classes nomm es en regroupant tous les caract res les composant Cette d finition d bute par le mot cl CLASSES Une classe se d finit par un nom identificateur suivi du symbole d une expression la d finition se termine par un L expression utilis e admet GL Suivi comme op randes des classes pr d finies des cha nes de caract res l ensemble des caract res de la cha ne appar tient la classe des codes octaux nombre octal de trois chiffres pr c d du caract re dont la valeur est la repr sentation interne en ASCII du caract re d sign des intervalles d crivant une suite de caract res dont les codes internes sont contigus un intervalle est repr sent par le premier et le dernier caract re de la s quence s par s par Ces caract res marquant le d but et la fin de la s quence sont repr sent s soit par le caract re entre guillemets soit par son code interne exprim en octal et pr c d du caract re soit par le nom s il existe de ce caract re L ordre sous jacent est celui de l AS
85. lui du mot cl soit est la forme interne obtenue apr s reconnaissance et applica tion ventuelle des op rateurs par une unit lexicale dont le nom n est pas celui d un terminal du niveau syntaxique Cette possibilit est utilis e de facon intensive dans la description du niveau lexical de LECL lui m me voir en annexe B 2 Afin de d terminer statiquement la construction si un terminal du lan gage est un mot cl LECL recherche s il existe au moins une expression r guli re qui d crit le terminal consid r le terminal appartient il au langage d fini par l expression r guli re Or les expressions r guli res peuvent contenir des ac tions et des pr dicats utilisateur qu il est bien entendu impossible d ex cuter la construction La possibilit de manipuler des variables globales dont les valeurs peuvent tre utilis es d une unit lexicale une autre sp cifiant par exemple des contextes de reconnaissance interdit galement la connaissance statique du r sultat de l ex cution de pr dicats syst me Afin de ne pas oublier des possi bilit s de reconnaissance de mots cl s LECL suppose pour cette reconnaissance des mots cl s la construction que tous les pr dicats dynamiques retournent VRAI De ce fait LECL est susceptible de d cr ter que telle unit lexicale re connait tel mot cl alors qu il n en est rien G n ralement cet abus n est pas dommageable Pour des raisons analogues i
86. mbre d op rations ensemblistes pour d finir ces classes Les op rations disponibles pour la cons truction d expressions r guli res sont la s quence l alternative la r p tition l optionnalit et le groupement Il est aussi possible de d finir des abr viations correspondant des morceaux d expressions r guli res et de les utiliser pour d finir d autres expressions Pour construire l automate d tats finis implantant l analyseur lexical LECL utilise des techniques qui sont d riv es de la m thode LR pour la construction d analyseurs syntaxiques ceci lui permet d obtenir directement un automate d terministe Les in vitables conflits d tect s lors de la construction de l analyseur qui ne seraient pas r solus par la lecture d un caract re en avance peuvent l tre de CHAPITRE 1 INTRODUCTION 3 plusieurs autres mani res par l auteur de la description soit en r duisant les contextes d termin s partir de la grammaire soit en utilisant des pr dicats et des actions semblables ceux du niveau syntaxique soit en for ant des niveaux de priorit automatiquement par LECL soit statiquement en utilisant des r gles de r solution pr d finies par exemple Shift prend pr c dence sur Reduce soit dynamiquement en lisant un nombre ventuellement non born de caract res en avance LECL construit aussi un automate tr s performant pour la reconnaissance des mots cl s Les automates produi
87. mbre entier Ce nombre indique le num ro de l action s mantique qui sera appel e par l analyseur syntaxique au moment de la reconnaissance de la r gle associ e Dans le cas o une r gle n est pas suivie d un num ro d action le syst me ajoute automatiquement le nombre 0 la fin de cette r gle Ainsi l action nu m ro 0 sera appel e lors de la r duction de telles r gles En g n ral cette action ne fait rien L utilisateur doit alors crire un programme en langage C ou dans un autre langage apr s r alisation d une interface r alisant l ensemble des actions s mantiques du langage Ce programme doit correspondre la structure donn e en annexe C 1 5 2 SEMAT S mantique par arbre abstrait 5 2 1 Sp cification et construction de l arbre abstrait La phase pr liminaire de l analyse s mantique par arbre abstrait est la pro duction de cet arbre par le constructeur d arbres abstraits voir la documenta tion en ligne man sxatc au cours de l analyse syntaxique 46 CHAPITRE 5 LA SEMANTIQUE DANS SYNTAX AT Pour obtenir cette construction il faut modifier la d finition syntaxique il est d usage de nommer alors nom du langage at le fichier correspondant cette modification consiste en l ajout de noms de n uds la fin des r gles apr s le 37 ces noms sont des identificateurs la C plac s entre guillemets Lorsque l analyseur syntaxique reconnait une r gle les racines des arbres
88. mettant la correction vel la r cup ration automatique des erreurs Ces modules ont t sp cifi s par l interm diaire de RECOR voir le chapitre 6 8 1 Mise en uvre Se reporter la documentation en ligne voir notamment sxsrc_mngr 3 sxscanner 3 sxparser 3 sxstr mngr 3 sxatc 3 sxat mngr 3 58 Annexe A Sp cifications du langage BNF A 1 D finition syntaxique Ceci est la grammaire de BNF voir le chapitre 2 Les chaines de carac t res suivant une r gle de grammaire a la droite du sont une sp cification d arbre abstrait destin e SEMAT voir en 5 2 This grammar is used for the specification of BNF lt BNF gt lt RULE_LIST gt BNF lt RULE_LIST gt lt RULE_LIST gt lt RULE gt 3 lt RULE_LIST gt lt RULE gt RULE S lt RULE gt lt VOCABULARY_LIST gt lt VOCABULARY_LIST gt lt VOCABULARY_LIST gt VOCABULARY lt VOCABULARY_LIST gt LHS_NON_TERMINAL VOCABULARY S VOCABULARY ANON TERMINAL NON TERMINAL VOCABULARY ANON TERMINAL PREDICATE X NON TERMINAL VOCABULARY ACTION ACTION VOCABULARY TERMINAL lt VOCABULARY gt lt TERMINAL gt PREDICATE X TERMINAL TERMINAL TERMINAL TERMINAL TERMINAL 4GENERIC TERMINAL GENERIC TERMINAL A 2 D finition lexicale Classes PRINT ANY 000 040 177 59 ANNEXE A SPECIFICATIONS DU LANG
89. n de r soudre de tels conflits LECL met la disposition de l utilisateur deux m canismes les contextes qui font l objet de 4 1 7 1 et les priorit s qui sont trait es en 4 1 7 3 4 1 7 1 Les contextes La grammaire du niveau syntaxique d finit les s quences valides d unit s lexicales mais ne pr cise pas la fa on dont elles vont tre s par es les unes des autres Consid rons par exemple un langage o un nombre peut suivre un identifi cateur la cha ne A1 peut tre consid r e soit comme un seul identificateur de texte A1 soit comme la s quence identificateur A nombre 1 Les s quences valides d unit s lexicales d duites de la grammaire syntaxi que permettent galement dans certains cas de lever des ambig it s Soit un Les conflits Shift Action n existent pas ce ne sont que des mirages CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICALAI langage o et sont des op rateurs valides La vue d une toile ne suffit pas pour d cider si l on a reconnu l op rateur ou si l on est dans l op rateur En revanche si l on suppose que l op rateur ne peut pas tre suivi d une unit lexicale commencant par une toile la connaissance d un caract re en avance look ahead d un caract re permet de r soudre ce conflit si ce caract re en avance est une toile on est dans la reconnaissance de sinon on vient de reconnaitre Les clauses contextes permettent d
90. n de texte d j analys e ao est le symbole pr c dent ai et y a1a2a3 est la partie non encore analys e La m thode de correction locale s nonce comme suit On consid re l ensemble Y de toutes les chaines terminales de longueur n telles que quelle que soit la cha ne t de V la cha ne xt soit un pr fixe de chaine syntaxiquement correcte On choisit dans une cha ne qui va remplacer le d but de agy de telle facon que le texte source modifi ressemble au texte source initial Cette ressemblance est d crite par l utilisateur qui sp cifie une liste de mod les de priorit d croissante Consid rons par exemple les trois mod les suivants num rot s de 1 3 52 CHAPITRE 6 LE TRAITEMENT DES ERREURS 53 1 0X123 aoe 3 0234 Dans ces mod les X a la signification un symbole terminal quelconque du langage et les nombres repr sentent les symboles terminaux du texte source O pour 1 pour ay Supposons que la cha ne soit dans V Cette cha ne satisfait le mod le num ro 2 ce qui est interpr t de la facon suivante Le symbole a est erron mais peut tre remplac par le symbole b La chaine d entr e aga1a25a3a4 sera donc remplac e par a96a5a3a4 moins qu il n y ait dans V une cha ne qui satisfasse le premier mod le par exemple de plus forte priorit Les mod les peuvent videmment
91. n terminaux de la partie gauche des r gles ont le m me nombre de fils Voir par exemple la grammaire d crivant le m talangage lexical en page 65 Une fois la grammaire modifi e on la soumet l entr e de SEMAT En plus des sorties propres BNF SEMAT fournit pour chaque nom de noeud et pour chacune des positions des fils la liste de tous les noms de noeuds qui peuvent se trouver cette position De plus une trame de passe s mantique est engendr e crite en langage C Cette trame peut tre utilis e apr s avoir t compl t e manuellement par les calculs d attributs pour crire l analyseur s mantique 5 2 2 R alisation de l analyseur s mantique 5 2 2 1 valuation des attributs s mantiques Les attributs s mantiques sont associ s aux n uds de l arbre abstrait Une passe s mantique consiste en un parcours de cet arbre dans le sens haut bas gauche droite en profitant des passages sur les n uds pour valuer les attributs Plusieurs passes peuvent tre r alis es de la sorte Chaque n ud est visit deux fois 1 l entr e de son sous arbre lors de ce passage les attributs h rit s du n ud sont valu s Cette visite sera dite h rit e 2 la sortie du sous arbre cette fois les attributs synth tis s sont valu s Cette visite sera qualifi e de synth tis e Depuis un n ud il est possible d acc der aux n uds voisins s ils existent savoir son p re
92. ndu qu ils n ont pas de solution compl te 1 3 6 Utilitaires divers Outre les constructeurs de base et les outils traitant la s mantique SYNTAX comprend un certain nombre d utilitaires Cx un g n rateur de r f rences crois es pour le langage C PPC et PPADA des paragrapheurs pour les langages C et Ada respecti vement Ces outils ont bien s r t construits l aide de SYNTAX 1 4 Mise en CEuvre de SYNTAX sur UNIX SYNTAX est actuellement disponible sur de nombreuses machines munies du syst me d exploitation UNIX ou l un de ses d riv s Soit sx le r pertoire o a t install SYNTAX Le contenu des diff rents sous r pertoires de sx est le suivant sx bin contient les versions binaires ex cutables de tous les processeurs de SvNTAX Habituellement ces fichiers sont aussi li s au sens UNIX dans un r pertoire standard comme usr 1ocal bin ce qui vite aux utili sateurs d avoir changer leur PATH sx doc contient la documentation Outre un fichier de nom NOUVEAUTES qui r sume l volution des diverses versions distribu es il contient les sous r pertoires man les pages de manuel habituellement li es ou copi es dans usr man ou autre pour acc s imm diat et help courtes descriptions des commandes de SYNTAX utilisables en particulier par la fonction help de tcsh 1 ainsi que divers fichiers facilitant la mise en ceuvre de SYNTAX sx incl contient des f
93. ne unit lexicale dont le nom est diff rent de celui du mot cl Exemple lD LETTER LETTER DIGIT CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL30 Supposons que le terminal begin apparaisse dans la grammaire syntaxique mais ne soit pas d crit au niveau lexical La chaine de caract res begin tant reconnue par AID le terminal begin est par d finition un mot cl LECL construit le texte en langage C d une fonction de nom check keyword qui permet de v rifier si une cha ne est ou non un mot cl Le texte de cette fonction fait partie int grante des tables d analyse produites par le module TABLES C voir le chapitre 7 Chaque fois qu un terminal est reconnu par une unit lexicale pouvant reconnaitre des mots cl s l analyseur lexical appelle check keyword qui retourne 0 le terminal n est pas un mot cl le code retourn par l analyseur lexical est celui de l unit lexicale 41 dans l exemple n gt 0 le terminal est un mot cl de code interne n Si l unit lexicale est un identificateur qui n est le nom d aucun terminal du langage l analyseur lexical effectue la m me recherche en table que dans le cas pr c dent Si cette recherche r ussit l analyseur lexical retourne l analyseur syntaxique le code du terminal mot cl ainsi reconnu Dans le cas contraire il limine purement et simplement la chaine reconnue en signalant une erreur et ne renvoie pas de code Ce ge
94. nre d unit lexicale permet donc de d crire un ensemble de terminaux du langage par une expression r guli re unique dans le cas o ils ne peuvent pas tre reconnus par un terminal g n rique Exemple Dans le langage LECL les s quences de caract res DECR GERASE Sont des mots cl s r serv s qui d signent des actions pr d finies Dans la ver sion actuelle du langage ces mots cl s sont au nombre de 12 De plus toute autre s quence de caract res v rifiant l expression r guli re 0 LETTER LETTER est erron e La description des ces mots cl s est r alis e simplement par l ajout de la d finition KEYWORD LETTER _ LETTER KEYWORD est un identificateur qui n est pas un symbol terminal de la gram maire du niveau syntaxique du langage LECL De plus le source d une sp cification LECL a pu tre cr par un programme paragrapheur ou autre qui a produit les mots cl s en gras Chaque caract re c d un mot cl a pu tre superpos un certain nombre de fois sur lui m me par la s quence c BS pour cr er une impression de gras Chaque mot cl peut donc maintenant avoir un nombre infini de repr sentations dont la reconnaissance si on adopte la philosophie pron e par LECL d grossissage de la reconnaissance par une expression r guli re puis utilisation de la fonction check keyword g n r e automatiquement n cessite l obtention d une forme normale Or LECL a la possib
95. ntaxique 2 2 1 Les l ments syntaxiques 2 2 2 Les actions et pr dicats 2 3 Mis en uvre wok m tn 2 4 Exemples de d finitions syntaxiques 3 CSYNT Construction de l Analyseur Syntaxique 3 1 Classe de grammaires accept e 912 Des Commits e eur ERROR Panne 3 9 Deur 36sol tion hoe dede R a R lO XC 3 3 1 langage PRIO 3 4 Optimisation de l automate 3 5 Listage de l automate engendr 3 6 Miseen uvre 4 LECL Construction de l Analyseur Lexical 4 1 M talangage lexical All Te S classes LLAR NR mn an ef 4 1 2 Les abr viations 0 1 OG i amp ND ND H TABLE DES MATIERES 4 1 3 Les unit s lexicales 4 1 4 Les synonymes 4 1 5 sp cification de repr sentation 4 1 6 Les expressions r guli res 42127 L s CONMILSE ur sn GREEN 4 1 8 Exemples de d finitions lexicales 4 2 Miseen uvre La s mantique dans SYNTAX 5 1 SEMACT Actions s mantiques 5 2 SE
96. oix et les corrections correspondantes tenteront de la rapprocher du choix C5 Le lecteur pourra regarder ce propos les grammaires des exemples suivants On trouvera en annexe B 1 la grammaire syntaxique d crivant le langage LECL Cette grammaire utilise un pr dicat syntaxique amp 1 associ un terminal g n rique pour traiter la suite de mots cl s non r serv s NOT KEYWORD sinon la grammaire propos e n est pas LR 1 On trouvera en annexe B 4 le programme C codant le pr dicat amp 1 On trouvera en annexe E 3 une grammaire LALR 2 o les conflits LALR 1 sont r solus par l utilisation d un non terminal tendu et le programme codant le pr dicat correspondant On trouvera de m me en annexe E 4 la grammaire d un langage non d terministe et le programme associ r alisant les actions et pr dicats syntaxiques n cessaires 2 3 Mise en ceuvre Se reporter la documentation en ligne man bnf CHAPITRE 2 BNF LECTURE DES DEFINITIONS SYNTAXIQUES 14 2 4 Exemples de d finitions syntaxiques On trouvera en annexe A 1 la grammaire du processeur BNF lui m me et en annexe B 1 la grammaire de LECL voir le chapitre 4 Chapitre 3 CSYNT Construction de l Analyseur Syntaxique 3 1 Classe de grammaires accept e CSYNT accepte en entr e des grammaires de la classe LALR 1 ceci permet notre avis de r aliser le meilleur compromis possible l heure actuelle entre le temps de construction d une part et la p
97. ot cl INCLUDE dans la rubrique TOKENS Cette d finition doit comporter une expression r guli re qui reconnait la commande et deux actions utilisateur dont une post action La premi re action doit assurer le changement de fichier source en fonction des informations extraites de la commande alors que la post action doit assurer le retour normal a la lecture du fichier courant Le module de librairie sxincl_mngr include manager peut tre utilis voir la documentation en ligne man sxincl_mngr Exemple Soit un langage ot la commande include est introduite par le caract re et se termine sur la premi re fin de ligne Les caract res non blancs sont cens s repr senter le chemin pathname du fichier consid rer La description lexicale correspondante peut donc tre Include SP HT t n SP HT EOL 01 02 On trouvera en annexe F 3 le texte du programme codant les actions 1 et 02 4 1 7 Les conflits Les langages d crits par les expressions r guli res de la rubrique TOKENS doivent tre disjoints deux deux c est dire que lors d une analyse lexicale toute s quence de caract res ne doit pouvoir tre reconnue que par une seule expression r guli re Sinon on a un conflit potentiel qui est dit Reduce Reduce De m me une cha ne reconnue par une expression r guli re donn e ne peut tre le pr fixe d un autre cha ne sinon on a un conflit potentiel qui est dit Shift Reduce Afi
98. pilation de textes sources l aide des analyseurs cr s au pr alable Les buts poursuivis sont donc du m me ordre que ceux qui ont pr sid la d finition des utilitaires LEX et YACO de UNIX mais il est beaucoup plus puis sant et performant en particulier en ce qui concerne le traitement des erreurs De plus les analyseurs produits peuvent tre associ s des formes de traitement s mantique de plus haut niveau que celle disponible dans Yacc c est dire la simple ex cution de fragments de code associ s chaque production SYNTAX comprend principalement les modules suivants BNF mise sous forme interne des d finitions syntaxiques CSYNT constructeur syntaxique LECL constructeur lexicographique RECOR traitement des erreurs TABLES C production des tables d analyse en langage C les outils r alisant l analyse des textes source sxscanner ou aidant cette analyse sxsrc_mngr sxstr mngr et cetera La majeure partie de ce manuel est consacr e la description de ces modules tant en ce qui concerne leurs fonctionnalit s qu en ce qui concerne leur mise en ceuvre sous le syst me UNIX En outre le chapitre 5 est consacr aux divers moyens de r aliser des traitements s mantiques l aide de SvNTAX 1 1 Les processeurs de base 1 1 1 Introducteur syntaxique BNF BNF est le processeur de base pour la mise sous forme interne des d finitions syn
99. ration globale de l analyseur syntaxique d finit l ensemble des symboles terminaux sur lesquels sera tent e la r cup ration si la correction a chou Ces symboles sont galement utilis s pour limiter la taille d un mod le de correction Soit 0 X 12 3 4 CHAPITRE 6 LE TRAITEMENT DES ERREURS 56 un mod le tel que pour l erreur courante le symbole a2 soit un l ment de Key Terminals Dans ce cas il est quivalent au mod le O X 1 2 la chaine a3a4 n a pas besoin d tre valid e Cette extension permet d accroitre les possibilit s de correction dans des portions de texte denses en erreurs Chapitre 7 TABLES C Production des tables d analyse en langage C Le module TABLES C constitue l pilogue obligatoire d une construction il a deux fonctions V rifier la coh rence globale des tables qui ont t pr alablement produites par les diff rents constructeurs de SYNTAX ces tables contiennent en effet une indication permettant de d terminer si les constructeurs ont exploit la m me version de la grammaire syntaxique Traduire l ensemble de ces tables en un programme en langage C form essentiellement de variables initialis es TABLES C produit un texte sur sa sortie standard stdout qui est usuelle ment redirig e vers un fichier de nom nom du langage t c ce texte rassemble pour le langage nom du langage toutes les tables n cessaires l analyse et au traitement de la s m
100. re est LR 1 Si la gram maire n est pas LR 1 CSYNT produit deux d rivations droites diff rentes qui violent la d finition du LR 1 Premi re d rivation lt S gt beta A t z gt beta alpha t z Deuxi me d rivation lt S gt gt gamma gt beta alpha t z avec gamma Z beta lt A gt t z Outre un int r t p dagogique vident ces deux d rivations peuvent aider la compr hension du conflit On trouvera en annexe E 2 une grammaire non LR 1 et les messages de non conformit produits par CSvNT lorsque l option path est positionn e des fins p dagogiques ou pour comprendre les raisons de conflits com plexes l option 1alri de CSYNT permet d obtenir l automate LALR 1 sous une forme lisible les items constituant chaque tat sont explicit s les tran sitions avant et arri re reliant entre eux les tats sont indiqu es ainsi que les ensembles de symboles terminaux formant le contexte droit look ahead de chaque r duction impliqu e dans un conflit LR 0 3 3 Leur r solution Face une grammaire pr sentant des conflits on peut r agir de quatre facons non exclusives 1 Supprimer les conflits en transformant la grammaire afin de la rendre LALR 1 2 Nerien faire car les r gles par d faut choisies par le constructeur conviennent 3 crire une sp cification la Yacc qui indique au constructeur les choix de l utilisateur face un conflit CHAPITRE 3 CSYNT CONSTRUCTI
101. rique de ces arbres Le processeur MIX permet d automatiser la mise jour des passes s mantiques apr s modification de la grammaire vel de la sp cification des arbres abstraits 1 3 5 Paragraphage L exp rience prouve rapidement qu il est beaucoup plus agr able et efficace de travailler sur des programmes dont la mise en page refl te la structure Des processeurs permettant de produire automatiquement une version paragraph e de textes crits sans prendre en compte leur structure sont donc bienvenus SYNTAX propose un moyen de construire automatiquement de tels paragra pheurs en utilisant une technique bas e sur la remarque suivante quand on crit la grammaire d un langage on pr sente souvent les productions de cette grammaire de la m me facon qu on voudrait voir paragrapher les textes de ce langage voir la figure 1 1 Le processeur PARADIS permet donc d obtenir peu de frais un paragrapheur pour un langage une fois qu on en a crit la grammaire en pr sentant cette derni re de facon ce qu elle soit agr able l ceil En fait cette approche est un peu simpliste PARADIS propose donc en plus de ce principe g n ral des directives de paragraphage qui permettent d obtenir CHAPITRE 1 INTRODUCTION 8 des mises en page plus sophistiqu es En outre les probl mes classiques de longueur born e de la ligne de sortie et de placement des commentaires sont trait s de mani re g n ralement satisfaisante tant ente
102. s s mantiques de SYNTAX SEMACT SEMAT TABC 2 2 2 Les actions et pr dicats Fondamentalement la classe de grammaires accept e par SYNTAX est le LALR 1 voir en 3 1 Cette classe bien fond e th oriquement r alise pour un langage donn un bon compromis entre la rapidit de construction d un ana lyseur et la facilit d criture de sa grammaire Cependant dans certains cas l obtention d une grammaire LALR 1 peut se r v ler malcommode et le r sultat obtenu tre trop loign de la grammaire naturelle il peut m me tre impossible d crire une telle grammaire si le langage est non d terministe Afin de pallier ces faiblesses nous avons ajout la d finition syntaxique deux m canismes Une sp cification de priorit a la YACC voir en 3 1 Un m canisme d actions et de pr dicats d crit ci dessous Ces actions et pr dicats sont le pendant syntaxique des actions et pr dicats de LECL voir en 4 1 6 3 et 4 1 6 4 2 2 2 1 Les actions Il est possible de sp cifier des actions syntaxiques dans les parties droites des r gles de grammaire Une action syntaxique est un nombre entier n positif ou nul pr c d du caract re Lors de la reconnaissance de l ex cution de l action n pendant l analyse d un texte source un programme crit par l uti lisateur sera appel avec le param tre n En g n ral ces actions par utilisation du contexte gauche ou droi
103. s est form par les noms de classes pr d finies nomm es ou anonymes d abr viations d actions et de pr dicats Une expression r guli re est une liste d alternatives s par es par des ou Une alternative est d finie par les r gles suivantes alternative alternative facteur facteur facteur expression r guli re gt expression r guli re gt lt expression r guli re gt lt expression r guli re gt lt expression r guli re gt lt expression r guli re gt expression r guli re gt lt primaire gt ra d NAAN Et primaire est un l ment du vocabulaire Les parenth ses et ont la signification usuelle Les couples et C sont utilis s pour symboliser l op rateur de fermeture transitive r flexive Les couples 7 et sont utilis s pour symboliser l op rateur de fermeture transitive Le couple 77 indique que l expression r guli re est facultative CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL34 Fic 4 4 Exemple d expression r guli re Les identificateurs du langage d entr e LECL peuvent tre d finis par l expression r guli re LETTER _ LETTER DIGIT 4 1 6 1 L op rateur Certains caract res reconnus au niveau lexical n ont aucune utilit pour Vanalyse syntaxique Par exemple dans une chaine de caract res l
104. sact entry action_no int entry action_no switch entry case OPEN case CLOSE case FINAL return case INIT a_number 1 a_s b_s 0 return case PREDICATE switch action_no case 1 return a_s b_s case 2 return a_number lt k break case ACTION switch action_no case 1 register int i sxplocals atok_no lahead define GET_LAHEAD lahead sxget token i gt lahead ANNEXE E EXEMPLES DE GRAMMAIRES NON LALR 1 89 while GET_LAHEAD code a stt for lahead b code GET LAHEAD _ if a_s b_s for lahead a_code GET_LAHEAD k for lahead b_code GET_LAHEAD k return case 2 a_number return fputs The function NDL_act is out of date n sxstderr abort Annexe F Exemples de d finitions lexicales F 1 D finition lexicale de PASCAL Tokens Comments fSP HT EOL wen ANY amp True Aut IDENTIFIER LETTER LETTER DIGIT UPPER_CASE Context 11 But ANATUREL REEL ANATUREL DIGIT Priority Reduce gt Reduce Unbounded Context 11 But 4 IDENTIFIER REEL DIGIT DIGIT E DIGIT Context 11 But YIDENTIFIER ASTRING uon ono Luo oU non lt gt lt n n Ww p 1 non QU Q F 2 D
105. st interdit les r cursions gauche et droite sont bien entendu autoris es BNF construit en outre pour chaque terminal la liste des terminaux pouvant le suivre contexte cette information est utilis e par LECL voir en 4 1 7 2 2 M talangage syntaxique 2 2 1 Les l ments syntaxiques La description de la grammaire utilis e l entr e du processeur BNF est tr s proche de la forme normale de Backus appel e galement forme de Backus Naur Backus Naur Form d o le nom de BNF Toutefois pour faciliter l criture et la lecture de la grammaire des notations particuli res sont employ es les notations de BNF sont d crites ci dessous La grammaire est une liste de r gles appel es aussi productions Le sym bole ou de la BNF standard n est pas utilis il doit y avoir autant de r gles que d alternances Chaque r gle se d compose en une partie gauche et une partie droite s par es par un caract re qui remplace le symbole de la BNF standard et se termine par un caract re CHAPITRE 2 BNF LECTURE DES DEFINITIONS SYNTAXIQUES 10 Les symboles non terminaux sont d limit s par les caract res lt et gt et se composent d un nombre quelconque de caract res imprimables autres que gt et d espaces 4 7 Le symbole non terminal constituant la partie gauche d une r gle doit obligatoirement commencer en colonne 1 L a
106. t lt CLASSES_LIST gt lt CLASS gt lt CLASS_NAME gt lt CLASS_EXP gt lt CLASS_EXP gt lt CLASS_EXP gt lt CLASS_TERM gt lt CLASS_TERM gt lt CLASS_REF gt lt CLASS_REF gt lt SLICE gt lt SIMPLE_REF gt lt SIMPLE_REF gt lt SIMPLE_REF gt ABBREV CLASSES LIST CLASS CLASS n n gt lt CLASS_NAME gt COL 24 SPACE 4IDENTIFIER lt CLASS_EXP gt CLASS EXP lt CLASS_TERM gt lt CLASS_EXP gt lt CLASS_REF gt lt SIMPLE_REF gt lt SLICE gt lt SIMPLE_REF gt 4IDENTIFIER YSTRING_LITERAL OCTAL_CODE IATIONS XABBREVIATIONS LIST OPTION INH XABBREVIATIONS LIST OPTION ABBREVIATIONS lt ABBREVIATIONS_LIST gt lt ABBREVIATIONS_LIST gt lt ABBREVIATIONS_LIST gt lt ABBREVIATION gt lt ABBREVIATIONS_LIST gt lt ABBREVIATION gt lt ABBREVIATION gt lt ABBREVIATION gt COL 24 SPACE lt PREDICATE_NAME gt COL 24 SPACE REGULAR EXPRESSION NAME 4IDENTIFIER lt PREDICATE_NAME gt PREDICATE NAME n n gt CLASS TERM CLASS TERM SIMPLE REF n n gt lt REGULAR_EXPRESSION_NAME gt lt REGULAR_EXPRESSION gt 66 CLASS S CLASS EXP CLASS CLASS NAME PLUS 77 MINUS 77 SLICE 27 Tp STRING OCTAL CODE ABBREVIATION S ABBRE
107. t de contexte ou de post action voir en 4 1 7 et 4 1 6 3 Un nom d unit lexicale peut tre le mot cl COMMENTS le mot cl INCLUDE un terminal g n rique voir en 2 2 1 une chaine de caract res terminal du langage entre guillemets le mot cl EOF pour End Of File voir plus loin un identificateur dont le nom n est pas significatif CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL29 L unit lexicale de nom COMMENTS d finit les commentaires L expression r guli re de sa partie droite doit d crire non seulement les commentaires du langage mais galement les espacements entre les symboles terminaux blanc fin de ligne et cetera L unit lexicale de nom INCLUDE permet de d finir des includes voir en 4 1 6 5 Les terminaux g n riques sont les seuls qui doivent obligatoirement tre d finis au niveau lexical Les autres terminaux sont trait s par LECL de la facon suivante Pour un terminal donn non d fini c est dire dont le nom n ap parait pas en partie gauche d unit lexicale LECL regarde s il est reconnu par l expression r guli re d une unit lexicale si non LECL engendre automatiquement l expression r guli re le reconnaissant caract re par caract re si oui ce terminal est rang dans une table qui sera utilis e par l analyseur lexical Lors de l analyse lexicale si une chaine de caract res est reconnue par un
108. t 6 lt Else_Part gt else lt Stmt gt Reduce 5 lt Else_Part gt derived from 3 lt If_Stmt gt if cond lt Then_Part gt lt Else_Part gt Using the system disambiguating rules priority is given to shift 83 ANNEXE EXEMPLES DE GRAMMAIRES NON LALR 1 84 E 1 2 2 Option path SAMPLE PATH from state 1 to 6 if cond lt Then_Part gt NOT L R 1 Shift Reduce conflict in state 6 on else between Shift 6 Else Part else lt Stmt gt derivation lt Stmt gt gt if cond lt Then_Part gt lt Else_Part gt gt if cond lt Then_Part gt else lt Stmt gt gt if cond lt Then_Part gt else Reduce b Else Part derived from 3 If Stmt if cond Then Part Else Part by lt Stmt gt gt lt If_Stmt gt gt if cond lt Then_Part gt lt Else_Part gt gt if cond lt Then_Part gt else gt x if cond then lt Stmt gt else gt if cond then lt If_Stmt gt else gt x if cond then if cond Then Part XElse Part else gt if cond then if cond Then Part else The grammar is AMBIGUOUS First derivation lt Stmt gt gt lt If_Stmt gt gt if cond Then Part Else Part gt if cond Then Part else gt if cond then lt Stmt gt else gt if cond then lt If_Stmt gt else gt
109. t vont positionner des variables qui peuvent tre utilis es par les pr dicats voir ci dessous D un point de vue syntaxique une action joue le r le d un symbole non terminal dont la d finition est fournie par le syst me sous la forme d une partie droite vide A l analyse d un texte l action n est appel e chaque fois que la r gle vide correspondante est reconnue CHAPITRE 2 BNF LECTURE DES D FINITIONS SYNTAXIQUES 12 L adjonction d actions ne change pas le langage d crit par la grammaire il est possible en revanche que la grammaire devienne non LALR 1 2 2 2 2 Les pr dicats On peut associer pr dicat un symbole terminal quelconque g n rique ou non ou un symbole non terminal quelconque situ en partie droite d une r gle Un pr dicat est un nombre entier n positif ou nul pr c d du caract re amp Un pr dicat doit suivre lexicalement dans la grammaire le symbole auquel il est associ Un tel couple est appel terminal tendu ou non terminal tendu l analyse un terminal tendu t amp n est reconnu si et seulement si le texte source contient le symbole t et le pr dicat n rend vrai le pr dicat est implant par une fonction r sultat bool en crite par l utilisateur appel e avec le pa ram tre n Un non terminal tendu A amp n est reconnu si et seulement si une phrase de A a t reconnue on vient d effectuer une r duction et A est en partie gauche de la r gl
110. t pr sente permet de construire un analy seur lexicographique pour une machine diff rente de la machine h te On peut indiquer la repr sentation interne des caract res utilis e par la machine cible CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICAL33 ainsi que les longueurs de l octet byte et du mot word de cette machine cible La syntaxe est la suivante n et m tant deux entiers positifs For Internal Code Use liste de composants For Byte Use n Bits For Word Use m Bits Les composants sont s par s par des virgules et indiquent pour chaque index en partant de 0 si le nombre associ correspond une repr sentation interne d un caract re ou non et dans l affirmative pr cisent ce caract re UNUSED ou UNUSED un nombre ou n nombres cons cutifs ne sont pas des repr sentations internes de caract res un code octal ou une chaine de caract res fournissent une ou plusieurs correspondances caract re repr sentation interne F1G 4 3 Exemple de sp cification de repr sentation For Internal Code Use 10 Unused 01 Unused 012 Les repr sentations internes sont 10 pour le caract re 0 11 pour le caract re 1 et 13 pour le caract re ASCII de code 10 012 en octal Dans la machine cible les codes internes 0 9 et 12 correspondent des caract res ill gaux 4 1 6 Les expressions r guli res Le vocabulaire des expressions r guli re
111. taxiques il lit une grammaire ind pendante du contexte effectue quelques v rifications simples de coh rence et produit une forme interne de cette gram maire des tables qui sera utilis e par les autres processeurs La grammaire d entr e est crite dans un langage proche de la Backus Naur Form bien connue Les non terminaux et les terminaux sont distingu s CHAPITRE 1 INTRODUCTION 2 lexicalement Chaque alternative donne lieu une production diff rente BNF accepte des grammaires ambig es condition que ces ambig it s puissent tre lev es par la donn e de niveaux de priorit voir la section concernant CSYNT et PRIO ci dessous De plus l analyse syntaxique peut tre influenc e par des pr dicats et des actions programm s par l auteur de la grammaire ce qui permet de traiter des langages non d terministes voire d pendants du contexte 1 1 2 Constructeur syntaxique CSYNT et PRIO CSYNT est le constructeur syntaxique Il lit les tables produites par BNF et construit un analyseur syntaxique ascendant en utilisant la m thode LALR 1 Les conflits d tect s lors de la construction de l analyseur qui ne seraient pas r solus par la lecture d une unit lexicale en avance peuvent l tre de plusieurs autres mani res par l auteur de la description soit en utilisant des pr dicats et des actions comme d crit dans la section consacr e BNF soit en forcant des niveaux de priorit voir ci desso
112. terpr t de la fa on suivante apr s avoir cr t la pile d analyse de la longueur sp cifi e par le champ Stack on examine le contenu du champ Goto Si c est Goto n on va ex cuter inconditionnel lement l instruction num ro n Sinon on examine le sommet de la pile d analyse Si c est l adresse d une instruction voir action Shift on va ex cuter inconditionnellement cette instruction on ne peut jamais trouver l adresse z ro Sinon le sommet de pile d signe un NT bloc qui est activ et l on recherche dans sa liste d instructions le non terminal sp cifi dans le champ Goto Ce non terminal nt est en g n ral le non terminal se trouvant en partie gauche de la production num ro p du champ Reduce mais du fait des optimisations ce peut tre un autre non terminal ou m me un non terminal invent par l optimiseur d not par un nombre entier n compris entre un gt et un donc gt n lt L action Halt marque la fin de la reconnaissance du texte L action Error indique la d tection d une erreur de syntaxe Elle provoque l ex cution d un programme de rattrapage d erreur voir le chapitre 6 En fait les instructions qui viennent d tre d crites sont une forme simplifi e d un langage permettant de coder des automates pile d terministes et dont les instructions sont appel es productions de Floyd Evans Une production de Floyd Evans comporte cinq champs Test Scan Reduce Stack Goto
113. tivement le d but et la fin d un commentaire et qu il soit possible de trouver un commen taire l int rieur d un autre commentaire ce type de commentaire ne se rencontre l heure actuelle que tr s rarement dans les langages malheu reusement Une description possible est donn e en figure 4 9 F1G 4 9 Exemple de sp cification des commentaires de OLGA Comments i Reset 0 i Incr 0 amp Is_ Set 0 Decr 0 Remarque Plus g n ralement il est possible d utiliser LECL pour d crire des langages non r guliers en simulant l automate pile correspondant par des appels r cursifs de l analyseur lexical dans un style qui s apparente la descente r cursive dans les analyseurs syntaxiques de la classe LL chaque notion du langage non terminal on fait correspondre une description langage et chaque fois qu un niveau donn on reconnait gr ce un pr fixe la pr sence d une CHAPITRE 4 LECL CONSTRUCTION DE L ANALYSEUR LEXICALAO notion l analyseur lexical de cette notion est appel par l interm diaire d une action utilisateur Lorsque cette notion a t trait e une autre action utilisateur permet le retour au niveau appelant Par exemple la sp cification lexicale pr c dente des commentaires OLGA peut galement se d crire comme en annexe 2 4 1 6 5 Les includes L utilisateur ala possibilit de d finir des commandes d inclusion introduites par le m
114. to be 2 int XNT_parsact entry action_no int entry action_no switch entry case OPEN case CLOSE case FINAL case INIT return case PREDICATE switch action no case 1 if sxget_token sxplocals ptok_no gt lahead c_code amp amp sxget_token sxplocals ptok_no 1 gt lahead a_code return TRUE return FALSE default break break default break fputs The function XNT_parsact is out of date with respect to its specification n sxstderr abort 4 Un langage non d terministe E 4 1 Grammaire Langage non deterministe L aba b aba a b om k n gt 0 Grammaire non LR ni RLR ni LR 7 lt Z gt 1 lt S gt lt S gt lt A gt B lt S gt lt B gt lt C gt lt B gt lt A gt a lt A gt bb lt gt a bb 5 lt gt lt B gt b ANNEXE E EXEMPLES DE GRAMMAIRES NON LALR 1 88 lt B gt a b amp 1 B a lt B gt b lt gt ab C 02 amp 2 lt C gt lt C gt 2 a init a_number 1 et a_s b_s k 0 1 Compte les premiers a et b dans a_s et b_s Si a_s b_s compte les a et b de queue et calcule Ibl 2 a_number amp 1 return a_s b_s amp 2 return a_number lt k E 4 2 Actions include sxunix h include NDL_td h defines a_code to be 1 and b_code 2 static int a_s b_s a_number int NDL_par
115. tous faux En proc dant de cette facon il est bien entendu possible d oublier quelques corrections Il est donc conseill d viter de d tecter des erreurs dans les s quences de pr dicats en proc dant de la facon suivante Rappelons que la pr sence de pr dicats dans une grammaire permet d expliciter d une mani re non syntaxique un choix entre plusieurs possibilit s syntaxiques Consid rons pour simplifier deux choix C et C2 reconnus respectivement par les pr dicats amp 1 et amp 2 associ s au symbole X Il y a a priori deux fa ons d crire la grammaire correspondante Les symboles tendus X amp 1 et X amp 2 figurent en parall le dans la gram maire et en cons quence l automate engendr testera successivement amp 2 amp 1 ou inversement puis amp Else Il d tectera donc une erreur si ni 61 ni 2 n a retourn vrai erreur qui ne pourra pas tre corrig e Un seul choix est explicit le plus particulier si possible C4 par exemple par le symbole tendu X amp 1 l autre choix tant repr sent par le sym bole simple X qui est donc consid r par le syst me comme tant associ au pr dicat amp Else Dans ce cas l automate engendr testera successi vement 1 choix puis amp Else choix C2 Aucune erreur ne peut donc tre d tect e cet endroit Le choix C2 a t privil gi Des er reurs seront d tect es ult rieurement si la chaine ne correspond ni au choix ni au ch
116. ts par LECL sont repr sent s par des tables Sur option l analyseur lexical peut aussi tre produit sous la forme d un programme C sp cifique ce qui permet d augmenter la vitesse d analyse 1 1 4 Traitement des erreurs RECOR L avantage le plus appr ciable de SYNTAX sur YACC est son puissant trai tement d erreurs il faut d ailleurs reconnaitre que YACC est particuli rement rustique sur ce point Tout traitement d erreur se d compose en trois ou quatre phases 1 d tection 2 affichage 3 tentative de correction 4 rattrapage si la correction a chou En ce qui concerne la d tection d erreur les m thodes d analyse employ es par SYNTAX poss dent la propri t du pr fixe correct ce qui garantit qu une erreur est d tect e d s que la partie du texte d j lue ne peut pas faire partie d un texte correct En ce qui concerne l affichage SYNTAX met des messages d erreur tr s clairs avec rappel au terminal de la ligne du texte source et marqueur sous l erreur De plus si les analyseurs sont construits en cons quence un listage est produit contenant le texte source et les messages d erreur au bon endroit L analyse se poursuit apr s une correction ou un rattrapage 1 1 4 1 Correction locale Quand une erreur est d tect e l analyseur produit virtuellement toutes les parties de texte syntaxiquement correctes partir du point en erreur et les compare une liste ordonn e de mod les de corre
117. u langage PASCAL an nexe F 1 et des langages BNF A 2 et LECL lui m me B 2 4 2 Mise en uvre Voir la documentation en ligne man 1 De plus si l utilisateur a inclu des actions vel des pr dicats dans sa d finition lexicale il doit crire un pro gramme en langage C codant ces actions et pr dicats Ce codage n cessite en g n ral d acc der un certain nombre de variables manipul es par SYNTAX se reporter la documentation en ligne concernant notamment sxunix 3 sxsrc mngr 3 sxscanner 3 et sxstr mngr 3 On trouvera des exemples de codage d actions et de pr dicats en annexes B 3 et A 3 Chapitre 5 La s mantique dans SYNTAX SYNTAX permet deux types distincts de traitement s mantique soit en effectuant des actions s mantiques pendant l analyse syntaxique l appel de l action associ e une r gle de la grammaire s effectue apr s la reconnaissance de la partie droite de cette r gle soit en utilisant l arbre abstrait que peut construire l analyseur syntaxi que et en appliquant sur cet arbre un programme d valuation d attributs s mantiques Ces deux possibilit s sont obtenues respectivement par utilisation des construc teurs SEMACT et SEMAT 5 1 SEMACT Actions s mantiques Pour introduire des actions s mantiques dans la grammaire contenue alors g n ralement dans un fichier de nom nom du langage bnf l utilisateur doit ajouter en fin de r gle apr s le un no
118. uissance d expression permise par la classe de grammaires accept e d autre part CSYNT recoit en entr e la forme interne de la grammaire produite par BNF voir le chapitre 2 et construit un analyseur syntaxique ascendant sous forme d un automate pile Si CSYNT au cours de cette construction d tecte une non conformit dans la d finition de la grammaire il le signale de deux facons Le message NON LALR 1 est crit sur stderr en g n ral le terminal de l utilisateur Un diagnostic circonstanci des causes de cette non conformit est inscrit dans le fichier nom du langage 1a 1 donnant notamment les r gles de la grammaire qui la produisent et une partie du contexte 3 2 Les conflits On peut avoir deux types de non conformit des conflits Reduce Reduce il existe plusieurs possibilit s de reconnais sance simultan e de parties droites de r gles Reduce et les symboles du contexte droit de ces r gles look ahead ne permettent pas de faire un choix des conflits Shift Reduce il y a conflit entre l absorption shift du sym bole suivant et une r duction ou plusieurs Dans les messages d erreur mis par CSYNT chacune des r gles de grammaire mentionn es comporte un marqueur LR symbolis par un qui indique o a t d tect e la non conformit 15 CHAPITRE 3 CSYNT CONSTRUCTION DE L ANALYSEUR SYNTAXIQUE16 Exemple La figure 3 1 donne un exemple de diagnostic mis par CSYNT
119. us automatiquement par CSYNT gr ce l utilisation par celui ci de r gles de r solution pr d finies par exemple Shift prend pr c dence sur Reduce La sp cification de r solution des conflits est trait e par PRIO Elle se fait en utilisant une syntaxe et une s mantique tr s proches de celles de YACC mais la description est s par e de la grammaire proprement dite Sur option CSYNT produit un listage d taill d crivant les conflits d tect s ce qui permet un utilisateur averti de les comprendre facilement Le second composant de CSYNT r duit tr s fortement usuellement de plus de 9596 la taille des tables repr sentant l automate implantant l analyseur syn taxique En outre sur option il est capable d liminer totalement les r ductions par des productions simples ce qui augmente en g n ral la vitesse de l analyse 1 1 3 Constructeur lexical LECL LECL est le constructeur lexical Il lit les tables produites par BNF en par ticulier la table donnant pour chaque terminal ceux qui peuvent le suivre ainsi qu une description lexicale du langage et produit des tables d crivant l analy seur lexical engendr Certains terminaux de la grammaire tels ceux qui repr sentent les identifi cateurs du langage ou ses constantes ainsi que les commentaires du langage doivent tre d crit par une expression r guli re sur un alphabet dont les lettres sont des classes de caract res LECL propose un certain no
120. vided that the copyright notice and this permission notice are preserved thus giving the recipient permission to redistribute in turn Permission is granted to distribute modified versions of this document or of portions of it under the above conditions provided also that they carry prominent notices stating who changed them where and why SynTax est une marque d pos e de l INRIA Uurx est une marque d pos e des Laboratoires Cloche AT amp T Bell Laboratories 3 boullier deschamp minos inria fr Table des mati res 1 Introduction 1 1 Les processeurs de base 1 1 1 Introducteur syntaxique BNF 1 1 2 Constructeur syntaxique CSYNT et PRIO 11 3 Constructeur lexical 1 1 4 Traitement des erreurs 1 1 5 Production des tables TABLES C 1 2 Le Syst me d Ex cution 1 3 Le Traitement S mantique T ACTIONS enin v gum RU inb Ge goo E 13 2 Actions la YAGO x xxx 1 3 3 Attributs s mantiques purement synth tis s 1 3 4 Arbres abstraits 13 5 1 3 6 Utilitaires divers 1 4 Mise en uvre de SYNTAX sur 2 BNF Lecture des d finitions syntaxiques 221 FONCUON 52 2 dent Su 2 2 M talangage sy
121. xincl_mngr entry return case ACTION switch act_no The pathname of the include file is in token_string int ste sxstrsave sxsvar sxlv_s token_string it is saved permanently in the string_manager char path sxstrget ste and get back ANNEXE EXEMPLES DE DEFINITIONS LEXICALES 93 case 1 if sxpush_incl path The source text now comes from the include file return something failed unable to open recursive call error message sxput_error sxsvar sxlv terminal_token source_index source coordinates of the include command sUnable to process the include file 5 sxsvar sxtables gt err_titles 2 severity level error path include file name however scanning of the current file is going on return case 2 End of include processing if sxpop_incl return something really wrong error message fputs Sorry the include processing garbled nevertheless hope to see you again soon n sxstderr abort panic default fputs The function your_scan_act is out of date with respect to its specification n sxstderr abort
122. xiome de la grammaire est par d finition le symbole non terminal figurant en partie gauche de la premi re r gle On distingue deux types de symboles terminaux les terminaux g n riques tels que les identificateurs et les litt raux pou vant recouvrir un ensemble th oriquement infini de possibilit s pour le programme et qui doivent obligatoirement tre d finis au niveau lexical voir le chapitre 4 De tels terminaux sont d not s par un identificateur forme C du terme pr c d du caract re les autres terminaux mots cl s symboles sp ciaux Ceux ci sont en g n ral crits exactement tels qu ils devront apparaitre dans les pro grammes et se terminent au premier blanc ou fin de ligne rencontr Toutefois pour r soudre les probl mes d ambig it que posent les ter minaux commen ant par un des caract res 7 lt 0 tout terminal peut tre pr c d d un caract re Tout terminal peut galement tre crit entre guillemets dans ce cas les conventions d criture des chaines de caract res du langage C s appliquent ces conventions sont rappel es dans la table 2 1 La figure 2 1 donne TAB 2 1 Conventions d criture des caract res dans les cha nes S quence Nom du caract re Code ASCII en octal Nb Back Space 010 Nt Horizontal Tabulation 011 Mn New Line 012 f Form Feed 014 r Carriage Return 015 Double Quote 042 Back Slash 134 nnn nnn
123. xique d un texte ner case SEMPASS appele apres l analyse syntaxique d un texte break case CLOSE appele apres l analyse de tous les textes source break default Message d erreur C 2 Trame de passes s mantiques Ceci est la trame de passe s mantique produite par SEMAT partir de la sp cification d arbre abstrait de l annexe A 1 oe ae fe de kkk k k k kk kk k IGRI k kk kk ak kk This program has been generated from bnf at on Mon Apr 11 15 44 23 1988 by the SYNTAX abstract tree constructor RH kk k kk kkk kk kk kkk k k k k k I I Ia k k k k K SYNTAX is a trademark of INRIA RH AH INCLUDES define NODE struct bnf_node include sxunix h struct bnf_node SXNODE_HEADER_S VOID_NAME ANNEXE EXEMPLES LIES A LA SEMANTIQUE your attribute declarations NODE NAMES define ERROR_n 1 define ACTION_n 2 define BNF_n 3 define GENERIC_TERMINAL_n 4 define LHS_NON_TERMINAL_n 5 define NON_TERMINAL_n 6 define PREDICATE_n 7 define RULE_S_n 8 define TERMINAL_n 9 define VOCABULARY_S_n 10 define X_NON_TERMINAL_n 11 define X_TERMINAL_n 12 END NODE NAMES static bnf pi O INHERITED switch VISITED gt father gt name case ERROR n break case BNF_n VISITED gt name RULE_S_n break case RULE_S_n VISITED gt name VOCABULAR

LE SYSTÈME SYNTAXTM MANUEL D`UTILISATION ET DE

Contents

Download Pdf Manuals

Related Search

Related Contents

LE SYST&Egrave;ME SYNTAXTM MANUEL D`UTILISATION ET DE

Contents

Download Pdf Manuals

Related Search

Related Contents

LE SYSTÈME SYNTAXTM MANUEL D`UTILISATION ET DE