148 lines
4.2 KiB
PHP
148 lines
4.2 KiB
PHP
<?php
|
|
|
|
function markov($text, $ruleset) {
|
|
$lines = explode(PHP_EOL, $ruleset);
|
|
$rules = array();
|
|
foreach ($lines AS $line) {
|
|
$spc = "[\t ]+";
|
|
if (empty($line) OR preg_match('/^#/', $line)) {
|
|
continue;
|
|
} elseif (preg_match('/^(.+)' . $spc . '->' . $spc . '(\.?)(.*)$/', $line, $matches)) {
|
|
list($dummy, $pattern, $terminating, $replacement) = $matches;
|
|
$rules[] = array(
|
|
'pattern' => trim($pattern),
|
|
'terminating' => ($terminating === '.'),
|
|
'replacement' => trim($replacement),
|
|
);
|
|
}
|
|
}
|
|
do {
|
|
$found = false;
|
|
foreach ($rules AS $rule) {
|
|
if (strpos($text, $rule['pattern']) !== FALSE) {
|
|
$text = str_replace($rule['pattern'], $rule['replacement'], $text);
|
|
if ($rule['terminating']) {
|
|
return $text;
|
|
}
|
|
$found = true;
|
|
break;
|
|
}
|
|
}
|
|
} while($found);
|
|
return $text;
|
|
}
|
|
|
|
$conf = array(
|
|
1 => array(
|
|
'text' => 'I bought a B of As from T S.',
|
|
'rule' => '
|
|
# 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
|
|
',
|
|
),
|
|
2 => array(
|
|
'text' => 'I bought a B of As from T S.',
|
|
'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
|
|
',
|
|
),
|
|
3 => array(
|
|
'text' => 'I bought a B of As W my Bgage from T S.',
|
|
'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
|
|
',
|
|
),
|
|
4 => array(
|
|
'text' => '_1111*11111_',
|
|
'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
|
|
_+_ ->
|
|
',
|
|
),
|
|
5 => array(
|
|
'text' => '000000A000000',
|
|
'rule' => '
|
|
# 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
|
|
',
|
|
),
|
|
6 => array(
|
|
'text' => '101',
|
|
'rule' => '
|
|
# Another example extracted from Wikipedia:
|
|
# http://en.wikipedia.org/wiki/Markov_Algorithm
|
|
1 -> 0|
|
|
|0 -> 0||
|
|
0 ->
|
|
',
|
|
),
|
|
);
|
|
|
|
foreach ($conf AS $id => $rule) {
|
|
echo 'Ruleset ', $id, ' : ', markov($rule['text'], $rule['rule']), PHP_EOL;
|
|
}
|