Thue is a minimal string-rewriting language.

A Thue program consists of two parts: a list of substitution rules, which is terminated with a line having both sides of the operator empty, followed by a string representing the initial program state:

#::=Unused rules are comments
a::=~Hello Thue!
::=
[a] []

Execution consists of picking, from the list of rules, an arbitrary rule whose original string exists as a substring somewhere in the program state, and replacing that substring by the rule's replacement string. This process repeats until there are no rules that can be applied, at which point, the program ends.

#::=Increment binary number
1_::=1++
0_::=1
01++::=10
11++::=1++0
_0::=_
_1++::=10
::=
_10010011_ _10010100

I/O

Added to this system are two strings which are used to permit Thue to communicate with the outside world. The first of these is the input symbol(:::) which is actually the left-side of an implicit rule of which the user input is a component. The input symbol, therefore, is replaced by a line of text received from the "input stream."

As a counterpart of input, the output symbol(~) is supplied. Like the input symbol, the output symbol triggers an implicit rule which, in this case, encompasses the "output stream." The specific effect is that all text to the right of the output symbol in the rhs of a production is sent to the output stream.

Note that either (or both) of these implicit rules may be overridden by providing explicit rules that perform some other task.

#::=Sierpinski's triangle, backticks are linebreaks
X::=~_
Y::=~*
Z::=~`
_.::=._X
_*::=*_Y
._|::=.Z-|
*_|::=Z
..-::=.-.
**-::=*-.
*.-::=*-*
.*-::=.-*
@.-::=@_.
@*-::=@_*
::=
@_*...............................|

• On Esolangs
• Interpreter, written in Uxntal. Video
• Wanda, concatenative language meets string rewriting.