README
¶
GPeg
GPeg is a tool for working with parsing expression grammars (PEGs). It is built with three primary goals in mind:
- Efficient parsing for two use-cases.
- Language grammars with AST construction (where PEGs serve as a CFG alternative)
- Patterns (where PEGs serve as a regex alternative).
- Incremental parsing.
- Support for dynamically loading grammars (meaning parsers can be generated and used at runtime).
GPeg uses the same general parsing techniques as Lua's LPeg library and is heavily inspired by LPeg.
Features
- Fast incremental parsing.
- Parsing virtual machine (parsers can be dynamically generated).
- Pattern compiler with optimizations.
- Support for the original PEG syntax with some extensions.
- Parse more complex string data structures (via ReaderAt interface).
- Support for back-references (context-sensitivity).
- Can convert most Go regular expressions to PEGs (see the
rxconvpackage). - Basic error recovery.
- Syntax highlighting library (zyedidia/flare).
- Tools for visualizing grammars, ASTs, and memo tables (zyedidia/gpeg-extra).
Publications
- Zachary Yedidia and Stephen Chong. "Fast Incremental PEG Parsing." Proceedings of the 14th ACM SIGPLAN International Conference on Software Language Engineering (SLE), October 2021. Link.
- Zachary Yedidia. "Incremental PEG Parsing." Bachelor's thesis. Link.
Related work
- Ford, Bryan. "Parsing expression grammars: a recognition-based syntactic foundation." Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 2004. Link.
- LPeg.
- Ierusalimschy, Roberto. "A text pattern‐matching tool based on Parsing Expression Grammars." Software: Practice and Experience 39.3 (2009): 221-258. Link.
- Medeiros, Sérgio, and Fabio Mascarenhas. "Syntax error recovery in parsing expression grammars." Proceedings of the 33rd Annual ACM Symposium on Applied Computing. 2018. Link.
- Medeiros, Sérgio, Fabio Mascarenhas, and Roberto Ierusalimschy. "Left recursion in parsing expression grammars." Science of Computer Programming 96 (2014): 177-190. Link.
- NPeg.
- Papa Carlo.
- Dubroy, Patrick, and Alessandro Warth. "Incremental packrat parsing." Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering. 2017. Link.
- Marcelo Oikawa, Roberto Ierusalimschy, Ana Lucia de Moura. "Converting regexes to Parsing Expression Grammars." Link.
- Tree Sitter.
Directories
¶
| Path | Synopsis |
|---|---|
|
Package charset provides data types and functions for managing sets of characters.
|
Package charset provides data types and functions for managing sets of characters. |
|
cmd
|
|
|
gpeg
command
|
|
|
Package input defines data types and functions for managing input data.
|
Package input defines data types and functions for managing input data. |
|
Package isa provides types for all instructions in the GPeg virtual machine.
|
Package isa provides types for all instructions in the GPeg virtual machine. |
|
interval/lazy
Package lazy provides an interval tree backed by an AVL tree.
|
Package lazy provides an interval tree backed by an AVL tree. |
|
interval/lazylog
Package lazylog provides an interval tree backed by an AVL tree.
|
Package lazylog provides an interval tree backed by an AVL tree. |
|
Package pattern provides data types and functions for compiling patterns into GPeg VM programs.
|
Package pattern provides data types and functions for compiling patterns into GPeg VM programs. |
|
Package re provides functions for compiling 're' patterns (given as strings) into standard patterns.
|
Package re provides functions for compiling 're' patterns (given as strings) into standard patterns. |
|
Package rxconv provides functions to convert a Go regexp into a PEG so that it can be used for incremental parsing.
|
Package rxconv provides functions to convert a Go regexp into a PEG so that it can be used for incremental parsing. |
|
Package vm implements the GPeg virtual machine.
|
Package vm implements the GPeg virtual machine. |
Click to show internal directories.
Click to hide internal directories.