Thue (programmeringsspråk)

Thue ( / ˈ t uː eɪ / TOO -ay ) är ett esoteriskt programmeringsspråk som uppfanns av John Colagioia i början av 2000. Det är ett metaspråk som kan användas för att definiera eller känna igen typ-0-språk från Chomsky- hierarkin . Eftersom det kan definiera språk av sådan komplexitet, är det också Turing-komplett i sig. Thue bygger på ett icke-deterministiskt strängomskrivningssystem som kallas semi-Thue grammatik , som i sig är uppkallat efter den norske matematikern Axel Thue . Författaren beskriver det på följande sätt: "Thue representerar ett av de enklaste möjliga sätten att tolka begränsningsbaserad programmering . Det är för det begränsningsbaserade paradigmet vad språk som OISC är för imperativparadigmet; med andra ord, det är en tar pit . "

Produktionsregler

Ett Thue-program börjar med en regelbas, som är en serie ersättningsregler, var och en av denna form:

 lhs  ::=  rhs

Regelbasen avslutas med en ensam produktionssymbol på en rad:

::=

Det initiala tillståndet är en serie symboler som följer regelbasen.

Thue konsumerar de initiala symbolerna och ersätter resultatet av reglerna för var och en av initialtillståndets symboler.

Thue avslutas när lhs inte kan hittas i ett resulterande tillstånd.

Anteckningar

  • ::= uttalas kan vara .
  • lhs är "vänster sida".
  • rhs är "höger sida".
  • " ::= " kan aldrig vara lhs.
  • ":::" är en ingångsström.
  • "~" är utgångsströmmen.
  • Semi-Thue-system är isomorfa till obegränsad grammatik .

Ringer Thue

När den anropas med 'd' (debug), skriv ut tillståndet. När den anropas med 'l' (vänster sida), tillämpa reglerna från vänster till höger. När den anropas med 'r' (höger sida), tillämpa reglerna från höger till vänster. Det sista 'l' eller 'r' åsidosätter de tidigare omkopplarna.

Exempel på program

Här är den traditionella "Hello World!" i Thue:

a::=~Hej världen! ::= a

Följande Thue-program utför en ökning av ett binärt tal som anges som initialtillstånd omgivet av "_"-tecken, i detta fall numret 1111111111:

1_::=1++ 0_::=1 01++::=10 11++::=1++0 _0::=_ _1++::=10 __::=1 ::= _1111111111_

Följande exempelprogram är för att demonstrera Thues icke-determinism (och för att visa ett exempel på en oändlig loop, dessutom). Programmet matar ut bitar i en odefinierad (och möjligen slumpmässig) sekvens.

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

Se även

externa länkar


Hämtad från " https://en.wikipedia.org/w/index.php?title=Thue_(programming_language)&oldid=1098855164 "