cpp peglib
1.0.0
Библиотека PEG (грамматики выражений синтаксического анализа) C++17 только для заголовков. Вы можете начать использовать его прямо сейчас, просто включив peglib.h в свой проект.
Поскольку эта библиотека поддерживает только компиляторы C++17, убедитесь, что опция компилятора -std=c++17 включена. ( /std:c++17 /Zc:__cplusplus для MSVC)
Вы также можете попробовать онлайн-версию PEG Playground по адресу https://yhirose.github.io/cpp-peglib.
Синтаксис PEG хорошо описан на странице 2 документа Брайана Форда. cpp-peglib на данный момент также поддерживает следующий дополнительный синтаксис:
'...'i (литеральный оператор, нечувствительный к регистру)
[...]i (оператор класса символов без учета регистра)
[^...] (оператор класса отрицательных символов)
[^...]i (оператор класса отрицательных символов без учета регистра)
{2,5} (оператор повторения, подобный регулярному выражению)
< ... > (Оператор границы токена)
~ (игнорировать оператор)
x20 (шестнадцатеричный символ)
u10FFFF (символ Юникода)
%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 .
ВАЖНОЕ ПРИМЕЧАНИЕ для некоторых дистрибутивов Linux, таких как Ubuntu и CentOS: при связывании требуется опция -pthread . См. № 23, № 46 и № 62.
Я уверен, что вам понравится эта превосходная статья Берта Хьюберта «Практический анализ с помощью 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"( # Грамматика для калькулятора... Аддитив <- Мультипликативный '+' Аддитивный / Мультипликативный Мультипликативный <- Первичный '*' Мультипликативный / Первичный Первичный <- '(' Аддитивный ')' / Число Число <- < [ 0-9]+ > %whitespace <- [ t]* )"); Asser(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["Мультипликативный"] = [](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["Number"] = [](const SemanticValues &vs) {return vs.token_to_number<int>();
}; // (4) Анализ
parser.enable_packrat_parsing(); // Включаем парсинг Packrat.
интервал значений;
parser.parse(" (1 + 2) * 3", val); утверждать (значение == 9);
}Чтобы отобразить синтаксические ошибки в тексте грамматики:
auto grammar = R"( # Грамматика для калькулятора... Аддитив <- Мультипликативный '+' Аддитивный / Мультипликативный Мультипликативный <- Первичный '*' Мультипликативный / Первичный Первичный <- '(' Аддитивный ')' / Число Число <- < [ 0-9]+ > %whitespace <- [ t]*)";
парсер парсер;
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);Доступны четыре семантических действия:
[](const SemanticValues& vs, Any& dt) [](const SemanticValues& vs) [](SemanticValues& vs, Any& dt) [](Семантические значения& против)
Значение SemanticValues содержит следующую информацию:
Семантические значения
Информация о совпавшей строке
Информация о токене, если правило является буквальным или использует оператор границы токена.
Номер выбора, когда правилом является «приоритетный выбор».
any& dt — это контекстные данные «чтения и записи», которые можно использовать для любых целей. Исходные данные контекста задаются в методе peg::parser::parse .
Семантическое действие может возвращать значение произвольного типа данных, которое будет заключено в peg::any . Если пользователь ничего не возвращает в семантическом действии, будет возвращено первое семантическое значение в аргументе const SemanticValues& vs (Парсер Yacc ведет себя так же.)
Здесь показана структура SemanticValues :
struct SemanticValues: protected std::vector<any>
{ // Ввод текста
константный символ* путь; константный символ* сс; // Соответствующая строка
std::string_view sv() const { return 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; шаблон <имя типа T> T token_to_number() const; // Номер выбора (индекс от 0)
size_t выбор () const; // Преобразуем вектор семантического значения в другой вектор
шаблон <имя_типа T> вектор<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) { // 'токен' не включает конечные пробелы
автоматический токен = 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); // должно быть 2 вместо 5.};auto ret = parser.parse(" item1, item2 ");Следующая грамматика аналогична приведенной выше.
peg::parser parser(R"( ROOT <- ~_ ITEM (',' ~_ ITEM ~_)* ITEM <- ([a-z0-9])+ _ <- [ t]*)");Поддержка семантических предикатов доступна с помощью действия предиката .
peg::parser parser("ЧИСЛО <- [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 = "ошибка значения!!";return false;
} Вернуть истину;
};long val;auto ret = parser.parse("100", val);assert(ret == true);assert(val == 100);
ret = parser.parse("200", val);assert(ret == false);Также доступны действия входа и выхода .
parser["ПРАВИЛО"].enter = [](const Context &c, const char* s, size_t n, Any& dt) {
std::cout << "ввести" << std::endl;
};
parser["ПРАВИЛО"] = [](const SemanticValues& vs, Any& dt) {
std::cout << "действие!" << станд::эндл;
};
parser["ПРАВИЛО"].leave = [](const Context &c, const char* s, size_t n, size_t matchlen, Any& Value, Any& dt) {
std::cout << "оставить" << std::endl;
};Вы можете получить информацию об ошибках через логгер:
parser.set_logger([](линия size_t, столбец size_t, константная строка и сообщение) {
...
});
parser.set_logger([](size_t line, size_t col, const string& msg, const string &rule) {
...
}); Как вы можете видеть в первом примере, мы можем автоматически игнорировать пробелы между токенами с помощью правила %whitespace .
Правило %whitespace может быть применено к следующим трем условиям:
конечные пробелы в токенах
ведущие пробелы в тексте
конечные пробелы в литеральных строках в правилах
Это действительные токены:
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("Привет, мир"); // OKparser.parse("helloworld"); // НГ peg::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>."); // НГ | Оператор позволяет нам создать словарь слов для быстрого поиска, используя внутреннюю структуру 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 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 '+': результат += число; перерыв; случай '-': результат -= число; перерыв; случай '*': результат *= число; перерыв; случай '/': результат /= число; перерыв;
}
} вернуть результат;
};
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 ^
}Инструкция приоритета содержит записи информации о приоритете. Каждая запись начинается с ассоциативности «L» (слева) или «R» (справа), затем следуют токены операторного литерала . Первая запись имеет самый высокий уровень заказа.
cpp-peglib способен генерировать AST (абстрактное синтаксическое дерево) при анализе. Метод enable_ast в классе peg::parser включает эту функцию.
ПРИМЕЧАНИЕ. Узел 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 мы также можем создать синтаксический анализатор вручную с помощью комбинаторов синтаксического анализатора . Вот пример:
использование привязки пространства имен; использование тегов пространства имен std;vector<string>;
Определение ROOT, TAG_NAME, _;
КОРЕНЬ <= 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] ");Доступны следующие операторы:
| Оператор | Описание | Оператор | Описание |
|---|---|---|---|
| последовательность | Последовательность | чо | Приоритетный выбор |
| зом | Ноль или больше | ом | Один или несколько |
| выбрать | Необязательный | апд | И предикат |
| НПД | Не предикат | горит | Литеральная строка |
| Лити | Литеральная строка без учета регистра | клс | Класс персонажа |
| нклс | Отрицательный класс символов | чр | Характер |
| точка | Любой персонаж | ток | Граница токена |
| зажечь | Игнорировать смысловое значение | csc | Область захвата |
| кепка | Захватывать | бкр | Обратная ссылка |
| член | Словарь | предварительно | Инфиксное выражение |
| запись | Инфиксное выражение | usr | Пользовательский парсер |
| представитель | Повторение |
Определения можно добавлять/переопределять.
автоматический синтаксис = R"(ROOT <- _ 'Hello' _ NAME '!' _)";
Правила дополнительные_правила = {
{"NAME", usr([](const char* s, size_t n, SemanticValues& vs, Any& dt) -> size_t { static Vector<string> name = { "PEG", "BNF" }; for (const auto& name : имена) {if (name.size() <= n && !name.compare(0, name.size(), s, name.size()))) { return name.size(); // обработано; длина}
} Вернуть -1; // ошибка анализа})
},
{"~_", zom(cls("trn"))
}
};auto g = parser(syntax, extra_rules);assert(g.parse("Привет, BNF!")); cpp-peglib принимает текст UTF8. . соответствует кодовой точке Юникода. Кроме того, он поддерживает u???? .
cpp-peglib поддерживает отчет о положении самой дальней ошибки, как описано в исходном документе Брайана Форда.
Для лучшего отчета об ошибках и восстановления cpp-peglib поддерживает оператор восстановления с меткой, которая может быть связана с выражением восстановления и настраиваемым сообщением об ошибке. Эта идея взята из фантастической статьи Серхио Медейроса и Фабио Маскареньяса «Восстановление синтаксических ошибок при синтаксическом анализе грамматик выражений».
Пользовательское сообщение поддерживает %t , который является заполнителем для неожиданного токена, и %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 sample.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: отсутствует точка с запятой в присваивании.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 <- '[один]' / '[два]' %whitespace <- [ tn]*)";
peg::parser parser(grammar, "A"); // Правило начала — «А»
orpeg::parser парсер;
parser.load_grammar(грамматика, "А"); // Начальное правило: "A"parser.parse(" [один], [два] "); // ХОРОШО> 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)Калькулятор
Калькулятор (с операторами парсера)
Калькулятор (версия AST)
Калькулятор (разбор выражений по возрастанию приоритета)
Калькулятор (версия AST и анализ выражений по возрастанию приоритета)
Крошечный JIT-компилятор PL/0 менее чем за 900 LOC с анализатором LLVM и PEG.
Язык программирования, предназначенный только для написания программы Fizz Buzz. :)
Лицензия MIT (© 2022 Юджи Хиросе)
