Scribd
Importer
26 vues1 page

TD03

Le document présente un TD sur la compilation, avec des exercices portant sur des grammaires non contextuelles, leur dérivation, arbres d'analyse et langages engendrés. Les exercices incluent des dérivations à gauche et à droite, ainsi que des analyses de grammaires ambiguës. Il aborde également des méthodes pour réaliser une analyse syntaxique déterministe.

Transféré par

lahlou khalid
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
26 vues1 page

TD03

Le document présente un TD sur la compilation, avec des exercices portant sur des grammaires non contextuelles, leur dérivation, arbres d'analyse et langages engendrés. Les exercices incluent des dérivations à gauche et à droite, ainsi que des analyses de grammaires ambiguës. Il aborde également des méthodes pour réaliser une analyse syntaxique déterministe.

Transféré par

lahlou khalid
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Centre Universitaire de Mila Informatique – Semestre 5

Institut des sciences et de la technologie COMPILATION – TD N° 03

Exercice 1.

 Considérons la grammaire non contextuelle suivante:

S  SS+ | SS* | a
a) Donner une dérivation à gauche de la chaine aa+a*
b) Donner une dérivation à droite de la chaine aa+a*
c) Donner un arbre d'analyse de la chaine aa+a*
d) Décrire le langage engendré par la grammaire.

Exercice 2.

 Décrire le langage engendré par les grammaires suivantes:


a) S +SS | *SS | a
b) S  S(S)S | 
c) S → x | y | z | S+S | S-S | S*S | S/S | (S)

Exercice 3.

 Considérer la grammaire G=<N,T,P,S> dont les productions sont données ci-après :

P :<Instruction> if <Condition> then <Instruction> else <Instruction>


| if<Condition> then <Instruction>
| begin <LI> end
|i
<Condition> c
<LI><LI> ; i | i
a) Montrer que la grammaire G précédente est ambiguë en donnant deux arbres syntaxiques pour le
fragment de programme suivant :

if c then if c then i else i


b) Comment pourra-t-on faire une analyse syntaxique "déterministe" pour ce type d'instructions
(instructions conditionnelles if).

Exercice 4.

 Soit la grammaire G=<{ A,B,C},{a,b},P,A>

A aB
B bC
C aC | bC | ɛ
a) Donner la dérivation la plus à gauche de la chaine : abbbaab
b) Donner la dérivation la plus à droite de la chaine : abbbaab
c) Donner le langage engendré par la grammaire.

1/1 2020-2021

Vous aimerez peut-être aussi