LRSTAR Parser Generator A.M.D.G.
  Home News Comparison Papers Installation LRSTAR DFASTAR Skeleton Definitions Contact  

LRSTAR Parser Generator 7.0

  • Creates LR(1)/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 can do AST construction and traversal
  • yes
  • Microsoft Visual C++ projects included
  • 6
  • BNF grammars included
  • 20

    DFA Lexer Generator 7.0 (included)

  • 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

    Feedback From Users

    2012   "Many thanks for LRSTAR.  I used to use flex/bison for my DSLs.  I'm working on a project which requires the fastest possible lexer/scanner for DSL (part of my web-server).  I can get it only with LRSTAR.  In my opinion, TBNF is the best grammar notation I've ever seen."

    Sergey Kuritsin, PhD, Yekaterinburg, Russia

    2012   "LRSTAR seems quite professionally built.  About parser and lexer speed, I'm literally impressed.  I'm finding this kind of parser generator suitable for parsers that I'm working on (high-speed server-side processing).  It works great for my purpose even on 64-bit machines with Linux and Mac OS X, compiled with GCC and Intel CPP compiler."

    Vasko Mitanov, Software R&D Department Manager at Skopski Pazar, Romania

    2011   "I just happened upon your very high quality lexer and parser generators.  Firstly, I'm really impressed with the capabilities of your generator.  I've toyed a bit with Bison/Yacc, and in my opinion, yours is far superior.  I am finding LRSTAR particularly easy to use and quite powerful.  The ability to build the AST and have the parser generated from a skeleton really makes things easy for me.  On my machine, I am getting an insane number of lines per second, in the `numerous hundreds of thousands."

    Bill Hart, PhD, Warwick University, UK

    2011   "I really like the LRSTAR tool (compared to yacc/bison).  I prefer the simplicity of LRSTAR.  I did a re-write using another parser generator, but the speed of their parser is at least an order of magnitude slower than LRSTAR [parsers] which was quite surprising.  I am certain you have a good, maybe even a great, product."

    Sidney Worth, PhD, Active Education

    2009   "I used your LALR tool for developing a Verilog parser around 1991.  I remember that the generated parser was extremely fast."

    Eli Sternheim, PhD, InterHDL

    2005   "The TBNF notation used for translations is the most concise notation that I have ever seen implemented in a tool, still remarkably powerful."

    Ralf Lammel, PhD, Koblenz University, Germany

    2005   "I like the TBNF idea.  It's a much more sophisticated evolution of the way I build my ASTs for my validation tool."

    Michael Fromberger, PhD, Dartmouth College

    2005   "We are still using your LALR product [since 1991].  It's a little secret that we don't want our competitors to know about."


    1999   "We used your LALR product to build the compiler in Lotus Notes [in 1993] and it's been very successful, over 135,000,000 users now."

    Kevin Jackson, IBM Software Group

    1991   "I recommended that we use your LALR product for all internal language-development efforts."

    Ken Allen, Information Builders

    1985   "LALR 1.0 ... Unbelievably fast ... able to handle huge grammars [in 640K RAM]."

    Daryl Rubin, a review published by Computer Language Magazine


    LR(1)/LR(k) Parsers

    LRSTAR creates LR(1) parsers if your grammar is LR(1). These are minimal LR(1) parsers, the same size or slightly larger than LALR(1) parsers. If your grammar is not LR(1), LRSTAR creates nondeterministic LR(k) parsers.  An NDLR(k) parser uses 'k' symbols of lookahead (at parsing time) to make parsing decisions.  NDLR(k) parsers are slightly larger than minimal LR(1) parsers because there are typically not many states that require LR(k) parsing (for k > 1).  In those states, the LR(k) parser will try all valid tokens for that state to find out which one allows the parser to consume 'k' additional tokens.  'k' is set to a fixed number (2,3,4) by the user.  Canonical LR(1) parsers are not usually supported because they are extremely large and not as fast as minimal LR(1) parsers, however LRSTAR is capable of generating canonical LR(1) parsers.

    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 usually belongs to the parser.  Before DFA's became available, lexical analysis had been known to consume a large percentage of the processing time in compiler front-ends.  With DFA's that time is reduced to about 10-15% of the 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. 

    LRSTAR 7.0

    Includes the LRSTAR parser generator and DFASTAR lexer generator.

    Personal Use

    Use of LRSTAR only for projects which do not generate income.

    Commercial Use

    Use of LRSTAR for projects which generate income.

    Source-Code License

    For internal use only.



    Paul B Mann
    P O Box 156
    Saint Marys, KS 66536

    785-321-6000 M-F 8-5 p.m.

    pbm [at] lrtec [dot] com

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