Une grammaire décrit récursivement un ensemble d’objets. Elle est constituée d’un ensemble de règles ayant chacune un nom (chaîne de caractères). Le nom d’une règle est appelé symbole non-terminal ou plus simplement non-terminal de la grammaire.
Une règle de grammaire décrit un ensemble qui est
La taille ou poids d’un objet est le nombre d’atomes qu’il
contient. Le poids d’un élément correspondant à une paire est
donc la somme des poids de
et de
.
À chaque non-terminal on associe la taille du plus petit objet qui en dérive. Cette taille est appelé valuation du non-terminal.
On modélise chacun de ces ensembles décrits récursivement par un objet (au sens de la programmation orientées objets) Sage. Dans l’exemple des arbres binaires, l’objet treeGram["Tree"] modélise l’ensemble de tous les arbres binaires. Cet ensemble est construit comme l’union de deux sous ensembles modélisés par les objets treeGram["Node"] et treeGram["Leaf"]. La classe de treeGram["Tree"] est ainsi UnionRule, il est construit grâce à un appel au constructeur par UnionRule("Node", "Leaf").
Une grammaire sera stockées sous la forme d’un dictionnaire qui associe à une chaîne de caractère un objet. Dans le but de ne pas recopier plusieurs fois du code, on utilisera avantageusement la programmation objet et l’héritage. Ainsi chaque règle de grammaire sera un objet de la classe abstraite AbstractRule. On distingue deux types de règles de grammaires:
Voici un schéma de la hiérarchie de classe:
Voici la liste des constructeurs (méthodes __init__) des différentes classes avec les paramètres et leurs types:
En plus des méthodes listées dans ce diagramme, chaque classe devra implanter (ou bien hériter) les méthodes d’énumération suivantes: count, count_naive, list, unrank, random,dots
Le principal problème d’implantation provient du fait qu’une grammaire est un ensemble de définitions mutuellement récursives. Il y a donc un travail à faire pour «~casser des boucles infinies~» et s’assurer que la récursion est bien fondée. Voici quelques éléments permettant de résoudre ce problème: