我已经将原始解析器生成器重写为仅标头的库，该库使用模板和功能来提高类型安全性和清晰度。生成的解析器创建一个抽象语法树，可以使用功能和访问者模式对其进行有效评估。解析器存储中间步骤，以保证线性解析时间（如果语法包括左递归，则在最坏的情况下平方）。我的目标是创建一个专注于可用性的通用C ++解析器生成器。到目前为止，缺少文档，但是我相信用法从以下示例中或多或少会变得很清楚。

此代码使用左递归和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"] << "[ \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;
}


这段代码创建了无左递归且使用访问者模式的代码：

#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;
}


某些语言（包括C） ）使用歧义语法，如果x是a）变量或b）类型，则显然需要以不同的方式解析诸如x*y之类的表达式。为了解决这个问题，我介绍了语法过滤器，该语法过滤器是在匹配生产规则后立即调用的功能(expression)->bool。例如，以下语法中的单词仅在存在名为的类型时才注册为类型。 word和其他形式作为变量：

  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]*";


我想知道的是：根据示例，这里发生了什么情况是否很清楚？它们或其他语法可以改善吗？您认为该项目有用吗？

完整的源代码可以在GitHib上找到。

评论

使用Lex（Flex）/ Yacc（Bison）来执行此操作要容易得多。
恕我直言，Flex / Bison与众不同，学习和使用起来更加困难。首先，这只是您包括的c ++头文件。在Flex / Bison中，您需要混合使用多种语言，并且需要单独的工具来进行生成。其次，PEG语法与Flex / Bison语法有很大不同，因为它们不需要词法化。这使它们的构造更加直观。我知道这个特定的示例在Bison中是微不足道的，但是在大多数情况下，使用Flex实际上会变得更加复杂（例如，使用转义字符对String进行词法分析）。
我真的很喜欢使用命名空间std也在我的代码中重新使用它。
@MORTAL除外，这里它用于实现文件（在其他位置未包含），因此，如果您知道后果，那就很好了。
为了清楚起见，您是否要求对您在此处发布的代码或GitHub上的代码进行审查？如果是后者，则问题确实需要包含要检查的代码。

#1 楼

您已经在函数visit_left_binary_operator_list中的代码中嵌入了“数据”。您可以使用std::unordered_map<char, double(*)(double, double)>来帮助分离数据和实际算法：

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;
}


您可能还想为表达式\ $（（x- 1）/ 2）* 2 + 1 \ $。目前，它还不是很易读，但是感觉就像是野外很普遍的操作，需要一个适当的名称。

而不是对指数进行特殊处理，拥有它不是更好的选择一个visit_right_binary_operator_list呢？这将是对操作符进行更通用处理的第一步。另外，如果运算符可以是std::string实例而不是char实例来处理多字符运算符，则将更通用。

回答您的问题：虽然我对词法分析器和解析器没有完全的了解，您的代码对我来说很清楚。一开始我唯一遇到的问题是value() / get_value()，其命名可能有点含糊。但是一旦您了解了访问者，正则表达式和lambda，就可以快速了解正在发生的事情。

评论

\ $ \ begingroup \ $
+1操作员图的好主意！我可能应该做一些像range（begin，end，increment_size）来提高可读性。为了保持一致性，正确的操作员列表可能更有意义。我只是在这里省略了它，以使示例简短，并说明它们不需要左拨。但是我可能会选择更一致的方式。我在这里使用char是因为我想在示例中显示此功能，但也许string可以显示更多的可能性；-)。访问者模式是我最担心的部分，我想我会写一个教程来阐明。谢谢！
\ $ \ endgroup \ $
–拉尔·梅尔基奥尔
2014年12月18日上午11:55
\ $ \ begingroup \ $
@Lars我了解您的选择。当我编写第一个表达式解析器时（确实很丑），我只使用一个字符的运算符，并且只实现了我现在所需要的，而没有考虑未来。既然我们拥有用户定义的文字“”，那么使用std :: string应该更干净：)
\ $ \ endgroup \ $
–莫文
2014年12月18日在12:06

#2 楼

也许这应该是一个注释，但是为什么它只是纯标题呢？

更特别的是，为什么语法（例如"Set | Sum"之类的字符串）嵌入在标题软件中，而不是文本/语法中文件？我曾经在与解析器软件不同的文件中查看语法。

我的第二个评论是，您似乎没有单独的lexxer和解析器？

第三，乍看之下……...这样的语句是关于
[](expression e){ e.visitor().visit_left_binary_operator_list(e); }


...是关于什么的。但是显然（由于它们混入了语法中），如果我想将解析器与新语法一起使用（即，如果我想定义新语法），我需要理解/编写这样的语句？ br />

评论

\ $ \ begingroup \ $
我相信您误解了“仅标头”的含义。解析器生成器库本身仅是标头，这意味着您只需包含标头即可在项目中使用它。然后，您通常可以在实现文件中定义所需的语法。其次，您是对的，不需要简单的词法化步骤，因为您只需在上下文中定义标记并将它们与语言混合即可。第三，我不确定我是否理解您的问题，但是您不需要使用c ++ 11 lambda函数（正常的函数指针也可以使用）。
\ $ \ endgroup \ $
–拉尔·梅尔基奥尔
2014年12月18日上午11:20