0 évaluation0% ont trouvé ce document utile (0 vote) 61 vues8 pagesTP Exam
Copyright
© © All Rights Reserved
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
FSTE-LST Informatique-Contrble théorie des langages 1513-H. SADKI
Université Moulay Ismail
Faculté des Sciences et Techniques
Errachidia
Département Informatique
2470372021
Contréle de la théorie des langages: 1513
Durée : th 30mn
Exercice 1
Soit lensemble P des régles d'une grammaire G
ne | Régle de production Commentaire i
1 |LOG — ELS [Expression logique
j 2 BL > PL EL VFL ‘ou’ logique entre expressions |
3° |FL + PL| PL ‘a'' FL ‘et’ logique enter expressions — |
4 [PL = idt| CEL YY Variable logique ou expression}
| [logique avec parentheses
1°) Définir les ensembles V; et Vi et V'axiome S de G?
2°) Transformer les régles récursives & gauche ?
3°) Transformer les régles non déterministes ?
4°) Vérifier si la grammaire G' obtenue est LL(1) ou non ?
5°) Les expressions logiques suivantes sont-elles correctes ou non ? Justifier ?
a) @*Bve b) 24@
Exercice 2.
Soit l'sutomate d'état fini suivant:
1°) Montrer que l'sutomate est non déterministe (AFN) ?
2°) Donner Yautomate d'état fini déterministe AFD correspondant 4 'AFN ? Préciser la table de
transition et le graphe de I" AFD ?
3°) Par élimination d'états, trouver 'expression réguliére associée a |! AFN ?
4°) En utilisant un systéme d'équations linéaires, trouver l'expression réguliére associée & 'AFD ?
5°) Comparer le résultat de la question 3°) avec celui de la question 4°) ?
“Wl Université Moulay Ismail
Faculté des Sciences et Techniques
Département d’Informatique
Errachidia
16/01/2018
Examen 1513 (2H)
Traduction des langages
Probleme J : Soit la grammaires G suivante:
N® | Régle Désignation
1 | PRO‘ LY Programme
2 |UD? Liste instructions
3 | ID idf'="E tion
4 |EOFIE ee F ‘Somme de deux expressions
5 |FOP| Pep Multiplication de deux expressions
6|P>s |p a Puissance entiére d’une expression
7\s > cste| “CEY Constante entire ou expression entre parentheses
1°) Définir les différents termes de la grammaire G=?
2°) Transformer G pour enlever les régles non déterministes ?
3°) Transformer G pour enlever les régles récursives a gauche ?
4°) Pour toutes les régles de la forme A> | a dans G’ obtenue,
calculer X=Suiv(A) et Y=Prem(ay)?
5)° En utilisant les résultats de 4°), montrer que G” obtenue est LL(1) ?
6°) Ecrire la descente récursive des régles 1 et 5 aprés leurs transformations ?
7°) Soit la phrase suivante écrite dans ce langage :
{iz "2 +(i+5)*2 }, Remplir ’arbre ARB sous sa forme poste fixée ?
8°) Interpréter arbre ARB?
Probléme 2 : Scit !’automate A suivant :
1°) En utilisant la méthode des équations linéaires, calculer le langage L(_4)?
2°) Rendre déterministe I’automate 4 pour obtenir 4?
a) Donner la table de l’automate 4 ?
b) Renommer les nouveaux états obtenus et donner la nouvelle table ?
©) Dessiner automate 41?
3°) les mots suivants appartiennent-ils au langage de 4 ? :
a) ‘abb’ justifier? b) ‘baba! justifier ? FSTE-LST Informatique-TP Traduction des Langages I1108-H. SADKI
Université Moulay Ismail
Faculté des Sciences et Techniques
Errachidia
Département Informatique
‘Travaux Pratiques N° 1
Analyseur Lexical des expressions arithmitiques avec l'outil Jex sous UNIX/LINUX
Le butde ce TP est d'ecrire un analyseur lexical pour une calculatrice simple qui utilise le clavier numérique:
© Nombres entiers et nombre reéls fixe (")
© Les opérateurs arithmitiques (+!
© Les parenthises ('("et')),
Voici le fichier source Lex calcul. d'expressions arithmitiques:
Hl
#include
#include
#define NOMBRE
#define PLUS
#define MOINS
#define FOIS
#define DEVISE
#define — PUISSANCE
define PARENTHESE-GAUCHE 7
define PARENTHESE-DROITE 8
%}
blancs [ \t]+
chiffre [0-9]
entier {chiffre}+
exposant [eE][+-]?{entier}
reel {entier}(*."{entier}) ?{exposant}?
es
{blancs} { /* On ignore */ }
{reel} {yylval=atof (yytext) ; return (NOMBRE) ;}
return(PLUS)
return (MOINS) ;
return(FOIS) ;
return(DIVISE) ;
return (PUISSANCE) ;
return(PARENTHESE GAUCHE) ;
")" return (PARENTHESE DROITE) ;
"\n" return(FIN) ;
%
“* puissance)
ouauNne
main(){
Printf(*L‘unité lexicale %s & pour code %d\n",yytext,yylex());
“12 le 20/10/08 FSTE-LST Informatique-TP Traduction des Langages [1 108-H. SADKI
a) Créer un fichier de description lex calcul.1 en y inserant les expressions
réguliéres: # vi calcul.t
b) Compiler le fichier calcul.1 avec la commande suivante:
# lex calcul.t
¢) Executer le programme résultant calcul: # calcul
Annexe : format du fichier de description et la syntaxe des
expression réguliéres sous lex
Un fichier de description pour Lex est formé de trois parties, selon le schéma suivant
declarations
%%
productions
%%
code additionnel
dans lequel aucune partie n'est obligatoire. Cependant, le premier 8 Test, afin dindiquer la séparation entre les
<éclaration et les productions.
‘Symbole | Signification
Le caractere ‘x*
N‘importe quel caractere sauf \n
[xyz] | Soit x, soit y, soit z
[*bz] | Tous les caracteres, SAUF b et z
[a-z] | N'importe quel caractere entre a et z
{*a-z] | Tous les caracteres, SAUF ceux compris entre a et z
R* | Zero R ou plus, ou R est n'importe quelle expression reguliere
R+ | Un R ou plus
Zero ou un R (c'est-a-dire un R optionnel)
!
!
|
|
I
!
I
| Entre deux et cing R
| Deux R ou plus
| Exactement deux R
"[xyz\"foo" | La chaine '[xyz"foo'
|
|
|
!
|
|
|
!
|
I
|
|
{NOTION} L'expansion de la notion NOTION definie plus haut
| \X | SiXest un ‘a’, ‘bY, ‘f', ‘nt, r', 't', ou
‘v', represente L'interpretation ANSI-C de \x.
\o Caractere ASCII 0
\123 Caractere ASCII dont le numero est 123 EN OCTAL
\x2A | Caractere ASCII en hexadecinal
RS | R suivi de S
RIS | Rous
R/S | R, seulement s'il est suivi par $
*R | R, mais seulement en debut de Ligne
RS R, mais seulement en fin de ligne
<> | Fin de fichier | otal 2
~ 22 Je 20/10/08 FSTE-LST Informatique-TP Traduction des Langages [1108-H. SADKI
Université Moulay Ismail
Faculté des Sciences et Techniques
Errachidia
Département Informatique
Travaux Pratiques N° 2
Un mini interpréte d'expressions
ot imerrctedexpressions est eapable de calle Ia valeur de nimporte quelle expression mathématique exprimée
‘Lide de nombres réels et des opérateurs','(considéré en tae qwopérateur unaire et binaire, ce qui signifie que
¥" et 2" seront des expressions valides), , ,"" (opérateur Puissance). Cet interpréte ne pourra pas faire appel &
des fonctions ni A des variables,
1. Le source Lex du mini-interpréte d'expressions
~ Voici tout d'abord le source complet
arg
#include “global.h*
#include “calc.h*
#include
s}
blancs [ \t]+
chiffre [0-9]
entier — {chiffre}+
exposant [eE][+-]?{entier}
cect {entier}(*.*{entier})7{exposant}7
aa
{blancs} { /* On ignore */ }
freely { yylvat=atof (yytext); return(NOMBRE) ; }
“+"" “return(PLUS)
return(MOINS) ;
return(FOIS) ;
return(DIVISE) ;
return(PUISSANCE) ;
return(PARENTHESE GAUCHE) ;
return (PARENTHESE DROITE) ;
“\e" return(FIN) ;
Eaxmlication de texte
1. Lapremitre parted fichier permet dinclure le fichier calc. qui sera généré plus tard par Yace et qui
incre elton des identificateurs NOMBRE, PLUS, MOINS, ee Og ot rofite au passage pour
“fea ga lbtite stb, qui content Tentte dela fonction atOF() antes pa la suite, On déclare la notion
“réel” qui sera utlisée plus bas. On peut aussi sy é
Par une ditective #deFine YYSTYPE double.
"ype YYSTYPE.
2 Kadevritme partie set sgnaler 3 fanalyscur sytaxique quel terminal ag
neontré. Sil sit dun
NOMBRE, alors il faut stocker sa valeur dans la variable yyLval, afin qu'elle puisse étve utilise,
ultérieurement
Yin, la woisidme partie n'existe pas, puisqu’on ne veut as que Lex mette un main () dans le texte source
ree, Le main () sera fait dans la partie su Yave
le 15/12/08 E-LST Informatique-TP Traduction des Langages [1 108-H1. SADKI
2. Le source Yace du mini-interpréte d'expressions
CCest le plus important, et le plus intéressant. Le voici
sf
#include “global.
#include
#include
#include
%
‘stoken NOMBRE
‘token PLUS MOINS FOIS DIVISE PUISSANCE
Sstoken PARENTHESE_GAUCHE PARENTHESE DROITE
‘token FIN
Sleft PLUS MOINS
‘left FOIS DIVISE
Sleft NEG
Sight PUISSANCE
sstart Input
os
Input:
/* Vide */
| Input Ligne
Ligne:
FIN
| Expression FIN { printf("Resultat : %f\n",$1); }
Expression:
NOMBRE { $$=$1; }
| Expression PLUS Expression { $$=$1+$3; }
| Expression MOINS Expression { $$=$1-$3; }
| Expression FOIS Expression { $$=$1*$3; }
| Expression DIVISE Expression { $$=$1/$3; }
|
I
|
MOINS Expression ‘prec NEG { $$=-$2; }
Expression PUISSANCE Expression { $$=pow($1,$3); }
PARENTHESE GAUCHE Expression PARENTHESE DROITE { $$=$2; }
96
int yyerror(char *s) {
printf ("%s\n", 5);
int main(void) {
yyparse();
}
SS
ce Te 15/12/08 FSTE-LST Informatique-TP Traduction des Langages 11108-H. SADKT
Aprés avoir inclus les fichiers habituels, tw utilises Ia directive Setoken pour déclarer les terminaux pouvant tre
rencontrés. II n'y a, dans ce cas, aucun ordre & respecter.
Ensuite, ga se complique avec les directives Left et right. Celle-ci servent & donner Vassociativité des
péateurs. ans ue leu précédences. On defini done es opérateurs par ordre croissant de priori, Ainsi "1+2*3" est
evalué comme "I+(2*3)". D’autre part, le fait que l'on choisisse “left” ou “right” dépend du comportement que tu
voudras donner & ton opérateur. Pour un opérateur (ici +) associatif a gauche, a+D4+C sera évalué comme (a+b)+¢.
Inversement, pour Tassociativité & droite, a“bC est évalué comme a” (b”C). C'est pas si compliqué, hein ?
On signale ensuite & Yace que laxiome de départ sera Input, cest-d-dire quiil se place au départ dans un état tel
‘que toute entrée sera considérée comme un Input. A ce sujet, note Ia écursion dans la définition de Input. Cela
permet de traiter une entrée de taille inconnue. Pour des raisons internes & Yace, il est préférable d'utiliser
Input:
7* Vide */
: | Input Ligne
plut6t que
Input:
/* Vide */
| Ligne Input +
(Cela permet une réduetion ds que c'est possible).
Passons 8 la définition de Ligne. Si la définition seule ne pose pas de probléme, peut-étre es-tu intrigué par le $1?
Cest simple, $1 fait référence & la valeur renvoyée parla premiéze notion de la production. De la méme fagon pour $2,
$3... Par contre, $$ est la valeur reavoyé par la production. Ainsi, dans la définition d Expression, lorsqu'on
rencontre Expression '+' Expression on fait laction $$=$14+$3, qui ne fait qu'ajouter.
Dans un autre ordre d'idée, regarde la ligne définissant le moins unaire. Le &Prec sert juste & indiquer que la priorité
de ceci est celle de NEG.
Enfin la toisitme partie du fichier est banale, puisqu‘lle se contente Fappeler yyparse().
3. Comment faire marcher cet exemple...
Sie fichier Lex sappelle calc. Lex et le fichier Yace ca1LC. y, il sufft de faire la procédure suivante
>bison -d calc.y
>mv [Link].h calc.h
>mv [Link].c calc.y.c
>flex calc. lex
>mv [Link].c [Link].c
>gcc -c [Link].c -o [Link].o
>gcc -¢ calc.y.c -0 cale.y.o
pac -0 calc [Link].o calc.y.o -1L -Im [eventuellement -UfL]
Veuillez noter que vous devez eréer le fichier gLobaL .h pour que cela compile. Ce fichier contiendra :
#tdefine YYSTYPE double s
extern YYSTYPE yylval;
Je dispose uniquement de bison et de flex, au lieu de Lex et de yacc, mais cela devrait fonctionnes de la
facon, & part le nom des fichiers générés. ens oo Ie wotene
ee
oat le 15/12/08 FSTE-LST Informatique-TP ‘Traduction des Langages 11108-H. SADKI
Lapel & bison (le Yace de GNU) avec option "-<" crée le fichier [Link] pour définir les terminaux. On appelle
flex (le Lex de GNU) et on donne des noms plus convenables pour fe tout. Il suffit alors de compiler, sans
uber de linker avec Ia ibrairie mathématique ("-Im") et la librairie spéciale Lex ("II"). On obtient:
>cale
14283
Resultat : 7.000009
2.5*(3.2-4.1°2)
Resultat : -34.025000
4, Une amélioration possible...
‘Afin de permetire le rattrapage erreurs syntaxiques, et pour ne pas voir le programme sarréter sur un "parse error”, on
peut remplacer
Ligne:
FIN
| Expression FIN { printf("Resultat : %f\n",$1); }
par
Ligne:
FIN
| Expression FIN { printf("Resultat : %f\n",$1); }
| error FIN { yyerrok; }
mais ce n'est qu'une possibilité parmi d'autres (utilisation et définition de variables et de fonctions, plusieurs types de
yi données, ...)
SESE ee
414 le 15/12/08
Vous aimerez peut-être aussi
