left-recursive grammar breaks the parser about java-probabilistic-earley-parser HOT 5 CLOSED

Wow, good point. There is nothing wrong with the grammar, but in the way I represent the grammar to efficiently calculate probabilities. It's been a while, I hope I still understand it enough to investigate.

from java-probabilistic-earley-parser.

I suspect it's just for the edge case of this minimal, almost trivial example. Investiginating now.

from java-probabilistic-earley-parser.

Confirmed: happens for edge cases where p=1.0 and matrix is indeed singular. Shouldn't be hard to fix.

from java-probabilistic-earley-parser.

@digitalheir Awesome! Thanks for mentioning what the problem was. I tried having a look at the code just out of curiosity, but since I familiar only with CYK and not Earley parser, I could not really understand what was happening except that there is a matrix somewhere which has a 0 determinant.

from java-probabilistic-earley-parser.

I've been silly. Of course we get strange results if the program assigns P=1.0 to each rule by default. I had the idea to normalize the probabilities as above example yields P(A)=1+1=2, an illegal probability. So should normalize to [0.5, 0.5] so that P(A)=1.0. I never got around to implementing it and have acted as if it's no problem.

Easier fix than I had thought!

from java-probabilistic-earley-parser.