LRSTAR Parser Generator AMDG
Home News Installation LRSTAR DFASTAR Skeleton Definitions Contact

LRSTAR Parser Generator

  • 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 can do AST construction and traversal
  • yes
  • Includes 6 Microsoft Visual C++ projects
  • yes
  • Includes 20 BNF grammars
  • yes

    DFASTAR Lexer Generator

  • 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 + DFASTAR v 7.0.000 (open-source project)


    LR(k) Parsers

    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 LALR(1) parsers because there are typically not a larger number of 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 is correct.  'k' is set to a fixed number (i.e. 2,3,4) by the user. 

    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. 

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