Scribd Logo
Importer

Bienvenue sur Scribd !

  • 187 vues

    TD5

    Transféré par

    Jassem

    Droits d'auteur :

    Attribution Non-Commercial (BY-NC)
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    TD5

    Transféré par

    Jassem
    187 vues4 pages

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    Attribution Non-Commercial (BY-NC)
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    187 vues4 pages

    TD5

    Transféré par

    Jassem

    Droits d'auteur :

    Attribution Non-Commercial (BY-NC)
    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 4

    Licence Informatique

    Parcours Miage-2010/2011

    Analyse Syntaxique – Cours-TD 5


    Analyse syntaxique (suite)
    Les analyseurs syntaxiques ”universels” fonctionnent pour toute grammaire algébrique :
    – algorithme de Cocke-Younger-Kasami pour des grammaires en forme normale de Chomsky
    (' Greibach) ;
    – algorithme de Earley pour des grammaires algébriques quelconques.
    Leur complexité est en o(n3 ), où n est la longueur du mot à analyser.
    – cette complexité est trop élevée (programmes de grande taille), on souhaite o(n).
    – Les langages de programmation peuvent être décrits par des grammaires en général peu
    complexes (en particulier, non-ambiguës).

    On peut réaliser une analyse syntaxique avec rebroussement :


    – une méthode descendante qui construit une dérivation gauche
    – on utilise autant que possible le mot d’entrée (dans une lecture de gauche a droite) pour
    déterminer la règle à utiliser.
    – si on ne peut pas déterminer la règle à utiliser, on fait un choix ....
    – si le choix s’avère mauvais, on “rebrousse son chemin” pour faire un autre choix.
    Exemple d’acceptation sans rebroussement avec
    G = ({a, b, c, d}, {S, T }, S, {S → aSbT | cT | d, T → aT | bS | c})

    a c c b b a d b c a c c b b a d b c
    4 4
    g
    S S →G aSbT

    a c c b b a d b c
    4
    g g g g g
    . . . →G acT bT →G accbT →G accbbS →G accbbaSbT →G accbbadbc

    Le mot est accepté.


    Exemple avec rebroussement avec G0 = ({a, b, c}, {S, A}, S, {S → aAb, A → cd | c})

    a c b a c b a c b
    4 4 4
    g g g
    S S →G0 aAb S →G0 aAb →G0 acdb
    On a choisi la règle A → cd. Il y a un conflit entre b et d. On fait un rebroussement et on
    essaye avec un autre choix, A → c.

    a c b a c b
    4 4
    g g g
    S →G0 aAb S →G0 aAb →G0 acb

    Cette méthode est peu efficace en cas de rebroussement (proche de la méthode naı̈ve).
    Analyseur prédictif descendant LL(k)
    Prédictif : on utilise une partie du mot d’entrée pour “prédire” la règle à utiliser et de façon
    irrémédiable.
    Analyse prédictive descendante : Analyse LL(k)
    – Left-to-right scanning : on lit l’entrée de gauche à droite.
    – Leftmost derivation : on construit une dérivation gauche partant de l’axiome.
    – on utilise les k lettres courantes de l’entrée pour faire la prédiction.
    On va principalement s’intéresser à l’analyse LL(1) : on ne regarde qu’une lettre de l’entrée.
    Il y a deux types d’analyse descendante : l’analyse récursive et l’analyse non-récursive.

    Analyseur récursif LL(1)


    On a une grammaire algébrique G = (Σ, V, S, P ). A toute variable Vi ∈ V , on fait correspondre
    une procédure Vi () en charge de “reconnaı̂tre” les mots w tels que Vi →∗G w.
    – les différentes procédures vont s’appeler les unes les autres selon les règles de production
    de la grammaire.
    – Le programme d’analyse est simplement un appel à la procédure de l’axiome S.
    – on place à la fin du mot à analyser un marqueur de fin $.
    – le pointeur 4 désignant une position dans le mot ne peut qu’avancer (pas de rebroussement)
    ⇒ mot d’entrée ' un flôt de lettres.
    Plus important : selon le terminal désigné dans le mot d’entrée, pour un non-terminal donné
    (partie gauche de règle), il n’y a qu’une règle de production utilisable.

    Pour la procédure Vi () :
    1. selon le terminal pointé par 4 (chaque terminal est donc un cas), on considère la règle
    de production Vi → α1 . . . αn à utiliser
    2. en séquence, pour j allant de 1 à n,
    – si αj ∈ Σ, alors on appelle consommer(αj ).
    – si αj ∈ V , on appelle la procédure αj ()
    3. si la règle à considérer est Vi → , alors on ne fait rien.
    procedure consommer(a) :
    - si 4 pointe sur le terminal a alors on avance 4
    sinon on lève exception d’erreur de syntaxe

    procedure analyse() :
    - on place le 4 sur la première lettre du mot à analyser ;
    - S() ;
    - si 4 ne pointe pas sur $ alors
    on lève une exception d’erreur de syntaxe ;

    2
    On ne peut pas construire un analyseur (récursif) LL(1) pour une grammaire G si :
    – G est ambiguë
    – G est récursive gauche
    A → Aa |  : le pointeur reste sur la première lettre du mot à analyser et on ne
    peut choisir avec cette information assurément entre A → Aa et A → .
    – G n’est pas factorisée à gauche
    A → aA | aB : si le pointeur désigne a, on ne peut choisir avec cette information
    assurément entre A → aA et A → aB.
    Récursivité à gauche
    – immédiate : la grammaire contient un non-terminal A et une règle de production A → Aα
    (α ∈ (Σ ∪ V )+ ).
    – générale : la grammaire contient un non-terminal A et il existe une dérivation A →+ G Aα
    (α ∈ (Σ ∪ V ) ).+

    Elimination de la récursivité à gauche immédiate


    On remplace les règles de la grammaire de la forme A → Aα1 | . . . | Aαn | β1 | . . . | βm où
    – αi ∈ (Σ ∪ V )+ et βj ∈ (Σ ∪ V )∗
    – les βj ne commencent pas par A
    par les règles
    A → β1 A0 | . . . | βm A0
    A0 → α 1 A0 | . . . | α n A0 | 

    où A0 est un nouveau non-terminal.


    E →E+T |T
    Exemple : T → T ∗ F | F
    F → (E) | i
    E → T E0
    E 0 → +T E 0 | 
    Après élimination de la récursivité gauche immédiate : T → F T 0
    T 0 → ∗F T 0 | 
    F → (E) | i
    Elimination de la récursivité à gauche générale
    – On ordonne les non-terminaux : A1 , A2 , . . . , An
    – On applique l’algorithme suivant :
    Pour i allant de 1 à n faire
    Pour j allant de 1 à i − 1 faire
    on remplace la règle Ai → Aj α où Aj → β1 | . . . | βk
    par la règle Ai → β1 α | . . . | βk α.
    FinPour
    On élimine la récursivité à gauche immédiate
    pour toutes les règles de Ai .
    FinPour

    3
    S → Aa | b
    Premier exemple : On ordonne : S, A
    A → Ac | Sd | c
    – 1ère itération : S → Aa | b, on ne change rien ...
    – 2ème itération : On remplace A → Sd par A → Aad | bd.

    S → Aa | b
    A → Ac | Aad | bd | c

    Elimination de la récursivité gauche immédiate pour A :

    S → Aa | b
    A → cA0 | bdA0
    A0 → cA0 | adA0 | 

    S → Sa | T Sc | d
    Deuxième exemple :
    T → T bT | 
    On ordonne : S, T
    – 1ère itération : S → Sa | T Sc | d, élimination de la récursivité immédiate pour S

    S → T ScS 0 | dS 0 T → T bT | 
    S 0 → aS 0 | 

    – 2ème itération : T → T bT | , élimination de la récursivité immédiate pour T

    S → T ScS 0 | dS 0 T → T0
    S 0 → aS 0 |  T 0 → bT T 0 | 

    Malheureusement, S →G0 T ScS 0 →G0 T 0 ScS 0 →G0 ScS 0 ! !

    ⇒ l’algorithme ne fonctionne pas toujours, notamment à cause des règles de la forme X → ,


    ou plus généralement si X →∗G . Cependant, si la grammaire est propre, alors cette méthode
    pour ôter le récursivité gauche fonctionne toujours.
    Factorisation à gauche d’une grammaire
    – On remplace les règles de la forme

    X → αβ1 | . . . | αβn | γ1 | . . . | γm

    où
    – α ∈ (Σ ∪ V )+ et βi , γj ∈ (Σ ∪ V )∗ ,
    – le préfixe commun α est choisi le plus grand possible,
    – α n’est pas préfixe des γj .
    par les règles
    X → αX 0 | γ1 | . . . | γm
    X 0 → β1 | . . . | βn
    où X 0 est un nouveau non-terminal.
    – On réitère tant que nécessaire.

    Vous aimerez peut-être aussi