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.

Roadmap

• Parsing virtual machine.
• Pattern compiler with optimizations.
• Support for original PEG syntax.
• AST generation/captures.
• Parse non-string data structures (via interface).
• Incremental matching.
• Incremental AST/captures.
  • Logarithmic incremental parsing algorithm.
• Support for an extended PEG syntax.
• Syntax highlighting example.
• Polish, documentation, and examples.
• Additional niceties (TBD).
  • Error recovery.
  • Grammar tree visualizer.
  • AST visualizer.
  • Memoization table visualizer.
  • Support for left recursion.

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.
• Tree Sitter.