c++ - 使用git中的cparse库解析用户输入的字符串

Question

我是c ++编程的新手，并希望使用在我的项目https://github.com/cparse/cparse中找到的cparse库。我想解释用户输入的字符串，例如“ a*(b+3)”（对于变量a和b），并在不同的输入集上重复使用它作为函数。

例如，以一个文本文件作为输入，每行输入2个double数字，我的代码将在每行中写入一个结果为“ a*(b+3)”的新文件（假设a是第一个数字，而b是第二）。

当我尝试从git包含cparse库时，出现了我的问题。我天真地遵循了安装说明（是git的新手）：

$ cd cparse
$ make release

但是我不能像在Windows中那样使用make命令。我尝试下载zip文件并将 .cpp和 .h文件直接复制到项目中，并在Visual Studio中使用“包括现有的”选项，但遇到了大量的编译器错误，无法自己使代码正常工作。

我是否以某种方式错过了重点？我如何使它工作？

失败的话，还有另一种方法来解析用户输入的字符串并将其用作函数吗？

Answer 1

失败的话，还有另一种方法来解析用户输入的字符串并将其用作函数吗？


我想回答您的问题的这一部分，因为我觉得功能齐全的C解析器对于您的意图可能有点过于繁琐。 （顺便说一句，一旦您运行了C解析器–如何处理其输出？动态链接？）

相反，我想向您展示如何自行构建一个简单的计算器（带有递归下降解析器）。对于我将要使用的技术的文档，我热烈推荐Compilers (Principles, Techniques & Tools) by Aho, Lam, Sethi, Ullman（更好地称为“龙书”），尤其是第4章。

小计算器项目

在下文中，我将逐步描述我的示例解决方案。

语言设计

在开始编写编译器或解释器之前，定义一种可接受的语言是合理的。我想使用由以下组成的C：表达式的非常有限的子集：


C像浮点数（常数）
像C的标识符（变量）
一元运算符+和-
二进制运算符+，-，*和/
括号()
分号;（标记表达式的末尾，必须的）。


空格（包括换行符）将被简单地忽略，但可用于分隔事物以及提高人类可读性。 C或C ++之类的注释（以及许多其他糖）我并未考虑将源代码保持在最小限度。 （尽管如此，我得到了将近500行。）

OP的特定示例将通过添加分号适合此语言：

a*(b+3);

仅支持一种类型： double。因此，我不需要类型或任何使事情变得容易的声明。

在开始草绘此语言的 grammar之前，我正在考虑编译的“目标”，并决定为...创建类。

抽象语法树

首先–一个存储变量的类：

// storage of variables

class Var {
  private:
    double _value;
  public:
    Var(): _value() { }
    ~Var() = default;
    double get() const { return _value; }
    void set(double value) { _value = value; }
};

变量为值提供存储，但不为标识符提供存储。后者是单独存储的，因为变量的实际使用不需要它，而只能按名称查找它：

typedef std::map<std::string, Var> VarTable;

std::map的使用可自动创建变量。从许多高级语言中可以知道，变量在首次访问时就开始存在。

Abstract Syntax Tree是一个


  用编程语言编写的源代码抽象句法结构的树形表示。树的每个节点表示在源代码中出现的构造。


我从上面链接的Wikipedia文章中摘录了这些文字–不能说得短些。在以下我的AST课程中：

// abstract syntax tree -> storage of "executable"

