Pour aller plus loin, on peut

1. Lors des appels récursifs, on calcule plusieurs fois la même chose. Une amélioration consiste à stocker les résultats des différents appels récursifs dans un tableau pour ne pas refaire le calcul. Pour ceci on peut utiliser les décorateurs cached_function et cached_method de Sage. C’est particulièrement utile pour les méthodes de comptage.

2. Pour avoir un programme plus facile à utiliser, on aimerait bien pouvoir donner des grammaires sous le format:

   {"Tree" :  Union (Singleton Leaf,
                     Prod(NonTerm "Tree", NonTerm "Tree", "".join)}

   Une telle grammaire est dite condensée. Une amélioration consiste à écrire une fonction qui développe automatiquement en grammaire simple une grammaire condensée.

3. Ajouter le constructeur Sequence("NonTerm", casvide, cons) aux constructeurs autorisés. Ceci peut se faire soit dans les grammaires simples, soit dans les grammaires condensées. En effet, le constructeur Sequence peut s’écrire avec Epsilon et Prod:

   "Sequence" = Union(Epsilon casvide, Prod("Sequence", "NonTerm", cons))

4. Écrire des grammaires pour engendrer des documents XML ou HTML complexe.

Bon Travail !