Baixar cpp peglib - download do código-fonte cpp peglib

cpp peglib

C/C++

1.0.0

Baixar

cpp-peglib

Biblioteca PEG (Parsing Expression Grammars) somente cabeçalho C++ 17. Você pode começar a usá-lo imediatamente incluindo peglib.h em seu projeto.

Como esta biblioteca suporta apenas compiladores C++17, certifique-se de que a opção do compilador -std=c++17 esteja habilitada. ( /std:c++17 /Zc:__cplusplus para MSVC)

Você também pode experimentar a versão online, PEG Playground em https://yhirose.github.io/cpp-peglib.

A sintaxe PEG está bem descrita na página 2 do documento de Bryan Ford. cpp-peglib também suporta a seguinte sintaxe adicional por enquanto:

'...'i (operador literal que não diferencia maiúsculas de minúsculas)
[...]i (operador de classe de caracteres que não diferencia maiúsculas de minúsculas)
[^...] (operador de classe de caractere negado)
[^...]i (operador de classe de caractere negado sem distinção entre maiúsculas e minúsculas)
{2,5} (operador de repetição semelhante a Regex)
< ... > (Operador de limite de token)
~ (Ignorar operador)
x20 (caractere de número hexadecimal)
u10FFFF (caractere Unicode)
%whitespace (pular automaticamente espaços em branco)
%word (expressão de palavra)
$name( ... ) (operador de escopo de captura)
$name< ... > (operador de captura nomeado)
$name (operador de referência retroativa)
| (Operador de dicionário)
↑ (Operador de corte)
MACRO_NAME( ... ) (Regra ou Macro parametrizada)
{ precedence L - + L / * } (Analisando expressão infixa)
%recovery( ... ) (operador de recuperação de erros)
exp⇑label ou exp^label (açúcar de sintaxe para (exp / %recover(label)) )
label { error_message "..." } (instrução da mensagem de erro)
{ no_ast_opt } (sem instrução de otimização do nó AST)

A verificação de 'Fim da entrada' será feita como padrão. Para desativar a verificação, ligue para disable_eoi_check .

Esta biblioteca oferece suporte à análise de tempo linear conhecida como análise Packrat .

NOTA IMPORTANTE para algumas distribuições Linux, como Ubuntu e CentOS: Necessita da opção -pthread ao vincular. Consulte #23, #46 e #62.

Tenho certeza que você irá gostar deste excelente artigo "Análise prática com PEG e cpp-peglib" de bert hubert!

Como usar

Este é um exemplo simples de calculadora. Mostra como definir gramática, associar ações semânticas à gramática e lidar com valores semânticos.

 // (1) Incluir o arquivo de cabeçalho#include <peglib.h>#include <assert.h>#include <iostream>using namespace peg;using namespace std;int main(void) { // (2) Faça um analisador
  analisador analisador (R"( # Gramática para Calculadora... Aditivo <- Multiplicativo '+' Aditivo / Multiplicativo Multiplicativo <- Primário '*' Multiplicativo / Primário Primário <- '(' Aditivo ')' / Número Número <- < [ 0-9]+ > %espaço em branco <- [ t]* )");  assert(static_cast<bool>(parser) == true);  // (3) Ações de configuração
  parser["Additive"] = [](const SemanticValues &vs) {switch (vs.choice()) {case 0: // "Multiplicativo '+' Aditivo" return any_cast<int>(vs[0]) + any_cast< int>(vs[1]);default: // "Multiplicativo" return any_cast<int>(vs[0]);
    }
  };

  parser["Multiplicative"] = [](const SemanticValues &vs) {switch (vs.choice()) {case 0: // "Primário '*' Multiplicativo" return any_cast<int>(vs[0]) * any_cast< int>(vs[1]);default: // "Primário" return any_cast<int>(vs[0]);
    }
  };

  analisador["Número"] = [](const SemanticValues &vs) {return vs.token_to_number<int>();
  };  // (4) Analisar
  parser.enable_packrat_parsing(); // Habilita a análise do packrat.

  valor interno;
  parser.parse("(1 + 2) * 3", val);  afirmar(val == 9);
}

Para mostrar erros de sintaxe no texto gramatical:

 gramática automática = R"( # Gramática para Calculadora... Aditivo <- Multiplicativo '+' Aditivo / Multiplicativo Multiplicativo <- Primário '*' Multiplicativo / Primário Primário <- '(' Aditivo ')' / Número Número <- < [ 0-9]+ > %espaço em branco <- [ t]*)";

analisador analisador;

