2024-07-13 15:19:22 -07:00
|
|
|
|
T Rule = (String pattern, String replacement, Bool terminating)
|
2023-07-01 11:58:00 -04:00
|
|
|
|
|
|
|
|
|
|
F parse(rules)
|
|
|
|
|
|
[Rule] result
|
|
|
|
|
|
L(line) rules.split("\n")
|
|
|
|
|
|
I line.starts_with(‘#’)
|
|
|
|
|
|
L.continue
|
|
|
|
|
|
I line.trim(‘ ’).empty
|
|
|
|
|
|
L.continue
|
|
|
|
|
|
|
|
|
|
|
|
V (pat, rep) = line.split(‘ -> ’)
|
|
|
|
|
|
|
|
|
|
|
|
V terminating = 0B
|
|
|
|
|
|
I rep.starts_with(‘.’)
|
|
|
|
|
|
rep = rep[1..]
|
|
|
|
|
|
terminating = 1B
|
|
|
|
|
|
|
|
|
|
|
|
result.append(Rule(pat, rep, terminating))
|
|
|
|
|
|
R result
|
|
|
|
|
|
|
|
|
|
|
|
F apply(text, rules)
|
|
|
|
|
|
V result = text
|
|
|
|
|
|
V changed = 1B
|
|
|
|
|
|
|
|
|
|
|
|
L changed == 1B
|
|
|
|
|
|
changed = 0B
|
|
|
|
|
|
L(rule) rules
|
|
|
|
|
|
I rule.pattern C result
|
|
|
|
|
|
result = result.replace(rule.pattern, rule.replacement)
|
|
|
|
|
|
I rule.terminating
|
|
|
|
|
|
R result
|
|
|
|
|
|
changed = 1B
|
|
|
|
|
|
L.break
|
|
|
|
|
|
|
|
|
|
|
|
R result
|
|
|
|
|
|
|
|
|
|
|
|
V SampleTexts = [‘I bought a B of As from T S.’,
|
|
|
|
|
|
‘I bought a B of As from T S.’,
|
|
|
|
|
|
‘I bought a B of As W my Bgage from T S.’,
|
|
|
|
|
|
‘_1111*11111_’,
|
|
|
|
|
|
‘000000A000000’]
|
|
|
|
|
|
|
|
|
|
|
|
V RuleSets = [
|
|
|
|
|
|
‘# 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’,
|
|
|
|
|
|
|
|
|
|
|
|
‘# Slightly modified from the rules on Wikipedia
|
|
|
|
|
|
A -> apple
|
|
|
|
|
|
B -> bag
|
|
|
|
|
|
S -> .shop
|
|
|
|
|
|
T -> the
|
|
|
|
|
|
the shop -> my brother
|
|
|
|
|
|
a never used -> .terminating rule’,
|
|
|
|
|
|
|
|
|
|
|
|
‘# 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’,
|
|
|
|
|
|
|
|
|
|
|
|
‘### 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
|
|
|
|
|
|
_+_ -> ’,
|
|
|
|
|
|
|
|
|
|
|
|
‘# 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’]
|
|
|
|
|
|
|
|
|
|
|
|
L(ruleset) RuleSets
|
|
|
|
|
|
V rules = parse(ruleset)
|
|
|
|
|
|
print(apply(SampleTexts[L.index], rules))
|
