Turn automata into grammars

[xurxodiz]

There are a lot of states that are basically the same. Couldn't we convert the automata into context-free grammars and thus reduce the number of states and overall make the system easier to manage?

[xurxodiz]

For future reference: http://www.parse2.com/manual-java.shtml

[xurxodiz]

To clarify: we would define automata as grammars. So we'd need to make a BNF grammar to describe and parse grammars.

[xurxodiz]

Alright, let me clarify. We need a grammar to read automata files. These automata files will be written in BNF-like fashion.

The confusion comes from calling the automata-describing files "grammars". Let's call them "schematics".

So we need a BNF grammar from which to construct a parser, that will read the schematics and output a Java object of the class Automaton.

And, incidentally, the schematics are written in pseudo-BNF form. Yeah, that's it.

[xurxodiz]

Furthermore, this is what came out of my recent brainstorm in the whiteboard (my best ally in the whole wide world):

Sample of a schematic:

Aut = SL, 1
L = PL, 0.2
      | GL, 0.3
      | CL, 0.3
      | EL, 0.2
P = p, 0.5
      | ph, 0.5
G = g, 0.7
      | st g sv, 0.3
C = c, 0.2
      | cC, 0.8
E = X, 0.7
      | B, 0.3
X = m, 0.2
      | mX, 0.8
B = b, 0.2
      | bB, 0.8

Ok, then how would we parse these rules? Let's say we have A -> bC, w (A produces b, then C, with probability w).

check if A exists in StateHashMap<String, State>
   take it if it does
   create it if it doesn't
get token b from predefinedEnum
get/create State C (as before)
store chain[b,c] with weight w in A.transitions<chain,prob>

A chain is an array of Elements. Element is an interface for both States and Tokens. They both provide a genesis method. Tokens by calling the function associated, States by picking one of their transitions, and calling genesis on the chain.

So if we happen to pick A -> bC, the genesis of A would call b.genesis and then C.genesis.

We effectively have two kind of transitions. One deterministic: in the above case, we execute b, and inexorably, then C. another probabilistic: among the transitions for A, we can pick bC or some other rule.

If would be nice, as an off-topic addendum, to have a validate() function on States after creating the automaton, making sure their transitions add up to 1.

[xurxodiz]

Grammar created as a restricted subset of aBNF, RFC 5234 .

Notable changes: change of / for | (I like it better, visually -- blame OCaml/Haskell), no groups, no loop, no options. I mean, we are trying to do a Markov chain of order one. So forbidding those constructs forces you to rephrase what you're trying to do into using new states for that. Which maintains that beautiful order one.

Also, again for visuals, non-terminals or nodes are ALLCAPS, while terminals or leaves are smallcaps.

[xurxodiz]

Reminder to clarify on the paper that the grammar is context-free and its unrollment follows leftmost derivation.

It's like a tree with infinite branches from root, being traversed by depth-first.

[xurxodiz]

Ok, let's do something. This has gone too far away from original purpose.

We'll close this issue and leave it as "design a grammar for the schematics of the automata".

I will open a new one for "reading schematics into automata".

[xurxodiz]

Continued in #45.