Scribd
Importer
10 vues1 page

Grammaires de Précédence Simple en Informatique

Le document présente des exercices sur la transformation de grammaires pour qu'elles soient de précédence simple, en se concentrant sur des conditions spécifiques. Il aborde également l'analyse syntaxique des expressions arithmétiques et des instructions conditionnelles en utilisant des algorithmes et des structures de données appropriés. Enfin, il discute des multidéfinitions dans les tables SLR(1) et de leur levée pour une analyse syntaxique déterministe.

Transféré par

Heisenbug
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
10 vues1 page

Grammaires de Précédence Simple en Informatique

Le document présente des exercices sur la transformation de grammaires pour qu'elles soient de précédence simple, en se concentrant sur des conditions spécifiques. Il aborde également l'analyse syntaxique des expressions arithmétiques et des instructions conditionnelles en utilisant des algorithmes et des structures de données appropriés. Enfin, il discute des multidéfinitions dans les tables SLR(1) et de leur levée pour une analyse syntaxique déterministe.

Transféré par

Heisenbug
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

ECOLE NATIONALE SUPERIEURE EN INFORMATIQUE

COMPILATION TRAVAUX DIRIGÉS 4 2016/2017

Exercice 1.
 On peut transformer aisément certaines grammaires pour qu'elles soient de précédence simple. Ces grammaires
sont celles vérifiant toutes les conditions que doit satisfaire une grammaire de précédence simple sauf des cas de
multidéfinitions <= ou >=.
Cas X < = Y :
 X = Y i.e.  A  N | A  XY, (,)  (N  T)*
 X < Y i.e.  B  N | B  'XZ', (',')  (N  T)* et Y  PREMIER(Z)
Cas X > = a :
 X = a i.e.  A  N | A  Xa, (,)  (N  T)* et a  T
 X > a i.e.  B  N | B  'ZY', X  DERNIER(Z) et a  DEBUT(Y)
a) Quelles sont les transformations à effectuer sur ces grammaires pour qu'elles soient de précédence simple ?
b) De quelle condition faudra-il s'assurer pour que ces transformations soient suffisantes pour rendre une grammaire
de précédence simple ?

Exercice 2.
 Considérer la grammaire des expressions arithmétiques G=<N={E,T,F},T={+,,(,),i},E,P> dont les productions sont
données ci-après ( désigne l'opérateur de puissance) :
P: E  E + T | T
TFT|F
F  (E) | i
a) Cette grammaire est-elle de précédence simple ? faible ?
b) Donner algorithme et structure de donné utilisés pour faire les réductions lors de l'analyse syntaxique par
précédence faible pour analyser les mots du langage L(G).

Exercice 3.
 Considérer la grammaire suivante G=<T={i,e,a}, N={S], P, S> représentant la génération de l'instruction
conditionnelle if du langage C.
P: S→iS|iSeS|a
a) Cette grammaire est elle de précédence simple ?
b) Comment procéder pour analyser, "en précédence simple", les instructions conditionnelles ?
c) En utilisant l'analyse de précédence simple, analyser la représentation de l'instruction C if a if b i++ else if c i-- et
qui est donnée par :
iaiaeia
d) Donner l'arbre syntaxique correspondant à l'analyse de l'instruction précédente.

Exercice 4.
 Considérer la grammaire des expressions arithmétiques G=({E},{+,-,*,/,,(,),i},P,E) :
P: E  E + E | E - E | E * E | E / E | E  E | -E | (E) | i
a) Sans construire la table SLR(1), donner le nombre de multidéfinitions existantes dans cette table. Justifier.
b) Sans construire la table SLR(1), donner uniquement les cases concernées par les multidéfinitions pour la
grammaire restreinte dont les productions sont données ci-après :
P: E  E - E | E * E | -E | (E) | i
c) Expliquer comment lever ces multidéfinitions de ces cases pour faire une analyse syntaxique déterministe.
d) Comment seront interprétées les expressions suivantes ; donner leurs arbres syntaxiques :
12 + 3 * 3  2  1 - 4  2 * 5
(2 + 4) * 4  1  2 - 2 3 / 2
e) Donner, dans chaque cas, le nombre de réductions effectuées.
f) Si on devait utiliser une grammaire non ambigüe pour ces expressions, quel est le nombre de réductions
nécessaires pour analyser les expressions précédentes ? (sans construire la table SLR(1))
Compilation-2CS 1/1

Vous aimerez peut-être aussi