C++17 헤더 전용 PEG(Parsing Expression Grammars) 라이브러리입니다. 프로젝트에 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
(유니코드 문자)
%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 네임스페이스 peg;using 네임스페이스 std;int main(void) { // (2) 파서 만들기 파서 파서(R"( # 계산기 문법... 덧셈 <- 곱셈 '+' 덧셈 / 곱셈 곱셈 <- 1차 '*' 곱셈 / 1차 1차 <- '(' 덧셈 ')' / 숫자 숫자 <- < [ 0-9]+ > %공백 <- [ t]* )"); 주장(static_cast<bool>(파서) == true); // (3) 설정 작업 파서["덧셈"] = [](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]); } }; 파서["곱셈"] = [](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]); } }; 파서["번호"] = [](const SemanticValues &vs) {return vs.token_to_number<int>(); }; // (4) 구문 분석 파서.enable_packrat_parsing(); // packrat 구문 분석을 활성화합니다. int 값; parser.parse(" (1 + 2) * 3 ", val); 주장(val == 9); }
문법 텍스트에 구문 오류를 표시하려면:
auto Grammar = R"( # 계산기 문법... 덧셈 <- 곱셈 '+' 덧셈 / 곱셈 곱셈 <- 1차 '*' 곱셈 / 1차 기본 <- '(' 덧셈 ')' / 숫자 숫자 <- < [ 0-9]+ > %공백 <- [ 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& 대) [](SemanticValues& 대, 모든& dt) [](의미적 값& 대)
SemanticValues
값에는 다음 정보가 포함됩니다.
의미론적 값
일치하는 문자열 정보
규칙이 리터럴이거나 토큰 경계 연산자를 사용하는 경우 토큰 정보
규칙이 '우선 선택'인 경우 선택 번호
any& dt
어떤 목적으로든 사용할 수 있는 '읽기-쓰기' 컨텍스트 데이터입니다. 초기 컨텍스트 데이터는 peg::parser::parse
메소드에 설정됩니다.
의미론적 작업은 peg::any
로 래핑되는 임의 데이터 유형의 값을 반환할 수 있습니다. 사용자가 의미 체계 작업에서 아무것도 반환하지 않으면 const SemanticValues& vs
인수의 첫 번째 의미 값이 반환됩니다. (Yacc 파서의 동작은 동일합니다.)
다음은 SemanticValues
구조를 보여줍니다.
struct SemanticValues : 보호된 std::벡터<모든> { // 텍스트 입력 const char* 경로; const char* ss; // 일치하는 문자열 std::string_view sv() const { return sv_; } // 일치하는 문자열이 있는 줄 번호와 열 std::pair<size_t, size_t> line_info() const; // 토큰 std::벡터<std::string_view> 토큰; std::string_view 토큰(size_t id = 0) const; // 토큰 변환 std::string token_to_string(size_t id = 0) const; template <typename T> T token_to_number() const; // 선택번호(0 기반 인덱스) size_t 선택() const; // 의미 값 벡터를 다른 벡터로 변환합니다. template <typename T> 벡터<T> 변환(size_t beg = 0, size_t end = -1) const; }
다음 예에서는 토큰 경계 연산자인 <
... >
연산자를 사용합니다.
peg::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 파서(R"( ROOT <- _ ITEM (',' _ ITEM _)* ITEM <- ([a-z0-9])+ ~_ <- [ t]*)"); 파서["ROOT"] = [&](const SemanticValues& vs) { 주장(vs.size() == 2); // 5 대신 2여야 합니다.};auto ret = parser.parse(" item1, item2 ");
다음 문법은 위와 동일합니다.
peg::parser 파서(R"( ROOT <- ~_ ITEM (',' ~_ ITEM ~_)* ITEM <- ([a-z0-9])+ _ <- [ t]*)");
의미론적 조건자 지원은 조건자 작업을 통해 사용할 수 있습니다.
peg::parser 파서("NUMBER <- [0-9]+"); 파서["NUMBER"] = [](const SemanticValues &vs) { return vs.token_to_number<long>(); }; 파서["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 = 파서.parse("200", val);assert(ret == false);
입장 및 퇴장 조치도 가능합니다.
파서["RULE"].enter = [](const Context &c, const char* s, size_t n, any& dt) { std::cout << "입력" << std::endl; }; 파서["RULE"] = [](const SemanticValues& vs, any& dt) { std::cout << "액션!" << 표준::endl; }; 파서["RULE"].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 line, size_t col, const string& msg) { ... }); 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 파서(R"( ROOT <- 'hello' 'world' %whitespace <- [ trn]* %word <- [az]+)"); parser.parse("안녕하세요 세계"); // OKparser.parse("helloworld"); // NG
peg::parser 파서(R"( ROOT <- CONTENT CONTENT <- (ELEMENT / TEXT)* ELEMENT <- $(STAG CONTENT ETAG) STAG <- '<' $tag< TAG_NAME > '>' ETAG <- '< /' $tag '>' TAG_NAME <- 'b' / 'u' TEXT <- 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()
와 일치하는 항목을 찾을 수 있습니다.
파서["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 > _
우선 순위 상승 알고리즘 에 대해서는 이 문서를 참조하세요.
파서 파서(R"( EXPRESSION <- INFIX_EXPRESSION(ATOM, OPERATOR) ATOM <- NUMBER / '(' EXPRESSION ')' OPERATOR <- < [-+/*] > NUMBER <- < '-'? [0-9 ]+ > %whitespace <- [ t]* # 우선순위 선언 INFIX_EXPRESSION(A, O) <- A (O A)* { 우선순위 L + - L * / })"); 파서["INFIX_EXPRESSION"] = [](const SemanticValues& vs) -> long { 자동 결과 = 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 '+': 결과 += 숫자; 부서지다; 케이스 '-': 결과 -= 숫자; 부서지다; 케이스 '*': 결과 *= 숫자; 부서지다; 케이스 '/': 결과 /= 숫자; 부서지다; } } 결과를 반환합니다. }; 파서["OPERATOR"] = [](const SemanticValues& vs) { return *vs.sv(); }; 파서["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(추상 구문 트리)를 생성할 수 있습니다. 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 구문 텍스트를 구문 분석하여 파서를 만드는 대신 파서 결합자를 사용하여 직접 파서를 구성할 수도 있습니다. 예는 다음과 같습니다.
네임스페이스 페그 사용;네임스페이스 std 사용;벡터<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] ");
사용 가능한 연산자는 다음과 같습니다.
연산자 | 설명 | 연산자 | 설명 |
---|---|---|---|
순서 | 순서 | 초 | 우선순위 선택 |
좀 | 0 이상 | 옴 | 하나 이상 |
고르다 | 선택 과목 | APD | 그리고 술어 |
npd | 술어 아님 | 문학 | 리터럴 문자열 |
리티 | 대소문자를 구분하지 않는 리터럴 문자열 | cls | 캐릭터 클래스 |
NCLS | 부정된 문자 클래스 | 문자 | 성격 |
점 | 모든 문자 | 톡 | 토큰 경계 |
점화하다 | 의미적 값 무시 | csc | 캡처 범위 |
캡 | 포착 | bkr | 역참조 |
딕 | 사전 | 미리 | 중위 표현 |
기록 | 중위 표현 | 우리 | 사용자 정의 파서 |
대표 | 되풀이 |
정의를 추가/재정의하는 것이 가능합니다.
자동 구문 = R"( ROOT <- _ 'Hello' _ NAME '!' _)"; 규칙 extra_rules = { {"NAME", usr([](const char* s, size_t n, SemanticValues& vs, any& dt) -> size_t { static vector<string> names = { "PEG", "BNF" }; for (const auto& 이름 : 이름) {if (name.size() <= n && !name.compare(0, name.size(), s, name.size())) { return name.size(); // 처리된 길이} } -1을 반환합니다; // 구문 분석 오류}) }, {"~_", zom(cls(" trn")) } };auto g = 파서(syntax, added_rules);assert(g.parse(" Hello BNF! "));
cpp-peglib는 UTF8 텍스트를 허용합니다. .
유니코드 코드 포인트와 일치합니다. 그리고 그것은 u????
.
cpp-peglib는 Bryan Ford 원본 문서에 설명된 대로 가장 먼 오류 위치 보고서를 지원합니다.
더 나은 오류 보고 및 복구를 위해 cpp-peglib는 복구 표현식 및 사용자 정의 오류 메시지와 연관될 수 있는 레이블이 있는 '복구' 연산자를 지원합니다. 이 아이디어는 Sergio Medeiros와 Fabio Mascarenhas가 쓴 환상적인 "Syntax Error Recovery in Parsing Expression Grammars" 논문에서 나왔습니다.
사용자 정의 메시지는 예상치 못한 토큰에 대한 자리 표시자인 %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
"할당 시 세미콜론이 누락되었습니다"라는 사용자 정의 메시지와 연결되어 있습니다.
결과는 다음과 같습니다.
> 고양이 샘플.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: 할당.샘플에 세미콜론 누락) .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...
참고: 우선순위 선택 항목에 오류 메시지 지침이 있는 요소가 두 개 이상 있는 경우 이 기능이 예상대로 작동하지 않을 수 있습니다.
아래와 같이 시작 정의 규칙을 변경할 수 있습니다.
자동 문법 = R"( 시작 <- A A <- B (',' B)* B <- '[one]' / '[two]' %whitespace <- [ tn]*)"; peg::parser 파서(grammar, "A"); // 시작 규칙은 "A"입니다. orpeg::파서 파서; parser.load_grammar(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 Yuji Hirose)