cpp peglib
1.0.0
Biblioteca PEG (Gramáticas de expresión de análisis) de solo encabezado C ++ 17. Puede comenzar a usarlo de inmediato simplemente incluyendo peglib.h en su proyecto.
Dado que esta biblioteca solo admite compiladores de C++ 17, asegúrese de que la opción del compilador -std=c++17 esté habilitada. ( /std:c++17 /Zc:__cplusplus para MSVC)
También puede probar la versión en línea, PEG Playground en https://yhirose.github.io/cpp-peglib.
La sintaxis de PEG está bien descrita en la página 2 del documento de Bryan Ford. cpp-peglib también admite la siguiente sintaxis adicional por ahora:
'...'i (Operador literal que no distingue entre mayúsculas y minúsculas)
[...]i (operador de clase de caracteres que no distingue entre mayúsculas y minúsculas)
[^...] (Operador de clase de carácter negado)
[^...]i (Operador de clase de caracteres negados que no distingue entre mayúsculas y minúsculas)
{2,5} (Operador de repetición tipo Regex)
< ... > (Operador de límite de token)
~ (Ignorar operador)
x20 (carácter de número hexadecimal)
u10FFFF (carácter Unicode)
%whitespace (salto automático de espacios en blanco)
%word (expresión de palabra)
$name( ... ) (Operador de alcance de captura)
$name< ... > (Operador de captura con nombre)
$name (operador de referencia inversa)
| (Operador del diccionario)
↑ (Operador de corte)
MACRO_NAME( ... ) (Regla parametrizada o Macro)
{ precedence L - + L / * } (Análisis de expresión infija)
%recovery( ... ) (Operador de recuperación de errores)
exp⇑label o exp^label (Sintaxis de azúcar para (exp / %recover(label)) )
label { error_message "..." } (Instrucción de mensaje de error)
{ no_ast_opt } (Sin instrucción de optimización del nodo AST)
La verificación de 'Fin de entrada' se realizará de forma predeterminada. Para desactivar la verificación, llame a disable_eoi_check .
Esta biblioteca admite el análisis de tiempo lineal conocido como análisis Packrat .
NOTA IMPORTANTE para algunas distribuciones de Linux como Ubuntu y CentOS: se necesita la opción -pthread al vincular. Consulte los puntos 23, 46 y 62.
¡Estoy seguro de que disfrutará de este excelente artículo "Análisis práctico con PEG y cpp-peglib" de bert hubert!
Este es un ejemplo de calculadora simple. Muestra cómo definir la gramática, asociar acciones semánticas a la gramática y manejar valores semánticos.
// (1) Incluir el archivo de encabezado#include <peglib.h>#include <assert.h>#include <iostream>using namespace peg;using namespace std;int main(void) { // (2) Crear un analizador
parser parser(R"( # Gramática para Calculadora... Aditivo <- Multiplicativo '+' Aditivo / Multiplicativo Multiplicativo <- Primario '*' Multiplicativo / Primario Primario <- '(' Aditivo ')' / Número Número <- < [ 0-9]+ > %espacios en blanco <- [ t]* )"); afirmar(static_cast<bool>(analizador) == verdadero); // (3) Acciones de configuración
analizador["Aditivo"] = [](const SemanticValues &vs) {switch (vs.choice()) {caso 0: // "Aditivo multiplicativo '+'" return any_cast<int>(vs[0]) + any_cast< int>(vs[1]);default: // "Multiplicativo" return any_cast<int>(vs[0]);
}
};
analizador["Multiplicativo"] = [](const SemanticValues &vs) {switch (vs.choice()) {caso 0: // "Primario '*' Multiplicativo" return any_cast<int>(vs[0]) * any_cast< int>(vs[1]);default: // "Primario" return any_cast<int>(vs[0]);
}
};
analizador["Número"] = [](const SemanticValues &vs) {return vs.token_to_number<int>();
}; // (4) Analizar
parser.enable_packrat_parsing(); // Habilitar el análisis de packrat.
valor int;
analizador.parse(" (1 + 2) * 3 ", val); afirmar(val == 9);
}Para mostrar errores de sintaxis en un texto gramatical:
auto grammar = R"( # Gramática para Calculadora... Aditivo <- Multiplicativo '+' Aditivo / Multiplicativo Multiplicativo <- Primario '*' Multiplicativo / Primario Primario <- '(' Aditivo ')' / Número Número <- < [ 0-9]+ > %espacios en blanco <- [t]*)";
analizador analizador;
parser.set_logger([](size_t línea, size_t col, cadena constante y mensaje, cadena constante y regla) {
cerr << línea << ":" << col << ": " << mensaje << "n";
});auto ok = parser.load_grammar(gramática);assert(ok);Hay cuatro acciones semánticas disponibles:
[](const SemanticValues& vs, any& dt) [](const ValoresSemánticos& vs) [](ValoresSemánticos& vs, cualquiera& dt) [](ValoresSemánticos& vs)
El valor SemanticValues contiene la siguiente información:
Valores semánticos
Información de cadena coincidente
Información del token si la regla es literal o utiliza un operador de límite de token
Número de elección cuando la regla es 'elección priorizada'
any& dt son datos de contexto de "lectura y escritura" que se pueden utilizar para cualquier propósito. Los datos del contexto inicial se establecen en el método peg::parser::parse .
Una acción semántica puede devolver un valor de tipo de datos arbitrario, que estará envuelto por peg::any . Si un usuario no devuelve nada en una acción semántica, se devolverá el primer valor semántico en el argumento const SemanticValues& vs (El analizador Yacc tiene el mismo comportamiento).
Aquí se muestra la estructura de SemanticValues :
estructura SemanticValues: std protegido::vector<cualquier>
{ // Introducir texto
ruta constante char*; carácter constante* ss; // cadena coincidente
std::string_view sv() const { return sv_; } // Número de línea y columna en la que se encuentra la cadena coincidente
std::par<tamaño_t, tamaño_t> line_info() const; // fichas
std::vector<std::string_view> tokens;
std::string_view token(size_t id = 0) const; // conversión de tokens
std::string token_to_string(size_t id = 0) const; plantilla <tiponombre T> T token_to_number() const; // Número de elección (índice basado en 0)
elección de tamaño_t() const; // Transformamos el vector de valor semántico en otro vector
plantilla <typename T> vector<T> transform(size_t beg = 0, size_t end = -1) const;
} El siguiente ejemplo utiliza el operador < ... > , que es un operador de límite de token .
peg::parser parser(R"( ROOT <- _ TOKEN (',' _ TOKEN)* TOKEN <- < [a-z0-9]+ > _ _ <- [ trn]*)");
parser["TOKEN"] = [](const SemanticValues& vs) { // 'token' no incluye espacios en blanco finales
token automático = vs.token();
};auto ret = parser.parse(" token1, token2 "); Podemos ignorar valores semánticos innecesarios de la lista usando el operador ~ .
peg::parser parser(R"( ROOT <- _ ITEM (',' _ ITEM _)* ITEM <- ([a-z0-9])+ ~_ <- [ t]*)");
analizador["ROOT"] = [&](const SemanticValues& vs) { afirmar(vs.size() == 2); // debería ser 2 en lugar de 5.};auto ret = parser.parse(" elemento1, elemento2 ");La siguiente gramática es la misma que la anterior.
peg::parser parser(R"( ROOT <- ~_ ITEM (',' ~_ ITEM ~_)* ITEM <- ([a-z0-9])+ _ <- [ t]*)");El soporte de predicado semántico está disponible con una acción de predicado .
peg::parser analizador("NÚMERO <- [0-9]+");
analizador["NÚMERO"] = [](const SemanticValues &vs) { return vs.token_to_number<long>();
};
analizador["NÚMERO"].predicate = [](const SemanticValues &vs,const std::any & /*dt*/, std::string &msg) { if (vs.token_to_number<long>() != 100) {
msg = "¡error de valor!";return false;
} devuelve verdadero;
};long val;auto ret = parser.parse("100", val);assert(ret == verdadero);assert(val == 100);
ret = parser.parse("200", val);assert(ret == falso);Las acciones de entrada y salida también están disponibles.
analizador["REGLA"].enter = [](const Context &c, const char* s, size_t n, any& dt) {
std::cout << "entrar" << std::endl;
};
analizador["REGLA"] = [](const SemanticValues& vs, any& dt) {
std::cout << "acción!" << std::endl;
};
analizador["REGLA"].leave = [](const Context &c, const char* s, size_t n, size_t matchlen, any& value, any& dt) {
std::cout << "dejar" << std::endl;
};Puede recibir información de error a través de un registrador:
parser.set_logger([](size_t línea, size_t col, cadena constante y mensaje) {
...
});
parser.set_logger([](size_t línea, size_t col, cadena constante y mensaje, cadena constante y regla) {
...
}); Como puede ver en el primer ejemplo, podemos ignorar los espacios en blanco entre tokens automáticamente con la regla %whitespace .
La regla %whitespace se puede aplicar a las siguientes tres condiciones:
espacios finales en tokens
espacios iniciales en el texto
espacios finales en cadenas literales en reglas
Estos son tokens válidos:
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.
La siguiente gramática acepta one, "two three", four .
ROOT <- ITEM (',' ITEM)*
ITEM <- WORD / PHRASE
WORD <- < [a-z]+ >
PHRASE <- < '"' (!'"' .)* '"' >
%whitespace <- [ trn]* peg::parser parser(R"( ROOT <- 'hola' 'mundo' %espacio en blanco <- [ trn]* %palabra <- [az]+)");
parser.parse("hola mundo"); // OKparser.parse("holamundo"); // NG peg::parser parser(R"( RAÍZ <- CONTENIDO CONTENIDO <- (ELEMENTO / TEXTO)* ELEMENTO <- $(STAG CONTENIDO ETAG) STAG <- '<' $etiqueta< NOMBRE_TAG > '>' ETAG <- '< /' $etiqueta '>' NOMBRE_TAG <- 'b' / 'u' TEXTO <- DATOS_TEXTO DATOS_TEXTO <- ![<] .)");
parser.parse("Este es <b>un texto de <u>prueba</u></b>."); // OKparser.parse("Este es <b>un texto de <u>prueba</b></u>."); // NGparser.parse("Este es <b>un <u>texto de prueba</b>."); // NG | El operador nos permite crear un diccionario de palabras para una búsqueda rápida utilizando la estructura Trie internamente. No tenemos que preocuparnos por el orden de las palabras.
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan' | 'January' | 'Feb' | 'February' | '...' Podemos encontrar qué elemento coincide con choice() .
analizador["MES"] = [](const SemanticValues &vs) { identificación automática = vs.choice();
};Admite el modo que no distingue entre mayúsculas y minúsculas.
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan'i | 'January'i | 'Feb'i | 'February'i | '...'i ↑ El operador podría mitigar el problema de rendimiento de retroceso, pero tiene el riesgo de cambiar el significado de la gramática.
S <- '(' ↑ P ')' / '"' ↑ P '"' / P
P <- 'a' / 'b' / 'c' Cuando analizamos (z con la gramática anterior, no tenemos que retroceder en S después de que ( coincida, porque se inserta un operador de corte allí.
# 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 > _Con respecto al algoritmo de escalada de precedencia , consulte este artículo.
parser parser(R"( EXPRESIÓN <- INFIX_EXPRESSION(ÁTOMO, OPERADOR) ÁTOMO <- NÚMERO / '(' EXPRESIÓN ')' OPERADOR <- < [-+/*] > NÚMERO <- < '-'? [0-9 ]+ > %espacio en blanco <- [ t]* # Declarar orden de precedencia INFIX_EXPRESSION(A, O) <- A (O A)* { precedencia L + - L * / })");
analizador["INFIX_EXPRESSION"] = [](const SemanticValues& vs) -> long { resultado automático = 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 '+': resultado += número; romper; caso '-': resultado -= número; romper; caso '*': resultado *= núm; romper; caso '/': resultado /= núm; romper;
}
} devolver resultado;
};
analizador["OPERADOR"] = [](const SemanticValues& vs) { return *vs.sv(); };
analizador["NÚMERO"] = [](const SemanticValues& vs) { return vs.token_to_number<long>(); };valor largo;
parser.parse(" -1 + (1 + 2) * 3 - -1", val);assert(val == 9);La instrucción de precedencia sólo se puede aplicar a la siguiente regla de estilo de 'lista'.
Rule <- Atom (Operator Atom)* {
precedence
L - +
L / *
R ^
}La instrucción de precedencia contiene entradas de información de precedencia. Cada entrada comienza con asociatividad que es 'L' (izquierda) o 'R' (derecha), luego siguen los tokens literales del operador. La primera entrada tiene el nivel de orden más alto.
cpp-peglib puede generar un AST (árbol de sintaxis abstracta) al analizar. El método enable_ast en la clase peg::parser habilita la función.
NOTA: Un nodo AST contiene un token correspondiente como std::string_vew para rendimiento y menor uso de memoria. Es responsabilidad de los usuarios conservar el texto fuente original junto con el árbol AST generado.
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 elimina los nodos redundantes para simplificar un AST. Si desea deshabilitar este comportamiento de reglas particulares, se puede usar la instrucción no_ast_opt .
Llama internamente peg::AstOptimizer para hacer el trabajo. Puede crear sus propios optimizadores AST que se ajusten a sus necesidades.
Vea los usos reales en el ejemplo de la calculadora AST y el ejemplo del lenguaje PL/0.
En lugar de crear un analizador analizando el texto de sintaxis PEG, también podemos construir un analizador a mano con combinadores de analizadores . Aquí hay un ejemplo:
usando la clavija del espacio de nombres; usando las etiquetas std del espacio de nombres; vector<cadena>;
Definición RAÍZ, TAG_NAME, _;
ROOT <= seq(_, zom(seq(chr('['), TAG_NAME, chr(']'), _)));
TAG_NAME <= oom(seq(npd(chr(']')), punto())), [&](const SemanticValues& vs) {
etiquetas.push_back(vs.token_to_string());
};
_ <= zom(cls(" t"));auto ret = ROOT.parse(" [etiqueta1] [etiqueta:2] [etiqueta-3] ");Los siguientes son operadores disponibles:
| Operador | Descripción | Operador | Descripción |
|---|---|---|---|
| secuencia | Secuencia | cho | Elección priorizada |
| Zom | Cero o más | oom | Uno o más |
| optar | Opcional | apd | y predicado |
| npd | No predicado | iluminado | cadena literal |
| liti | Cadena literal que no distingue entre mayúsculas y minúsculas | cls | Clase de personaje |
| ncls | Clase de personaje negado | chr | Personaje |
| punto | cualquier personaje | tok | Límite del token |
| firmar | Ignorar el valor semántico | csc | Alcance de captura |
| tapa | Captura | bkr | Referencia posterior |
| dic | Diccionario | pre | expresión infija |
| rec | expresión infija | usr | Analizador definido por el usuario |
| reps | Repetición |
Es posible agregar/anular definiciones.
sintaxis automática = R"( ROOT <- _ 'Hola' _ NOMBRE '!' _)";
Reglas reglas_adicionales = {
{"NOMBRE", usr([](const char* s, size_t n, SemanticValues& vs, any& dt) -> size_t { vector estático<string> nombres = { "PEG", "BNF" }; for (const auto& nombre : nombres) {if (nombre.tamaño() <= n && !nombre.compare(0, nombre.tamaño(), s, nombre.tamaño())) { return nombre.tamaño(); longitud}
} devolver -1; // error de análisis})
},
{"~_", zom(cls("trn"))
}
};auto g = analizador(sintaxis, reglas_adicionales);assert(g.parse(" ¡Hola BNF! ")); cpp-peglib acepta texto UTF8. . coincide con un punto de código Unicode. Además, ¿ u???? .
cpp-peglib admite el informe de posición de error de falla más lejana como se describe en el documento original de Bryan Ford.
Para obtener mejores informes de errores y recuperación, cpp-peglib admite el operador de 'recuperación' con una etiqueta que puede asociarse con una expresión de recuperación y un mensaje de error personalizado. Esta idea proviene del fantástico artículo "Recuperación de errores de sintaxis en gramáticas de expresiones de análisis" de Sergio Medeiros y Fabio Mascarenhas.
El mensaje personalizado admite %t , que es un marcador de posición para el token inesperado, y %c para el carácter Unicode inesperado.
A continuación se muestra un ejemplo de gramática similar a 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)* / (!')' .)* Por ejemplo, ';'^semi es un azúcar sintáctico para (';' / %recovery(semi)) . El operador %recover intenta recuperar el error en ';' omitiendo el texto ingresado con la expresión de recuperación semi . Además, semi está asociado con un mensaje personalizado "falta punto y coma en la tarea".
Aquí está el resultado:
> cat sample.javapublic class Ejemplo { 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: error de sintaxis, '<' inesperado, esperando '(', <NÚMERO>, <NOMBRE>.sample.java:8:5: falta punto y coma en asignación.sample .java:8:6: declaración no válidaComo puede ver, ahora puede mostrar más de un error y proporcionar mensajes de error más significativos que los mensajes predeterminados.
Podemos asociar mensajes de error personalizados a definiciones.
# 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...
NOTA: Si hay más de un elemento con una instrucción de mensaje de error en una elección priorizada, es posible que esta función no funcione como esperaba.
Podemos cambiar la regla de definición de inicio como se muestra a continuación.
gramática automática = R"( Inicio <- A A <- B (',' B)* B <- '[uno]' / '[dos]' %espacio en blanco <- [tn]*)";
peg::parser analizador(gramática, "A"); // La regla de inicio es "A"
orpeg::parser analizador;
parser.load_grammar(gramática, "A"); // La regla de inicio es "A"parser.parse(" [uno], [dos] "); // DE ACUERDO> 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)Calculadora
Calculadora (con operadores de analizador)
Calculadora (versión AST)
Calculadora (analizando expresiones por escalada de precedencia)
Calculadora (versión AST y análisis de expresiones por escalada de precedencia)
Un pequeño compilador PL/0 JIT en menos de 900 LOC con analizador LLVM y PEG
Un lenguaje de programación solo para escribir el programa Fizz Buzz. :)
Licencia MIT (© 2022 Yuji Hirose)
