There is a variety of PEG (Parsing Expression Grammar) parser generators are available for Python, Rust, and C++. They differ primarily in how they handle actions, AST generation, and error handling.
Python
| Generator | Key Features |
|---|---|
| Pegen | Embedded Code: Supports embedding Python code directly into the grammar file, known as “grammar actions,” to build the AST. AST/CST: Directly generates AST objects based on the grammar actions. The current CPython interpreter is built using Pegen. Semantic Predicates: The grammar actions, which can execute arbitrary Python expressions, effectively function as semantic predicates, allowing context-sensitive parsing. |
| Parsimonious | Embedded Code: Does not embed code directly in the grammar. The grammar defines the structure, and you traverse the resulting concrete syntax tree (CST) with a visitor or a custom transformation class. AST/CST: Generates a CST (a full parse tree) from the input. It is up to the developer to then process this tree into a more abstract representation (AST). Semantic Predicates: Does not support semantic predicates directly in the grammar. You would perform semantic checks during the post-parsing tree traversal. |
| Fastidious | Embedded Code: Aims to support complex rule actions but primarily uses a separate compilation step. AST/CST: Plans to support automatic AST node generation. Semantic Predicates: Not specified in the documentation, suggesting it is handled outside the grammar rules. |
Rust
| Generator | Key Features |
|---|---|
peg |
Embedded Code: Uses a procedural macro (peg::parser!{}) to embed a PEG grammar directly in your Rust code. Rust expressions can be embedded within the rules to define actions and return values. AST/CST: Actions within the grammar rules build the AST incrementally. You define the return types for each rule, which allows you to construct your AST enums or structs. Semantic Predicates: Supports conditional actions with a ? syntax that can fail a match if a Rust expression returns an Err. This enables context-dependent logic. |
| Pest | Embedded Code: The grammar is separate from the Rust code, and it does not embed code within the grammar file. Parsing actions are defined externally in your Rust code. AST/CST: Parses the input into an intermediate CST. You then write Rust code to traverse and match the CST, converting it to a custom AST. Semantic Predicates: Lacks semantic predicates. Since parsing is separate from logic, all semantic checks must happen after the parsing is complete. |
| Peginator | Embedded Code: Actions are defined using helper attributes on structs and enums. It does not support embedding arbitrary Rust code directly within the grammar itself. AST/CST: Its primary purpose is to automatically generate a typed AST from a grammar. It works by mapping grammar rules to user-defined structs and enums. Semantic Predicates: Not supported directly within the grammar. Context-sensitive logic is typically handled by post-processing the generated AST. |
C++
| Generator | Key Features |
|---|---|
| PEGTL (Template Library) | Embedded Code: As a header-only library, it defines grammars using C++ types and templates. The grammar is inseparable from the C++ source code. AST/CST: It is a low-level combinator library. You must explicitly define your C++ actions (using a “visitor” or “selector”) to build a CST or AST. Semantic Predicates: Supports semantic predicates through C++ expression evaluations within rules, which can influence the parser’s decision-making. |
| cpp-peglib | Embedded Code: Embeds grammar as a string literal within C++ source code and binds C++ lambda functions to grammar rules for actions. AST/CST: Supports automatically creating a CST (a peglib::ast object) with each rule match. Custom actions (lambdas) are used to manipulate and build the desired AST. Semantic Predicates: Not directly supported within the grammar rules, though you can use conditionals within the lambda functions to perform checks. |
| PEGParser | Embedded Code: Supports binding rules to C++ functions via lambdas to execute actions upon a successful match. AST/CST: Provides a mechanism to build an AST with custom actions, similar to cpp-peglib. It also includes memoization for linear time complexity. Semantic Predicates: Supports context-dependent grammars, which can be seen as a form of semantic predication. |
peg |
Embedded Code: The original tool, along with leg, is a C-based generator that uses a syntax similar to Yacc/Lex. It does not typically embed C++ code but generates C code with embedded actions. AST/CST: Builds the AST via explicit, embedded C code actions. Semantic Predicates: Supports semantic predicates via C code, similar to how it handles actions. |
ANTLR
Although ANTLR is not a PEG parser, it represents a modern alternative to traditional LALR parser generators like Yacc and Bison . Instead of bottom-up LALR parsing, which can be difficult to debug and requires grammars to be rewritten to avoid issues like shift/reduce conflicts, ANTLR uses a top-down, predictive LL(*) algorithm. This adaptive approach dynamically determines the necessary lookahead, offering greater power and flexibility while preserving the good error-reporting and easy-to-read grammar of LL parsers. ANTLR’s multi-target language support and separation of grammar from embedded actions also provide a significant productivity boost over older tools tied to C/C++.