test/Calculator failure

[vrotaru]

java  -cp jmeta-runtime.jar:test Calculator "4 * 3 - 2/2"
Exception in thread "main" jmeta.SyntaxError: expected end of input before '/2' (at line: 1, char: 9)
    at Calculator.start(Calculator.java:22)
    at jmeta.BaseParser.parse(BaseParser.java:199)
    at jmeta.BaseParser.parse(BaseParser.java:190)
   at Calculator.main(Calculator.java:8)

I've just started playing with it and, and have run into this. Interesting enough, this:

java  -cp jmeta-runtime.jar:test Calculator "4 * 3/3 - 2"
2

works

[onnlucky]

unfortunately, I can confirm the issue; and it seems not to be some trivial mistake

still unsure what triggers it, but it seems a combination of the direct left recursion and the general left recursion and not memoizing certain rules, the whole rule is parsed correctly, but an attempt to grow the left recursion fails halfway, but doesn't return the old result. It might still be because it happens at end of input.

but truly debugging and fixing the issue will require some time

minimal trigger: "3 - 2 * 1" as input if we remove the position and other parsings we should end up with a small testcase to debug

[onnlucky]

looking further into this issue; it seems that removing the whitespace '.' before expr and expr2 rules fixes the problem. These whitespace marks are redundant there anyhow. Why exactly they cause this parsing problem I still don't know.

diff --git a/test/Calculator.jmeta b/test/Calculator.jmeta
index 4483471..874e62e 100644
--- a/test/Calculator.jmeta
+++ b/test/Calculator.jmeta
@@ -8,14 +8,14 @@ public parser Calculator {

     start: ! e=expr . end      { e };
     expr:
-        | .p=pos l=expr ."+"! r=expr1 { ['ADD, l, r, p] }
-        | .p=pos l=expr ."-"! r=expr1 { ['SUB, l, r, p] }
+        | p=pos l=expr ."+"! r=expr1 { ['ADD, l, r, p] }
+        | p=pos l=expr ."-"! r=expr1 { ['SUB, l, r, p] }
         | expr1
     ;
     expr1:
-        | .p=pos l=expr1 ."*"! r=value { ['MUL, l, r, p] }
-        | .p=pos l=expr1 ."/"! r=value { ['DIV, l, r, p] }
-        | .p=pos l=expr1 ."%"! r=value { ['MOD, l, r, p] }
+        | p=pos l=expr1 ."*"! r=value { ['MUL, l, r, p] }
+        | p=pos l=expr1 ."/"! r=value { ['DIV, l, r, p] }
+        | p=pos l=expr1 ."%"! r=value { ['MOD, l, r, p] }
         | value
     ;
     value:

[onnlucky]

so, the problem is: in the rule expr r=expr1 is cached at a different location, compared to rule expr1 l=expr1 and this is crucial for left recursion to function properly.

Unsure yet if an PEG implementation with direct and indirect left recursion can actually solve this problem ... I think it is up to the grammar author to ensure these line up.

(btw; another fix is to add whitespace before the r=... statements)

[onnlucky]

oh, and an actual minimal testcase is: "3+ 2*1"

public parser run {
    public static void main(String[] args) {
        run parser = new run();
        //parser.tracing = true;
        System.out.println(print_r(parser.parse("3+ 2*1")));
    }

     start: e=expr1 end           { e } ;
     expr1: .l=expr1 ."+" r=expr2 { [l, "+", r] } | expr2 ;
     expr2: .l=expr2 ."*" r=value { [l, "*", r] } | value ;
     value: .digit ;
}

[onnlucky]

and the fix:

public parser run {
    public static void main(String[] args) {
        run parser = new run();
        //parser.tracing = true;
        System.out.println(print_r(parser.parse("3+ 2*1")));
    }

     start: e=expr1 end           { e } ;
     expr1: l=expr1 ."+" r=expr2 { [l, "+", r] } | expr2 ;
     expr2: l=expr2 ."*" r=value { [l, "*", r] } | value ;
     value: .digit ;
}

(removed the two . in expr1 and expr2)