LRStar: LR(*) parser generator

A.M.D.G.

Home Downloads Feedback Comparison Theory Papers Documentation Contact

LRStar vs ANTLR vs Bison

LRStar ANTLR Bison
LL(k) Parsers (recursive descent) no yes no
LALR(1) Parsers yes no yes
Canonical LR(1) Parsers no no yes
Minimal LR(1) Parsers yes no yes
Minimal LR(k) Parsers yes no no
GLR Parsers no no yes
EBNF grammar notation yes yes no
Grammar is independent from code yes yes no
Symbol-Table Builder yes yes no
Automatic AST Construction yes parse treeno
C++ Output yes yes yes
C# Output no yes no
Java Output no yes yes
License fee ??? free free

Note. Things change over time. Some of these items may be different from what is shown above. To make sure you have the latest information, visit the competitor's website

Canonical LR(1) vs Minimal LR(1)

September 2018. I just finished a 3-day study of Canonical LR(1) versus Minimal LR(1) parser tables. The "dragon" textbook by Alfred Aho and others, says canonical parser tables can be as large as 10,000 states, but I have never seen any published results on this. Since we don't worry much about CPU memory usage anymore, I thought it would be interesting to see just how large the canonical parser tables can get for large grammars. Answer: very large, ridiculously large. See the DB2 grammar at the bottom of the chart below.

Grammar Rules Terminals CLR States CLR Parser Table Size (bytes) CLR Generation Time (seconds) MLR States MLR Parser Table Size (bytes) MLR Generation Time (seconds)
C99 238 89 1,856 87,852 0.37 212 8,994 0.08
Zeus 1985 223 71 2,583 99,196 0.39 233 5,673 0.03
CICS 74 821 216 1,393 102,042 0.15 668 12,281 0.06
Modula-2 90 228 71 2,738 108,605 0.51 208 4,972 0.02
SQL 88 400 138 1,917 118,184 0.24 532 10,118 0.04
Java 1.1 265 98 2,466 181,779 0.73 233 10,312 0.09
Verilog 2003 521 176 3,690 247,915 0.82 569 16,736 0.07
C11 344 108 4,031 260,212 0.94 350 15,127 0.11
Basic 88 471 176 5,926 268,771 1.45 611 15,591 0.13
Turbo Pascal 5.5 378 113 4,316 324,311 1.09 348 12,774 0.06
C++ 88? 307 103 6,239 386,686 1.52 251 11,266 0.06
Fortran 77 1,133 268 4,831 446,236 2.47 724 20,270 0.17
dBASE III 618 280 9,599 490,620 1.70 635 13,722 0.09
PL/I 88 1,272 227 4,965 576,613 3.88 861 40,122 0.30
Visual Basic 97 497 138 8,261 913,721 7.88 455 17,787 0.07
Lotus Script 99 761 214 12,977 1,698,425 28.17 675 33,313 0.42
Oracle-SQL 8 1,201 317 54,072 14,968,200 929.67 863 40,458 0.53
DB2 2005 1,856 584 131,548 50,516,126 5,007.36 1,666 77,031 0.57

Note. For large grammars, 99% of the time was spent in compressing the parser tables from the original matrix down to 4 smaller ones, 3 of which can take advantage of graph coloring to reduce their size. The size shown in the chart is the reduced size which includes all 4 tables.

(c) Copyright Paul B Mann 2018.  All rights reserved.