Home News Comparison Papers Contact Installation LRSTAR DFASTAR Skeleton Definitions  

LRSTAR Parser Generator v 7.0

Creates LR(k) parsers in C++
Creates parser tables of type Matrix
Reads grammar notation with EBNF operators (+,*,?) yes
Parsers have a symbol-table builder yes
Parsers do AST construction and traversal yes
Includes 6 Microsoft Visual Studio 2013 C++ projects yes
Includes 20 BNF grammars yes

DFASTAR Lexer Generator v 7.0 (included with LRSTAR)

Creates DFA lexical analyzers in C++
Creates lexer tables of type Matrix
Lexer speed (2 times the speed of flex) 30,000,000  tokens/sec.
Lexers do keyword recognition yes

LRSTAR 7.0.055 Express (250 rules) ...

LRSTAR 7.0.055 Professional (unlimited) ... $99.
LRSTAR 7.0.055 Professional (source code) ... $199.


Microsoft Visual Studio 2013 C++

I'm using MS VS 2013 Windows Desktop for my IDE now. It is not fun. I'm finding that it still has bugs as of Sep 13 2014. The old MS VS of 2008 was much better, but too old. Hopefully, Microsoft will fix the bugs before I die, but I'm not betting on it. I don't have a better IDE to work with. Perhaps someone can recommend one. Here is the link to it: Microsoft Visual Studio 2013 C++. You don't have to use it. You can use whatever editor and compiler you want.

LR(k) Parsers

LRSTAR creates LR(k) parsers as follows. Firstly, it creates a minimal LR(1) state machine, by merging compatible states during the canonical LR(1) construction process. The minimal LR(1) state machine may have a few more states than an LALR(1) state machine. Secondly, any states with conflicts will be made into nondeterministic states. For ND states, the generated LR(k) parser will use 'k' tokens of lookahead to resolve the conflicts an run time. 'k' is set to 2, 3, or more by the user.

LR(1) Parsers

If your grammar has no conflicts, the generated parser will not have any ND states and it will operate as an LR(1) parser. Additionally, options are available to force conflict resolution in the LR(1) state machine and generate an LR(1) parser which does not do ND parsing. The advantage is a slightly faster parser. The disadvantage is a parser that is more likely to be incorrect.

The correct 'k'

An LR(k) parser may be incorrect if 'k' is not large enough. Because the grammar analysis is LR(1), if your grammar has conflicts, the correct 'k' is unknown. You will have to do a lot of testing to find the correct 'k' or a 'k' that handles all your test cases. Hopefully, a future version of LRSTAR will determine the correct 'k' for each ND state.

DFA Lexical Analyzers

A DFA lexer is a finite-state automata without a pushdown stack (i.e. not a PDA).  DFA is the fastest recognition algorithm (5 times the speed of PDA's).  A DFA algorithm does not use any lookahead characters.  Because it is not a PDA, it cannot handle nested comments or any type of nested input (e.g. [[a]]).  However, DFA's work fine for most programming languages.  Afterall, the job of handling nested types of input belongs to the parser.  Before DFAs became available, lexical analysis had been known to consume a large percentage of the processing time in compiler front-ends.  With DFAs that time is reduced to about 10-15% of a compiler front-end.

Matrix Tables

Matrix tables provide the fastest table-driven parsers and lexers.  LRSTAR and DFASTAR use compressed-matrix tables, which provide small tables but still very fast.  The DFA matrix lexers are nearly as fast as direct-code lexers, such as RE2C generated lexers. For more details on that, see the comparison of FLEX, DFASTAR, RE2C.

  (c) Copyright LRSTAR.ORG 2014.  All rights reserved.