Création d'un nouveau langage

Enoncé du problème :

On considére l'ensemble M des rectangles du plan dont les côtés sont paralléles à deux directions fixes et qui sont formés par juxtaposition et rotation de deux carrés primitifs.

Un tel rectangle est appelé un motif. Un motif est caractérisé par sa hauteur, sa longueur et une certaine répartition des motifs primitifs qu'il s'agit de décrire convenablement.

Les motifs primitifs sont deux carrés de côté égal à l'unité.

• Les deux carrés primitifs sont des motifs.
• Si l'on tourne un motif de (/2 on obtient un motif.
• Si on juxtapose horizontalement deux motifs de m'me hauteur on obtient un motif.
• Il n'y pas d'autres motifs que ceux que l'on peut obtenir à partir des deux carrés primitifs par un nombre fini de rotations et de juxtapositions.

Base théorique : langage et grammaire

• St est l'ensemble des symboles terminaux. Il s'agit de signes élémentaires au niveau d'abstraction choisi, à l'aide desquels sont formés les phrases du langage.
• Snt est l'ensemble des symboles non terminaux. Un symbole non terminal est un nom donné à une unité syntaxique du langage. Une unité syntaxique caractérise un ensemble de chaÓnes de symboles terminaux qui jouent le m'me rôle dans la formation des phrases du langage.
• RP est l'ensemble des régles de production. Ces régles décrivent la maniére de construire une unité syntaxique en termes des autres unités syntaxiques ou signes du langage.

Inventer un langage

Tout d'abord on définit les unité lexicales à partir desquelles sont formées les phrases du langage ; il s'agit de choisir les noms ou les symboles désignant les carrés primitifs, les opérations et les séparateurs éventuels :

• Nom des carrés primitifs :
figure-carré ou c figure-triangle ou t
• Nom des opérations
rotation-(/2 ou * juxtaposition ou #
• Séparateur : parenthéses ( et )

• Place des opérateurs (juxtaposition, rotation) par rapport aux opérandes(motifs).
• Séparateurs éventuels entre les différents constituant d'une phrase du langage. Voici des exemples de régles de syntaxe :
• Aprés le symbole *, on trouve une parenthése ouvrante, puis la description d'un motif, puis une parenthése fermante (style préfixé).
• Entre deux motifs, on trouve le symbole # (style infixé).

Enfin, on précise des contraintes sémantiques : l'opération de juxtaposition est soumise à la condition que les deux motifs aient la m'me hauteur. Ainsi la phrase *(c#c)#t, correspond pas à un motif car elle ne respecte pas la régle des hauteurs.

Selon les conventions de notations choisies, on peut introduire des ambiguÔtés sémantiques. Par exemples *c#c peut avoir deux interprétations : (*c)#c ou *(c#c)

Pour appréhender les différents niveaux de définition d'un langage, il est intéressant de voir la forme de phrases erronées selon chacun de ces aspects.

• Erreur lexicographique : c ?*(t)
• Erreur syntaxique : *(t#c ou #*(t)
• Erreur sémantique : *(t#*(t))#c

Extensions

On veut pouvoir nommer un motif. On étend le langage en conséquence et on propose une nouvelle variété de formes syntaxiques.

Cette fonction attribue à <nom clé> la possibilit&eacute; de représenter un motif non défini au départ.

Cet opérateur permet d'attribuer un motif à <nom clé>. On remarque que la syntaxe suivante est possible <nom clé A> ( <nom clé B>.

ex :
motif Fléche
motif A
A ( (***c)#(**t)
A ( *A
motif B
B ( c#(*t)
B ( *B
Fléche = *(A#B)

Spécification de la syntaxe

Le but est de supprimer les ambiguïtés liées à la syntaxe. Il faut trouver une méthode pour dériver n'importe quelle phrase en suite d'opérations simples :

On fixe d'abord les priorités par ordre décroissant pour les différents opérateurs :

• Les parenthéses (les plus intérieures sont prioritaires sur les autres).
• La rotation *
• La juxtaposition
• L'attribution

Dans le cas ou l'on se retrouve avec plusieurs parties d'une phrase avec un même niveau de priorité, c'est la partie la plus à droite qui a la priorité.