namespace AST {

class Expr {
  protected:
    Expr() = default;
  public:
    virtual ~Expr() = default;
  public:
    virtual double solve() const = 0;
};

class ExprConst: public Expr {
  private:
    double _value;
  public:
    ExprConst(double value): Expr(), _value(value) { }
    virtual ~ExprConst() = default;
    virtual double solve() const { return _value; }
};

class ExprVar: public Expr {
  private:
    Var *_pVar;
  public:
    ExprVar(Var *pVar): Expr(), _pVar(pVar) { }
    virtual ~ExprVar() = default;
    virtual double solve() const { return _pVar->get(); }
};

class ExprUnOp: public Expr {
  protected:
    Expr *_pArg1;
  protected:
    ExprUnOp(Expr *pArg1): Expr(), _pArg1(pArg1) { }
    virtual ~ExprUnOp() { delete _pArg1; }
};

class ExprUnOpNeg: public ExprUnOp {
  public:
    ExprUnOpNeg(Expr *pArg1): ExprUnOp(pArg1) { }
    virtual ~ExprUnOpNeg() = default;
    virtual double solve() const
    {
      return -_pArg1->solve();
    }
};

class ExprBinOp: public Expr {
  protected:
    Expr *_pArg1, *_pArg2;
  protected:
    ExprBinOp(Expr *pArg1, Expr *pArg2):
      Expr(), _pArg1(pArg1), _pArg2(pArg2)
    { }
    virtual ~ExprBinOp() { delete _pArg1; delete _pArg2; }
};

class ExprBinOpAdd: public ExprBinOp {
  public:
    ExprBinOpAdd(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpAdd() = default;
    virtual double solve() const
    {
      return _pArg1->solve() + _pArg2->solve();
    }
};

class ExprBinOpSub: public ExprBinOp {
  public:
    ExprBinOpSub(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpSub() = default;
    virtual double solve() const
    {
      return _pArg1->solve() - _pArg2->solve();
    }
};

class ExprBinOpMul: public ExprBinOp {
  public:
    ExprBinOpMul(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpMul() = default;
    virtual double solve() const
    {
      return _pArg1->solve() * _pArg2->solve();
    }
};

class ExprBinOpDiv: public ExprBinOp {
  public:
    ExprBinOpDiv(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpDiv() = default;
    virtual double solve() const
    {
      return _pArg1->solve() / _pArg2->solve();
    }
};

因此，使用AST类，样本 a*(b+3)的表示为

VarTable varTable;
Expr *pExpr
= new ExprBinOpMul(
    new ExprVar(&varTable["a"]),
    new ExprBinOpAdd(
      new ExprVar(&varTable["b"]),
      new ExprConst(3)));

注意：

没有从 Expr派生的类来表示括号 ()，因为这完全没有必要。在构建树本身时会考虑对括号的处理。通常，具有较高优先级的运算符将成为具有较低优先级的运算符的子级。结果，前者先于后者计算。在上面的示例中， ExprBinOpAdd的实例是 ExprBinOpMul的实例的子代（尽管乘法的优先级高于加法的优先级），这是通过适当考虑括号而得出的。

除了存储已解析的表达式外，还可以通过调用根节点的 Expr::solve()方法来使用此树来计算表达式：

double result = pExpr->solve();

拥有我们的Tiny Calculator的后端，接下来就是前端。

语法

正式语言最好用 grammar描述。

program
  : expr Semicolon program
  | <empty>
  ;

expr
  : addExpr
  ;

addExpr
  : mulExpr addExprRest
  ;

addExprRest
  : addOp mulExpr addExprRest
  | <empty>
  ;

addOp
  : Plus | Minus
  ;

mulExpr
  : unaryExpr mulExprRest
  ;

mulExprRest
  : mulOp unaryExpr mulExprRest
  | <empty>
  ;

mulOp
  : Star | Slash
  ;

unaryExpr
  : unOp unaryExpr
  | primExpr
  ;

unOp
  : Plus | Minus
  ;

primExpr
  : Number
  | Id
  | LParen expr RParen
  ;

以开始符号 program。

规则包含


终端符号（以大写字母开头）和
非终端符号（以小写字母开头）
用冒号（ :）将左侧与右侧分开（左侧的非终端可能会扩展为右侧的符号）。
竖线（ |）以分隔替代项
<empty>符号，用于扩展为空（用于终止递归）。


从终端符号中，我将得出扫描仪的令牌。

非终结符将转换为解析器函数。

addExpr和 mulExpr的分离是有意进行的。因此，乘法运算符比加法运算符的优先级将被“消化”在语法本身中。显然，浮点常量，变量标识符或括号中的表达式（ primExpr中接受）将具有最高优先级。

规则仅包含权利递归。这是递归下降解析器的要求（正如我在Dragon书中从理论上学到的，以及从调试器的实际经验中学到的，直到我完全理解其原因）。在递归下降解析器中实现左递归规则将导致未终止的递归，而递归最终将导致StackOverflow。

扫描仪

通常将编译器拆分为扫描器和解析器。

扫描程序处理输入的字符流，并将字符分组为令牌。标记在解析器中用作终端符号。

对于令牌的输出，我制作了一个类。在我的专业项目中，它还会存储确切的文件位置以表示其来源。这很方便使用源代码引用以及错误消息和调试信息的任何输出来标记创建的对象。 （...这里尽量将其保持在最小限度...）

// token class - produced in scanner, consumed in parser
struct Token {
  // tokens
  enum Tk {
    Plus, Minus, Star, Slash, LParen, RParen, Semicolon,
    Number, Id,
    EOT, Error
  };
  // token number
  Tk tk;
  // lexem as floating point number
  double number;
  // lexem as identifier
  std::string id;

