1. Voici les classes utiles.
   1. La pyramide sera représentée par un tableau des lignes de décorations, une ligne sera un tableau de décoration de la longueur appropriée, les décorations seront des ensembles de symboles (classe SymbolSet, les symboles sont des caractères). La déclaration de la pyramide sera donc

      SymbolSet [] [] m ; // Tableau de tableaux d'ensembles de symboles

      Pour éviter de nous fatiguer trop, définissons la classe SymbolSet comme des listes de caractères sans répétitions, l'ensemble vide étant représenté par null.

      class SymbolSet { char val ; SymbolSet next ; // test d'appartenance static boolean mem(char c, SymbolSet e) // ajouter un élément static SymbolSet add(char c, SymbolSet e) // union des ensembles static SymbolSet union(SymbolSet e1, SymbolSet e2) }

      Les champs val et next sont exposés pour nous permettre d'itérer facilement sur les ensembles.
      
      
   2. Lors de la construction de la pyramide, nous avons en fait besoin de retrouver les ensembles de non-terminaux correspondant à un membre droit donné, ces membres droits sont de deux sortes possibles : un simple symbole (qui est toujours terminal) ou une paire de symboles (qui sont toujours non-terminaux). En faisant fi de la distinction entre terminaux et non-terminaux, nous avons donc besoin d'une classe Pair des paires de symboles.

      class Pair { char fst, snd ; Pair (char c1, char c2) { fst = c1 ; snd = c2 ; } }

      La classe Chomsky proposera trois méthodes, deux méthodes pour retrouver tous les non-terminaux définis par un membre droit donné, et une méthode qui donne le symbole de départ.

      class Chomsky { SymbolSet getLhs(char t) SymbolSet getLhs(Pair p) char getStartSymbol() ; }

   
   
   
2. Bon nous voilà prêts. Commençons par traiter le cas de l'entrée vide et par déclarer notre pyramide.

   static boolean parse(Chomsky g, String alpha) { int len = s.length() ; if (len == 0) return false ; SymbolSet [] [] m = new SymbolSet [len+1] [];

   L'initialisation de m est une initialisation de tableau, dont les éléments sont des tableaux (valant ici initialement null). On notera que le tableau m comprend ℓ+1 éléments, ainsi m[j][i] sera m_j,i. La ligne d'indice zéro ne sera pas employée.
   
   Remplissons la base, qui est la ligne d'indice 1.

   SymbolSet [] m1 = new SymbolSet[len] ; for (int i = 0 ; i < len ; i++) { m0[i] = g.getLhs(alpha.charAt(i)) ; } m[1] = m1 ;

   C'est tout à fait facile, puisque la majeure partie du travail (regrouper les productions de membre droit identique) est faite par la méthode getLhs de la classe Chomsky.
   
   Enfin construisons les lignes de la base vers de sommet.

   for (int j = 2 ; j <= len ; j++) { // Pour toutes les longueurs j SymbolSet [] row = new SymbolSet [len-j+1] ; for (int i = 0 ; i <= len-j ; i++) { // Pour tous les indices i de sous-chaînes de longueur j SymbolSet set = null ; for (int k = 1 ; k < j ; k++) { // Pour tous les découpages de [i..i+j[ en [i..i+k[ et ... for (SymbolSet p = m[k][i] ; // [i..i+k[ p != null ; p = p.next) { for(SymbolSet q = m[j-k][i+k] ; //[i+k..i+k+k'[, k+k' = j q != null ; q = q.next) { set = SymbolSet.union(g.getLhs(new Pair(p.val, q.val)), set) ; } } } row[i] = set ; } m[j] = row ; }

   Ce n'est pas si difficile que ça en a l'air. Une fois fixée une décomposition en deux de la sous-chaîne α[i…i+j[ dont la première composante est de longueur k (avec 1 ≤ k ≤ j−1) on obtient les deux ensembles E = m_k,i et E' = m_{k', i+k} (avec k+k' = j). Il faut ensuite considérer toutes les paires (A,A') (avec A ∈ E et A' ∈ E') et accumuler les membres droits des productions de la forme B → A A'. D'où les cinq boucles imbriquées...
   
   Et on peut enfin savoir si α dérive du symbole de départ de g.

   return SymbolSet.mem(g.getStartSymbol(),m[len][0]) ; }

   
   
   
3. Les clefs des tables de hachage seront donc des charactères (classe Character) et nos paires (classe Pair).

   class Pair { char fst, snd ; Pair (char c1, char c2) { fst = c1 ; snd = c2 ; } public boolean equals(Object o) { if (o == null) return false ; try { Pair p = (Pair)o ; return fst == p.fst && snd == p.snd ; } catch (ClassCastException e) { return false ; } } public int hashCode() { int f = fst ; int s = snd ; int h = (f << 16) | s ; return h ; } public String toString() { return "(" + fst + "," + snd + ")" ; } }

   On remarque que equals doit traiter le cas où l'objet o n'est pas une paire, car nous avons deux classes de clefs différentes pour une même table. La méthode hashCode est naïve et exploite que les caractères sont des entiers sur 16 bits (tandis que les int sont sur 32 bits).
   
   Et voici la classe Chomsky.

   import java.util.* ; class Chomsky { private char start ; private Hashtable t_lhs ; char getStartSymbol() { return start ; } static private void error(String msg) { System.err.println("Chomsky: " + msg) ; System.exit(2) ; } private void add(Object key, char c) { SymbolSet p = (SymbolSet)(t_lhs.get(key)) ; t_lhs.put(key, SymbolSet.add (c, p)) ; } Chomsky(char c, Rules rs) { start = c ; t_lhs = new Hashtable () ; for (Rules p = rs ; p != null ; p = p.next) { char lhs = p.lhs ; List rhs = p.rhs ; if (rhs == null) error("règle vide") ; if (rhs.next == null) { add(new Character(rhs.val), lhs) ; } else if (rhs.next.next == null) { add(new Pair(rhs.val, rhs.next.val), lhs) ; } else error("règle trop longue") ; } } SymbolSet getLhs(Pair p) { return (SymbolSet)t_lhs.get(p) ; } SymbolSet getLhs(char t) { return (SymbolSet)t_lhs.get(new Character(t)) ; } }