Un generador de perros de PEG de PEG para la recursión izquierda y la ambigüedad de la gramática -- ++ campo con c++11 campo con parsing campo con template campo con generator camp codereview Relacionados El problema

A header-only linear-time C++11 PEG parser generator supporting left-recursion and grammar ambiguity


27
vote

problema

Español

He reescrito a mi original Parser Generator a una biblioteca de solo encabezado que Utiliza plantillas y funcionales para una mayor seguridad y claridad de tipo. El analizador generado crea un árbol de sintaxis abstracto que se puede evaluar de manera efectiva utilizando funcionales y un patrón de visitantes. El analizador memoriza los pasos intermedios que resultan en un tiempo de análisis lineal garantizado (cuadrado en el peor de los casos si la gramática incluye la recursión izquierda). Mi objetivo es crear un generador de parser de C ++ de propósito general con enfoque en la facilidad de uso. Falta la documentación hasta ahora, pero creo que el uso debe ser más o menos claro del siguiente ejemplo.

Este código crea una calculadora simple usando la recursión izquierda y los funcionales C ++ 11:

  #include <iostream> #include <unordered_map> #include <cmath>  #include "parser/parser.h"  using namespace std; using namespace lars;  int main(int argc, char ** argv){   parsing_expression_grammar_builder<double> g;   using expression = expression<double>;    unordered_map<string,double> variables;    g["Expression"] << "Set | Sum"                       << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Set"       ] << "Name '=' Sum"                    << [&](expression e){ variables[e[0].string()] = e[1].get_value();        };   g["Sum"       ] << "Add | Subtract | Product"        << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Add"       ] << "Sum '+' Product"                 << [ ](expression e){ e.value() = e[0].get_value() + e[1].get_value();    };   g["Subtract"  ] << "Sum '-' Product"                 << [ ](expression e){ e.value() = e[0].get_value() - e[1].get_value();    };   g["Product"   ] << "Multiply | Divide | Exponent"    << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Multiply"  ] << "Product '*' Exponent"            << [ ](expression e){ e.value() = e[0].get_value() * e[1].get_value();    };   g["Divide"    ] << "Product '/' Exponent"            << [ ](expression e){ e.value() = e[0].get_value() / e[1].get_value();    };   g["Exponent"  ] << "Power | Atomic"                  << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Power"     ] << "Atomic '^' Exponent"             << [ ](expression e){ e.value() = pow(e[0].get_value(),e[1].get_value()); };   g["Atomic"    ] << "Number | Brackets | Variable"    << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Brackets"  ] << "'(' Sum ')'"                     << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Number"    ] << "'-'? [0-9]+ ('.' [0-9]+)?"       << [ ](expression e){ e.value() = stod(e.string());                       };   g["Variable"  ] << "Name"                            << [&](expression e){ e.value() = variables[e[0].string()];               };   g["Name"      ] << "[a-zA-Z] [a-zA-Z0-9]*"           ;    g.set_starting_rule("Expression");    g["Whitespace"] << "[  ]";   g.set_separator_rule("Whitespace");    auto p = g.get_parser();    while (true) {     string str;     cout << "> ";     getline(cin,str);     if(str == "q" || str == "quit")break;     try {       auto e = p.parse(str);       cout << str << " = " << *e.evaluate() << endl;     }     catch (parser<double>::error e){       cout << "  ";       for(auto i UNUSED :range(e.begin_position().character))cout << " ";       for(auto i UNUSED :range(e.length()))cout << "~";       cout << "^ ";       cout << e.error_message() << " while parsing " << e.rule_name() << endl;     }   }    return 0; }   