  // constructors.
  explicit Token(Tk tk): tk(tk), number() { }
  explicit Token(double number): tk(Number), number(number) { }
  explicit Token(const std::string &id): tk(Id), number(), id(id) { }
};

特殊令牌有两个枚举器：


EOT ...文本结尾（表示输入的结尾）
为不适合任何其他标记的任何字符生成 Error...。


令牌用作实际扫描仪的输出：

// the scanner - groups characters to tokens
class Scanner {
  private:
    std::istream &_in;
  public:
    // constructor.
    Scanner(std::istream &in): _in(in) { }
    /* groups characters to next token until the first character
     * which does not match (or end-of-file is reached).
     */
    Token scan()
    {
      char c;
      // skip white space
      do {
        if (!(_in >> c)) return Token(Token::EOT);
      } while (isspace(c));
      // classify character and build token
      switch (c) {
        case '+': return Token(Token::Plus);
        case '-': return Token(Token::Minus);
        case '*': return Token(Token::Star);
        case '/': return Token(Token::Slash);
        case '(': return Token(Token::LParen);
        case ')': return Token(Token::RParen);
        case ';': return Token(Token::Semicolon);
        default:
          if (isdigit(c)) {
            _in.unget(); double value; _in >> value;
            return Token(value);
          } else if (isalpha(c) || c == '_') {
            std::string id(1, c);
            while (_in >> c) {
              if (isalnum(c) || c == '_') id += c;
              else { _in.unget(); break; }
            }
            return Token(id);
          } else {
            _in.unget();
            return Token(Token::Error);
          }
      }
    }
};

扫描器用于解析器。

解析器

class Parser {
  private:
    Scanner _scanner;
    VarTable &_varTable;
    Token _lookAhead;

  private:
    // constructor.
    Parser(std::istream &in, VarTable &varTable):
      _scanner(in), _varTable(varTable), _lookAhead(Token::EOT)
    {
      scan(); // load look ahead initially
    }

    // calls the scanner to read the next look ahead token.
    void scan() { _lookAhead = _scanner.scan(); }

    // consumes a specific token.
    bool match(Token::Tk tk)
    {
      if (_lookAhead.tk != tk) {
        std::cerr << "SYNTAX ERROR! Unexpected token!" << std::endl;
        return false;
      }
      scan();
      return true;
    }

    // the rules:

    std::vector<AST::Expr*> parseProgram()
    {
      // right recursive rule
      // -> can be done as iteration
      std::vector<AST::Expr*> pExprs;
      for (;;) {
        if (AST::Expr *pExpr = parseExpr()) {
          pExprs.push_back(pExpr);
        } else break;
        // special error checking for missing ';' (usual error)
        if (_lookAhead.tk != Token::Semicolon) {
          std::cerr << "SYNTAX ERROR: Semicolon expected!" << std::endl;
          break;
        }
        scan(); // consume semicolon
        if (_lookAhead.tk == Token::EOT) return pExprs;
      }
      // error handling
      for (AST::Expr *pExpr : pExprs) delete pExpr;
      pExprs.clear();
      return pExprs;
    }

