Thue (langage)

Thue est un langage de programmation exotique inventé par John Colagioia au début des années 2000. Il s'agit d'un méta-langage permettant la définition et la reconnaissance de langages de type 0 dans la hiérarchie de Chomsky. Thue est basé sur système de réécriture non-déterministe appelé grammaire de semi-Thue, dont le nom est lui-même tiré du nom du mathématicien norvégien Axel Thue. L'inspiration vient également du monstre grue.

Pour les articles homonymes, voir Thue.

Règles de production

Un programme Thue commence par des règles de substitution de la forme lhs ::= rhs

Des règles peuvent être ajoutées à la suite. L'ensemble des règles de base se termine par une ligne contenant une règle vide. L'état initial est une suite de symboles spécifiée à la fin du programme après l'ensemble des règles de substitution.

Thue consomme les symboles de l’état initial et substitue les résultats des règles pour chacun de ces symboles.

Thue termine quand plus aucune substitution n'est possible dans la partie gauche.

Syntaxe
  • ::= se prononce peut être.
  • lhs est « partie gauche » (left hand side).
  • rhs est « partie droite » (right hand side).
  • ::= ne peut jamais être dans la partie gauche d'une règle (lhs).
  • ::: est un flux d'entrée, substitué par ce qui a été lu.
  • ~ est un flux de sortie permettant d'afficher le texte qui le suit.

Appel à Thue

L'interpréteur peut être appelé avec différentes options :

Option 'd' (debug)
Afficher l'état.
Option 'l' (left side)
Appliquer les règles de gauche à droite (left-to-right).
Option 'r' (right side)
Appliquer les règles de droite à gauche (right-to-left).

Seule la dernière option 'l' ou 'r' est prise en compte.

Exemples de programmes

Le traditionnel « Hello World! » en Thue:

a::=~Hello World!
::=
a

Le programme suivant incrémente un nombre binaire entré comme état initial, encadré du caractère « _ », ici le nombre 1111111111:

1_::=1++
0_::=1

01++::=10
11++::=1++0

_0::=_
_1++::=10

::=

_1111111111_

Le programme suivant permet d'exposer le caractère non-déterministe du Thue. La sortie du programme est un ensemble de bits dans un ordre non défini.

b::=~0
b::=~1
ac::=abc
::=
abc

Liens externes
  • Portail de la programmation informatique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.