cpp-peglib
==========


C++17 header-only PEG (Parsing Expression Grammars) library, by Yuji Hirose. You can start using it right away just by including peglib.h in your project.

Since this library only supports C++17 compilers, please make sure that the compiler option -std=c++17 is enabled.
(/std:c++17 /Zc:__cplusplus for MSVC)

You can also try the online version, PEG Playground at https://yhirose.github.io/cpp-peglib.

The PEG syntax is well described on page 2 in the document by Bryan Ford. cpp-peglib also supports the following additional syntax for now:

* '...'i (Case-insensitive literal operator)
* [...]i (Case-insensitive character class operator)
* [^...] (Negated character class operator)
* [^...]i (Case-insensitive negated character class operator)
* {2,5} (Regex-like repetition operator)
* < ... > (Token boundary operator)
* ~ (Ignore operator)
* \x20 (Hex number char)
* \u10FFFF (Unicode char)
* %whitespace (Automatic whitespace skipping)
* %word (Word expression)
* $name( ... ) (Capture scope operator)
* $name< ... > (Named capture operator)
* $name (Backreference operator)
* | (Dictionary operator)
* ↑ (Cut operator)
* MACRO_NAME( ... ) (Parameterized rule or Macro)
{ precedence L - + L / } (Parsing infix expression)
* %recovery( ... ) (Error recovery operator)
* exp⇑label or exp^label (Syntax sugar for (exp / %recover(label)))
* label { error_message "..." } (Error message instruction)
* { no_ast_opt } (No AST node optimization instruction)

'End of Input' check will be done as default. To disable the check, please call disable_eoi_check.

This library supports the linear-time parsing known as the Packrat parsing.

IMPORTANT NOTE for some Linux distributions such as Ubuntu and CentOS: Need -pthread option when linking. See #23, #46 and #62.

I am sure that you will enjoy this excellent "Practical parsing with PEG and cpp-peglib" article by bert hubert!

Installation
------------

Run:

``bash
$ npm i peglib.cxx
`

And then include peglib.h as follows:

`cxx
// main.cxx
#include

int main() { / ... / }
`

Finally, compile while adding the path node_modules/peglib.cxx to your compiler's include paths.

`bash
$ clang++ -std=c++17 -I./node_modules/peglib.cxx main.cxx # or, use g++
$ g++ -std=c++17 -I./node_modules/peglib.cxx main.cxx
`

You may also use a simpler approach with the cpoach tool, which automatically adds the necessary include paths of all the installed dependencies for your project.

`bash
$ cpoach clang++ -std=c++17 main.cxx # or, use g++
$ cpoach g++ -std=c++17 main.cxx
`

How to use
----------

This is a simple calculator sample. It shows how to define grammar, associate semantic actions to the grammar, and handle semantic values.

`cpp
// (1) Include the header file
#include
#include
#include

using namespace peg;
using namespace std;

int main(void) {
// (2) Make a parser
parser parser(R"(
# Grammar for Calculator...
Additive <- Multiplicative '+' Additive / Multiplicative
Multiplicative <- Primary '*' Multiplicative / Primary
Primary <- '(' Additive ')' / Number
Number <- < [0-9]+ >
%whitespace <- [ \t]*
)");

assert(static_cast(parser) == true);

// (3) Setup actions
parser["Additive"] = [](const SemanticValues &vs) {
switch (vs.choice()) {
case 0: // "Multiplicative '+' Additive"
return any_cast(vs[0]) + any_cast(vs[1]);
default: // "Multiplicative"
return any_cast(vs[0]);
}
};

parser["Multiplicative"] = [](const SemanticValues &vs) {
switch (vs.choice()) {
case 0: // "Primary '*' Multiplicative"
return any_cast(vs[0]) * any_cast(vs[1]);
default: // "Primary"
return any_cast(vs[0]);
}
};

parser["Number"] = [](const SemanticValues &vs) {
return vs.token_to_number();
};

// (4) Parse
parser.enable_packrat_parsing(); // Enable packrat parsing.

int val;
parser.parse(" (1 + 2) * 3 ", val);

assert(val == 9);
}
`

To show syntax errors in grammar text:

`cpp
auto grammar = R"(
# Grammar for Calculator...
Additive <- Multiplicative '+' Additive / Multiplicative
Multiplicative <- Primary '*' Multiplicative / Primary
Primary <- '(' Additive ')' / Number
Number <- < [0-9]+ >
%whitespace <- [ \t]*
)";

parser parser;

parser.set_logger([](size_t line, size_t col, const string& msg, const string &rule) {
cerr << line << ":" << col << ": " << msg << "\n";
});

auto ok = parser.load_grammar(grammar);
assert(ok);
`

There are four semantic actions available:

`cpp
[](const SemanticValues& vs, any& dt)
[](const SemanticValues& vs)
[](SemanticValues& vs, any& dt)
[](SemanticValues& vs)
`

SemanticValues value contains the following information:

* Semantic values
* Matched string information
* Token information if the rule is literal or uses a token boundary operator
* Choice number when the rule is 'prioritized choice'

any& dt is a 'read-write' context data which can be used for whatever purposes. The initial context data is set in peg::parser::parse method.

A semantic action can return a value of arbitrary data type, which will be wrapped by peg::any. If a user returns nothing in a semantic action, the first semantic value in the const SemanticValues& vs argument will be returned. (Yacc parser has the same behavior.)

Here shows the SemanticValues structure:

`cpp
struct SemanticValues : protected std::vector
{
// Input text
const char* path;
const char* ss;

// Matched string
std::string_view sv() const { return sv_; }

// Line number and column at which the matched string is
std::pair line_info() const;

// Tokens
std::vector tokens;
std::string_view token(size_t id = 0) const;

// Token conversion
std::string token_to_string(size_t id = 0) const;
template T token_to_number() const;

// Choice number (0 based index)
size_t choice() const;

// Transform the semantic value vector to another vector
template vector transform(size_t beg = 0, size_t end = -1) const;
}
`

The following example uses < ... > operator, which is token boundary operator.

`cpp
peg::parser parser(R"(
ROOT <- _ TOKEN (',' _ TOKEN)*
TOKEN <- < [a-z0-9]+ > _
_ <- [ \t\r\n]*
)");

