|LRSTAR Parser Generator||A.M.D.G.
|Home News Comparison Papers Installation LRSTAR DFASTAR Skeleton Definitions Contact|
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. There is another type, called canonical LR(1) parser, which can be extremely large and not as fast as minimal 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 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.|