Este código crea lo mismo sin la recursión a la izquierda y utilizando un patrón de visitante:

  #include <iostream> #include <unordered_map> #include <cmath>  #include "parser/parser.h"  using namespace std; using namespace lars;  class math_visitor{    double value;   unordered_map<string,double> variables;  public:    double get_value(){     return value;   }    double get_value(expression<math_visitor> e){     e.accept(this);     return get_value();   }    void visit_number(expression<math_visitor> e){     value = stod(e.string());   }    void visit_set_variable(expression<math_visitor> e){     variables[e[0].string()] = get_value(e[1]);   }    void visit_variable(expression<math_visitor> e){     value = variables[e[0].string()];   }    void visit_left_binary_operator_list (expression<math_visitor> e){     double lhs = get_value(e[0]);      for(auto i:range((e.size()-1)/2)*2+1){       double rhs = get_value(e[i+1]);            if(e[i].character()=='+'){ lhs = lhs + rhs; }       else if(e[i].character()=='-'){ lhs = lhs - rhs; }       else if(e[i].character()=='*'){ lhs = lhs * rhs; }       else if(e[i].character()=='/'){ lhs = lhs / rhs; }       else throw "undefined operator";     }      value = lhs;   }    void visit_exponent(expression<math_visitor> e){     if(e.size() == 1) e[0].accept();     else value = pow(get_value(e[0]), get_value(e[1]));   }  };  int main(int argc, char ** argv){   parsing_expression_grammar_builder<math_visitor> g;   using expression = expression<math_visitor>;    g["Expression"] << "Set | Sum"                               << [](expression e){ e[0].accept(); };   g["Set"       ] << "Name '=' Sum"                            << [](expression e){ e[0].visitor().visit_set_variable(e); };   g["Sum"       ] << "Product  (AddSub Product)*"              << [](expression e){ e.visitor().visit_left_binary_operator_list(e); };   g["AddSub"    ] << "[+-]"                                    ;   g["Product"   ] << "Exponent (MulDiv Exponent)*"             << [](expression e){ e.visitor().visit_left_binary_operator_list(e); };   g["MulDiv"    ] << "[*/]"                                    ;   g["Exponent"  ] << "Atomic (('^' | '**') Exponent) | Atomic" << [](expression e){ e.visitor().visit_exponent(e); };   g["Atomic"    ] << "Number | Brackets | Variable"            << [](expression e){ e[0].accept(); };   g["Brackets"  ] << "'(' Sum ')'"                             << [](expression e){ e[0].accept(); };   g["Number"    ] << "'-'? [0-9]+ ('.' [0-9]+)?"               << [](expression e){ e.visitor().visit_number(e); };   g["Variable"  ] << "Name"                                    << [](expression e){ e.visitor().visit_variable(e); };   g["Name"      ] << "[a-zA-Z] [a-zA-Z]*"                      ;    g.set_starting_rule("Expression");    g["Whitespace"] << "[  ]";    g.set_separator_rule("Whitespace");    auto p = g.get_parser();    math_visitor visitor;    while (true) {     string str;     cout << "> ";     getline(cin,str);     if(str == "q" || str == "quit")break;     cout << " -> ";     try { p.parse(str).accept(&visitor); cout << visitor.get_value(); }     catch (parser<math_visitor>::error e){ cout << e.error_message(); }     cout << endl;   }    return 0; }   

Algunos idiomas (incluidos C) Use gramáticas ambiguas donde, obviamente, una expresión, como x*y , obviamente, debe analizarse de manera diferente si X es A) una variable o B) un tipo. Para resolver esto, he introducido filtros de gramática que son funcionales (expression)->bool se llama inmediatamente después de hacer coincidir una regla de producción.

Por ejemplo, una palabra en la siguiente gramática solo se registrará como un tipo si hay un tipo llamado como la palabra y, de lo contrario, como variable:

    unordered_set<string> types;   g["Expression"] << "Type | Variable";   g["Type"]       << "Name" >> [&](expression e)->bool{ return types.find(e[0].string()) != types.end(); };   g["Variable"]   << "Name" ;   g["Name"]       << "[a-zA-Z] [a-zA-Z0-9]*";   

Lo que me gustaría saber es: ¿Es claro qué está sucediendo aquí en función de los ejemplos? ¿Pueden mejorarse ellos u otra sintaxis? ¿Crees que el proyecto es útil?

El código fuente completo está disponible en GITHIB .

Original en ingles

I've rewritten my original parser generator to a header-only library which uses templates and functionals for better type safety and clarity. The generated parser creates an abstract syntax tree which can be evaluated effectively using functionals and a visitor pattern. The parser memorizes intermediate steps resulting in guaranteed linear parsing time (squared in worst-case if the grammar includes left-recursion). My goal is to create a general-purpose C++ parser generator with focus on usability. So far documentation is missing but I believe the usage should become more or less clear from the following example.

This code creates a simple calculator using left-recursion and C++11 functionals:

