Left or right recursion?

julius-speech / julius

Open-Source Large Vocabulary Continuous Speech Recognition Engine

BSD 3-Clause "New" or "Revised" License

1.84k stars 300 forks source link

Left or right recursion? #140

Open OddLingo opened 4 years ago

OddLingo commented 4 years ago

The Julius documentation has always said that only left recursion can be used in grammars and I have always used it that way.. Yet now when I submit a grammar like this:

S: NS_B NOUNP NS_E
NOUNP: NOUNP NOUN
NOUNP: NOUN

I get a message from mkdfa.pl saying "Error: Left recusion is formed in class,"NOUNP"

If I reverse the terms in the definition of NOUNP as follows:

S: NS_B NOUNP NS_E
NOUNP: NOUN NOUNP
NOUNP: NOUN

Then it completes without error, yielding this dfa file:

0 1 1 0 0
1 2 2 0 0
2 0 3 0 0
2 2 2 0 0
3 -1 -1 1 0

Is there new guidance on writing grammar files?

OddLingo commented 4 years ago

I see that the grammar-kit/README.md file has not changed since 2015. It contains this text:

If you want to use an "infinite loop" in part of your grammar, you should write a
recursion rule like this (only left-recursion is allowed):

S: NS_B WORD_LOOP NS_E
WORD_LOOP: WORD_LOOP WORD
WORD_LOOP: WORD

Yet when I look at the module nfa.c in the mkfa program, it contains code that checks for recursion and generates the error message I have encountered if it sees "left recursion". And that code is just as old as the README, from 2015.

So I am not clear on how I ever got this working before. And I am stuck for now.

LeeAkinobu commented 4 years ago

I've found a bug in mkdfa and have fixed it just now. Could you try the latest version on the master branch?

Why the description differs between README and mkfa codes:

The internal grammar compiler "mkfa" can handle only right recursion rules
"mkdfa" make a reversed grammar from the given grammar, and then give the reversed grammar to mkfa to generate right-to-left DFA, since the 2nd pass of Julius is a backward process.
Thus, the given grammar should be written in left recursion (which will be a right recursion after reversal, which matches the mkfa)

Why left recursion makes error while right recursion does not in recent version:

Old Julius generates only right-to-left DFA (.dfa), but recent Julius also generates left-to-right DFA (.dfa.forward).
So a recursion always had caused error on the reverse direction: left recursion will pass the old part but cause error on the new part, whereas right recursion will fail on the old part but goes well on the new part.
We've fixed mkdfa to generate the left-to-right DFA (.dfa.forward) directly from the old right-to-left DFA (.dfa) by reversing the edges of the DFA.

I hope this fix helps you.

7402 commented 3 years ago

I can confirm that I also saw the problem("Error: Left recusion is formed in class") reported by OddLingo using the release version 4.6.

Following the suggestion of nitslp-ri, I downloaded the latest master as of July 13, 2021, and I can confirm that the problem is now fixed. I can process my grammer without any error. Thank you, nitslp-ri.

From my point of view, I think this fix is ready for the next release.