    AST::Expr* parseExpr()
    {
      return parseAddExpr();
    }

    AST::Expr* parseAddExpr()
    {
      if (AST::Expr *pExpr1 = parseMulExpr()) {
        return parseAddExprRest(pExpr1);
      } else return nullptr; // ERROR!
    }

    AST::Expr* parseAddExprRest(AST::Expr *pExpr1)
    {
      // right recursive rule for left associative operators
      // -> can be done as iteration
      for (;;) {
        switch (_lookAhead.tk) {
          case Token::Plus:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseMulExpr()) {
              pExpr1 = new AST::ExprBinOpAdd(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Minus:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseMulExpr()) {
              pExpr1 = new AST::ExprBinOpSub(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Error:
            std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
            delete pExpr1;
            return nullptr;
          default: return pExpr1;
        }
      }
    }

    AST::Expr* parseMulExpr()
    {
      if (AST::Expr *pExpr1 = parseUnExpr()) {
        return parseMulExprRest(pExpr1);
      } else return nullptr; // ERROR!
    }

    AST::Expr* parseMulExprRest(AST::Expr *pExpr1)
    {
      // right recursive rule for left associative operators
      // -> can be done as iteration
      for (;;) {
        switch (_lookAhead.tk) {
          case Token::Star:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseUnExpr()) {
              pExpr1 = new AST::ExprBinOpMul(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Slash:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseUnExpr()) {
              pExpr1 = new AST::ExprBinOpDiv(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Error:
            std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
            delete pExpr1;
            return nullptr;
          default: return pExpr1;
        }
      }
    }

    AST::Expr* parseUnExpr()
    {
      // right recursive rule for right associative operators
      // -> must be done as recursion
      switch (_lookAhead.tk) {
        case Token::Plus:
          scan(); // consume token
          // as a unary plus has no effect it is simply ignored
          return parseUnExpr();
        case Token::Minus:
          scan();
          if (AST::Expr *pExpr = parseUnExpr()) {
            return new AST::ExprUnOpNeg(pExpr);
          } else return nullptr; // ERROR!
        default:
          return parsePrimExpr();
      }
    }

    AST::Expr* parsePrimExpr()
    {
      AST::Expr *pExpr = nullptr;
      switch (_lookAhead.tk) {
        case Token::Number:
          pExpr = new AST::ExprConst(_lookAhead.number);
          scan(); // consume token
          break;
        case Token::Id: {
          Var &var = _varTable[_lookAhead.id]; // find or create
          pExpr = new AST::ExprVar(&var);
          scan(); // consume token
        } break;
        case Token::LParen:
          scan(); // consume token
          if (!(pExpr = parseExpr())) return nullptr; // ERROR!
          if (!match(Token::RParen)) {
            delete pExpr; return nullptr; // ERROR!
          }
          break;
        case Token::EOT:
          std::cerr << "SYNTAX ERROR: Premature EOF!" << std::endl;
          break;
        case Token::Error:
          std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
          break;
        default:
          std::cerr << "SYNTAX ERROR: Unexpected token!" << std::endl;
      }
      return pExpr;
    }

  public:

    // the parser function
    static std::vector<AST::Expr*> parse(
      std::istream &in, VarTable &varTable)
    {
      Parser parser(in, varTable);
      return parser.parseProgram();
    }
};

基本上，解析器基本上由一堆相互调用的规则函数（根据语法规则）组成。规则函数周围的类负责管理某些全局解析器上下文。因此， class Parser的唯一公共方法是

static std::vector<AST::Expr*> Parser::parse();

它使用私有构造函数构造一个实例，并调用与起始符号 Parser::parseProgram()相对应的函数 program。

在内部，解析器调用 Scanner::scan()方法填充其预读令牌。

这是在 Parser::scan()中完成的，当必须使用令牌时，始终会调用它。

仔细观察，就会发现一种模式，这些规则是如何将规则转换为解析器功能的：


左侧的每个非终端变为解析函数。 （仔细看一下源代码，您会发现我并没有完全做到这一点。有些规则已经“内联”了。–从我的角度来看，我插入了一些额外的规则来简化我没有的语法。打算从一开始就转型。对不起。）
替代项（ |）被实现为 switch (_lookAhead.tk)。从而，每个案例标签对应于最左边的符号可以扩展到的第一终端（令牌）。 （我相信这就是为什么它被称为“超前解析器”的原因-应用规则的决定总是基于前瞻性标记。）龙书中有一个关于FIRST-FOLLOW集合的主题，它对此进行了更详细的解释。
对于终端符号，调用 Parser::scan()。在特殊情况下，如果只需要一个终端（令牌），则将其替换为 Parser::match()。
对于非终端符号，将调用相应的函数。
符号序列只是作为上述调用的序列完成的。


这个解析器的错误处理是我做过的最简单的事情。可以/应该做更多的支持（投入更多的精力，即增加代码行）。 （...但是在这里我试图使它最小化...）

放在一起

为了进行测试和演示，我准备了 main()函数，其中包含一些内置示例（程序源代码和要处理的数据）：

// a sample application

using namespace std;

int main()
{
  // the program:
  const char *sourceCode =
    "1 + 2 * 3 / 4 - 5;\n"
    "a + b;\n"
    "a - b;\n"
    "a * b;\n"
    "a / b;\n"
    "a * (b + 3);\n";
  // the variables
  const char *vars[] = { "a", "b" };
  enum { nVars = sizeof vars / sizeof *vars };
  // the data
  const double data[][nVars] = {
    { 4.0, 2.0 },
    { 2.0, 4.0 },
    { 10.0, 5.0 },
    { 42, 6 * 7 }
  };
  // compile program
  stringstream in(sourceCode);
  VarTable varTable;
  vector<AST::Expr*> program = Parser::parse(in, varTable);
  if (program.empty()) {
    cerr << "ERROR: Compile failed!" << endl;
    string line;
    if (getline(in, line)) {
      cerr << "Text at error: '" << line << "'" << endl;
    }
    return 1;
  }
  // apply program to the data
  enum { nDataSets = sizeof data / sizeof *data };
  for (size_t i = 0; i < nDataSets; ++i) {
    const char *sep = "";
    cout << "Data Set:" << endl;
    for (size_t j = 0; j < nVars; ++j, sep = ", ") {
      cout << sep << vars[j] << ": " << data[i][j];
    }
    cout << endl;
    // load data
    for (size_t j = 0; j < nVars; ++j) varTable[vars[j]].set(data[i][j]);
    // perform program
    cout << "Compute:" << endl;
    istringstream in(sourceCode);
    for (const AST::Expr *pExpr : program) {
      string line; getline(in, line);
      cout << line << ": " << pExpr->solve() << endl;
    }
    cout << endl;
  }
  // clear the program
  for (AST::Expr *pExpr : program) delete pExpr;
  program.clear();
  // done
  return 0;  
}

我在VS2013（Windows 10）上进行了编译和测试，并得到：

Data Set:
a: 4, b: 2
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: 2
a * b;: 8
a / b;: 2
a * (b + 3);: 20

Data Set:
a: 2, b: 4
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: -2
a * b;: 8
a / b;: 0.5
a * (b + 3);: 14

Data Set:
a: 10, b: 5
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 15
a - b;: 5
a * b;: 50
a / b;: 2
a * (b + 3);: 80

Data Set:
a: 42, b: 42
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 84
a - b;: 0
a * b;: 1764
a / b;: 1
a * (b + 3);: 1890

请考虑解析器本身忽略任何空格和换行符。但是，为了使示例输出格式更简单，我必须每行使用一个以分号结尾的表达式。否则，将很难将源代码行与相应的编译表达式相关联。
（请记住我上面关于 Token的注释，该注释可能会添加源代码引用（也称为文件位置）。）

完整样本

...带有源代码和测试运行的信息可以在 ideone上找到。