#include <iostream> #include <unordered_map> #include <cmath>  #include "parser/parser.h"  using namespace std; using namespace lars;  int main(int argc, char ** argv){   parsing_expression_grammar_builder<double> g;   using expression = expression<double>;    unordered_map<string,double> variables;    g["Expression"] << "Set | Sum"                       << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Set"       ] << "Name '=' Sum"                    << [&](expression e){ variables[e[0].string()] = e[1].get_value();        };   g["Sum"       ] << "Add | Subtract | Product"        << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Add"       ] << "Sum '+' Product"                 << [ ](expression e){ e.value() = e[0].get_value() + e[1].get_value();    };   g["Subtract"  ] << "Sum '-' Product"                 << [ ](expression e){ e.value() = e[0].get_value() - e[1].get_value();    };   g["Product"   ] << "Multiply | Divide | Exponent"    << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Multiply"  ] << "Product '*' Exponent"            << [ ](expression e){ e.value() = e[0].get_value() * e[1].get_value();    };   g["Divide"    ] << "Product '/' Exponent"            << [ ](expression e){ e.value() = e[0].get_value() / e[1].get_value();    };   g["Exponent"  ] << "Power | Atomic"                  << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Power"     ] << "Atomic '^' Exponent"             << [ ](expression e){ e.value() = pow(e[0].get_value(),e[1].get_value()); };   g["Atomic"    ] << "Number | Brackets | Variable"    << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Brackets"  ] << "'(' Sum ')'"                     << [ ](expression e){ e.value() = e[0].get_value();                       };   g["Number"    ] << "'-'? [0-9]+ ('.' [0-9]+)?"       << [ ](expression e){ e.value() = stod(e.string());                       };   g["Variable"  ] << "Name"                            << [&](expression e){ e.value() = variables[e[0].string()];               };   g["Name"      ] << "[a-zA-Z] [a-zA-Z0-9]*"           ;    g.set_starting_rule("Expression");    g["Whitespace"] << "[ \t]";   g.set_separator_rule("Whitespace");    auto p = g.get_parser();    while (true) {     string str;     cout << "> ";     getline(cin,str);     if(str == "q" || str == "quit")break;     try {       auto e = p.parse(str);       cout << str << " = " << *e.evaluate() << endl;     }     catch (parser<double>::error e){       cout << "  ";       for(auto i UNUSED :range(e.begin_position().character))cout << " ";       for(auto i UNUSED :range(e.length()))cout << "~";       cout << "^\n";       cout << e.error_message() << " while parsing " << e.rule_name() << endl;     }   }    return 0; } 

This code creates the same without left-recursion and using a visitor pattern:

#include <iostream> #include <unordered_map> #include <cmath>  #include "parser/parser.h"  using namespace std; using namespace lars;  class math_visitor{    double value;   unordered_map<string,double> variables;  public:    double get_value(){     return value;   }    double get_value(expression<math_visitor> e){     e.accept(this);     return get_value();   }    void visit_number(expression<math_visitor> e){     value = stod(e.string());   }    void visit_set_variable(expression<math_visitor> e){     variables[e[0].string()] = get_value(e[1]);   }    void visit_variable(expression<math_visitor> e){     value = variables[e[0].string()];   }    void visit_left_binary_operator_list (expression<math_visitor> e){     double lhs = get_value(e[0]);      for(auto i:range((e.size()-1)/2)*2+1){       double rhs = get_value(e[i+1]);            if(e[i].character()=='+'){ lhs = lhs + rhs; }       else if(e[i].character()=='-'){ lhs = lhs - rhs; }       else if(e[i].character()=='*'){ lhs = lhs * rhs; }       else if(e[i].character()=='/'){ lhs = lhs / rhs; }       else throw "undefined operator";     }      value = lhs;   }    void visit_exponent(expression<math_visitor> e){     if(e.size() == 1) e[0].accept();     else value = pow(get_value(e[0]), get_value(e[1]));   }  };  int main(int argc, char ** argv){   parsing_expression_grammar_builder<math_visitor> g;   using expression = expression<math_visitor>;    g["Expression"] << "Set | Sum"                               << [](expression e){ e[0].accept(); };   g["Set"       ] << "Name '=' Sum"                            << [](expression e){ e[0].visitor().visit_set_variable(e); };   g["Sum"       ] << "Product  (AddSub Product)*"              << [](expression e){ e.visitor().visit_left_binary_operator_list(e); };   g["AddSub"    ] << "[+-]"                                    ;   g["Product"   ] << "Exponent (MulDiv Exponent)*"             << [](expression e){ e.visitor().visit_left_binary_operator_list(e); };   g["MulDiv"    ] << "[*/]"                                    ;   g["Exponent"  ] << "Atomic (('^' | '**') Exponent) | Atomic" << [](expression e){ e.visitor().visit_exponent(e); };   g["Atomic"    ] << "Number | Brackets | Variable"            << [](expression e){ e[0].accept(); };   g["Brackets"  ] << "'(' Sum ')'"                             << [](expression e){ e[0].accept(); };   g["Number"    ] << "'-'? [0-9]+ ('.' [0-9]+)?"               << [](expression e){ e.visitor().visit_number(e); };   g["Variable"  ] << "Name"                                    << [](expression e){ e.visitor().visit_variable(e); };   g["Name"      ] << "[a-zA-Z] [a-zA-Z]*"                      ;    g.set_starting_rule("Expression");    g["Whitespace"] << "[ \t]";    g.set_separator_rule("Whitespace");    auto p = g.get_parser();    math_visitor visitor;    while (true) {     string str;     cout << "> ";     getline(cin,str);     if(str == "q" || str == "quit")break;     cout << " -> ";     try { p.parse(str).accept(&visitor); cout << visitor.get_value(); }     catch (parser<math_visitor>::error e){ cout << e.error_message(); }     cout << endl;   }    return 0; } 

