'Number' Crunching Benchmark I just want to do some benchmarking of different programming languages. So here is a tip: You can use as many characters as you want. In the end there is only the time your program needed.

So, here is the Task:

Task

After searching for a good task that would require a lot of computation, I came up with the problem Is a word in a given Type-1 grammar? 

For people not knowing what this is: Formal Grammar&nbsp;&nbsp;Chomsky-Hierarchy

Maybe there is a better algorithm but I came only up with brute forcing.

So, write a code that brute forces the Grammars as fast as possible.

Rules


Parallel execution is allowed
Delete your cache after every tested word
Add your complete compiler command for optimized result
You can use any algorithm and language you want, as long as the job gets done.
Add to your answer what files are read/how to set the files that should be read.


I Guarantee


Input is always well formatted
Variables are always capital letters, Terminals always small ones
Words only consist of Terminals
No empty Word


Input

For equal footing we need to define what the input looks like. The input is a file. I write multiple grammars and words in one file. The structure can be described with following Pseudocode:

foreach(Grammar G) do
    write('{');
    foreach (Variable V in G) do
        write(T + ',');
    od
    deleteLast();
    write('}');
    linebreak();
    write('{');
    foreach (Terminal T in G) do
        write(V + ',');
    od
    deleteLast();
    write('}');
    linebreak();
    write('{');
    foreach(Production P in G) do
        write(P + ',');
    od
    write('}');
    linebreak;
    write(StartSymbol(G));
    linebreak;
    foreach(Word W for G) do
        write(W + ',');
    od
    deleteLast();
    linebreak;
od
deleteLastLinebreak();


An Example

Output

The output has to be put in a file as well. The formatting of the output does not matter. It should be recognizable which result belongs to which word.

An Example

Example

Here is an example written in C# by myself.

Main Class

Data Classes

Test System

The system the code will run on is following:


Arch Linux
RunTime you need (if available; Please add in answer)
Intel i7-4700MQ 3.4GHz
16GB RAM


How do I test

After the code is compiled I'll run a bash script that runs your program a certain amount of times and calculates the average and median run time.

Good Luck and may the best code win.

My Benchmark: Not completed after 8-9 hours of runtime.

My Benchmark (after changing some words): 


mean: 39.5157
median: 39.448687194


PS: Here is the originally planned input, which took ages with my program. Grammars are slightly changed in the new input and words are way shorter.
As the code is rather long, it can be found here (Java 8): http://pastebin.com/Q5Buuqfx

How I did it:

Instead of brute-force creating the possible word combinations and then try to find a match I instead did the reverse and tried to collapse the target word to find the starting point. As a result the path the algorithm has to traverse is much less branched, and the words from the example can all be verified in about 35 ms (on my machine).

As a side-effect of the reverse-search I do not need the first two lines of each task (variables, terminals).

In addition I utilize the Java 8 streaming technology, which allows to easily activate parallel processing with just a single change in one line of code.

Usage: java Grammar &lt;inputFile&gt;

Edit: Did some code cleanup and further speed tests and it ironically turned out, that the algorithm is so fast, that setting up the parallel stream takes longer than the actual task. I now use a single-CPU stream() instead and the complete example input set is processed in ~35 ms on my machine instead of ~80 ms if I use parallelStream().

Edit2: Further testing reveals some strange effects with parallelStream and certain types of Collections. A TreeSet seems to work best in both single and parallel processing. I did some tests on your extended input set and it seems to work fine, except for the task with the looping rules (CD->DC,DC->CD). Detecting and removing those would cause the search to verify instantly.