(phixonline)-->
procedure markov(string rules, input, expected)
sequence subs = {}, reps = {}
sequence lines = split(substitute(rules,'\t',' '),'\n')
for i=1 to length(lines) do
string li = lines[i]
if length(li) and li[1]!='#' then
integer k = match(" -> ",li)
if k then
subs = append(subs,trim(li[1..k-1]))
reps = append(reps,trim(li[k+4..$]))
end if
end if
end for
string res = input
bool term = false
while 1 do
bool found = false
for i=1 to length(subs) do
string sub = subs[i]
integer k = match(sub,res)
if k then
found = true
string rep = reps[i]
if length(rep) and rep[1]='.' then
rep = rep[2..$]
term = true
end if
res[k..k+length(sub)-1] = rep
exit
end if
if term then exit end if
end for
if term or not found then exit end if
end while
?{input,res,iff(res=expected?"ok":"**ERROR**")}
end procedure
constant ruleset1 = """
# This rules file is extracted from Wikipedia:
# http://en.wikipedia.org/wiki/Markov_Algorithm
A -> apple
B -> bag
S -> shop
T -> the
the shop -> my brother
a never used -> .terminating rule"""
markov(ruleset1,"I bought a B of As from T S.","I bought a bag of apples from my brother.")
constant ruleset2 = """
# Slightly modified from the rules on Wikipedia
A -> apple
B -> bag
S -> .shop
T -> the
the shop -> my brother
a never used -> .terminating rule"""
markov(ruleset2,"I bought a B of As from T S.","I bought a bag of apples from T shop.")
constant ruleset3 = """
# BNF Syntax testing rules
A -> apple
WWWW -> with
Bgage -> ->.*
B -> bag
->.* -> money
W -> WW
S -> .shop
T -> the
the shop -> my brother
a never used -> .terminating rule"""
markov(ruleset3,"I bought a B of As W my Bgage from T S.","I bought a bag of apples with my money from T shop.")
constant ruleset4 = """
### Unary Multiplication Engine, for testing Markov Algorithm implementations
### By Donal Fellows.
# Unary addition engine
_+1 -> _1+
1+1 -> 11+
# Pass for converting from the splitting of multiplication into ordinary
# addition
1! -> !1
,! -> !+
_! -> _
# Unary multiplication by duplicating left side, right side times
1*1 -> x,@y
1x -> xX
X, -> 1,1
X1 -> 1X
_x -> _X
,x -> ,X
y1 -> 1y
y_ -> _
# Next phase of applying
1@1 -> x,@y
1@_ -> @_
,@_ -> !_
++ -> +
# Termination cleanup for addition
_1 -> 1
1+_ -> 1
_+_ ->
"""
markov(ruleset4,"_1111*11111_","11111111111111111111")
constant ruleset5 = """
# Turing machine: three-state busy beaver
#
# state A, symbol 0 => write 1, move right, new state B
A0 -> 1B
# state A, symbol 1 => write 1, move left, new state C
0A1 -> C01
1A1 -> C11
# state B, symbol 0 => write 1, move left, new state A
0B0 -> A01
1B0 -> A11
# state B, symbol 1 => write 1, move right, new state B
B1 -> 1B
# state C, symbol 0 => write 1, move left, new state B
0C0 -> B01
1C0 -> B11
# state C, symbol 1 => write 1, move left, halt
0C1 -> H01
1C1 -> H11
"""
markov(ruleset5,"000000A000000","00011H1111000")