Scribd Logo
Importer

Bienvenue sur Scribd !

  • 72 vues

    Corrige Exam Comp Principal 2017 2018

    Transféré par

    Zinab Jbour

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Corrige Exam Comp Principal 2017 2018

    Transféré par

    Zinab Jbour
    72 vues7 pages

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    72 vues7 pages

    Corrige Exam Comp Principal 2017 2018

    Transféré par

    Zinab Jbour

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 7

    Département de Mathématiques, Informatique &

    Gestion
    Sciences Mathématiques et Informatique (SMI/S5)
    Compilation
    Prof. : M. BENADDY
    A.U:2017/2018

    Corrigé de l’examen de la session principale


    durée : 1h30

    Exercice 1:
    Soit l'expression régulière suivante :
    a((b|a*c))x*|x*a
    1. Quel est le langage dénoté par cette expression
    Tout les mots qui commencent par ‘a’ suivi d’un ‘b’ ou plusieurs ‘a’ et un c suivi de
    plusieurs x ou tout les mots qui commencent par plusieurs ‘x’ (y compris 0) et se terminent
    par ‘a’
    2. Donner l'AFN correspondant à cette expression.

    Ou bien :

    3. Tranformer l'AFN de la question 2 en un AFD.


    Solution 1 :
    -f{0}={0,1,14,15,17}
    Ɛ-f{T(A,a)}=Ɛ-f{2,18}={2,3,4,8,6,18}=B
    Ɛ-f{T(A,b)}={Ø}
    Ɛ-f{T(A,c)}=Ɛ-f{Ø}
    Ɛ-f{T(A,x)}=Ɛ-f{16}={16,15,17}=C
    Ɛ-f{T(B,a)}=Ɛ-f{7}={6,7,8}=D
    Ɛ-f{T(B,b)}=Ɛ-f{5}={5,10,11,13}=E
    Ɛ-f{T(B,c)}=Ɛ-f{9}={9,10,11,13}=F
    Département de Mathématiques, Informatique &
    Gestion
    Sciences Mathématiques et Informatique (SMI/S5)
    Compilation
    Prof. : M. BENADDY
    A.U:2017/2018
    Ɛ-f{T(B,x)}=Ɛ-f{Ø}
    Ɛ-f{T(C,a)}=Ɛ-f{18}={18}=G
    Ɛ-f{T(C,b)}=Ɛ-f{Ø}
    Ɛ-f{T(C,c)}=Ɛ-f{16}=C
    Ɛ-f{T(C,x)}=Ɛ-f{16}=C
    Ɛ-f{T(D,a)}=Ɛ-f{7}=D
    Ɛ-f{T(D,b)}=Ɛ-f{Ø}
    Ɛ-f{T(D,c)}=Ɛ-f{9}=F
    Ɛ-f{T(D,x)}=Ɛ-f{Ø}
    Ɛ-f{T(E,a)}=Ɛ-f{Ø}
    Ɛ-f{T(E,b)}=Ɛ-f{Ø}
    Ɛ-f{T(E,x)}=Ɛ-f{12}={11,12,13}=H
    Ɛ-f{T(F,a)}=Ɛ-f{Ø}
    Ɛ-f{T(F,b)}=Ɛ-f{Ø}
    Ɛ-f{T(F,c)}=Ɛ-f{Ø}
    Ɛ-f{T(F,x)}=Ɛ-f{12}=H
    Ɛ-f{T(G,a)}=Ɛ-f{Ø}
    Ɛ-f{T(G,b)}=Ɛ-f{Ø}
    Ɛ-f{T(G,c)}=Ɛ-f{Ø}
    Ɛ-f{T(G,x)}=Ɛ-f{Ø}
    Ɛ-f{T(H,a)}=Ɛ-f{Ø}
    Ɛ-f{T(H,b)}=Ɛ-f{Ø}
    Ɛ-f{T(H,c)}=Ɛ-f{Ø}
    Ɛ-f{T(H,x)}=H
    États (AFN) États (AFD) a b c x
    {0,1,14,15,17} A B C
    {2,3,4,8,6,18} B D E F
    {16,15,17} C G C
    {6,7,8} D D F
    {5,10,11,13} E H
    {9,10,11,13} F H
    {18} G
    {11,12,13} H H
    Le graphe d’états :
    Département de Mathématiques, Informatique &
    Gestion
    Sciences Mathématiques et Informatique (SMI/S5)
    Compilation
    Prof. : M. BENADDY
    A.U:2017/2018

    4. Minimiser l'AFD résultant de la question 3 (donner la table des transitions et le graphe des
    états de l'AFD minimisé).
    Les états d’acceptation {B, E, F, G, H} et les états de non-acceptation {A,C,D}
    π={B,E,F,G,H} {A,C,D}
    On prend le groupe {B,E,F,G,H}
    sur le symbole a : T(B,a) = {D} ∉ {B, E, F, G, H} et sur les symboles b,c et x pas de
    distinction alors, π={B} {E,F,G,H} {A,C,D}
    on prend {E,F,G,H} sur les symboles a, b, c, et x pas de distinction.
    On prend le groupe {A, C, D}
    sur le symbole a on T(A,a)=B∉ {A, C, D} , T(C,a)=G∉ {A, C, D} et T(D,a)=D alors
    π={B} {E,F,G,H} {A} {C} {D}
    on prend E comme représentant de {E,F,G,H}
    πfinale={B} {E} {A} {C} {D}
    La table de transition de l’AFD minimal :
    a b c x
    A B E
    B D E E
    C E C
    D D E
    E E
    Le graphe de transition :

    Exercice 2:
    Soit la grammaire G avec les règles de production suivantes :
    S → (L) | a
    L → L,S|S

    1. Déterminer les non-terminaux et les terminaux de la grammaire G.


    N = {S,L}
    T={a , a ( )}
    Département de Mathématiques, Informatique &
    Gestion
    Sciences Mathématiques et Informatique (SMI/S5)
    Compilation
    Prof. : M. BENADDY
    A.U:2017/2018

    2. Calculer Début et Suivant pour les non terminaux de G.

    Premier Suivant
    L { a, ( } { ), , }
    S { a, ( } { $, ) , , }

    3. La grammaire G est elle LL(1), justifier ?


    Non car elle récursive à gauche.
    4. Donner la table d’analyse prédictive de G.
    ( ) , a $
    L L → L,S|S L → L,S|S
    S S → (L) S→a

    5. Donner l’automate des items LR(0) canoniques pour G.


    On augmente la grammaire :
    S’ →S
    S → (L) | a
    L → L,S|S
    Etats {items LR(0)}
    fermeture({S' → S})=I0 S' SS (L), S a 
    Transition(I0,( )= I1 L SL L,S, S a, S (L), S (L) 
    Transition(I0,S)= I2 S' S}
    Transition(I0,a)= I3 { S a 
    Transition(I1,L)= I4 {L L,S , S (L)}
    Transition(I1,S)= I5 L S }
    Transition(I4,L)= I6 { S (L)}
    Transition(I4, , )= I7 {L L,S , S (L), S a }
    Transition(I7,S)= I8 {L L,S }
    Transition(I7, ( )= I1 L SL L,S, S a, S (L), S (L) 
    Transition(I7, a )= I3 { S a 

    6. Donner la table des actions et successeurs SLR de G.


    Etats Actions Successeurs
    ( ) , a $ L S
    0 d1 d3 2
    1 d1 d3 4 5
    2 acc
    Département de Mathématiques, Informatique &
    Gestion
    Sciences Mathématiques et Informatique (SMI/S5)
    Compilation
    Prof. : M. BENADDY
    A.U:2017/2018
    3 r2 r2 r2
    4 d6 d7
    5 r4 r4
    6 r1 r1 r1
    7 d1 d3 8
    8 r3 r3

    7. La grammaire G est-elle SLR ? Oui car, pas d’entrée multiple dans la table
    8. Donner le résultat de l’analyse de la chaîne w = ((a,a),a,(a)).
    Pile Tampon Action
    0 ((a,a),a,(a))$ d1
    0(1 (a,a),a,(a))$ d1
    0 (1(1 a,a),a,(a))$ d3
    0 (1(1a3 ,a),a,(a))$ r2
    0 (1(1S5 ,a),a,(a))$ r4
    0 (1(1L4 ,a),a,(a))$ d7
    0 (1(1L4,7 a),a,(a))$ d3
    0 (1(1L4,7a3 ),a,(a))$ r2
    0 (1(1L4,7S8 ),a,(a))$ r3
    0 (1(1L4 ),a,(a))$ d6
    0 (1(1L4)6 ,a,(a))$ r1
    0(1S5 ,a,(a))$ r4
    0(1L4 ,a,(a))$ d7
    0(1L4,7 a,(a))$ d3
    0(1L4,7a3 ,(a))$ r2
    0(1L4,7S8 ,(a))$ r3
    0(1L4 ,(a))$ d7
    0(1L4,7 (a))$ d1
    0(1L4,7(1 a))$ d3
    0(1L4,7(1a3 ))$ r2
    0(1L4,7(1S5 ))$ r4
    0(1L4,7(1L4 ))$ d6
    0(1L4,7(1L4)6 )$ r1
    0(1L4,7S8 )$ r3
    Département de Mathématiques, Informatique &
    Gestion
    Sciences Mathématiques et Informatique (SMI/S5)
    Compilation
    Prof. : M. BENADDY
    A.U:2017/2018
    0(1L4 )$ d6
    0(1L4)6 $ r1
    0S2 $ acc

    9. Donner l’arbre syntaxique si la chaine w est acceptée.

    Exercice 3:
    Donner le code intermédiaire correspondant au bloc du code en C suivant :
    if (x >= 100 && x < 200 || x==y) z=0 ;

    Ce code peut être écrit comme Le code post fixé


    if x >= 100 goto L3 x 100 L3 bge
    goto L4 L4 br
    L3 : if x < 200 goto L2 L3 : x 200 L2 blt
    L4 : if x==y goto L2 L4 : x y L2 eq
    goto L1 L1 br
    L2 : x=0 L2 : x 0 =
    L1 : L1 :

    Exercice 4:
    Convertir l'expression ((x + y) – ((x + y) * (x – y))) + ((x + y) * (x - y))
    1. Arbre abstrait
    2. Triplet
    3. Triplet indirect
    Arbre abstrait
    Département de Mathématiques, Informatique &
    Gestion
    Sciences Mathématiques et Informatique (SMI/S5)
    Compilation
    Prof. : M. BENADDY
    A.U:2017/2018

    1. Triplet ((x + y) – ((x + y) * (x – y))) + ((x + y) * (x - y))


    op arg1 arg2
    0 + x y
    1 - x y
    2 * 0 1
    3 - 0 2
    4 + 3 2

    2. Triplet indirect

    op arg1 arg2
    0 + x y
    1 - x y
    2 * 0 1
    3 - 0 2
    4 + 3 2

    Vous aimerez peut-être aussi