- 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é semi-Thue grammar, dont le nom est lui-même tiré du nom du mathématicien norvégien Axel Thue. L'inspiration vient également de grue.
Sommaire
Règles de Production
Un programme Thue commence par des règles de substitution de la forme lhs ::= rhs
Des règles successives peuvent être ajoutées. L'ensemble des règles de base termine par une ligne contenant une règle vide. L'état initial est une série de symboles spécifiée à la fin du programme après l'ensemble des règles de substitution.
Thue consomme les symboles initiaux et substitue les résultats des règles pour chacun des symboles de l'état initial.
Thue termine quand lhs ne peut plus être substitué à l'aide des règles.
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
Wikimedia Foundation. 2010.
