#358 Patch to vastly decrease number of FSG states and null transitions

[Steven J. Boswell II]

The enclosed patch improves sphinxbase's jsgf_build_fsg_internal() so that as few FSG states and null-transitions are created as possible.

Tested against a grammar I'm working on, it went from creating 11377 FSG states and 67180 null-transitions during transitive-closure...to 781 FSG states and only 30 null-transitions during transitive-closure.

My testing seems to indicate that my code works, but of course I'd rather that the experts take a look at it too.

[Nickolay V. Shmyrev]

Hello Steve

Thanks, initially it looks great, it is really the patch we need. However, an issues again with coding style and algorithm. Consider this grammar from the tests:

~~~~~~~

JSGF V1.0;

grammar test;

public = computer <caction> please;</caction>

<caction> = go* | stop+;
~~~~~~~~~~</caction>

It worked before but it doesn't work with your patch.

As for coding style, remember about braces. Another thing is that usually typedefs are used for structs:

typedef struct_s struct_t;
struct struct_s {
};

and in code struct is used with *

I'm terribly sorry that it didnt work properly I was about to commit the patch but I decided to study the tests created by make check and found the issue. I feel this problem couldn't be solved easily, probably we need to create full FSG first and than run some minimization algorithm.

[Nickolay V. Shmyrev]

Attaching a slightly fixed patch I created

[Nickolay V. Shmyrev]

Or probably we need a special handler for +.

[Steven J. Boswell II]

Attached is a modified version of your patch that appears to fix the problem.
It's still not going to pass the jsgf2fsg regression tests, because compare_table.pl doesn't determine if two FSGs are actually equal, but if you look at the generated FSGs, you'll see that they're correct now.

The changes are (1) return a valid state, either the exit-state or entry-state, when right-recursion is detected, instead of -1, which is interpreted as an error, and (2) if all of a rule's alternates have been processed without creating an exit-state, that means the rule could match nothing, so create an exit-state and then a null-transition between the entry-state and exit-state.

[Steven J. Boswell II]

Argh, one more try...I found a problem reproduced by:

<rule1> = do <rule2>;
<rule2> = something [optional];

With the previous patch, the "optional" part was getting messed up & wasn't optional any more.

[Steven J. Boswell II]

No bug fixes this time, just some cleanups.

1) Several tests that checked for FSG states < 0 now check for == -1, mostly for the benefit of #2.
2) expand_rhs() now returns -2 if right-recursion ended the rule, instead of returning a weird combo of exit-state and entry-state. That means any code that wants to check for an error must compare the return value to -1, instead of comparing < 0.
3) If expand_rule() ends without creating an exit-state, the entry-state becomes the exit-state, i.e. no null-transition is added.

There are still two cases where null-transitions can be added, i.e. a rule consisting solely of the "<null>" atom, and to implement right-recursion. I can't get rid of either of these cases, because in both cases, the atom has a weight, and eliminating it will lead to a set of weights in a rule that don't add up to 1. I think this is still fixable, but it'll require a different way to calculate atom-weights, i.e. one that operates on FSG nodes instead of JSGF rules.</null>

[Nickolay V. Shmyrev]

This looks good, applied.

Thanks a lot, much better now.

[Nickolay V. Shmyrev]

And, btw, the weights are broken anyway. It's not correct to assign weight based on number of variants, I actually prefer to assign full weight to every path by default and only assign weights only if they are explicitely specified in JSGF. I'm sure that will better match with user's intuition.

[Steven J. Boswell II]

Actually, I thought of one more issue. In jsgf_build_fsg_internal(), after calling expand_rule(), if an exit-state hasn't been created, then create one. Lots of code relies on the fact that the entry-state and exit-state for the top-level rule are different.

[Nickolay V. Shmyrev]

I applied that bit too, thank you.