parser["TOKEN"] = [](const SemanticValues& vs) {
// 'token' doesn't include trailing whitespaces
auto token = vs.token();
};

auto ret = parser.parse(" token1, token2 ");
`

We can ignore unnecessary semantic values from the list by using ~ operator.

`cpp
peg::parser parser(R"(
ROOT <- _ ITEM (',' _ ITEM _)*
ITEM <- ([a-z0-9])+
~_ <- [ \t]*
)");

parser["ROOT"] = & {
assert(vs.size() == 2); // should be 2 instead of 5.
};

auto ret = parser.parse(" item1, item2 ");
`

The following grammar is the same as the above.

`cpp
peg::parser parser(R"(
ROOT <- ~_ ITEM (',' ~_ ITEM ~_)*
ITEM <- ([a-z0-9])+
_ <- [ \t]*
)");
`

Semantic predicate support is available with a predicate action.

`cpp
peg::parser parser("NUMBER <- [0-9]+");

parser["NUMBER"] = [](const SemanticValues &vs) {
return vs.token_to_number();
};

parser["NUMBER"].predicate = [](const SemanticValues &vs,
const std::any & /dt/, std::string &msg) {
if (vs.token_to_number() != 100) {
msg = "value error!!";
return false;
}
return true;
};

long val;
auto ret = parser.parse("100", val);
assert(ret == true);
assert(val == 100);

ret = parser.parse("200", val);
assert(ret == false);
`

enter and leave actions are also available.

`cpp
parser["RULE"].enter = [](const Context &c, const char* s, size_t n, any& dt) {
std::cout << "enter" << std::endl;
};

parser["RULE"] = [](const SemanticValues& vs, any& dt) {
std::cout << "action!" << std::endl;
};

parser["RULE"].leave = [](const Context &c, const char* s, size_t n, size_t matchlen, any& value, any& dt) {
std::cout << "leave" << std::endl;
};
`

You can receive error information via a logger:

`cpp
parser.set_logger([](size_t line, size_t col, const string& msg) {
...
});

parser.set_logger([](size_t line, size_t col, const string& msg, const string &rule) {
...
});
`

Ignoring Whitespaces
--------------------

As you can see in the first example, we can ignore whitespaces between tokens automatically with %whitespace rule.

%whitespace rule can be applied to the following three conditions:

* trailing spaces on tokens
* leading spaces on text
* trailing spaces on literal strings in rules

These are valid tokens:

`
KEYWORD <- 'keyword'
KEYWORDI <- 'case_insensitive_keyword'
WORD <- < [a-zA-Z0-9] [a-zA-Z0-9-_]* > # token boundary operator is used.
IDNET <- < IDENT_START_CHAR IDENT_CHAR* > # token boundary operator is used.
`

The following grammar accepts one, "two three", four .

`
ROOT <- ITEM (',' ITEM)*
ITEM <- WORD / PHRASE
WORD <- < [a-z]+ >
PHRASE <- < '"' (!'"' .)* '"' >

%whitespace <- [ \t\r\n]*
`

Word expression
---------------

`cpp
peg::parser parser(R"(
ROOT <- 'hello' 'world'
%whitespace <- [ \t\r\n]*
%word <- [a-z]+
)");

parser.parse("hello world"); // OK
parser.parse("helloworld"); // NG
`

Capture/Backreference
---------------------

`cpp
peg::parser parser(R"(
ROOT <- CONTENT
CONTENT <- (ELEMENT / TEXT)*
ELEMENT <- $(STAG CONTENT ETAG)
STAG <- '<' $tag< TAG_NAME > '>'
ETAG <- ''
TAG_NAME <- 'b' / 'u'
TEXT <- TEXT_DATA
TEXT_DATA <- ![<] .
)");

parser.parse("This is a test text."); // OK
parser.parse("This is a test text."); // NG
parser.parse("This is a test text."); // NG
`

Dictionary
----------

| operator allows us to make a word dictionary for fast lookup by using Trie structure internally. We don't have to worry about the order of words.

`peg
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan' | 'January' | 'Feb' | 'February' | '...'
`

We are able to find which item is matched with choice().

`cpp
parser["MONTH"] = [](const SemanticValues &vs) {
auto id = vs.choice();
};
`

It supports the case-insensitive mode.

`peg
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan'i | 'January'i | 'Feb'i | 'February'i | '...'i
`

Cut operator
------------

↑ operator could mitigate the backtrack performance problem, but has a risk to change the meaning of grammar.

`peg
S <- '(' ↑ P ')' / '"' ↑ P '"' / P
P <- 'a' / 'b' / 'c'
`

When we parse (z with the above grammar, we don't have to backtrack in S after ( is matched, because a cut operator is inserted there.

Parameterized Rule or Macro
---------------------------

`peg


Syntax