SQLite Forum

Comparing lemon/byacc/bison for LARL(1) grammars

Comparing lemon/byacc/bison for LARL(1) grammars

(1) By Domingo (mingodad) on 2021-11-15 11:47:09 [source]

I did a comparison between lemon (from sqlite) byacc (from https://invisible-island.net/byacc/byacc.html) and bison with a custom command line option to ignore all precedence settings  then tested with sqlite3/cfront3 grammar (see here https://github.com/mingodad/lalr-parser-test).

Probably still there is something I'm missing or misunderstood (pull requests are welcome) but again differences between how lemon/byacc/bison parse LARL(1) grammars seems strange:

For sqlite3 grammar:

lemon : zero conflicts

byacc/bison: 53 reduce/reduce conflicts

Again for sqlite3 grammar ignoring all precedences:

lemon/byacc: 827 parsing conflicts, 788 shift/reduce, 39 reduce/reduce

bison: 827 parsing conflicts, 734 shift/reduce, 93 reduce/reduce

Now for cfront3 grammar:

lemon: 19 parsing conflicts, 19 shift/reduce, 0 reduce/reduce

byacc: 24 parsing conflicts, 21 shift/reduce, 3 reduce/reduce

bison: 24 parsing conflicts, 20 shift/reduce, 4 reduce/reduce

Again for cfront3 grammar ignoring all precedences:

lemon/byacc: 1077 parsing conflicts, 1074 shift/reduce, 3 reduce/reduce

bison: 1077 parsing conflicts, 1073 shift/reduce, 4 reduce/reduce

I'll appreciate any help on figuring out what's happening here.

(2) By Domingo (mingodad) on 2021-11-15 14:31:45 in reply to 1 [link] [source]

I did some fixes for converting yacc grammars to lemong grammars and added more examples (cql, zephir-lang, postgresql-13.3) here https://github.com/mingodad/lalr-parser-test