Awesome Open Source
Awesome Open Source

Actions Status Actions Status Actions Status Actions Status codecov

PEGParser

A linear-time C++17 PEG parser generator supporting memoization, left-recursion and context-dependent grammars.

Example

The following defines a simple calculator program. It is able to parse and evaluate the basic operations +, -, *, / while obeying operator and bracket precedence and ignoring whitespace characters between tokens.

#include <peg_parser/generator.h>
#include <iostream>

void example() {
  peg_parser::ParserGenerator<float> g;

  // Define grammar and evaluation rules
  g.setSeparator(g["Whitespace"] << "[\t ]");
  g["Sum"     ] << "Add | Subtract | Product";
  g["Product" ] << "Multiply | Divide | Atomic";
  g["Atomic"  ] << "Number | '(' Sum ')'";
  g["Add"     ] << "Sum '+' Product"    >> [](auto e){ return e[0].evaluate() + e[1].evaluate(); };
  g["Subtract"] << "Sum '-' Product"    >> [](auto e){ return e[0].evaluate() - e[1].evaluate(); };
  g["Multiply"] << "Product '*' Atomic" >> [](auto e){ return e[0].evaluate() * e[1].evaluate(); };
  g["Divide"  ] << "Product '/' Atomic" >> [](auto e){ return e[0].evaluate() / e[1].evaluate(); };
  g["Number"  ] << "'-'? [0-9]+ ('.' [0-9]+)?" >> [](auto e){ return stof(e.string()); };
  g.setStart(g["Sum"]);

  // Execute a string
  auto input = "1 + 2 * (3+4)/2 - 3";
  float result = g.run(input); // -> 5
  std::cout << input << " = " << result << std::endl;
}

Quickstart

PEGParser requires at least cmake 3.14 and the ability to compile C++17 code. The following shows how to compile and run the calculator example.

cmake -Hexample -Bbuild/example
cmake --build build/example -j8
./build/examples/calculator

You should familiarize yourself with the syntax of parsing expression grammars. The included examples should help you to get started.

Installation and usage

PEGParser can be easily added to your project through CPM.cmake.

CPMAddPackage(
  NAME PEGParser
  VERSION 2.0
  GIT_REPOSITORY https://github.com/TheLartians/PEGParser.git
)

target_link_libraries(myProject PEGParser)

Project goals

PEGParser is designed for ease-of-use and rapid prototyping of grammars with arbitrary complexity, and builds its parsers at run time. So far no work has been invested on optimizing the library, however it runs fast enough to be used in several production projects.

Time complexity

PEGParser uses memoization, resulting in linear time complexity (as a function of input string length) for grammars without left-recursion. Left-recursive grammars have squared time complexity in worst case. Memoization can also be disabled on a per-rule basis, reducing the memory footprint and allowing context-dependent rules.


Get A Weekly Email With Trending Projects For These Topics
No Spam. Unsubscribe easily at any time.
c-plus-plus (17,365) 
cpp (1,224) 
parser (480) 
filter (196) 
dsl (164) 
parse (120) 
grammar (64) 
calculator (62) 
memoization (25) 
parser-generator (22) 
peg (20) 
complexity (17) 

Find Open Source By Browsing 7,000 Topics Across 59 Categories

Advertising 📦 10
All Projects
Application Programming Interfaces 📦 124
Applications 📦 192
Artificial Intelligence 📦 78
Blockchain 📦 73
Build Tools 📦 113
Cloud Computing 📦 80
Code Quality 📦 28
Collaboration 📦 32
Command Line Interface 📦 49
Community 📦 83
Companies 📦 60
Compilers 📦 63
Computer Science 📦 80
Configuration Management 📦 42
Content Management 📦 175
Control Flow 📦 213
Data Formats 📦 78
Data Processing 📦 276
Data Storage 📦 135
Economics 📦 64
Frameworks 📦 215
Games 📦 129
Graphics 📦 110
Hardware 📦 152
Integrated Development Environments 📦 49
Learning Resources 📦 166
Legal 📦 29
Libraries 📦 129
Lists Of Projects 📦 22
Machine Learning 📦 347
Mapping 📦 64
Marketing 📦 15
Mathematics 📦 55
Media 📦 239
Messaging 📦 98
Networking 📦 315
Operating Systems 📦 89
Operations 📦 121
Package Managers 📦 55
Programming Languages 📦 245
Runtime Environments 📦 100
Science 📦 42
Security 📦 396
Social Media 📦 27
Software Architecture 📦 72
Software Development 📦 72
Software Performance 📦 58
Software Quality 📦 133
Text Editors 📦 49
Text Processing 📦 136
User Interface 📦 330
User Interface Components 📦 514
Version Control 📦 30
Virtualization 📦 71
Web Browsers 📦 42
Web Servers 📦 26
Web User Interface 📦 210