The SLK Parser Generator supports C, C++, Java, JavaScript, and C#, optional backtracking, free

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.

SLK currently supports the C, C++, C#, Java, and JavaScript languages.

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.

Compiling SLK parsers is never a problem. All C, C++, C#, Java and JavaScript compilers and interpreters are fully supported.

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).

The SLK Parser Generator produces compact and efficient LR(k) or LL(k) parsers in C, C++, C#, JavaScript and Java. Features include automated grammar transformations, clean EBNF syntax, optional backtracking, new lookahead algorithms, and an uncomplicated API. Under development for over 25 years, the SLK parser generator is fully supported and is actively being enhanced on a full time basis. Users are encouraged to that they have about how SLK can be improved.

Download SLK Version 5.12

now supports javascript output in addition to C, C++, C#, and java
LL(2) C grammar and output. Handles the typedef problem in actions and error handler. Very compact.
LALR(3) C grammar and output showing that extra lookahead can help with the typedef problem and embedded actions.
LL(8) C++ grammar and output. Extension of the base C grammar to support simple C++.
LL(5) java grammar and output. Handles types in actions and error handler. Very compact.
Source code for the C recognizer. Handles the typedef problem in actions and error handler. Full code on the download page.
Source code for a C preprocessor. Illustrates parser reentracy, parsing from not the start symbol, other tricks. Full code on the download page.

More Detail About SLK

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.

SLK implements new lookahead algorithms that are not available in any other parser generator. One is an efficient grammar analysis algorithm and the other is a new table-driven LL(k) parsing algorithm. The new grammar analysis algorithm can very quickly analyze most grammars, even for large k-values.
SLK produces parsers that are nearly the fastest and most compact that is possible. The table compaction algorithms become more and more effective as the grammar size increases. This relationship is nearly exponential because the tables become extremely sparse as their size increases. A side effect of this is that very large grammars can be handled more easily than is the case with recursive-descent. There is no need to try to keep the grammar compact, at the expense of readability.
SLK produces fully modular parsers. Actions are invoked by number through a call table that is a parameter to the parser. The semantic stack is action-controlled for maximum flexibility. This means that the semantic stack is fully contained in, and controlled by the user-written action code. This approach is also more efficient because attribute assignment is only done where needed. Problems that sometimes occur because of the default $$=$1 assignment are avoided.
The SLK parser specification language, the grammar, is completely programming language independent. The grammar is the only input to the parser generator, so the same grammar can be used to produce parsers in all of the supported programming languages.
SLK currently supports the C, C++, C#, Java and JavaScript languages on all platforms. Note that the SLK parsers primarily consist of tables of integers as arrays and a very small parse routine that only uses the simple, and universally supported features of the language. This is in contrast to parser generators that produce recursive descent code. They must force a certain programming model on the user because the parsing code is intermixed with the user action code. SLK places no limits or requirements on the coding style of the user.
SLK introduced a new and more precise action placement syntax for EBNF notation. An action that is specified just after the end brace/bracket is only executed when the EBNF construct goes to null. An action that is specified just before the end brace/bracket is only executed when the EBNF construct does not go to null. This simplifies the semantic action code, since it does not need to handle both of these cases in the same action.
The SLK parsers are reentrant and thread-safe. The parsers have no library dependencies, so they are well-suited to embedded applications. Any number of parsers for different grammars can be contained in a single program. Compiling SLK parsers is never a problem. All C, C++, C#, Java and JavaScript compilers and interpreters are fully supported.
SLK supports a new white space delimited syntax that accepts grammars in the forms commonly found in published reference grammars. This syntax eliminates the need for reserved tokens, making the grammars appear cleaner. More descriptive identifiers result from the ability to use almost any ASCII character. For example, ;_opt and ,_id_* are valid nonterminal symbols in SLK. Quotes or terminal declarations are not needed for terminal symbols, so operators like != and -> can be written in the grammar as they are. This syntax supports both BNF and EBNF notation. SLK also supports a YACC-style BNF grammar syntax as a legacy, and to aid in porting a grammar from YACC to SLK.
SLK includes automated grammar transformation options that convert reference grammars to top-down format. These include smart left-factoring and left-recursion elimination. The new left-factoring algorithm does not convert those constructs that could be handled by the LL(k) lookahead. SLK also has extensive grammar debugging capabilities.
Predictive backtracking, also called LL(inf) or PEG, can be used selectively on the nonterminals that LL(k) is unable to handle. Predictive backtracking predicts which production to use by trying to parse each one in turn, and returning the first one that parses without error to the mainline parser. Semantic actions are not executed during backtracking, so the process is transparent to the programmer.
The SLK parser generator can also be used to aid in the development of hand-written recursive descent compilers. The -Da option can be used to display the parse table in readable text form. Only the valid entries are included, making it well suited to translation to recursive descent. The conflict table is also displayed as well as the FIRST and FOLLOW sets.
The SLK conflict resolution capability is now exported for use with any parser or parsing tool. If a conflict can be resolved by the use of extra lookahead, SLK will generate code to do this. It should be noted that for LR grammars many types of conflicts are not solvable with extra lookahead.

More Detail About SLK

Parsing Theory

Programming