Execute a Markov algorithm: Difference between revisions

{{task|Compilers and Interpreters}}

 

<ruleset> ::= ((<comment> | <rule>) <newline>+)*

<comment> ::= # {<any character>}

<rule> ::= <pattern> <whitespace> -> <whitespace> [.] <replacement>

<whitespace> ::= (<tab> | <space>) [<whitespace>]

 

 

Use the following tests on entries:

 

<pre>

# This rules file is extracted from Wikipedia:

</pre>

Sample text of:

Should generate the output:

 

A test of the terminating rule

<pre>

: <code>I bought a bag of apples from T shop.</code>

 

This tests for correct substitution order and may trap simple regexp based replacement routines if special regexp characters are not escaped.

A -> apple

WWWW -> with

T -> the

the shop -> my brother

Sample text of:

: <code>I bought a B of As W my Bgage from T S.</code>

: <code>I bought a bag of apples with my money from T shop.</code>

 

<pre>

### Unary Multiplication Engine, for testing Markov Algorithm implementations

</pre>

Sample text of:

should generate the output:

 

 

Besides demonstrating that the Markov algorithm is Turing-complete, it also made me catch a bug in the C++ implementation which wasn't caught by the first four rulesets.

</pre>

This ruleset should turn

into

 

=={{header|Ada}}==

markov.ads:

 

package Markov is

Entries : Entry_Array (1 .. Length);

end record;

 

markov.adb:

 

function Parse (S : String_Array) return Ruleset is

end Apply;

 

 

test_markov.adb:

with Ada.Text_IO.Unbounded_IO;

with Ada.Strings.Unbounded;

end;

end;

 

Output (rulesX contains the ruleset of above examples and testX the example text):

11111111111111111111

$ ./test_markov rules5 test5

00011H1111000</pre>

 

=={{header|AutoHotkey}}==

; Markov Algorithm.ahk

; by wolf_II

 

 

;---------------------------------------------------------------------------

Button1: ; http://rosettacode.org/wiki/Execute_a_Markov_algorithm#Ruleset_1

 

 

 

 

#include <stdlib.h>

#include <string.h>

 

 

} rule_t;

 

 

{

}

 

{

}

 

{

}

}

}

}

 

{

 

 

}

 

int main()

{

 

 

 

 

 

 

=={{header|C++}}==

Note: Non-use of <code>iswhite</code> is intentional, since depending on the locale, other chars besides space and tab might be detected by that function.

#include <cstdlib>

#include <iostream>

 

std::cout << output << "\n";

 

=={{header|D}}==

{{trans|Perl}}

 

 

 

string[][] capt;

}

 

if (c[1] == ".")

break;

goto REDO;

}

}

 

I bought a bag of apples from T shop.

I bought a bag of apples with my money from T shop.

11111111111111111111

00011H1111000</pre>

 

=={{header|Go}}==

 

import (

"fmt"

"strings"

)

ruleSet, sample, output string

}

 

func main() {

var failures bool

for i, tc := range testSet {

failures = true

}

fmt.Println("no failures")

}

}

 

}

 

var rules []rule

}

}

 

}

}

}

return s

 

# http://en.wikipedia.org/wiki/Markov_Algorithm

A -> apple

T -> the

the shop -> my brother

A -> apple

B -> bag

<pre>

validating 5 test cases

no failures

</pre>

 

This program expects a source file as an argument and uses the standard input and output devices for the algorithm's I/O.

 

import Data.Maybe (catMaybes)

import Control.Monad

then let new = reverse before ++ to ++ drop (length from) ahead

in if terminating then new else f rules new

 

=={{header|Icon}} and {{header|Unicon}}==

 

rules := loadRules(open(A[1],"r"))

every write(line := !&input, " -> ",apply(rules, line))

if (s == line) | \r.term then return s else line := s

}

 

Sample runs using above rule sets and test strings:

 

=={{header|J}}==

 

markovLexer =: verb define

end.

y

 

)

 

m1 markov 'I bought a B of As from T S.'

I bought a bag of apples from my brother.

'''Discussion''': The J implementation correctly processes all the rulesets. More details are available on the [[Talk:Markov Algorithm#explicit_vs_tacit|the talk page]].

 

=={{header|Perl}}==

This program expects a source file as an argument and uses the standard input and output devices for the algorithm's I/O.

 

open my $source, '<', $ARGV[0] or die "I couldn't open \"$ARGV[0]\" for reading. ($!.)\n";

my @rules;

and ($terminating ? last OUTER : redo OUTER);}}

 

 

=={{header|PicoLisp}}==

(use (@A @Z R)

(let Rules

(T (= "." (cadr (setq R @)))

(append @A (cddr R) @Z) )

Output:

<pre>: (markov "r1" "I bought a B of As from T S.")

: (markov "r5" "000000A000000")

-> "00011H1111000"</pre>

=={{header|PureBasic}}==

The GUI used here allows a ruleset to be loaded from a text file or manually added one rule at a time. Symbol input can be tested anytime by selecting 'Interpret'.

pattern.s

replacement.s

EndSelect

Until isDone

Sample output from loading Ruleset 1 and interpreting a symbol:

<pre>Comment: "# This rules file is extracted from Wikipedia:"

 

The example gains flexibility by not being tied to specific files. The functions may be imported into other programs which then can provide textual input from their sources without the need to pass 'file handles' around.

 

def extractreplacements(grammar):

== '11111111111111111111'

assert replace(text4, extractreplacements(grammar5)) \