|Home News Comparison Papers Contact Installation LRSTAR DFASTAR Skeleton Definitions|
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.
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 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.|