1. La suite (N_i) est croissante au sens large (pour ⊆) et bornée (par l'ensemble de tous les non-terminaux). Elle converge donc et sa limite est l'ensemble des non-terminaux nullables, selon l'introduction.
   
   
2. C'est un classique calcul par point fixe, on itère N jusqu'à stabilisation. Le booléen renvoyé par la méthode add des des objets de la classe Symbols aide un peu.

   static boolean isNullable(List rhs, Symbols nullable) { for (List q = rhs ; q != null ; q = q.next) { if (!nullable.mem(q.val)) return false ; } return true ; } static Symbols getNullables(Rules rs) { Symbols r = new Symbols() ; boolean changed = true ; while (changed) { changed = false ; for (Rules p = rs ; p != null ; p = p.next) { if (isNullable(p.rhs, r)) { changed = r.add(p.lhs) || changed ; } } } return r ; }

   
   
   
3. C'est techniquement assez casse-pieds. Le plus simple me semble d'abord d'expanser les membres droits contenant des nullables, puis d'effectuer une passe de nettoyage pour enlever toutes les productions vides.

   static Rules removeEmpty(Rules rs) { Symbols nullables = getNullables(rs) ; Rules r = null ; for (Rules p = rs ; p != null ; p = p.next) { r = expandNullables(p.lhs, nullables, p.rhs, r) ; } Rules rr = null ; for (Rules p = r ; p != null ; p = p.next) { if (p.rhs != null) rr = new Rules (p.lhs, p.rhs, rr) ; } return rr ; }

   On peut noter que la suppression des productions vides (dernière boucle) inverse la liste r, cela n'a pas d'importance ici.
   
   Notons aussi que, par hypothèse, puisque le mot vide n'est pas engendré, le symbole de départ S n'est pas nullable. Si tel était le cas, on pourrait ajouter une production S → є tout à la fin.
   
   Et voici expandNullable, qui expanse les membres droits.

   static Rules expandNullables(char lhs, Symbols nullables, List rhs, Rules k) { if (rhs == null) return new Rules (lhs, null, k) ; else { Rules p = expandNullables(lhs, nullables, rhs.next, k) ; Rules r ; if (nullables.mem(rhs.val)) { r = p ; } else { r = k ; } for ( ; p != k ; p = p.next) r = new Rules (lhs, new List(rhs.val, p.rhs), r) ; return r ; } }

   L'expansion est réalisée sur le principe récursif suivant.
   • Pour A → є l'expansion est A → є.
   • Sinon, pour A → Bα où B est nullable. On expanse A → α en A → α₀, ..., A → α_n et on renvoie les 2 × n productions A → Bα₀, ..., A → Bα_n, A → α₀, ..., A → α_n. Si B n'est pas nullable, (en particulier si B est terminal), on se contente de renvoyer A → Bα₀, ..., A → Bα_n.
   On peut noter la condition d'arrêt de la dernière boucle, assez subtile, elle évite une concaténation (ajouter k à la fin de toutes les listes de productions ci-dessus). Le code est en fait encore un peu plus subtil, il évide les recopie des listes A → Bα₀, ..., A → Bα_n

# java Parse g.txt

** No empty rules **
E «i»
E «+E»
E «-E»
E «(E)»
E «E%E»
E «E/E»
E «E*E»
E «E-E»
E «E+E»
S «E»
** No unit rules **
S «E+E»
S «E-E»
S «E*E»
S «E/E»
S «E%E»
S «(E)»
S «-E»
S «+E»
S «i»
E «E+E»
E «E-E»
E «E*E»
E «E/E»
E «E%E»
E «(E)»
E «-E»
E «+E»
E «i»
** No mixed rules **
E «i»
E «AE»
E «BE»
E «GEH»
E «EFE»
E «EDE»
E «ECE»
E «EBE»
E «EAE»
S «i»
S «AE»
S «BE»
S «GEH»
H «)»
G «(»
S «EFE»
F «%»
S «EDE»
D «/»
S «ECE»
C «*»
S «EBE»
B «-»
S «EAE»
A «+»
** No long rules **
A «+»
U «AE»
S «EU»
B «-»
T «BE»
S «ET»
C «*»
R «CE»
S «ER»
D «/»
Q «DE»
S «EQ»
F «%»
P «FE»
S «EP»
G «(»
H «)»
O «EH»
S «GO»
S «BE»
S «AE»
S «i»
N «AE»
E «EN»
M «BE»
E «EM»
L «CE»
E «EL»
K «DE»
E «EK»
J «FE»
E «EJ»
I «EH»
E «GI»
E «BE»
E «AE»
E «i»

i----i
 «ES» «B» «B» «B» «B» «ES»
 «» «» «» «» «TSME»
 «» «» «» «TSME»
 «» «» «TSME»
 «» «TSME»
 «ES»
-i+i*+i  
 «B» «ES» «A» «ES» «C» «A» «ES»
 «TSME» «» «USNE» «» «» «USNE»
 «» «ES» «» «» «RL»
 «TSME» «» «» «ES»
 «» «» «USNE»
 «» «ES»
 «TSME»