cpp peglib
1.0.0
C++17 ヘッダーのみの PEG (解析式文法) ライブラリ。 peglib.hプロジェクトに組み込むだけですぐに使い始めることができます。
このライブラリは C++17 コンパイラのみをサポートしているため、コンパイラ オプション-std=c++17が有効になっていることを確認してください。 (MSVC の場合は/std:c++17 /Zc:__cplusplus )
https://yhirose.github.io/cpp-peglib でオンライン バージョンの PEG Playground を試すこともできます。
PEG 構文については、Bryan Ford によるドキュメントの 2 ページに詳しく説明されています。 cpp-peglib は、現時点では次の追加構文もサポートしています。
'...'i (大文字と小文字を区別しないリテラル演算子)
[...]i (大文字と小文字を区別しない文字クラス演算子)
[^...] (否定文字クラス演算子)
[^...]i (大文字と小文字を区別しない否定文字クラス演算子)
{2,5} (正規表現のような繰り返し演算子)
< ... > (トークン境界演算子)
~ (演算子を無視)
x20 (16 進数文字)
u10FFFF (Unicode 文字)
%whitespace (空白の自動スキップ)
%word (単語式)
$name( ... ) (キャプチャ スコープ演算子)
$name< ... > (名前付きキャプチャ演算子)
$name (後方参照演算子)
| (辞書演算子)
↑ (カット演算子)
MACRO_NAME( ... ) (パラメータ化されたルールまたはマクロ)
{ precedence L - + L / * } (中置式の解析)
%recovery( ... ) (エラー回復演算子)
exp⇑labelまたはexp^label ( (exp / %recover(label))の構文シュガー)
label { error_message "..." } (エラーメッセージの指示)
{ no_ast_opt } (AST ノード最適化命令なし)
デフォルトでは「入力の終わり」チェックが行われます。チェックを無効にするには、 disable_eoi_checkを呼び出してください。
このライブラリは、 Packrat解析として知られる線形時間解析をサポートしています。
Ubuntu や CentOS などの一部の Linux ディストリビューションの重要な注意: リンク時に-pthreadオプションが必要です。 #23、#46、#62 を参照してください。
bert Hubert によるこの優れた記事「PEG と cpp-peglib を使用した実践的な解析」を楽しんでいただけると確信しています。
これは簡単な計算機のサンプルです。文法を定義し、意味論的なアクションを文法に関連付け、意味論的な値を処理する方法を示します。
// (1) ヘッダー ファイルをインクルードします#include <peglib.h>#include <assert.h>#include <iostream>using namespace peg;using namespace std;int main(void) { // (2) パーサーを作成します
parser parser(R"( # 電卓の文法... 加法 <- 乗法 '+' 加法 / 乗法 乗法 <- 主 '*' 乗法 / 主 主 <- '(' 加法 ')' / 数値 Number <- < [ 0-9]+ > %whitespace <- [ t]* )"); assert(static_cast<bool>(parser) == true); // (3) アクションの設定
parser["Additive"] = [](const SemanticValues &vs) {switch (vs.choice()) {case 0: // "乗法 '+' 加算" return any_cast<int>(vs[0]) + any_cast< int>(vs[1]);default: // "乗算" return any_cast<int>(vs[0]);
}
};
parser["Multiplicative"] = [](const SemanticValues &vs) {switch (vs.choice()) {case 0: // "Primary '*' Multiplicative" return any_cast<int>(vs[0]) * any_cast< int>(vs[1]);default: // "プライマリ" return any_cast<int>(vs[0]);
}
};
parser["Number"] = [](const SemanticValues &vs) {return vs.token_to_number<int>();
}; // (4) 解析する
parser.enable_packrat_parsing(); // Packrat 解析を有効にします。
整数型;
parser.parse(" (1 + 2) * 3 ", val); アサート(val == 9);
}文法テキストの構文エラーを表示するには:
auto grammar = R"( # 電卓の文法... 加法 <- 乗法 '+' 加法 / 乗法 乗法 <- 主 '*' 乗法 / 主 主 <- '(' 加法 ')' / Number Number <- < [ 0-9]+ > %whitespace <- [ t]*)";
パーサー パーサー;
parser.set_logger([](size_t 行、size_t 列、const 文字列&メッセージ、const 文字列&ルール) {
cerr << line << ":" <<col << ": " << msg << "n";
});auto ok = parser.load_grammar(grammar);assert(ok);使用可能なセマンティック アクションは 4 つあります。
[](const SemanticValues& vs, any& dt) [](const SemanticValues& vs) [](SemanticValues& vs, any& dt) [](SemanticValues& vs)
SemanticValues値には次の情報が含まれます。
意味値
一致した文字列情報
ルールがリテラルであるか、トークン境界演算子を使用している場合のトークン情報
ルールが「優先選択」の場合の選択肢番号
any& dtどのような目的にも使用できる「読み取り/書き込み」コンテキスト データです。初期コンテキストデータはpeg::parser::parseメソッドで設定されます。
セマンティック アクションは、 peg::anyでラップされる任意のデータ型の値を返すことができます。ユーザーがセマンティック アクションで何も返さない場合は、 const SemanticValues& vs引数の最初のセマンティック値が返されます。 (Yacc パーサーも同じ動作をします。)
SemanticValues構造を次に示します。
struct SemanticValues : protected std::vector<any>
{ // テキストを入力
const char* パス; const char* ss; // 一致した文字列
std::string_view sv() const {戻り値 sv_; } // 一致した文字列が存在する行番号と列
std::pair<size_t, size_t> line_info() const; // トークン
std::vector<std::string_view> トークン;
std::string_view トークン (size_t id = 0) const; // トークン変換
std::string token_to_string(size_t id = 0) const; テンプレート <typename T> T token_to_number() const; // 選択肢番号 (0 から始まるインデックス)
size_t Choice() const; // 意味値ベクトルを別のベクトルに変換します
テンプレート <typename T> Vector<T>transform(size_t beg = 0, size_t end = -1) const;
}次の例では、トークン境界演算子である< ... >演算子を使用します。
peg::parser parser(R"( ROOT <- _ TOKEN (',' _ TOKEN)* TOKEN <- < [a-z0-9]+ > _ _ <- [ trn]*)");
parser["TOKEN"] = [](const SemanticValues& vs) { // 'token' には末尾の空白は含まれません
自動トークン = vs.token();
};auto ret = parser.parse(" token1, token2 "); ~演算子を使用すると、リストから不要なセマンティック値を無視できます。
peg::parser parser(R"( ROOT <- _ ITEM (',' _ ITEM _)* ITEM <- ([a-z0-9])+ ~_ <- [ t]*)");
parser["ROOT"] = [&](const SemanticValues& vs) {assert(vs.size() == 2); // 5 ではなく 2 にする必要があります。};auto ret = parser.parse(" item1, item2 ");以下の文法は上記と同じです。
peg::parser parser(R"( ROOT <- ~_ ITEM (',' ~_ ITEM ~_)* ITEM <- ([a-z0-9])+ _ <- [ t]*)");セマンティック述語のサポートは、述語アクションで利用できます。
peg::parser parser("NUMBER <- [0-9]+");
parser["NUMBER"] = [](const SemanticValues &vs) { return vs.token_to_number<long>();
};
parser["NUMBER"].predicate = [](const SemanticValues &vs,const std::any & /*dt*/, std::string &msg) { if (vs.token_to_number<long>() != 100) {
msg = "値エラー!!"; false を返します。
true を返します。
};long val;auto ret = parser.parse("100", val);assert(ret == true);assert(val == 100);
ret = parser.parse("200", val);assert(ret == false);入力および退出アクションも使用できます。
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 << "アクション!" << 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;
};ロガーを介してエラー情報を受信できます。
parser.set_logger([](size_t 行、size_t 列、const string& msg) {
...
});
parser.set_logger([](size_t 行、size_t 列、const 文字列&メッセージ、const 文字列&ルール) {
...
});最初の例でわかるように、 %whitespaceルールを使用すると、トークン間の空白を自動的に無視できます。
%whitespaceルールは、次の 3 つの条件に適用できます。
トークンの末尾のスペース
テキストの先頭のスペース
ルール内のリテラル文字列の末尾のスペース
これらは有効なトークンです:
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.
次の文法はone, "two three", fourを受け入れます。
ROOT <- ITEM (',' ITEM)*
ITEM <- WORD / PHRASE
WORD <- < [a-z]+ >
PHRASE <- < '"' (!'"' .)* '"' >
%whitespace <- [ trn]*peg::parser parser(R"( ROOT <- 'hello' 'world' %whitespace <- [ trn]* %word <- [az]+)");
parser.parse("hello world"); // OKparser.parse("helloworld"); // NGpeg::parser parser(R"( ROOT <- CONTENT CONTENT <- (ELEMENT / TEXT)* ELEMENT <- $(STAG CONTENT ETAG) STAG <- '<' $tag< TAG_NAME > '>' ETAG <- '< /' $tag '>' TAG_NAME <- 'b' / 'u' テキスト <- TEXT_DATA TEXT_DATA <- ![<] .)");
parser.parse("これは<b><u>テスト</u>テキスト</b>です。"); // OKparser.parse("これは<b><u>テスト</b> テキスト</u>です。"); // NGparser.parse("これは<b><u>テスト テキスト</b>です。"); // NG|演算子を使用すると、内部で Trie 構造を使用して高速検索のための単語辞書を作成できます。言葉の順序を気にする必要はありません。
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan' | 'January' | 'Feb' | 'February' | '...' choice()を使用すると、どの項目が一致するかを見つけることができます。
parser["MONTH"] = [](const SemanticValues &vs) { auto id = vs.choice();
};大文字と小文字を区別しないモードをサポートします。
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan'i | 'January'i | 'Feb'i | 'February'i | '...'i↑演算子はバックトラックのパフォーマンスの問題を軽減できますが、文法の意味を変えるリスクがあります。
S <- '(' ↑ P ')' / '"' ↑ P '"' / P
P <- 'a' / 'b' / 'c'上記の文法で(z解析するとき)、そこにカット演算子が挿入されるため、 (が一致した後にSでバックトラックする必要はありません。
# Syntax
Start ← _ Expr
Expr ← Sum
Sum ← List(Product, SumOpe)
Product ← List(Value, ProOpe)
Value ← Number / T('(') Expr T(')')
# Token
SumOpe ← T('+' / '-')
ProOpe ← T('*' / '/')
Number ← T([0-9]+)
~_ ← [ trn]*
# Macro
List(I, D) ← I (D I)*
T(x) ← < x > _優先順位上昇アルゴリズムについては、こちらの記事をご覧ください。
パーサー parser(R"( EXPRESSION <- INFIX_EXPRESSION(ATOM, OPERATOR) ATOM <- NUMBER / '(' EXPRESSION ')' OPERATOR <- < [-+/*] > NUMBER <- < '-'? [0-9 ]+ > %whitespace <- [ t]* # 優先順位を宣言 INFIX_EXPRESSION(A, O) <- A (O A)* { 優先順位 L + - L * / })");
parser["INFIX_EXPRESSION"] = [](const SemanticValues& vs) -> long { auto result = any_cast<long>(vs[0]); if (vs.size() > 1) {auto ope = any_cast<char>(vs[1]);auto num = any_cast<long>(vs[2]);switch (ope) { case '+': result += 数値;壊す; ケース '-': 結果 -= 数値;壊す; ケース '*': 結果 *= 数値;壊す; ケース '/': 結果 /= 数値;壊す;
}
結果を返します。
};
parser["OPERATOR"] = [](const SemanticValues& vs) { return *vs.sv(); };
parser["NUMBER"] = [](const SemanticValues& vs) { return vs.token_to_number<long>(); };長い値;
parser.parse(" -1 + (1 + 2) * 3 - -1", val);assert(val == 9);優先順位命令は、次の「リスト」スタイルのルールにのみ適用できます。
Rule <- Atom (Operator Atom)* {
precedence
L - +
L / *
R ^
}precedence命令には、優先情報エントリが含まれます。各エントリは、「L」(左) または「R」(右) の結合性で始まり、演算子リテラルトークンが続きます。最初のエントリの順序レベルが最も高くなります。
cpp-peglib は、解析時に AST (抽象構文ツリー) を生成できます。 peg::parserクラスのenable_astメソッドは、この機能を有効にします。
注: AST ノードは、パフォーマンスとメモリ使用量の削減のために、対応するトークンをstd::string_vewとして保持します。生成された AST ツリーとともに元のソース テキストを保管するのはユーザーの責任です。
peg::parser parser(R"(
...
definition1 <- ... { no_ast_opt }
definition2 <- ... { no_ast_opt }
...
)");
parser.enable_ast();
shared_ptr<peg::Ast> ast;
if (parser.parse("...", ast)) {
cout << peg::ast_to_s(ast);
ast = parser.optimize_ast(ast);
cout << peg::ast_to_s(ast);
} optimize_ast冗長なノードを削除して AST を簡素化します。特定のルールでこの動作を無効にしたい場合は、 no_ast_opt命令を使用できます。
内部的にpeg::AstOptimizer呼び出してジョブを実行します。ニーズに合わせて独自の AST オプティマイザーを作成できます。
AST 計算機の例と PL/0 言語の例で実際の使用法を参照してください。
PEG 構文テキストを解析してパーサーを作成する代わりに、パーサー コンビネータを使用して手動でパーサーを構築することもできます。以下に例を示します。
ネームスペース peg の使用;ネームスペース std の使用;vector<string> タグ;
定義 ROOT、TAG_NAME、_;
ROOT <= seq(_, zom(seq(chr('['), TAG_NAME, chr(']'), _)));
TAG_NAME <= oom(seq(npd(chr(']')), dot())), [&](const SemanticValues& vs) {
tags.push_back(vs.token_to_string());
};
_ <= zom(cls(" t"));auto ret = ROOT.parse(" [tag1] [tag:2] [tag-3] ");使用可能な演算子は次のとおりです。
| オペレーター | 説明 | オペレーター | 説明 |
|---|---|---|---|
| 連続 | 順序 | チョー | 優先順位のある選択 |
| ゾム | ゼロ以上 | うーん | 1 つ以上 |
| 選択する | オプション | APD | そして述語 |
| NPD | 述語ではありません | 点灯 | リテラル文字列 |
| リティ | 大文字と小文字を区別しないリテラル文字列 | CLS | 文字クラス |
| NCLS | 否定文字クラス | chr | キャラクター |
| ドット | どのキャラクターでも | トク | トークン境界 |
| 点火する | 意味値を無視する | csc | キャプチャ範囲 |
| キャップ | 捕獲 | BKR | 後方参照 |
| ディック | 辞書 | 前 | 中置式 |
| 録音 | 中置式 | ユーザー | ユーザー定義のパーサー |
| 担当者 | 繰り返し |
定義を追加/上書きすることが可能です。
自動構文 = R"( ROOT <- _ 'Hello' _ NAME '!' _)";
ルール追加_ルール = {
{"NAME", usr([](const char* s, size_t n, SemanticValues& vs, any& dt) -> size_t { static Vector<string> names = { "PEG", "BNF" }; for (const auto& name : names) {if (name.size() <= n && !name.compare(0, name.size(), s, name.size())) { return name.size(); // 処理された長さ}
-1 を返します。 // 解析エラー})
}、
{"~_", zom(cls(" trn"))
}
};auto g = parser(syntax,Additional_rules);assert(g.parse(" Hello BNF! "));cpp-peglib は UTF8 テキストを受け入れます。 . Unicode コードポイントと一致します。また、それはu???? 。
cpp-peglib は、Bryan Ford のオリジナル文書で説明されているように、最も遠い障害エラー位置レポートをサポートしています。
エラー レポートとリカバリを改善するために、cpp-peglib は、リカバリ式とカスタム エラー メッセージに関連付けることができるラベルを持つ「recovery」演算子をサポートしています。このアイデアは、Sergio Medeiros と Fabio Mascarenhas による素晴らしい論文「Syntax Error Recovery in Parsing Expression Grammars」から来ています。
カスタム メッセージは、予期しないトークンのプレースホルダーである%tと、予期しない Unicode 文字の%cをサポートしています。
Java に似た文法の例を次に示します。
# java.peg
Prog ← 'public' 'class' NAME '{' 'public' 'static' 'void' 'main' '(' 'String' '[' ']' NAME ')' BlockStmt '}'
BlockStmt ← '{' (!'}' Stmt^stmtb)* '}' # Annotated with `stmtb`
Stmt ← IfStmt / WhileStmt / PrintStmt / DecStmt / AssignStmt / BlockStmt
IfStmt ← 'if' '(' Exp ')' Stmt ('else' Stmt)?
WhileStmt ← 'while' '(' Exp^condw ')' Stmt # Annotated with `condw`
DecStmt ← 'int' NAME ('=' Exp)? ';'
AssignStmt ← NAME '=' Exp ';'^semia # Annotated with `semi`
PrintStmt ← 'System.out.println' '(' Exp ')' ';'
Exp ← RelExp ('==' RelExp)*
RelExp ← AddExp ('<' AddExp)*
AddExp ← MulExp (('+' / '-') MulExp)*
MulExp ← AtomExp (('*' / '/') AtomExp)*
AtomExp ← '(' Exp ')' / NUMBER / NAME
NUMBER ← < [0-9]+ >
NAME ← < [a-zA-Z_][a-zA-Z_0-9]* >
%whitespace ← [ tn]*
%word ← NAME
# Recovery operator labels
semia ← '' { error_message "missing semicolon in assignment." }
stmtb ← (!(Stmt / 'else' / '}') .)* { error_message "invalid statement" }
condw ← &'==' ('==' RelExp)* / &'<' ('<' AddExp)* / (!')' .)*たとえば、 ';'^semi (';' / %recovery(semi))の糖衣構文です。 %recover演算子は「;」のエラーを回復しようとします。回復式semiを使用して入力テキストをスキップします。また、 semi 、「割り当てにセミコロンがありません」というカスタム メッセージに関連付けられています。
結果は次のとおりです。
> catサンプル.javapublicクラス 例 { public static void main(String[] args) {int n = 5;int f = 1;while( < n) { f = f * n; n = n - 1};System.out.println(f);
}
}
> peglint java.peg sample.javasample.java:5:12: 構文エラー、予期しない '<'、期待される '('、<NUMBER>、<NAME>.sample.java:8:5: assign.sample にセミコロンがありません.java:8:6: 無効なステートメントご覧のとおり、複数のエラーを表示し、デフォルト メッセージよりも意味のあるエラー メッセージを提供できるようになりました。
カスタム エラー メッセージを定義に関連付けることができます。
# custom_message.peg
START <- CODE (',' CODE)*
CODE <- < '0x' [a-fA-F0-9]+ > { error_message 'code format error...' }
%whitespace <- [ t]*> cat custom_message.txt 0x1234,0x@@@@,0xABCD > peglint custom_message.peg custom_message.txt custom_message.txt:1:8: code format error...
注: 優先順位の高い選択肢にエラー メッセージの指示を持つ要素が複数ある場合、この機能は期待どおりに動作しない可能性があります。
以下のように開始定義ルールを変更できます。
auto grammar = R"( Start <- A A <- B (',' B)* B <- '[one]' / '[two]' %whitespace <- [ tn]*)";
peg::parser parser(文法, "A"); // 開始ルールは「A」です
orpeg::parser パーサー;
parser.load_grammar(文法, "A"); // 開始ルールは "A"parser.parse(" [one] , [two] "); // わかりました> cd lint > mkdir build > cd build > cmake .. > make > ./peglint usage: grammar_file_path [source_file_path] options: --source: source text --packrat: enable packrat memoise --ast: show AST tree --opt, --opt-all: optimize all AST nodes except nodes selected with `no_ast_opt` instruction --opt-only: optimize only AST nodes selected with `no_ast_opt` instruction --trace: show concise trace messages --profile: show profile report --verbose: verbose output for trace and profile
> cat a.peg
Additive <- Multiplicative '+' Additive / Multiplicative
Multiplicative <- Primary '*' Multiplicative / Primary
Primary <- '(' Additive ')' / Number
%whitespace <- [ trn]*
> peglint a.peg
[commandline]:3:35: 'Number' is not defined.> cat a.peg
Additive <- Multiplicative '+' Additive / Multiplicative
Multiplicative <- Primary '*' Multiplicative / Primary
Primary <- '(' Additive ')' / Number
Number <- < [0-9]+ >
%whitespace <- [ trn]*
> peglint --source "1 + a * 3" a.peg
[commandline]:1:3: syntax error> cat a.txt 1 + 2 * 3 > peglint --ast a.peg a.txt + Additive + Multiplicative + Primary - Number (1) + Additive + Multiplicative + Primary - Number (2) + Multiplicative + Primary - Number (3)
> peglint --ast --opt --source "1 + 2 * 3" a.peg + Additive - Multiplicative[Number] (1) + Additive[Multiplicative] - Primary[Number] (2) - Multiplicative[Number] (3)
no_ast_opt命令を使用して AST 最適化を調整する> cat a.peg
Additive <- Multiplicative '+' Additive / Multiplicative
Multiplicative <- Primary '*' Multiplicative / Primary
Primary <- '(' Additive ')' / Number { no_ast_opt }
Number <- < [0-9]+ >
%whitespace <- [ trn]*
> peglint --ast --opt --source "1 + 2 * 3" a.peg
+ Additive/0
+ Multiplicative/1[Primary]
- Number (1)
+ Additive/1[Multiplicative]
+ Primary/1
- Number (2)
+ Multiplicative/1[Primary]
- Number (3)
> peglint --ast --opt-only --source "1 + 2 * 3" a.peg
+ Additive/0
+ Multiplicative/1
- Primary/1[Number] (1)
+ Additive/1
+ Multiplicative/0
- Primary/1[Number] (2)
+ Multiplicative/1
- Primary/1[Number] (3)電卓
計算機 (パーサー演算子付き)
電卓（AST版）
計算機 (優先順位の上昇による式の解析)
計算機 (AST バージョンおよび優先順位上昇による式の解析)
LLVM および PEG パーサーを備えた 900 LOC 未満の小型 PL/0 JIT コンパイラー
Fizz Buzz プログラムを書くためだけのプログラミング言語。 :)
MIT ライセンス (© 2022 廣瀬裕二)
