|Home FAQ Docs Download|
|The SLK Parser Generator|
SLK is the only both LL(k) and LR(k) parser generator available. The same syntax is used in both, so it is easy to switch between top-down and bottom-up parsing based on need or just preference. SLK quickly does a full analysis of the grammar. The SLK algorithm is the only known solution to this NP-hard problem. SLK can produce a customizable persistent parse tree in addition to executing actions during parsing.
|SLK implements new lookahead algorithms that are not available in any other parser generator.|
|SLK produces parsers that are nearly the fastest and most compact that is possible.|
|The SLK parser generator produces fully modular parsers.|
|The SLK parser specification language, the grammar, is completely programming language independent.|
|SLK introduced a new and more precise action placement syntax for EBNF notation.|
|SLK supports a new white space delimited syntax that accepts grammars in the forms commonly found in published reference grammars.|
|SLK parsers have no library dependencies, so they are well-suited to embedded applications.|
|SLK includes automated grammar transformation options that convert reference grammars to top-down format.|
|Predictive backtracking can be enabled under programmer control as part of the syntax of the SLK parser generator.|
|The SLK parsers are reentrant and thread-safe.|
|Any number of SLK parsers for different grammars can be contained in a single program.|
|SLK can produce a persistent parse tree to aid in source to source translation. The parse tree can also be transformed into an AST. The parse tree source code is included for customization to produce whatever shape tree is desired.|
|The conflict resolution table is exposed as a method call. This enables adding k lookahead to any other LL or LR parser.|
|SLK can now also generate LR(k) bottom-up parsers, in addition to top-down LL(k).|
An obvious question is "why yet another parser generator?" The SLK parser generator is different from all others in two fundamental ways. First, it produces table-driven LL(k) parsers instead of recursive-descent parsers. The table-driven parsers are generally less than one tenth the size of the equivalent recursive-descent parsers. The SLK tables are actual two dimensional tables rather than the inefficient linked lists that would be used to implement a traditional LL(k) parse table. The SLK lookup is fast and consistent. Exactly "k" lookups are required for an LL(k) nonterminal. Most grammars contain very few nonterminals that are not LL(1), so usually only one lookup is required.
The second difference is that SLK does a full LL(k) analysis of the grammar. The SLK algorithm is the only known solution to this NP-hard problem. Other deterministic algorithms must either limit k to a very small value, usually two, or use approximate lookahead methods that are considerably weaker than the LL(k) method.
The SLK parser generator also includes the ability to do selective, controlled nondeterministic parsing where needed. SLK produces compact and efficient parsing code modules that can be easily integrated with other generated or hand-written code modules. SLK is targeted to the developer who wants an uncomplicated tool that is easy to use and easy to learn to use.
SLK is the only tool available that enables table-driven LL(k) parsing. Top-down parsing (LL) is thought to be better suited to syntax directed translation (compilers) than the bottom-up parsing technique (LALR) that is used by most parser generators. The SLK table-driven parsing method is also superior to the recursive-descent technique that is used by programmers because it automates much of the process. The simple driver treats all symbol types of the grammar the same because the grammar is encoded in a set of tables. In recursive-descent, all of the productions are individually written out in the source code of the program. This is tedious, prone to error, difficult to maintain, and it obscures the grammar in a way that makes it difficult to determine exactly what language is really being recognized by the compiler.
SLK combines the simplicity and efficiency of the LL(1) method with the power and flexibility of LL(k) parsing. The SLK parser generator creates parsers that are smaller and faster than others. They also have consistent, easily customizable, automated error recovery. Correctness is easier to demonstrate since the parsing code is separate from the semantic action code. This improved modularity also simplifies debugging by fully separating the debugging of the grammar from that of the semantic action code. Parse derivation files enable the static examination of the behavior of the grammar without having to step through the code using a symbolic debugger. In effect, the parse trace is a flat file version of the entire parse tree. Of course, the parse code module is clearly written so it can be debugged if desired. More likely is that the programmer would set break points only in his action code, bypassing all of the code created by the parser generator.
The SLK parser generator creates LL(k) parsing code modules. These can be combined with a lexical analyzer and semantic action code to produce translators or compilers. Some of the features of the SLK parser generator follow.