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



windows parsing (1)

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

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

当我尝试从git包含 cparse库 时,我的问题出现了。 我天真地遵循了设置说明(对git来说是新手):

$ cd cparse
$ make release

但我不能使用make命令,因为我正在使用Windows。 我尝试下载zip文件并直接将 .cpp.h 文件复制到项目中,并使用visual studio中的 “include existing” 选项,但是却得到了大量的编译器错误,并且无法使代码自行运行。

我不知何故错过了这一点? 我如何让它工作?

如果失败了,是否有另一种解析用户输入字符串并将其用作函数的方法?


如果失败了,是否有另一种解析用户输入字符串并将其用作函数的方法?

我想回答你问题的这一部分,因为我觉得功能齐全的C解析器可能有点太重了,不适合你的意图。 (顺便说一句,一旦你运行了C解析器 - 如何处理它的输出?动态链接?)

相反,我想告诉你如何自己构建一个简单的计算器(使用递归下降解析器)。 对于我将使用的技术的文档,我热烈推荐 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 自动创建变量。 从许多高级语言中可以看出,变量在第一次访问时就开始存在。

抽象语法树 是一个

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

我从上面链接的维基百科文章中获取了这个文本 - 不能说它更短。 在下面我的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 的实例是 ExprBinOpAdd 实例的子实例(尽管乘法的优先级高于add的优先级),这是由于对括号的正确考虑 ExprBinOpMul

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

double result = pExpr->solve();

拥有我们的 微型计算器 的后端,接下来是前端。

语法

形式语言最好用 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> 符号,用于扩展为 <empty> (用于终止递归)。

从终端符号,我将导出扫描仪的令牌。

非终端符号将被转换为解析器函数。

addExprmulExpr 的分离是故意完成的。 因此,乘法运算符优先于加法运算符将会“烧毁”语法本身。 显然,括号中的浮点常量,变量标识符或表达式(在 primExpr 中接受)将具有最高优先级。

规则只包含正确的递归。 这是递归下降解析器的要求(正如我在龙书中理论上学到的,并从调试器的实际经验中学到,直到我完全理解其原因)。 在递归下降解析器中实现左递归规则会导致无终止递归,而这些递归又会以 结束。

扫描仪

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

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

对于令牌的输出,我做了一个课。 在我的专业项目中,它还存储了确切的文件位置以表示其来源。 这样可以方便地使用源代码引用标记创建的对象以及错误消息和调试信息的任何输出。 (...留在这里尽可能保持最小...)

// 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();

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

在内部,解析器调用 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 上找到源代码和测试运行。





compilation