DP Tool Club 17/CD_ASCQ_17_101194.iso/dos/prg/syntex/stxhlpf.hlp

Borland Turbo Vision Help | 1994-07-27 | 21KB | 630 lines

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