Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
En pratique : Utilisation de Yacc (règles syntaxiques et sections)
(Article écrit par Pascal Amiable et extrait d'Amiga News Tech - février 1992)
|
|
Comme promis, voici (enfin) l'étude de la version Amiga de Yacc, un utilitaire Unix aussi célèbre que Lex
et que l'on utilise d'ailleurs avec ce dernier pour réaliser, entre autres choses, des compilateurs.
Le nom de Yacc est la contraction de "Yet Another Compiler Compiler", c'est-à-dire un compilateur de
compilateurs. En effet, Yacc a été créé pour réaliser rapidement des compilateurs de langage : ces programmes
lisent en entrée un source sous la forme d'un langage de programmation et génèrent un code de sortie dans
un autre langage. Il s'agit d'un point de départ pour l'écriture de compilateurs BASIC, Pascal, C ou de toute
autre langage de votre choix. Il ne s'agit bien sûr que d'un outil d'aide à la réalisation de telles applications,
il ne fait pas tout, tout seul non plus.
Comparaison entre Flex et Yacc
Sous bon nombre d'aspects, Yacc est similaire à Flex.
Les deux programmes lisent un fichier d'entrée qui contient une liste de règles et la convertissent en une
fonction C qui peut être compilée et exécutée (fig. 1).
La différence est toutefois essentielle dans l'utilisation que l'on peut faire de ces deux logiciels : Flex est
utilisé pour produire un analyseur lexical dont le but est de reconnaître dans un flot d'entrée, un certain
nombre de symboles, alors que Yacc permet de réaliser un analyseur grammatical dont le but est de reconnaître des
associations de symboles sous la forme de phrases. Ces deux programmes sont donc totalement complémentaires,
car la base de tout programme de transcription est la combinaison d'un analyseur lexical et d'un analyseur syntaxique.
Une approche par l'exemple
Afin de mieux vous sensibiliser au fonctionnement de Yacc, nous allons réaliser un petit exemple d'analyseur
syntaxique en prenant comme base notre langue, le français. Toute phrase en français est constituée de mots
agencés suivant des règles précises. Par exemple, une phrase va être constituée d'un nom, d'un verbe et d'un complément.
La reconnaissance d'un mot appartenant à la langue française est du travail de Lex, alors que l'analyse de
l'assemblage de ces mots pour déterminer si la phrase formée a un sens du point de vue grammatical est du ressort
de Yacc.
En français, la grammaire est basée sur une série de règles utilisant des notions basiques tels les noms, verbes,
adjectifs et d'autres plus complexes, comme les phrases, attributs, sujets, objets... Dans un programme Yacc,
toutes ces notions sont représentées par des symboles grammaticaux.
Notre exemple d'analyseur va pouvoir traiter les notions suivantes :
- VERBE : pour un verbe.
- NOM : pour un nom.
- ADJECTIF : pour un adjectif.
- NOMBRE : pour représenter une indication numérique.
- Phrase : pour représenter une phrase.
- Predicat : pour représenter un prédicat.
- Complement : pour un complément.
- Sujet : pour le sujet.
- Objet : pour représenter un objet.
Une différence a été faite intentionnellement entre majuscules et minuscules, pour marquer les différences
de niveau grammatical. Un symbole comme "VERBE", qui représente un mot de la langue française, est une
entité de bas niveau. Ce symbole est dit aussi "terminal", car il représente l'entité manipulable de plus bas niveau.
Les symboles plus complexes comme "Phrase", qui sont réalisés à partir d'un assemblage de mots, sont dits
de haut niveau ou "non-terminaux", car formés d'autres symboles, terminaux ou non.
Nous allons maintenant étudier comment transposer cette hiérarchie à Yacc, en prenant comme exemple la
phrase suivante : "Stéphane range trois disquettes vertes".
En français, l'ordre normal pour représenter une phrase est un sujet suivi d'un prédicat (c'est le cas de notre
exemple). Toutefois, sous la forme impérative, seul le prédicat subsiste ("range trois disquettes vertes !').
Cette première règle peut être symbolisée en Yacc sous la forme :
"Phrase" représente ce qui va être défini. Il est suivi du caractère ":" et de sa définition, composée de "Sujet"
et "Predicat". A la ligne suivante, la définition continue avec une barre verticale "|", symbole du "ou",
lui-même suivi d'une deuxième définition. Ce genre de syntaxe est appelé une définition alternative ;
la définition de "Phrase" s'arrête à la présence du point-virgule.
La définition de la phrase n'est pas encore complète, dans la mesure où elle est composée de symboles
non-terminaux. En effet, "Predicat" et "Sujet" n'ont pas encore été définis. Un prédicat est constitué,
dans notre cas, d'un verbe et d'un complément, ce qui se représente fort simplement par :
Comme on peut le remarquer, nous avons déjà une branche de notre arbre d'analyse qui se termine, puisque
"VERBE" est terminal.
Étudions maintenant le sujet et le complément : tous deux peuvent être définis par un objet, ce qui ce traduit par :
Enfin, l'objet peut être :
- Un nom.
- Un nombre.
- Un nom.
- Un adjectif + un nom.
- Un nombre + un adjectif + un nom.
Soit en Yacc :
Étant arrivés à décrire l'ensemble des entités complexes sous forme de symboles terminaux, le travail d'analyse est,
par conséquent, terminé. Bien entendu, les règles de grammaire française sont beaucoup plus complexes que ce
petit exemple, en particulier pour les exceptions qui font tout le charme de notre langue, et le malheur
des programmeurs d'analyseurs syntaxiques.
Programmation de l'exemple
Maintenant que nous avons décrit les règles syntaxiques de notre exemple en langage Yacc, nous allons pouvoir
bâtir un programme complet autour de ces règles. Comme pour Flex, un programme Yacc est décomposé en trois sec-tions :
- La section Déclarations.
- La section Règles.
- La section Fonctions Utilisateur.
Chaque section étant séparée par "%%".
Nous commencerons notre programme par la section "Règles", qui représente le corps du programme.
La section Règles
Nous allons donc transformer nos règles grammaticales en un programme qui reconnaît les phrases françaises.
Nous devons également spécifier quelles sont les actions qui vont être effectuées lorsqu'une règle sera
déclenchée : ces actions sont des fragments de code C qui sont positionnés à la droite de la déclaration de
la règle, entourées par des accolades. Pour notre exemple précédent, la section règles devient :
Ce morceau de programme représente le coeur de notre analyseur. Pour le faire fonctionner correctement, il
nous faut désormais ajouter les autres sections.
Par rapport à ce que nous avions défini précédemment, nous avons ajouté la directive "error"
pour le traitement des erreurs de syntaxe ainsi que des caractères "retour chariot", pour déterminer la fin d'une phrase.
La section Déclarations
Nous allons maintenant étudier la première section du programme Yacc, à savoir la section Déclarations.
Dans cette zone du programme, nous allons définir les symboles terminaux ainsi que toutes les variables
globales dont nous aurons besoin dans le reste du programme.
Dans notre exemple, les symboles terminaux sont VERBE, ADJECTIF, NOM, NOMBRE. Ce sont des constantes entières,
appelées "tokens", qui représentent des symboles grammaticaux en provenance de Flex et passés à Yacc.
La directive "token" fait en sorte que chaque symbole reçoive une valeur constante. Cette valeur est
systématiquement supérieure à 256 pour qu'il n'y pas de conflit avec le passage de caractères, dont les codes
ASCII sont compris entre 0 et 255.
Dans notre exemple, la directive token serait :
%token VERBE NOM ADJECTIF NOMBRE
|
Le caractère "%" se place immédiatement devant la directive, sans espace entre les deux. Lors de la
phase de compilation, Yacc assignera une valeur à chaque symbole. Cette valeur est totalement transparente
pour le programmeur qui n'a, du reste, pas à s'en soucier.
La section Fonctions Utilisateur
La dernière section du programme Yacc contient les fonctions de support, comme le programme principal,
les routines de gestion des erreurs et le programme Lex. Dans un premier temps, nous allons créer
les routines minimales pour chaque support.
Pour éviter de taper ces routines, nous pourrions nous en remettre directement à la bibliothèque de
fonctions associée à Yacc. Mais pour une meilleure compréhension de l'ensemble et, compte tenu de la
faible taille des fonctions, il est préférable de les écrire soi-même.
Programme principal : comme dans tout programme C, le programme principal s'appelle main().
Il est le point de départ du programme généré par Yacc. Dans la première version de notre exemple,
le programme principal se contentera d'appeler la fonction yyparse(), qui est le nom de l'analyseur
syntaxique qu'aura généré Yacc (de l'anglais parse, acte de séparer en plusieurs parties).
Notre programme principal est donc :
On demande une phrase, on l'analyse et on rend la main à l'utilisateur. C'est tout.
Gestion des erreurs : deux fonctions de gestion des erreurs sont normalement nécessaires : yyerror() et yywrap().
La première est appelée lorsqu'en cours de fonctionnement, le programme Yacc découvre une erreur.
La deuxième est invoquée à la fin, pour tout remettre en ordre avant de terminer l'exécution du programme.
Pour une première version, ces deux routines seront vides.
La fonction Lex : elle peut être définie dans cette section. Elle doit s'appeler yylex().
Son rôle est de créer des tokens pour Yacc. Dans un premier temps, nous laisserons cette routine vide.
Voilà, nous avons maintenant tout ce qu'il nous faut pour réaliser un analyseur syntaxique. Le mois prochain,
nous verrons comment compiler ce programme Yacc sur Amiga et nous continuerons notre apprentissage de ce
langage en améliorant notre exemple. En attendant, pour ceux qui connaîtraient déjà ce langage, et également
pour vous permettre de vous le procurer pour le mois prochain, je vous signale que Yacc version Amiga est
disponible dans la collection Fred Fish sur la disquette
numéro 419.
|
