cpp peglib
1.0.0
Bibliothèque PEG (Parsing Expression Grammars) avec en-tête uniquement C++17. Vous pouvez commencer à l'utiliser immédiatement en incluant simplement peglib.h dans votre projet.
Étant donné que cette bibliothèque ne prend en charge que les compilateurs C++17, assurez-vous que l'option du compilateur -std=c++17 est activée. ( /std:c++17 /Zc:__cplusplus pour MSVC)
Vous pouvez également essayer la version en ligne, PEG Playground sur https://yhirose.github.io/cpp-peglib.
La syntaxe PEG est bien décrite à la page 2 du document de Bryan Ford. cpp-peglib prend également en charge la syntaxe supplémentaire suivante pour l'instant :
'...'i (opérateur littéral insensible à la casse)
[...]i (opérateur de classe de caractères insensible à la casse)
[^...] (Opérateur de classe de caractères annulé)
[^...]i (opérateur de classe de caractères annulés insensible à la casse)
{2,5} (opérateur de répétition de type Regex)
< ... > (Opérateur de limite de jeton)
~ (Ignorer l'opérateur)
x20 (caractère numérique hexadécimal)
u10FFFF (caractère Unicode)
%whitespace (saut automatique des espaces)
%word (Expression de mot)
$name( ... ) (opérateur de portée de capture)
$name< ... > (Opérateur de capture nommé)
$name (opérateur de référence arrière)
| (Opérateur de dictionnaire)
↑ (Opérateur Couper)
MACRO_NAME( ... ) (Règle paramétrée ou Macro)
{ precedence L - + L / * } (expression d'infixe d'analyse)
%recovery( ... ) (opérateur de récupération d'erreur)
exp⇑label ou exp^label (Syntaxe sugar for (exp / %recover(label)) )
label { error_message "..." } (Instruction de message d'erreur)
{ no_ast_opt } (Aucune instruction d'optimisation du nœud AST)
La vérification de « Fin de saisie » sera effectuée par défaut. Pour désactiver la vérification, veuillez appeler disable_eoi_check .
Cette bibliothèque prend en charge l'analyse en temps linéaire connue sous le nom d'analyse Packrat .
REMARQUE IMPORTANTE pour certaines distributions Linux telles que Ubuntu et CentOS : nécessite l'option -pthread lors de la liaison. Voir #23, #46 et #62.
Je suis sûr que vous apprécierez cet excellent article "Analyse pratique avec PEG et cpp-peglib" de bert hubert !
Ceci est un exemple simple de calculatrice. Il montre comment définir la grammaire, associer des actions sémantiques à la grammaire et gérer les valeurs sémantiques.
// (1) Inclure le fichier d'en-tête#include <peglib.h>#include <assert.h>#include <iostream>using namespace peg;using namespace std;int main(void) { // (2) Créer un analyseur
parser parser(R"( # Grammaire pour la calculatrice... Additif <- Multiplicatif '+' Additif / Multiplicatif Multiplicatif <- Primaire '*' Multiplicatif / Primaire Primaire <- '(' Additif ')' / Nombre Nombre <- < [ 0-9]+ > %espace blanc <- [ t]* )"); assert(static_cast<bool>(parser) == true); // (3) Actions de configuration
parser["Additive"] = [](const SemanticValues &vs) {switch (vs.choice()) {case 0 : // "Multiplicative '+' Additive" return any_cast<int>(vs[0]) + any_cast< int>(vs[1]);default : // "Multiplicatif" 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 : // "Primaire" renvoie any_cast<int>(vs[0]);
}
} ;
parser["Number"] = [](const SemanticValues &vs) {return vs.token_to_number<int>();
} ; // (4) Analyser
parser.enable_packrat_parsing(); // Active l'analyse packrat.
val int;
parser.parse(" (1 + 2) * 3 ", val); assert(val == 9);
}Pour afficher les erreurs de syntaxe dans un texte de grammaire :
grammaire automatique = R"( # Grammaire pour la calculatrice... Additif <- Multiplicatif '+' Additif / Multiplicatif Multiplicatif <- Primaire '*' Multiplicatif / Primaire Primaire <- '(' Additif ')' / Nombre Numéro <- < [ 0-9]+ > %espace blanc <- [ t]*)";
analyseur analyseur ;
parser.set_logger([](ligne size_t, col size_t, chaîne const et msg, chaîne const et règle) {
cerr << ligne << ":" << col << ": " << msg << "n";
});auto ok = parser.load_grammar(grammar);assert(ok);Quatre actions sémantiques sont disponibles :
[](const SemanticValues& vs, any& dt) [](const Valeurs Sémantiques& vs) [](Valeurs sémantiques& vs, any& dt) [](Valeurs sémantiques& vs)
La valeur SemanticValues contient les informations suivantes :
Valeurs sémantiques
Informations sur la chaîne correspondante
Informations sur le jeton si la règle est littérale ou utilise un opérateur de limite de jeton
Numéro de choix lorsque la règle est « choix prioritaire »
any& dt est une donnée contextuelle « lecture-écriture » qui peut être utilisée à toutes fins. Les données de contexte initiales sont définies dans la méthode peg::parser::parse .
Une action sémantique peut renvoyer une valeur de type de données arbitraire, qui sera enveloppée par peg::any . Si un utilisateur ne renvoie rien dans une action sémantique, la première valeur sémantique de l'argument const SemanticValues& vs sera renvoyée. (L'analyseur Yacc a le même comportement.)
Voici la structure SemanticValues :
struct SemanticValues : protégé std::vector<any>
{ // Saisir le texte
const char* chemin ; const char* ss; // Chaîne correspondante
std::string_view sv() const { return sv_; } // Numéro de ligne et colonne dans lesquels se trouve la chaîne correspondante
std::pair<size_t, size_t> line_info() const; // Jetons
jetons std::vector<std::string_view> ;
std::string_view token(size_t id = 0) const; // Conversion de jeton
std::string token_to_string(size_t id = 0) const; modèle <typename T> T token_to_number() const; // Numéro de choix (index basé sur 0)
size_t choix() const; // Transforme le vecteur de valeur sémantique en un autre vecteur
modèle <typename T> vector<T> transform(size_t beg = 0, size_t end = -1) const;
} L'exemple suivant utilise l'opérateur < ... > , qui est un opérateur de limite de jeton .
peg::parser parser(R"( ROOT <- _ TOKEN (',' _ TOKEN)* TOKEN <- < [a-z0-9]+ > _ _ <- [ trn]*)");
parser["TOKEN"] = [](const SemanticValues& vs) { // 'token' n'inclut pas les espaces de fin
jeton automatique = vs.token();
};auto ret = parser.parse(" token1, token2 "); Nous pouvons ignorer les valeurs sémantiques inutiles de la liste en utilisant l'opérateur ~ .
peg::parser parser(R"( ROOT <- _ ITEM (',' _ ITEM _)* ITEM <- ([a-z0-9])+ ~_ <- [ t]*)");
parser["ROOT"] = [&](const SemanticValues& vs) { assert(vs.size() == 2); // devrait être 2 au lieu de 5.};auto ret = parser.parse(" item1, item2 ");La grammaire suivante est la même que celle ci-dessus.
peg::parser parser(R"( ROOT <- ~_ ITEM (',' ~_ ITEM ~_)* ITEM <- ([a-z0-9])+ _ <- [ t]*)");La prise en charge des prédicats sémantiques est disponible avec une action de prédicat .
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 = "erreur de valeur !! ; return false ;
} renvoie vrai ;
};long val;auto ret = parser.parse("100", val);assert(ret == true);assert(val == 100);
ret = parser.parse("200", val);assert(ret == false);des actions d'entrée et de sortie sont également disponibles.
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 << " action ! " << std :: endl;
} ;
parser["RULE"].leave = [](const Context &c, const char* s, size_t n, size_t matchlen, any& value, any& dt) {
std :: cout << "quitter" << std :: endl;
} ;Vous pouvez recevoir des informations d'erreur via un enregistreur :
parser.set_logger([](ligne size_t, col size_t, chaîne const& msg) {
...
});
parser.set_logger([](ligne size_t, col size_t, chaîne const et msg, chaîne const et règle) {
...
}); Comme vous pouvez le voir dans le premier exemple, nous pouvons ignorer automatiquement les espaces entre les jetons avec la règle %whitespace .
La règle %whitespace peut être appliquée aux trois conditions suivantes :
espaces de fin sur les jetons
espaces de début sur le texte
espaces de fin sur les chaînes littérales dans les règles
Ce sont des jetons valides :
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 grammaire suivante accepte 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("bonjour tout le monde"); // OKparser.parse("bonjour le monde"); // NG peg::parser 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("Ceci est <b>un <u>texte de test</u></b>."); // OKparser.parse("Ceci est <b>un <u>texte de test</b></u>."); // NGparser.parse("Ceci est <b>un <u>texte de test</b>."); // NG | L'opérateur nous permet de créer un dictionnaire de mots pour une recherche rapide en utilisant la structure Trie en interne. Nous n'avons pas à nous soucier de l'ordre des mots.
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan' | 'January' | 'Feb' | 'February' | '...' Nous sommes capables de trouver quel élément correspond à choice() .
parser["MOIS"] = [](const SemanticValues &vs) { auto id = vs.choice();
} ;Il prend en charge le mode insensible à la casse.
START <- 'This month is ' MONTH '.'
MONTH <- 'Jan'i | 'January'i | 'Feb'i | 'February'i | '...'i ↑ l'opérateur pourrait atténuer le problème de performances de retour en arrière, mais risque de changer le sens de la grammaire.
S <- '(' ↑ P ')' / '"' ↑ P '"' / P
P <- 'a' / 'b' / 'c' Lorsque nous analysons (z avec la grammaire ci-dessus, nous n'avons pas besoin de revenir en arrière dans S après que ( correspond, car un opérateur de coupe y est inséré.
# 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 > _Concernant l' algorithme d'escalade de priorité , veuillez consulter cet article.
parser parser(R"( EXPRESSION <- INFIX_EXPRESSION(ATOM, OPERATOR) ATOM <- NUMBER / '(' EXPRESSION ')' OPERATOR <- < [-+/*] > NUMBER <- < '-'? [0-9 ]+ > %whitespace <- [ t]* # Déclarer l'ordre de priorité INFIX_EXPRESSION(A, O) <- A (O A)* { priorité 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 '+' : résultat += nombre ; casser; cas '-' : résultat -= num ; casser; cas '*' : résultat *= num ; casser; cas '/' : résultat /= num ; casser;
}
} renvoie le résultat ;
} ;
parser["OPERATEUR"] = [](const SemanticValues& vs) { return *vs.sv(); } ;
parser["NUMBER"] = [](const SemanticValues& vs) { return vs.token_to_number<long>(); };longue val;
parser.parse(" -1 + (1 + 2) * 3 - -1", val);assert(val == 9);L’instruction de priorité ne peut être appliquée qu’à la règle de style « liste » suivante.
Rule <- Atom (Operator Atom)* {
precedence
L - +
L / *
R ^
}L'instruction de priorité contient des entrées d'informations de priorité. Chaque entrée commence par l'associativité qui est « L » (gauche) ou « R » (droite), puis les jetons littéraux d'opérateur suivent. La première entrée a le niveau d'ordre le plus élevé.
cpp-peglib est capable de générer un AST (Abstract Syntax Tree) lors de l'analyse. La méthode enable_ast de la classe peg::parser active la fonctionnalité.
REMARQUE : Un nœud AST contient un jeton correspondant en tant que std::string_vew pour des performances et une utilisation moindre de la mémoire. Il est de la responsabilité des utilisateurs de conserver le texte source original ainsi que l'arborescence AST générée.
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 supprime les nœuds redondants pour simplifier un AST. Si vous souhaitez désactiver ce comportement pour des règles particulières, l'instruction no_ast_opt peut être utilisée.
Il appelle en interne peg::AstOptimizer pour faire le travail. Vous pouvez créer vos propres optimiseurs AST pour répondre à vos besoins.
Voir les utilisations réelles dans l'exemple de la calculatrice AST et l'exemple du langage PL/0.
Au lieu de créer un analyseur en analysant le texte de la syntaxe PEG, nous pouvons également construire un analyseur manuellement avec des combinateurs d'analyseurs . Voici un exemple :
en utilisant la cheville d'espace de noms ; en utilisant l'espace de noms std ; les balises vector<string> ;
Définition RACINE, TAG_NAME, _ ;
RACINE <= 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] ");Les opérateurs disponibles sont les suivants :
| Opérateur | Description | Opérateur | Description |
|---|---|---|---|
| séquence | Séquence | chou | Choix prioritaire |
| zom | Zéro ou plus | boum | Un ou plusieurs |
| opter | Facultatif | apd | Et le prédicat |
| npd | Pas de prédicat | allumé | Chaîne littérale |
| liti | Chaîne littérale insensible à la casse | cls | Classe de personnage |
| ncls | Classe de caractère niée | chr | Personnage |
| point | N'importe quel personnage | je t'aime | Limite du jeton |
| ign | Ignorer la valeur sémantique | csc | Portée de capture |
| capuchon | Capturer | bkr | Référence arrière |
| dés | Dictionnaire | pré | Expression infixe |
| rec | Expression infixe | usr | Analyseur défini par l'utilisateur |
| représentant | Répétition |
Il est possible d'ajouter/remplacer des définitions.
syntaxe automatique = R"( ROOT <- _ 'Bonjour' _ NAME '!' _)";
Règles supplémentaires_rules = {
{"NOM", usr([](const char* s, size_t n, SemanticValues& vs, any& dt) -> size_t { static vector<string> noms = { "PEG", "BNF" }; for (const auto& nom : noms) {if (name.size() <= n && !name.compare(0, name.size(), s, name.size())) { return name.size(); // longueur traitée}
} renvoie -1 ; // erreur d'analyse})
},
{"~_", zom(cls("trn"))
}
};auto g = parser(syntax, addition_rules);assert(g.parse(" Bonjour BNF ! ")); cpp-peglib accepte le texte UTF8. . correspond à un point de code Unicode. En plus, ça u???? .
cpp-peglib prend en charge le rapport de position d'erreur la plus éloignée, comme décrit dans le document original de Bryan Ford.
Pour un meilleur rapport d'erreurs et une meilleure récupération, cpp-peglib prend en charge l'opérateur 'recovery' avec une étiquette qui peut être associée à une expression de récupération et à un message d'erreur personnalisé. Cette idée vient du fantastique article "Syntax Error Recovery in Parsing Expression Grammars" de Sergio Medeiros et Fabio Mascarenhas.
Le message personnalisé prend en charge %t qui est un espace réservé pour le jeton inattendu et %c pour le caractère Unicode inattendu.
Voici un exemple de grammaire de type 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)* / (!')' .)* Par exemple, ';'^semi est un sucre syntaxique pour (';' / %recovery(semi)) . L'opérateur %recover essaie de récupérer l'erreur à ';' en ignorant le texte saisi avec l'expression de récupération semi . De plus, semi est associé à un message personnalisé « point-virgule manquant dans l'affectation ».
Voici le résultat :
> cat sample.javapublic class Exemple { 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 : erreur de syntaxe, '<' inattendu, attente de '(', <NUMBER>, <NAME>.sample.java:8:5 : point-virgule manquant dans assignation.sample .java:8:6 : instruction invalideComme vous pouvez le constater, il peut désormais afficher plusieurs erreurs et fournir des messages d'erreur plus significatifs que les messages par défaut.
Nous pouvons associer des messages d'erreur personnalisés aux définitions.
# 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...
REMARQUE : S'il existe plusieurs éléments avec une instruction de message d'erreur dans un choix prioritaire, cette fonctionnalité risque de ne pas fonctionner comme prévu.
Nous pouvons modifier la règle de définition de départ comme ci-dessous.
grammaire automatique = R"( Début <- A A <- B (',' B)* B <- '[un]' / '[deux]' %espace blanc <- [ tn]*)";
peg::analyseur analyseur(grammaire, "A"); // La règle de départ est "A"
orpeg::analyseur analyseur ;
parser.load_grammar(grammaire, "A"); // La règle de départ est "A"parser.parse(" [un] , [deux] "); // D'ACCORD> 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)Calculatrice
Calculatrice (avec opérateurs d'analyseur)
Calculatrice (version AST)
Calculatrice (analyse d'expressions par escalade de priorité)
Calculatrice (version AST et analyse d'expressions par escalade de priorité)
Un petit compilateur PL/0 JIT en moins de 900 LOC avec analyseur LLVM et PEG
Un langage de programmation uniquement pour écrire le programme Fizz Buzz. :)
Licence MIT (© 2022 Yuji Hirose)