parser.set_logger([](linha size_t, size_t col, const string& msg, const string &rule) {
  cerr << linha << ":" << col << ": " << msg << "n";
});auto ok = parser.load_grammar(gramática);assert(ok);

Existem quatro ações semânticas disponíveis:

 [](const SemanticValues& vs, any& dt)
[](const Valores Semânticos& vs)
[](Valores Semânticos& vs, qualquer& dt)
[](Valores Semânticos& vs)

O valor SemanticValues contém as seguintes informações:

Valores semânticos
Informações de string correspondentes
Informações de token se a regra for literal ou usar um operador de limite de token
Número de escolha quando a regra é 'escolha priorizada'

any& dt é um dado de contexto de 'leitura-gravação' que pode ser usado para qualquer finalidade. Os dados de contexto iniciais são definidos no método peg::parser::parse .

Uma ação semântica pode retornar um valor de tipo de dados arbitrário, que será encapsulado por peg::any . Se um usuário não retornar nada em uma ação semântica, o primeiro valor semântico no argumento const SemanticValues& vs será retornado. (O analisador Yacc tem o mesmo comportamento.)

Aqui mostra a estrutura SemanticValues :

 struct SemanticValues: protegido std::vector<any>
{ //Inserir texto
  const char* caminho;  const char* ss;  //Sequência correspondente
  std::string_view sv() const { return sv_; } // Número da linha e coluna na qual a string correspondente está
  std::pair<tamanho_t, tamanho_t> line_info() const;  // Tokens
  tokens std::vector<std::string_view>;
  std::string_view token(tamanho_t id = 0) const;  //Conversão de token
  std::string token_to_string(tamanho_t id = 0) const;  modelo <nome do tipo T> T token_to_number() const;  // Número da escolha (índice baseado em 0)
  size_t escolha() const;  //Transforma o vetor de valor semântico em outro vetor
  template <nome_tipo T> vetor<T> transform(tamanho_t beg = 0, tamanho_t end = -1) const;
}

O exemplo a seguir usa o operador < ... > , que é o operador de limite de token .

 peg::parser analisador(R"( ROOT <- _ TOKEN (',' _ TOKEN)* TOKEN <- < [a-z0-9]+ > _ _ <- [ trn]*)");

parser["TOKEN"] = [](const SemanticValues& vs) { // 'token' não inclui espaços em branco à direita
  token automático = vs.token();
};auto ret = parser.parse("token1, token2");

Podemos ignorar valores semânticos desnecessários da lista usando o operador ~ .

 peg::parser analisador(R"( ROOT <- _ ITEM (',' _ ITEM _)* ITEM <- ([a-z0-9])+ ~_ <- [ t]*)");

