Introduction

Traduction

            texte source -> text objet (binaire translatable) -> texte machine
                         ^                                    ^
                         |                                    |
                     Traducteur                           Edition des
                                                             liens

Définitions

Un symbole x quelconque ∈ V_a est un improductif (inutile) s'il n'existe pas de dérivation de la forme suivante S =>⁺ α x Β =>^* α ρ Β
x est un symbole inaccessible s'il n'apparaît dans aucune règle de L(G).
Une grammaire est dite réduite si elle n'a pas de symbole inaccessible ou improductif.
Une grammaire est ε-libre si elle n'a pas de règle epsilon de la forme A -> ε ou alors elle contient une seule règle S -> ε avec S qui n'apparaît jamais à droite d'une règle de production.
Une grammaire est dite sans-cycle s'il n'y a pas de dérivation de la forme A =>⁺ A.
Une grammaire est sous forme normale de Chomsky si ε appartient à la grammaire du langage, { S -> ε } ∈ P avec S qui n'apparaît pas à droite des règles.

Analyse

La valeur d'un nombre est représentée par un quadruplet (M, s, x, n).

M : Mantisse
s : signe de l'exposant
x : l'exposant
n : le nombre de chiffre fractionnaire

Autres notions

Supprimer la récursivité à droite ou à gauche consiste à trouver le langage généré et trouver une grammaire équivalente qui n'est pas récursive à droite ou à gauche.

Retour arrière : défaire des morceaux de l'abre et les reconstruire.

Méthodes d'analyse

Méthode ascendante : on part du code source pour avoir l'abre de dérivation
Méthode descendante : essayer différents alternants définissant la racine pour trouver l'abre de dérivation

Ascendante : dérivation plus à droite descendante : dérivation la plus à gauche

Analyse descendante

Fonction d'analyse

fonction analyse(Notion : N) : booléen
  var : posloc, // Indice dans tab source
        trouve, // Booléen
        R,      // La règle (alternant) courant
        E;      // Le premier élément

début
  posloc <- possource; // Variable globale
  R <- premiere regle;
  trouve <- faux;

  tant que non trouve et R != Vide faire
    si Essai(R)
      trouve <- vrai;
    sinon
      R <- suivant(R)
    fin
  fin

  retourner trouve
fin

Fonction d'essai

fonction Essai(Règle R) : booléen
début
  E <- premiere élément de R
  OK <- vrai

  tant que OK et E != Vide faire
    si E est 1 notion non terminale alors
      si analyse(E) alors
        E <- suivant(E)
      sinon
        OK <- faux
      fin
    sinon si (E = source[possource])
      possource <- possource + 1;
      E <- suivant(E);
    fin
  fin

  retourner OK
fin

Programme principal

programme principal
début
  possource <- début du texte source;

  si analyse(Axiome)
    écrire("Le mot est reconnu")
  sinon
    écrire("Le mot n'est pas reconnu");
  fin
fin

Ces algorithmes n'acceptent que des grammaires récursives à gauche sous peine d'appels récursifs infinis.

Il faut une grammaire:

Epsilon libre
Sous forme normale de Greibach

Transformer une expression régulière en grammaire régulière

Pour chaque règle r, supprimer les méta-symboles qui se trouvent dans r puis :

Si r est de la forme r1r2 alors remplacer la règle A -> r par
```
A -> r1B
B -> r2
```
Si r est sous la forme r1^*r2 alors la remplacer la règle A -> r par
```
A -> r1B
A -> r2
B -> r1B
B -> r2
```
Supprimer les parenthèses par la distribution
```
a(b|c) -> ab | ac
(b|c)a -> ba | ca
```

Analyse LL(1)

LL =
- Left to right scanning
- Leftmost derivation
k = nb symboles terminaux à retenir pour effectuer choix

Une grammaire G est LL(1) si toutes ses règles sont LL(1)

-> Si une règle a un seul alternant, alors elle est LL(1)
-> A -> α₁ | α₂ | ... | α_n est LL(1) si :
1. ∀i ∀j PREMIER(α_i) ∩ PREMIER(α_j) = ∅
2. si ε ∈ PREMIER(α_i) alors ∀j != i PREMIER(αj) ∩ SUIVANT(A) = ∅

Calcul de premier

Premier L1 ⊕ L2 =

Premier(L1) si ε ∉ L1
Premier(L1 ∩ V_T) ∪ Premier(L2) sinon

Exemple :

L1 = {x, xy, yy}
L2 = {a, aa, ab}
L3 = L1 ∪ { ε }

L1 ⊕ L2 = {x, y}
L3 ⊕ L2 = {x, y, a}

Calcul de suivant

F₀(A) = $ si A = S, ∅ sinon
Pour toutes les règles de la forme B -> ... A α avec α != ε

F₁(A) = F₀(A) ∪ (PREMIER(α) ∩ V_T)

Pour toutes les règles de la forme B -> ... A α avec α = ε ou &espilon; ∈ PREMIER(α)

i <- 2;

répéter
  Fi(A) = Fi-1(A) U Fi-1(B)
jusqu'à Fi(A) = Fi-1(A)

suivant(A) = Fi(A)

Table d'analyse

        |     Vt       | $ |
       -+--------------+---+
        |              |   |
    Vn  |              |   |
        |              |   |
       -|--------------+---|
        |              |   |
    Vt  |              |   |
        |              |   |
       -|--------------+   |
     $  |                  |
       -+------------------+

T(A, a) =
- n°règle A -> β si:
- a ∈ PREMIER(β) et ε ∉ PREMIER(β)
- ou a ∈ PREMIER(β) ∪ SUIVANT(A) (ε ∈ PREMIER(β))
- Erreur sinon
T(a, b) =
- dépiler si a = b
- succès si a = b = $
- erreur sinon
T($, $) = Succès

On construit la table et ensuite, on réalise l'analyse avec un triplet de piles initialisé à :

< chaîne d'entrée $, axiome $, ε >

Analyse SRL(1)

Construire les états de l'automate :
- 1 état = ensemble d'articles
- 1 article = Règle avec un '.'
Construire les tables :
- SAUT : par la fonction transition
- ACTION : 3 règles

Pour trouver les articles, par exemple, avec la règle E -> E + T, on a :

E -> . E + T
E -> E . + T
E -> E + . T
E -> E + T .

La fermeture consiste à rajouter des articles à 1 état :

Pour une règle A -> α . B β, pout toutes les règles B -> γ, rajouter les articles B -> . γ

Pour construire les états

Il faut tout d'abord augmenter la grammaire avec un nouvel axiome E' -> E$.
Ensuite on initialise le premeir état avec E' -> . E
Ensuite :
- Fermeture tant que c'est possible
- Transition
Remarques:
- Pour une transition, on utilise tous les articles ayant le même symbole à droite du point.
- Pour la fermeture, on reprend les mêmes articles même s'ils sont dans d'autres états.
- On ne construit pas un nouvel état avec un article présent autre part.
Ensuite, création de la table SAUT à partir des transitions effectués. Si l'état 1 représente la transition entre l'état 0 et la fermeture de E, on a SAUT(0, E) = 1
Ensuite, création de la table ACTION :
1. Si on a A -> α . a Β ∈ état i et si SAUT(i, a) = j => ACTION(i, a) = sj (s = shift, i.e. décaler 1 symbole d'entrée)
2. Si on a E' -> E . ∈ état i => ACTION(i, $) = succès.
3. Si on a A -> α . ∈ état i alors pour tout a ∈ SUIVANT(A) faire ACTION(i, a) = Rk (R = Réduire, k = n° de la règle A -> α)

M1