Scribd Logo
Importer

Bienvenue sur Scribd !

  • 10 vues

    TP 05

    Transféré par

    ayoub02boussaid

    Droits d'auteur :

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

    TP 05

    Transféré par

    ayoub02boussaid
    10 vues2 pages

    Titre original

    tp05

    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
    10 vues2 pages

    TP 05

    Transféré par

    ayoub02boussaid

    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 2

    UFR d’Informatique Grammaires et analyse syntaxique

    L3 Informatique, Math-Info et Japonais-Info Année 2023-2024

    TD n○5
    LL(1), le retour

    Exercice 1 On considère la grammaire suivante :


    Z → S$
    S → D ∣ XA ∣ X ∣ ϵ
    X → bX ∣ Y V W V
    Y → aX ∣ ϵ
    W →c∣d
    V →v∣ϵ
    D → DE
    E → e ∣ Ee
    F →f
    On considère deux méthodes pour réduire la grammaire :
    1. On détermine les non-terminaux non-productifs. On les enlève de la grammaire. On dé-
    termine les non-terminaux non-accessibles de la grammaire ainsi obtenue et on les enlève.
    2. On détermine les non-terminaux non-accessibles. On les enlève de la grammaire. On dé-
    termine les non-terminaux non-productifs de la grammaire ainsi obtenue et on les enlève.
    — Appliquer les deux méthodes.
    — Avec laquelle des deux méthodes on obtient une grammaire réduite ?
    — Réduire la grammaire.
    — Calculer l’ensemble de non-terminaux annulables EPS.
    — Calculer l’ensemble FIRST1 de chaque non-terminal.
    — Calculer l’ensemble FOLLOW1 de chaque non-terminal.
    — Est-ce que la grammaire est LL(1) ?

    Exercice 2 Soit la grammaire suivante, définie sur le vocabulaire terminal {[, ], i, +, −, $} :


    Z → S$
    S → OE
    O→[
    E → iK
    K → −E ∣ +E ∣ ]
    1. Faire la table d’analyse (c’est-à-dire un tableau avec les non-terminaux en ordonnée et les
    terminaux en abscisse), qui indique à chaque fois quelle règle on est censé appliquer.
    2. Récupérer les fichiers parser.ml, reader.ml, tree.ml, etc. fournis. La compilation se
    fait avec
    dune build main.exe
    on peut faire des tests en exécutant
    _build/default/main.exe < test.txt

    1
    où le fichier test.txt contient un mot à tester. Attention, il ne faut pas mettre d’espace
    ni de saut de ligne dans le fichier donné en entrée.
    3. Compléter le fichier parser.ml afin de faire une analyse LL(1) de la grammaire LL(1)
    correspondante au langage ci-dessus. Le symbole $ correspond à EOF.

    Exercice 3 On souhaite construire des analyseurs grammaticaux, en commençant par le lan-


    gage L1 des expressions arithmétiques (avec − et +) bien parenthésées engendré par la grammaire

    S → n ∣ (S) ∣ S + S ∣ S − S

    Le symbole “n” correspondra, dans la partie programmée, à des entiers sans signe “+” ni “−”.
    Récupérer les fichiers fournis. On fournit ici un lexer, qui servira à lire des entiers et autres
    mots-clés.
    1. Donner une grammaire LL(1) avec axiome Z pour le langage L1 .
    Compléter le parser.ml pour qu’il fasse l’analyse.
    2. On définit L2 à partir de L1 en ajoutant la possibilité de faire des opérations avec des noms
    de variables, que l’on représente par un nouveau terminal “n”. Il faudra aussi modifier les
    autres fichiers : token.ml, tree.ml, . . .
    3. On définit le langage L3 des expressions "let v = a1 and v = a2 ... and v = ak in b" avec
    les ai dans L1 , et b dans L2 .

    Vous aimerez peut-être aussi