Rats! is an easily extensible parser generator for C-like languages.
� organizes grammars into modules,
� builds on parsing expression grammars instead of context-free grammars and vintegrates lexing with parsing, i.e., is scannerless,
� supports the automatic generation of abstract syntax trees,
� and provides a well-defined interface for extending parsers to recognize context-sensitive languages and formats.
Parsers generated by Rats! memoize intermediate results, which ensures linear time performance in the presence of unlimited lookahead and backtracking. As a result, they are essentially functional (even though they are implemented in an imperative language) and also called "packrat parsers."
- Rats! relies on a module system to structure grammars and their extensions. In particular, it relies on modules to group related productions into separate units. Next, module modifications concisely express extensions to other modules and can add, change, or remove individual alternatives in productions. Finally, module parameters are used to compose modules and their extensions with each other.
- Rats!' grammars build on parsing expression grammars (PEGs). While PEGs share many constructs with the familiar EBNF notation, a key difference is that they utilize ordered choices instead of the unordered choices used by context-free grammars (CFGs) and other parser generators, such as Yacc or ANTLR. As a result, Rats! grammars avoid ambiguities and support localized changes. Additional flexibility is offered through syntactic predicates, which match expressions but do not consume the input, thus providing unlimited lookahead, and through the integration of lexing with parsing, which greatly simplifies the addition of new tokens to a grammar. PEGs have the additional benefit that they are not only closed under composition (unlike the LR or LL grammars used by Yacc and ANTLR), but also intersection and complement (unlike CFGs in general).
- To eliminate the need for explicit semantic actions, Rats! can automatically generate abstract syntax trees. In particular, it supports productions that return no semantic values (such as those recognizing spaces or comments), string values (such as those recognizing literals or identifiers), and generic tree nodes (potentially all other productions).
- Since some computer-readable formats are inherently context-sensitive and cannot be expressed as PEGs (or CFGs), Rats! supports two techniques for managing parser context or state, thus providing a well-defined interface for extending parsers. First, Rats! provides parser actions to recognize expressions that depend on local context, i.e., expressions that depend on immediately preceding expressions within the same production. An example for such local context is an explicit length preceding as many instances of some expression. Second, Rats! supports a global state object to recognize expressions that depend on possibly global context. State modifications are performed within lightweight transactions, which preserve the basically functional nature of Rats!-generated parsers. An example for a global context is the symbol table used for disambiguating variable and typedef names when parsing C.
In a hurry? Add it to your Download Basket!
What's New in version 1.14.2
- This release improves error reporting by generated parsers and fixes a code generation bug.