left-recursive grammar breaks the parser

[hristo-vrigazov]

I tried the following grammar:

S -> a
S -> S a

Reading it like this:

Grammar<String> grammar = Grammar.parse(
                Paths.get("/some/path/test.cfg"), Charset.forName("UTF-8"));

Results in:

java.lang.RuntimeException: Matrix is singular.

	at org.leibnizcenter.cfg.algebra.matrix.LUDecomposition.solve(LUDecomposition.java:140)
	at org.leibnizcenter.cfg.algebra.matrix.Matrix.solve(Matrix.java:346)
	at org.leibnizcenter.cfg.algebra.matrix.Matrix.inverse(Matrix.java:357)
	at org.leibnizcenter.cfg.grammar.Grammar.getReflexiveTransitiveClosure(Grammar.java:134)
	at org.leibnizcenter.cfg.grammar.Grammar.<init>(Grammar.java:102)
	at org.leibnizcenter.cfg.grammar.Grammar$Builder.build(Grammar.java:416)
	at org.leibnizcenter.cfg.grammar.Grammar.parse(Grammar.java:183)
	at org.leibnizcenter.cfg.grammar.Grammar.parse(Grammar.java:166)
	at com.vision4j.internal.cli.PlayTest.cfg(PlayTest.java:48)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
	at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
	at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
	at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
	at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
	at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
	at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:68)
	at com.intellij.rt.execution.junit.IdeaTestRunner$Repeater.startRunnerWithArgs(IdeaTestRunner.java:51)
	at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:237)
	at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:70)

Converting the grammar to right-recursive avoids this issue:

S -> a
S -> a S

I am using the latest version in Maven: 0.9.12
Is there something I misunderstood about the behaviour of the grammar or is this bug?

[digitalheir]

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.

[digitalheir]

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

[digitalheir]

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

[hristo-vrigazov]

@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.

[digitalheir]

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!