Division par deux, Chomsky
Cette feuille en Postscript

1  Forme normale de Chomsky

Selon le cours, une grammaire est en forme normale de Chomsky lorsque toutes ses productions sont de l'une des trois formes suivantes.
A → a,    A → BC,    S → є
Où les majuscules désignent des non-terminaux, les minuscules des terminaux et S est le symbole de départ. Dans tous les exercices on ne considère que des grammaires qui n'engendrent pas le mot vide, c'est à dire que l'on se passe de la troisième sorte de production ci-dessus.
  1. On considère la grammaire ambiguë des expressions arithmétiques.
    S → E         E → i          E → E + E          E → E * E
    Identifier les règles qui font que cette grammaire n'est pas en forme normale de Chomsky.

  2. Mettre la grammaire en forme normale de Chomsky. On procédera à trois transformations successives des productions.
    1. Éliminer les productions de la forme A → … a ….
    2. Éliminer les productions de la forme A → BCD….
    3. Éliminer les productions de la forme A → B.


  3. On représente les grammaires par les objets de la classe Rules suivante.
    class Rules { char lhs ; List rhs ; Rules next ; Rules (char c, List s, Rules r) { lhs = c ; rhs = s ; next = r ; } }
    Tandis que les membres droits sont représentés par des objets de la classe
    class List { char val ; List next; List (char c, List r) { val = c ; next = r ; } }
    Écrire une méthode static boolean isCNF(Rules rs) qui vérifie qu'une grammaire est en forme normale de Chomsky. On adopte la convention que les non-terminaux sont les lettres majuscules (identifiées par Character.isUpperCase(char c)) et les terminaux les autres caractères qui ne sont pas des espaces (identifiés par Character.isSpaceChar(char c)).
Solution.


2  Analyse avec une pyramide

Soit un mot de terminaux, représenté comme une chaîne α[0…0+ℓ[ (ℓ est la longueur de α). Plus généralement on note α[i…i+j[ la sous-chaîne de α de longueur j et commençant à l'indice i. On peut représenter une analyse de α à l'aide d'une pyramide, chaque étage de la pyramide correspondant à des sous-chaînes d'une longueur donnée, le sommet correspondant à la longueur ℓ et la base à la longueur 1. Par exemple voici une analyse de a(a)a, dans la grammaire suivante qui est une forme normale de Chomsky de la grammaire des suites de « a » bien parenthésées.
E → E E          E → O E'          E' → E F          E → a          O → (          F → )
  1. Dessiner une pyramide reflétant une autre analyse de a(a)a. On remarque que la pyramide n'est pas autre chose qu'un arbre de dérivation.

  2. Systématiser le procédé en dessinant une pyramide reflétant toutes les analyses possibles de i+i*i dans la grammaire de Chomsky des expressions arithmétiques. On procédera par décoration des sommets de la pyramide « complète » suivante.
    Le i-ème sommet de la j-ème ligne est à décorer par l'ensemble des non-terminaux dont α[i…i+j[ peut dériver. Donner la condition qui prouve que α est bien un mot du langage de la grammaire.

  3. Pour toute grammaire de Chomsky (qui n'engendre pas le mot vide) et tout mot non-vide α, donner le procédé général de décoration de la pyramide, en distinguant la base des autres sommets. On note mj,i la décoration portée par le i+1-ième sommet de la j-ème ligne de la pyramide.
Solution.


3  Programmation de l'analyse

  1. Commencer par identifier les structures de données dont nous allons avoir besoin.
    1. Pour la pyramide elle-même et ses décorations.
    2. Pour les grammaires supposées en forme normale de Chomsky.
    Il n'est pas demandé d'écrire le code des méthodes, seulement de les spécifier. La démarche consiste surtout à définir les classes dont on aura besoin, les spécifications des méthodes peuvent être complétées plus tard.

  2. Programmer la méthode d'analyse
    static boolean parse(Chomsky g, String alpha) ;
    On commencera évidemment pas remplir la base de la pyramide, puis on procédera du bas vers le haut, jusqu'à calculer mℓ,0.

  3. Programmer la classe Chomsky. Cette classe offre un constructeur.
    Chomsky(char start, Rules rs)
    Où start est le symbole de départ et rs sont les productions de la grammaire comme à l'exercice 1. On supposera que toutes les productions sont conformes et on utilisera la classe Hashtable de la librairie de Java. En effet on va construire une fois pour toute une association des membres droits de production vers les membres gauches correspondants.

    Les tables de hachage sont des structures de données qui se comportent en gros comme des tableaux d'objets, mais dont les indices sont n'importe quels objets. On utilisera principalement deux méthodes (des objets de la classe Hashtable) :
    // Renvoie l'objet associé à key, ou null si il n'y en a pas Object get(Object key) // Associe o à key, l'ancien objet associé à key est renvoyé Object put(Object key, Object o)
    L'idée est bien évidemment d'associer des ensembles de membres gauches aux membres droits.

    Les tables de hachage de Java demande de (re-)définir les méthodes equals et hashCode des clefs (à moins de prendre les clefs dans une classe standard, comme String).
    // Égalité de this et de o public boolean equals(Object o) // Renvoie un entier, deux objets égaux doivent renvoyer le même entier public int hashCode()
Solution.


4  Bonus : mise en forme normale de Chomsky

Un document joint trouvé sur le Web donne une procédure générale de mise en forme normale de Chomsky. Nous allons nous intéresser à une étape en particulier : l'élimination des production vides A → є.

On procède en deux temps, il faut d'abord identifier les non-terminaux nullables, c'est-à-dire ceux dont on peut dériver le mot vide.

On montre facilement qu'un non-terminal A est nullable si et seulement si : Nous pouvons définir un opérateur N sur les ensembles de non-terminaux :
N(S) = U ∪ { A, A → α, avec  α ∈ S* }
On construit ensuite la suite Ni d'ensembles de non-terminaux :
N0 = ∅ ,    Ni+1 = N(Ni)
  1. Montrer que la suite (Ni) converge vers l'ensemble des nullables.

  2. On suppose donnée une classe Symbols des ensembles (de symboles) codée selon un style impératif :
    class Symbols { // Constructeur de l'ensemble vide Symbols () // Test d'appartenance boolean mem(char c) // Ajout d'un élément, renvoie true si this est modifié (ie, this ne // contenait pas déjà c) boolean add (char c) }
    Coder la méthode :
    static Symbols getNullables(Rules rs)
    Qui renvoie les nullables de la grammaire passée en argument.

  3. Il s'agit maintenant de transformer la grammaire en une grammaire équivalente sans non-terminaux nullables. Le procédé est le suivant. Coder la méthode :
    static Rules removeEmpty(Rules rs)
    Qui transforme la grammaire passée en argument en une grammaire équivalente, sans non-terminaux nullables.
Solution.


Ce document a été traduit de LATEX par HEVEA