Some languages (including C) use ambiguous grammars where an expression such as x*y obviously needs to be parsed differently if x is a) a variable or b) a type. To resolve this I introduced grammar filters which are functionals (expression)->bool called immediately after matching a production rule.

For example, a word in the following grammar will only register as a type if there is a type named as the word and otherwise as a variable:

  unordered_set<string> types;   g["Expression"] << "Type | Variable";   g["Type"]       << "Name" >> [&](expression e)->bool{ return types.find(e[0].string()) != types.end(); };   g["Variable"]   << "Name" ;   g["Name"]       << "[a-zA-Z] [a-zA-Z0-9]*"; 

What I would like to know is: Is it clear what is happening here based on the examples? Can they or other syntax be improved? Do you think the project is useful?

The full source code is available at GitHib.

              
         
         

Lista de respuestas

7
 
vote
vote
La mejor respuesta
 

Tiene "datos" incrustados en código en la función visit_left_binary_operator_list . Puede usar un 9988776665544331 para ayudar a separar los datos y el algoritmo real:

  void visit_left_binary_operator_list (expression<math_visitor> e){    static const std::unordered_map<char, double(*)(double, double)> binary_ops = {     { '+', [](double x, double y) { return x + y; } },     { '-', [](double x, double y) { return x - y; } },     { '*', [](double x, double y) { return x * y; } },     { '/', [](double x, double y) { return x / y; } }   };    double lhs = get_value(e[0]);    for(auto i:range((e.size()-1)/2)*2+1){     auto op = binary_ops.find(e[i].character());     if (op == binary_ops.end()) {       throw "undefined operator";     }      double rhs = get_value(e[i+1]);     lhs = op->second(lhs, rhs);   }    value = lhs; }   

También puede querer encontrar un nombre adecuado para la expresión $ ((X-1) / 2) * 2 + 1 $. Actualmente, no es realmente legible, pero se siente como una operación lo suficientemente común en la naturaleza para necesitar un nombre adecuado.

En lugar de tener un caso especial para exponente, ¿no sería mejor tener un 99887776655544333 ? Sería un primer paso para un manejo más genérico de los operadores. Además, sería más genérico si los operadores podrían ser std::string instancias en lugar de char instancias para manejar operadores de caracteres múltiples.

Para responder a su pregunta: mientras que no tengo una comprensión completa de los lexores y los analizadores, lo que su código es claro para mí. Lo único que tenía un problema al principio fue el 99887776655544336 get_value() cuyo nombramiento puede ser un poco ambiguo. Pero una vez que conoce a los visitantes, regex y lambdas, usted rápidamente tiene una buena comprensión de lo que está sucediendo.

 

You have "data" embedded in code in the function visit_left_binary_operator_list. You could use an std::unordered_map<char, double(*)(double, double)> to help separate the data and the actual algorithm:

void visit_left_binary_operator_list (expression<math_visitor> e){    static const std::unordered_map<char, double(*)(double, double)> binary_ops = {     { '+', [](double x, double y) { return x + y; } },     { '-', [](double x, double y) { return x - y; } },     { '*', [](double x, double y) { return x * y; } },     { '/', [](double x, double y) { return x / y; } }   };    double lhs = get_value(e[0]);    for(auto i:range((e.size()-1)/2)*2+1){     auto op = binary_ops.find(e[i].character());     if (op == binary_ops.end()) {       throw "undefined operator";     }      double rhs = get_value(e[i+1]);     lhs = op->second(lhs, rhs);   }    value = lhs; } 

You may also want to find a suitable name for the expression \$ ((x-1)/2)*2+1 \$. Currently, it is not really readable, but it feels like an operation common enough in the wild to need a proper name.

Instead of having a special case for exponent, wouldn't it be better to have a visit_right_binary_operator_list as well? It would be a first step to some more generic handling of operators. Also, it would be more generic if operators could be std::string instances instead of char instances to handle multi-character operators.