analisador["ROOT"] = [&](const SemanticValues& vs) { assert(vs.size() == 2); // deveria ser 2 em vez de 5.};auto ret = parser.parse(" item1, item2 ");

A gramática a seguir é igual à anterior.

 peg::parser analisador(R"( ROOT <- ~_ ITEM (',' ~_ ITEM ~_)* ITEM <- ([a-z0-9])+ _ <- [ t]*)");

O suporte de predicado semântico está disponível com uma ação de predicado .

 peg::parser analisador("NÚMERO <- [0-9]+");

analisador["NUMBER"] = [](const SemanticValues &vs) { return vs.token_to_number<long>();
};

analisador["NUMBER"].predicate = [](const SemanticValues &vs,const std::any & /*dt*/, std::string &msg) { if (vs.token_to_number<long>() != 100) {
    msg = "erro de valor!!";return false;
  } retornar verdadeiro;
};long val;auto ret = parser.parse("100", val);assert(ret == true);assert(val == 100);

ret = parser.parse("200", val);assert(ret == false);

ações de entrar e sair também estão disponíveis.

 analisador["RULE"].enter = [](const Context &c, const char* s, size_t n, any& dt) {
  std::cout << "enter" << std::endl;
};

analisador["RULE"] = [](const SemanticValues& vs, any& dt) {
  std::cout << "ação!" << std::endl;
};

analisador["RULE"].leave = [](const Context &c, const char* s, size_t n, size_t matchlen, qualquer& valor, qualquer& dt) {
  std::cout << "sair" << std::endl;
};

Você pode receber informações de erro por meio de um registrador:

 parser.set_logger([](linha size_t, size_t col, const string& msg) {
  ...
});

parser.set_logger([](linha size_t, size_t col, const string& msg, const string &rule) {
  ...
});

Ignorando espaços em branco

Como você pode ver no primeiro exemplo, podemos ignorar os espaços em branco entre os tokens automaticamente com a regra %whitespace .

A regra %whitespace pode ser aplicada às três condições a seguir:

espaços finais em tokens
espaços iniciais no texto
espaços à direita em strings literais em regras

Estes são 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.

A gramática a seguir aceita one, "two three", four .

ROOT         <- ITEM (',' ITEM)*
ITEM         <- WORD / PHRASE
WORD         <- < [a-z]+ >
PHRASE       <- < '"' (!'"' .)* '"' >

%whitespace  <-  [ trn]*

Expressão de palavra

 peg::parser parser(R"( ROOT <- 'hello' 'world' %whitespace <- [ trn]* %word <- [az]+)");

parser.parse("olá mundo"); //OKparser.parse("olámundo");  //NG

Captura/referência retroativa

 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("Este é <b>um texto de <u>teste</u></b>."); // OKparser.parse("Este é <b>um texto de <u>teste</b></u>."); // NGparser.parse("Este é <b>um <u>texto de teste</b>.");     //NG

Dicionário

| O operador nos permite criar um dicionário de palavras para pesquisa rápida usando a estrutura Trie internamente. Não precisamos nos preocupar com a ordem das palavras.

START <- 'This month is ' MONTH '.'
MONTH <- 'Jan' | 'January' | 'Feb' | 'February' | '...'

Podemos descobrir qual item corresponde a choice() .

 analisador["MÊS"] = [](const SemanticValues &vs) { auto id = vs.choice();
};

Ele suporta o modo que não diferencia maiúsculas de minúsculas.

START <- 'This month is ' MONTH '.'
MONTH <- 'Jan'i | 'January'i | 'Feb'i | 'February'i | '...'i

Operador de corte

O operador ↑ pode mitigar o problema de desempenho de retrocesso, mas corre o risco de alterar o significado da gramática.

S <- '(' ↑ P ')' / '"' ↑ P '"' / P
P <- 'a' / 'b' / 'c'

Quando analisamos (z com a gramática acima, não precisamos voltar atrás em S depois que ( for correspondido, porque um operador cut é inserido lá.

Regra ou macro parametrizada

# 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 > _

Analisando expressão infixa por escalada de precedência

Em relação ao algoritmo de escalada de precedência , consulte este artigo.

 analisador analisador (R"( EXPRESSÃO <- INFIX_EXPRESSION(ATOM, OPERATOR) ATOM <- NUMBER / '(' EXPRESSION ')' OPERATOR <- < [-+/*] > NUMBER <- < '-'? [0-9 ]+ > %whitespace <- [ t]* # Declara a ordem de precedência INFIX_EXPRESSION(A, O) <- A (O A)* { precedência L + - L * / })");

analisador["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 += num; quebrar;      case '-': resultado -= num; quebrar;      case '*': resultado *= num; quebrar;      case '/': resultado /= num; quebrar;
    }
  } retornar resultado;
};
analisador["OPERATOR"] = [](const SemanticValues& vs) { return *vs.sv(); };
analisador["NUMBER"] = [](const SemanticValues& vs) { return vs.token_to_number<long>(); };valor longo;
parser.parse(" -1 + (1 + 2) * 3 - -1", val);assert(val == 9);

a instrução de precedência pode ser aplicada apenas à seguinte regra de estilo de 'lista'.

Rule <- Atom (Operator Atom)* {
  precedence
    L - +
    L / *
    R ^
}

a instrução de precedência contém entradas de informações de precedência. Cada entrada começa com associatividade que é 'L' (esquerda) ou 'R' (direita), seguida por tokens literais de operador. A primeira entrada tem o nível de pedido mais alto.

Geração AST

cpp-peglib é capaz de gerar uma AST (Abstract Syntax Tree) durante a análise. O método enable_ast na classe peg::parser habilita o recurso.

NOTA: Um nó AST contém um token correspondente como std::string_vew para desempenho e menos uso de memória. É responsabilidade do usuário manter o texto fonte original junto com a árvore AST gerada.

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 remove nós redundantes para tornar um AST mais simples. Se você deseja desabilitar este comportamento de regras específicas, a instrução no_ast_opt pode ser usada.

Ele chama internamente peg::AstOptimizer para fazer o trabalho. Você pode criar seus próprios otimizadores AST para atender às suas necessidades.

Veja os usos reais no exemplo da calculadora AST e no exemplo da linguagem PL/0.

Faça um analisador com combinadores de analisador

Em vez de criar um analisador analisando o texto da sintaxe PEG, também podemos construir um analisador manualmente com combinadores de analisador . Aqui está um exemplo:

 usando namespace peg;usando namespace std;vector<string> tags;

Definição ROOT, TAG_NAME, _;
ROOT <= seq(_, zom(seq(chr('['), TAG_NAME, chr(']'), _)));
TAG_NAME <= oom(seq(npd(chr(']')), ponto())), [&](const SemanticValues& vs) {
              tags.push_back(vs.token_to_string());
            };
_ <= zom(cls(" t"));auto ret = ROOT.parse(" [tag1] [tag:2] [tag-3] ");

A seguir estão os operadores disponíveis:

Operador	Descrição	Operador	Descrição
sequência	Sequência	cho	Escolha Priorizada
zoom	Zero ou mais	ah	Um ou mais
optar	Opcional	apd	E predicado
npd	Não predicado	aceso	Cadeia literal
liti	String literal sem distinção entre maiúsculas e minúsculas	cls	Classe de personagem
ncls	Classe de personagem negado	cr	Personagem
ponto	Qualquer personagem	tok	Limite do token
sinal	Ignorar valor semântico	csc	Escopo de captura
boné	Capturar	bkr	Referência anterior
dica	Dicionário	pré	Expressão infixa
recomendação	Expressão infixa	usr	Analisador definido pelo usuário
representante	Repetição

Ajustar definições

É possível adicionar/substituir definições.

 sintaxe automática = R"( ROOT <- _ 'Olá' _ NOME '!' _)";

Regras adicionais_rules = {
  {"NAME", usr([](const char* s, size_t n, SemanticValues& vs, any& dt) -> size_t { static vector<string> nomes = { "PEG", "BNF" }; for (const auto& nome : nomes) {if (name.size() <= n && !name.compare(0, name.size(), s, name.size())) { return name.size();
      } retornar -1; //erro de análise})
  },
  {"~_",zom(cls("trn"))
  }
};auto g = analisador(sintaxe, regras_adicionais);assert(g.parse(" Olá BNF! "));

Suporte Unicode

cpp-peglib aceita texto UTF8. . corresponde a um ponto de código Unicode. Além disso, ele suporta u???? .

Relatório de erros e recuperação

cpp-peglib suporta o relatório de posição de erro de falha mais distante conforme descrito no documento original de Bryan Ford.

Para melhor relatório de erros e recuperação, cpp-peglib suporta o operador 'recuperação' com rótulo que pode ser associado a uma expressão de recuperação e uma mensagem de erro personalizada. Essa ideia vem do fantástico artigo "Recuperação de erros de sintaxe na análise de gramáticas de expressões", de Sergio Medeiros e Fabio Mascarenhas.

A mensagem personalizada suporta %t , que é um espaço reservado para o token inesperado, e %c para o caractere Unicode inesperado.

Aqui está um exemplo de gramática semelhante 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 exemplo, ';'^semi é um açúcar sintático para (';' / %recovery(semi)) . O operador %recover tenta recuperar o erro em ';' ignorando o texto de entrada com a expressão de recuperação semi . Além disso, semi está associado a uma mensagem personalizada "falta de ponto e vírgula na atribuição".

Aqui está o resultado:

 > cat sample.javapublic class Exemplo { 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: erro de sintaxe, '<' inesperado, esperando '(', <NÚMERO>, <NOME>.sample.java:8:5: faltando ponto e vírgula na atribuição.sample .java:8:6: declaração inválida

Como você pode ver, agora ele pode mostrar mais de um erro e fornecer mensagens de erro mais significativas do que as mensagens padrão.

Mensagem de erro personalizada para definições

Podemos associar mensagens de erro personalizadas às definições.

# 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: Se houver mais de um elemento com uma instrução de mensagem de erro em uma escolha priorizada, esse recurso poderá não funcionar conforme o esperado.

Alterar a regra de definição inicial

Podemos alterar a regra de definição inicial conforme abaixo.

 gramática automática = R"( Iniciar <- A A <- B (',' B)* B <- '[um]' / '[dois]' %espaço em branco <- [ tn]*)";

peg::parser analisador(gramática, "A"); // A regra inicial é "A"

  orpeg::parser analisador;
parser.load_grammar(gramática, "A"); // A regra inicial é "A"parser.parse(" [one] , [two] "); // OK

peglint - utilitário lint de sintaxe PEG

Construir peglint

> 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

Verificação gramatical

> 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.

Verificação de origem

> 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

AST

> 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)

Otimização AST

> peglint --ast --opt --source "1 + 2 * 3" a.peg
+ Additive
  - Multiplicative[Number] (1)
  + Additive[Multiplicative]
    - Primary[Number] (2)
    - Multiplicative[Number] (3)

Ajuste a otimização AST com a instrução `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)