cpp peglib
1.0.0
Pustaka PEG (Parsing Expression Grammars) khusus header C++17. Anda dapat langsung mulai menggunakannya hanya dengan menyertakan peglib.h dalam proyek Anda.
Karena perpustakaan ini hanya mendukung kompiler C++17, pastikan opsi kompiler -std=c++17 diaktifkan. ( /std:c++17 /Zc:__cplusplus untuk MSVC)
Anda juga dapat mencoba versi online PEG Playground di https://yhirose.github.io/cpp-peglib.
Sintaks PEG dijelaskan dengan baik di halaman 2 dalam dokumen oleh Bryan Ford. cpp-peglib juga mendukung sintaks tambahan berikut untuk saat ini:
'...'i (Operator literal yang tidak peka huruf besar-kecil)
[...]i (Operator kelas karakter yang tidak peka huruf besar-kecil)
[^...] (Operator kelas karakter yang dinegasikan)
[^...]i (Operator kelas karakter yang tidak peka huruf besar dan kecil)
{2,5} (Operator pengulangan seperti regex)
< ... > (Operator batas token)
~ (Abaikan operator)
x20 (karakter nomor hex)
u10FFFF (karakter Unicode)
%whitespace (Melompati spasi putih otomatis)
%word (Ekspresi kata)
$name( ... ) (Tangkap operator cakupan)
$name< ... > (Bernama operator penangkapan)
$name (Operator referensi balik)
| (Operator kamus)
↑ (Potong operator)
MACRO_NAME( ... ) (Aturan berparameter atau Makro)
{ precedence L - + L / * } (Mengurai ekspresi infiks)
%recovery( ... ) (Operator pemulihan kesalahan)
exp⇑label atau exp^label (Sintaks gula untuk (exp / %recover(label)) )
label { error_message "..." } (Instruksi pesan kesalahan)
{ no_ast_opt } (Tidak ada instruksi pengoptimalan node AST)
Pemeriksaan 'End of Input' akan dilakukan secara default. Untuk menonaktifkan pemeriksaan, disable_eoi_check .
Pustaka ini mendukung penguraian waktu linier yang dikenal sebagai penguraian Packrat .
CATATAN PENTING untuk beberapa distribusi Linux seperti Ubuntu dan CentOS: Perlu opsi -pthread saat menghubungkan. Lihat #23, #46 dan #62.
Saya yakin Anda akan menikmati artikel "Penguraian praktis dengan PEG dan cpp-peglib" yang luar biasa ini oleh bert hubert!
Ini adalah contoh kalkulator sederhana. Ini menunjukkan cara mendefinisikan tata bahasa, mengaitkan tindakan semantik dengan tata bahasa, dan menangani nilai semantik.
// (1) Sertakan file header#include <peglib.h>#include <assert.h>#include <iostream>menggunakan namespace pasak;menggunakan namespace std;int main(void) {/ // (2) Membuat parser
parser parser(R"( # Tata Bahasa untuk Kalkulator... Aditif <- Perkalian '+' Aditif / Perkalian Multiplikatif <- Primer '*' Perkalian / Primer Primer <- '(' Aditif ')' / Nomor Angka <- < [ 0-9]+ > %spasi putih <- [ t]* )"); menegaskan(static_cast<bool>(parser) == benar); // (3) Tindakan pengaturan
parser["Additive"] = [](const SemanticValues &vs) {switch (vs.choice()) {case 0: // "Multiplicative '+' Additive" mengembalikan any_cast<int>(vs[0]) + any_cast< int>(vs[1]);default: // "Perkalian" mengembalikan any_cast<int>(vs[0]);
}
};
parser["Perkalian"] = [](const Nilai Semantik &vs) {switch (vs.choice()) {kasus 0: // "Perkalian '*' Utama" kembalikan any_cast<int>(vs[0]) * any_cast< int>(vs[1]);default: // "Utama" mengembalikan any_cast<int>(vs[0]);
}
};
parser["Nomor"] = [](const Nilai Semantik &vs) {return vs.token_to_number<int>();
}; // (4) Mengurai
parser.enable_packrat_parsing(); // Aktifkan penguraian paket.
ke dalam val;
parser.parse("(1+2)*3",val); menegaskan(val == 9);
}Untuk menampilkan kesalahan sintaksis dalam teks tata bahasa:
tata bahasa otomatis = R"( # Tata Bahasa untuk Kalkulator... Aditif <- Perkalian '+' Aditif / Perkalian Multiplikatif <- Primer '*' Perkalian / Primer Primer <- '(' Aditif ')' / Nomor Nomor <- < [ 0-9]+ > %spasi <- [ t]*)";
pengurai pengurai;
parser.set_logger([](baris size_t, kolom size_t, string const& pesan, string const &aturan) {
cerr << baris << ":" << kolom << ": " << pesan << "n";
});auto ok = parser.load_grammar(grammar);assert(ok);Ada empat tindakan semantik yang tersedia:
[](const Nilai Semantik& vs, apa saja& dt) [](const Nilai Semantik& vs) [](Nilai Semantik& vs, apa saja& dt) [](Nilai Semantik& vs)
Nilai SemanticValues berisi informasi berikut:
Nilai semantik
Informasi string yang cocok
Informasi token jika aturannya literal atau menggunakan operator batas token
Nomor pilihan ketika aturannya adalah 'pilihan yang diprioritaskan'
any& dt adalah data konteks 'baca-tulis' yang dapat digunakan untuk tujuan apa pun. Data konteks awal diatur dalam metode peg::parser::parse .
Tindakan semantik dapat mengembalikan nilai tipe data arbitrer, yang akan dibungkus dengan peg::any . Jika pengguna tidak mengembalikan apa pun dalam tindakan semantik, nilai semantik pertama dalam argumen const SemanticValues& vs akan dikembalikan. (Pengurai Yacc memiliki perilaku yang sama.)
Berikut ini menunjukkan struktur SemanticValues :
struct SemanticValues : dilindungi std::vector<any>
{//Masukkan teks
jalur const char*; konstan char* ss; // String yang cocok
std::string_view sv() const { kembali sv_; } // Nomor baris dan kolom tempat string yang cocok berada
std::pasangan<ukuran_t, ukuran_t> line_info() const; // Token
std::vektor<std::string_view> token;
std::string_view token(size_t id = 0) const; // Konversi token
std::string token_to_string(ukuran_t id = 0) const; templat <nama ketik T> T token_to_number() const; // Nomor pilihan (indeks berdasarkan 0)
size_t pilihan() konstan; // Ubah vektor nilai semantik ke vektor lain
templat <nama ketik T> vektor<T> transform(ukuran_t mohon = 0, ukuran_t akhir = -1) const;
} Contoh berikut menggunakan operator < ... > yang merupakan operator batas token .
pasak::parser parser(R"( ROOT <- _ TOKEN (',' _ TOKEN)* TOKEN <- < [a-z0-9]+ > _ _ <- [ trn]*)");
parser["TOKEN"] = [](const SemanticValues& vs) { // 'token' tidak menyertakan spasi tambahan
token otomatis = vs.token();
};auto ret = parser.parse("token1, token2"); Kita dapat mengabaikan nilai semantik yang tidak perlu dari daftar dengan menggunakan operator ~ .
pasak::parser parser(R"( ROOT <- _ ITEM (',' _ ITEM _)* ITEM <- ([a-z0-9])+ ~_ <- [ t]*)");
parser["ROOT"] = [&](const Nilai Semantik& vs) { menegaskan(vs.ukuran() == 2); // seharusnya 2, bukan 5.};auto ret = parser.parse(" item1, item2 ");Tata bahasa berikut ini sama dengan tata bahasa di atas.
pasak::parser parser(R"( ROOT <- ~_ ITEM (',' ~_ ITEM ~_)* ITEM <- ([a-z0-9])+ _ <- [ t]*)");Dukungan predikat semantik tersedia dengan tindakan predikat .
pasak::parser parser("NOMOR <- [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) {
pesan = "kesalahan nilai!!";return false;
} mengembalikan nilai benar;
};val panjang;auto ret = parser.parse("100", val);assert(ret == true);assert(val == 100);
ret = parser.parse("200", val);assert(ret == false);tindakan masuk dan keluar juga tersedia.
parser["RULE"].enter = [](const Konteks &c, const char* s, size_t n, any& dt) {
std::cout << "masukkan" << std::endl;
};
parser["RULE"] = [](const SemanticValues& vs, any& dt) {
std::cout << "aksi!" << std::endl;
};
parser["RULE"].leave = [](const Konteks &c, const char* s, size_t n, size_t matchlen, nilai& apa pun, apa saja& dt) {
std::cout << "pergi" << std::endl;
};Anda dapat menerima informasi kesalahan melalui logger:
parser.set_logger([](baris size_t, kolom size_t, string const& pesan) {
...
});
parser.set_logger([](baris size_t, kolom size_t, string const& pesan, string const &aturan) {
...
}); Seperti yang Anda lihat pada contoh pertama, kita dapat mengabaikan spasi antar token secara otomatis dengan aturan %whitespace .
Aturan %whitespace dapat diterapkan pada tiga kondisi berikut:
spasi tambahan pada token
spasi terdepan pada teks
spasi tambahan pada string literal dalam aturan
Ini adalah token yang valid:
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.
Tata bahasa berikut menerima one, "two three", four .
ROOT <- ITEM (',' ITEM)*
ITEM <- WORD / PHRASE
WORD <- < [a-z]+ >
PHRASE <- < '"' (!'"' .)* '"' >
%whitespace <- [ trn]* pasak::parser parser(R"( ROOT <- 'halo' 'dunia' %spasi <- [ trn]* %kata <- [az]+)");
parser.parse("halo dunia"); // OKparser.parse("helloworld"); // tidak peg::parser parser(R"( ROOT <- KONTEN KONTEN <- (ELEMEN / TEKS)* ELEMEN <- $(STAG CONTENT ETAG) STAG <- '<' $tag< TAG_NAME > '>' ETAG <- '< /' $tag '>' TAG_NAME <- 'b' / 'u' TEKS <- TEXT_DATA TEXT_DATA <- ![<] .)");
parser.parse("Ini adalah <b>teks <u>tes</u></b>."); // OKparser.parse("Ini adalah <b>teks <u>pengujian</b></u>."); // NGparser.parse("Ini adalah <b><u>teks pengujian</b>."); // tidak | Operator memungkinkan kita membuat kamus kata untuk pencarian cepat dengan menggunakan struktur Trie secara internal. Kita tidak perlu khawatir tentang urutan kata.
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan' | 'January' | 'Feb' | 'February' | '...' Kami dapat menemukan item mana yang cocok dengan choice() .
parser["BULAN"] = [](const Nilai Semantik &vs) { id otomatis = vs.pilihan();
};Ini mendukung mode peka huruf besar-kecil.
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan'i | 'January'i | 'Feb'i | 'February'i | '...'i ↑ operator dapat mengurangi masalah kinerja backtrack, namun memiliki risiko mengubah arti tata bahasa.
S <- '(' ↑ P ')' / '"' ↑ P '"' / P
P <- 'a' / 'b' / 'c' Saat kita mengurai (z dengan tata bahasa di atas, kita tidak perlu melakukan backtrack di S setelah ( cocok, karena disisipkan operator cut di sana.
# 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 > _Mengenai algoritma pendakian prioritas , silakan lihat artikel ini.
parser parser(R"( EKSPRESI <- INFIX_EXPRESSION(ATOM, OPERATOR) ATOM <- NUMBER / '(' EXPRESSION ')' OPERATOR <- < [-+/*] > NUMBER <- < '-'? [0-9 ]+ > %spasi <- [ t]* # Deklarasikan urutan prioritas INFIX_EXPRESSION(A, O) <- A (O A)* { diutamakan L + - L * / })");
parser["INFIX_EXPRESSION"] = [](const SemanticValues& vs) -> long { hasil otomatis = 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 '+': hasil += nomor; merusak; huruf '-': hasil -= angka; merusak; huruf '*': hasil *= angka; merusak; huruf '/': hasil /= angka; merusak;
}
} mengembalikan hasil;
};
parser["OPERATOR"] = [](const SemanticValues& vs) { return *vs.sv(); };
parser["NUMBER"] = [](const SemanticValues& vs) { return vs.token_to_number<long>(); };val panjang;
parser.parse(" -1 + (1 + 2) * 3 - -1", val);menegaskan(val == 9);instruksi prioritas hanya dapat diterapkan pada aturan gaya 'daftar' berikut.
Rule <- Atom (Operator Atom)* {
precedence
L - +
L / *
R ^
}instruksi prioritas berisi entri info prioritas. Setiap entri dimulai dengan asosiatif yaitu 'L' (kiri) atau 'R' (kanan), kemudian diikuti token literal operator. Entri pertama memiliki tingkat pesanan tertinggi.
cpp-peglib mampu menghasilkan AST (Pohon Sintaks Abstrak) saat parsing. metode enable_ast pada kelas peg::parser mengaktifkan fitur tersebut.
CATATAN: Node AST menyimpan token yang sesuai sebagai std::string_vew untuk kinerja dan penggunaan memori yang lebih sedikit. Merupakan tanggung jawab pengguna untuk menyimpan teks sumber asli bersama dengan pohon AST yang dihasilkan.
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 menghapus node yang berlebihan untuk membuat AST lebih sederhana. Jika Anda ingin menonaktifkan perilaku ini dari aturan tertentu, instruksi no_ast_opt dapat digunakan.
Secara internal memanggil peg::AstOptimizer untuk melakukan pekerjaan itu. Anda dapat membuat pengoptimal AST sendiri sesuai kebutuhan Anda.
Lihat penggunaan sebenarnya dalam contoh kalkulator AST dan contoh bahasa PL/0.
Daripada membuat parser dengan mengurai teks sintaksis PEG, kita juga dapat membuat parser dengan tangan menggunakan kombinator parser . Berikut ini contohnya:
menggunakan pasak namespace;menggunakan tag namespace std;vektor<string>;
Definisi ROOT, TAG_NAME, _;
ROOT <= seq(_, zom(seq(chr('['), TAG_NAME, chr(']'), _)));
TAG_NAME <= oom(seq(npd(chr(']')), titik())), [&](const Nilai Semantik& vs) {
tag.push_back(vs.token_to_string());
};
_ <= zom(cls(" t"));auto ret = ROOT.parse(" [tag1] [tag:2] [tag-3] ");Berikut ini adalah operator yang tersedia:
| Operator | Keterangan | Operator | Keterangan |
|---|---|---|---|
| seq | Urutan | cho | Pilihan yang Diprioritaskan |
| zom | Nol atau Lebih | oh | Satu atau Lebih |
| memilih | Opsional | apd | Dan predikat |
| npd | Bukan predikat | menyala | String literal |
| liti | String Literal yang tidak peka huruf besar-kecil | kl | Kelas karakter |
| ncls | Kelas Karakter yang dinegasikan | kr | Karakter |
| dot | Karakter apa pun | tok | Batas token |
| tanda | Abaikan nilai semantik | csc | Cakupan tangkapan |
| topi | Menangkap | bkr | Referensi kembali |
| dik | Kamus | pra | Ekspresi infiks |
| rek | Ekspresi infiks | usr | Pengurai yang ditentukan pengguna |
| reputasi | Pengulangan |
Dimungkinkan untuk menambahkan/mengganti definisi.
sintaks otomatis = R"( ROOT <- _ 'Halo' _ NAMA '!' _)";
Aturan tambahan_aturan = {
{"NAME", usr([](const char* s, size_t n, SemanticValues& vs, any& dt) -> size_t { vektor statis<string> nama = { "PEG", "BNF" }; for (const auto& nama : nama) {if (nama.ukuran() <= n && !nama.bandingkan(0, nama.ukuran(), s, nama.ukuran())) { kembalikan nama.ukuran();
} kembali -1; // kesalahan penguraian})
},
{"~_", zom(cls(" trn"))
}
};auto g = parser(sintaks, aturan_tambahan);assert(g.parse(" Halo BNF! ")); cpp-peglib menerima teks UTF8. . cocok dengan titik kode Unicode. Juga, ini mendukung u???? .
cpp-peglib mendukung laporan posisi kesalahan kegagalan terjauh seperti yang dijelaskan dalam dokumen asli Bryan Ford.
Untuk laporan kesalahan dan pemulihan yang lebih baik, cpp-peglib mendukung operator 'pemulihan' dengan label yang dapat dikaitkan dengan ekspresi pemulihan dan pesan kesalahan khusus. Ide ini berasal dari makalah fantastis "Pemulihan Kesalahan Sintaks dalam Tata Bahasa Parsing Ekspresi" oleh Sergio Medeiros dan Fabio Mascarenhas.
Pesan khusus mendukung %t yang merupakan pengganti token tak terduga, dan %c untuk karakter Unicode tak terduga.
Berikut ini contoh tata bahasa mirip 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)* / (!')' .)* Misalnya, ';'^semi adalah gula sintaksis untuk (';' / %recovery(semi)) . %recover operator mencoba memulihkan kesalahan di ';' dengan melewatkan teks masukan dengan ekspresi pemulihan semi . semi juga dikaitkan dengan pesan khusus "titik koma tidak ada dalam tugas".
Inilah hasilnya:
> cat sample.javapublic class Contoh { public static void main(String[] args) {int n = 5;int f = 1; while( < n) { f = f * n; n = n - 1};Sistem.keluar.println(f);
}
}
> peglint java.peg sample.javasample.java:5:12: kesalahan sintaksis, '<', mengharapkan '(', <NUMBER>, <NAME>.sample.java:8:5: tidak ada titik koma di tugas.sample .java:8:6: pernyataan tidak validSeperti yang Anda lihat, sekarang ini dapat menampilkan lebih dari satu kesalahan, dan memberikan pesan kesalahan yang lebih bermakna dibandingkan pesan default.
Kami dapat mengaitkan pesan kesalahan khusus ke definisi.
# 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...
CATATAN: Jika ada lebih dari satu elemen dengan instruksi pesan kesalahan dalam pilihan yang diprioritaskan, fitur ini mungkin tidak berfungsi seperti yang Anda harapkan.
Kita dapat mengubah aturan definisi awal seperti di bawah ini.
tata bahasa otomatis = R"( Mulai <- A A <- B (',' B)* B <- '[satu]' / '[dua]' %spasi <- [ tn]*)";
pasak::parser parser(tata bahasa, "A"); // Aturan Awal adalah "A"
orpeg::pengurai pengurai;
parser.load_grammar(tata bahasa, "A"); // Aturan Awal adalah "A"parser.parse(" [satu] , [dua] "); // OKE> 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 > 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)Kalkulator
Kalkulator (dengan operator parser)
Kalkulator (versi AST)
Kalkulator (mengurai ekspresi berdasarkan pendakian yang diutamakan)
Kalkulator (versi AST dan penguraian ekspresi dengan prioritas pendakian)
Kompiler JIT PL/0 kecil dalam waktu kurang dari 900 LOC dengan parser LLVM dan PEG
Bahasa Pemrograman hanya untuk menulis program Fizz Buzz. :)
Lisensi MIT (© 2022 Yuji Hirose)