To answer your question: while I don't have a full understanding of lexers and parsers, what your code does is clear to me. The only thing I had a problem with at first was the value()/get_value() whose naming can be a little bit ambiguous. But once you know visitors, regex and lambdas, you quickly have a good understanding of what is happening.

 
 
   
   
1
 
vote

Tal vez este debería ser un comentario, pero ¿por qué es solo el encabezado?

Más especialmente, ¿por qué la gramática (por ejemplo, cadenas como "Set | Sum"8 ) incorporada en el software de encabezado, en lugar de estar en un archivo de texto / gramática? Estoy acostumbrado a ver la gramática en un archivo que está separado del software del analizador. < / p>

Mi segundo comentario es que no pareces tener un lexxer y analizador separados?

En tercer lugar, no es obvio a primera vista, qué afirmaciones como ...

  [](expression e){ e.visitor().visit_left_binary_operator_list(e); }   

... se trata. Sin embargo, aparentemente (ya que están mezclados a la gramática), necesitaría entender / escribir declaraciones de esa manera, si quiero usar el analizador con una nueva gramática (es decir, si quiero definir una nueva gramática)? / p>

 

Maybe this should be a comment but why is it header-only?

More especially, why is the grammar (e.g. strings such as "Set | Sum") embedded in the header software, instead of being in a text/grammar file? I'm used to seeing the grammar in a file that's separate from the parser software.

My second comment is that you don't seem to have a separate lexxer and parser?

Thirdly it's not obvious at first glance what statements like ...

[](expression e){ e.visitor().visit_left_binary_operator_list(e); } 

... are about. Yet apparently (since they're mixed-in to the grammar) I'd need to understand/write statements like that, if I want to use the parser with a new grammar (i.e. if I want to define a new grammar)?

 
 
 
 

Relacionados problema

3  Aplanamiento recursivo de secuencias rápidas - un enfoque demasiado complicado  ( Recursive flattening of swift sequences an overly complicated approach ) 
Recientemente leí y respondí Martin R 's Recursive Aplanking of Swift Secuencias y continuó jugando con el código hasta que llegué a algo que era bastante...

1  Función del generador para enumerar archivos  ( Generator function to enumerate files ) 
Quiero implementar una función que enumera todos los archivos en el directorio. Creo que la función debe devuelve una promesa , porque se prefiere la llam...

4  Combinando fragmentos de datos en una tubería del generador  ( Combining fragments of data in a generator pipeline ) 
Editar: Parece que el enfoque de programación basado en flujo (o reactivo) ayudaría aquí; Hay algunas bibliotecas en Python que lo intentan. Intenté seguir ...

1  Una clase con un puntero de función en lugar de un generador  ( A class with a function pointer instead of a generator ) 
Estoy construyendo archivos Tikz, un PDF para cada imagen que tengo. El propósito es agregar texto a cada uno por separado. Las imágenes son LEGION, así que c...

3  Parser de texto implementado como generador  ( Text parser implemented as a generator ) 
A menudo necesito analizar el texto separado por pestañas (generalmente de un archivo enorme) a los registros. Escribí un generador para hacer eso por mí; ¿Ha...

10  Uso de generadores para imprimir la estructura similar a un árbol de un proyecto  ( Using generators to print the tree like structure of a project ) 
El objetivo de este código es imprimir el árbol de entidad de un proyecto VHDL. Hay un readme y pruebas muy mínimas en la github repo . Estoy tratando de h...

2  ASYNC LINKED LISTA DE Y DESYNC ITERABLE  ( Async linked list to and from async iterable ) 
Estoy trabajando en algunas cosas que funciona mejor con listas vinculadas (inmutables ASYNC), como esta: { value: 'one', next: async () => { value: 'two',...

4  Creación de un índice invertido de documentos de texto  ( Creating an inverted index from text documents ) 
Estoy trabajando en un proyecto de recuperación de información, donde tengo que procesar un Datos de texto de ~ 1.5 GB y crear un diccionario (palabras, frecu...

9  Generador de cadena aleatorio en C  ( Random string generator in c ) 
He creado esta pequeña función solo para practicar el código C. Es un simple generador de cadenas aleatorias. #include <string.h> #include <time.h> char *...

2  Proyecto EULER # 2: Suma de incluso números de Fibonacci, utilizando generadores  ( Project euler 2 sum of even fibonacci numbers using generators ) 
Actualmente estoy trabajando en Project Euler Problem # 2, lo que requiere que imprima la suma de todos los números de Fibonacci todos incluso por debajo ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos