编译器中如何区分负号和减号

Question

我正在编写一个小型 PL/0 编译器用于练习。

我在编写表达式求值部分时遇到了一些问题。

这是一个小例子：

-2 + 1

我的程序逻辑如下：

1. 词法分析

   根据我查到的文档，PL/0中没有“负整数”这样的东西，因此

   -2

   会被解析为

   -

   和

   2

   。这一步的结果是：

   -

   、

   2

   、

   +

   和

   1

2. 语法分析

   这一步我用的是SLR1，由于表达式正确，所以什么也不会发生。

3. 语义分析

   程序将在这一步构建一个抽象语法树。原理很简单，一个操作符栈和一个操作数栈共同完成这部分。然而，“负”号在我的代码中将被视为“减”号，我没有好主意来处理这个问题。

这是一段显示逻辑的代码：

struct ASTNode {
  ASTNode(char op, int val, ASTNode *left = nullptr, ASTNode *right = nullptr);

  char _op;                   // operator
  int _val;                   // operand
  shared_ptr<ASTNode> _left;  // left child node
  shared_ptr<ASTNode> _right; // right child node
};

void semantic_analyzer::construct_tree(vector<string> &tokens) {
  stack<shared_ptr<ASTNode>> nodeStack;  // operand stack
  stack<char> opStack;                   // operator stack

  // iterate tokens and construct part of the AST
  for (auto &token : tokens) {
    // if the token is a positive integer
    if (str_opekit::is_digit(token)) {
      int val = stoi(token);
      nodeStack.push(make_shared<ASTNode>(' ', val)); // the children will be set as nullptr
    }
    // If the token is a left paren, push it into operator stack
    else if (token == "(") {
      opStack.push('(');
    }
    // If the token is a right paren, pop the operator in the operator stack and calculate result
    else if (token == ")") {
      // Keep popping operators in the operator stack until reach a left paren
      while (opStack.top() != '(') {
        // Pop two operands in the operand stack and construct them into a node
        shared_ptr<ASTNode> right = nodeStack.top();
        nodeStack.pop();
        shared_ptr<ASTNode> left = nodeStack.top();
        nodeStack.pop();
        // Construct a new ASTNode with the two nodes and push into the stack
        shared_ptr<ASTNode> node(new ASTNode(opStack.top(), 0, left, right));
        opStack.pop();
        nodeStack.push(node);
      }
      opStack.pop();  // pop left paren
    }
    // If the token is #, which stands for the end of the expression
    else if (token == "#") {
      break;
    }
    // If the token is an operator, compare its priority with the operator on the top
    // of the stack
    else {
      char op = token[0];
      // while:
      // 1. the operator stack is not empty
      // 2. the operator on the top of the stack is not a left paren
      // 3. the priority of the operator on the top of the stack is higher
      while (!opStack.empty() && opStack.top() != '(' &&
             is_prior(op, opStack.top()) ) {
        // Pop two operands in the stack and construct them into an ASTNode
        shared_ptr<ASTNode> right = nodeStack.top();
        nodeStack.pop();
        shared_ptr<ASTNode> left = nodeStack.top();
        nodeStack.pop();
        // Construct a new ASTNode with the two nodes and push it into the
        // operand stack
        shared_ptr<ASTNode> node =
            make_shared<ASTNode>(opStack.top(), 0, left, right);
        opStack.pop();
        nodeStack.push(node);
      }
      opStack.push(op);
    }
  }

  // Process operators and operands in the stack and construct the tree
  while (!opStack.empty()) {
    shared_ptr<ASTNode> right = nodeStack.top();
    nodeStack.pop();
    shared_ptr<ASTNode> left = nodeStack.top();
    nodeStack.pop();
    shared_ptr<ASTNode> node =
        make_shared<ASTNode>(opStack.top(), 0, left, right);
    opStack.pop();
    nodeStack.push(node);
  }

  this->_root = nodeStack.top();
  nodeStack.pop();
}

由于“负”号会被解析为“减”号，不仅执行结果会错误，而且程序会在空栈上调用

pop()

，从而导致崩溃。

如果您需要有关我的代码的更多详细信息，请告诉我。欢迎任何建议。

---

EBNF 来自我之前学过的课程。与问题相关的部分如下：

1. letter ::= a|b|...|X|Y|Z

2. digit ::= 0|1|...|8|9

3. identifier ::= <letter>{<letter>|<digit>}

4. unsigned integer ::= <digit>{<digit>}

5. factor ::= <identifier>|<unsigned integer>|...

6. item ::= <factor>{<multiplying operator><factor>}

7. expression ::= [+|-]<item>{<adding operator><item>}

'|'代表“|”在正则表达式中

'{...}' 代表正则表达式中的“*”

'[...]' 代表“零或一”，与“?”有些相似。在正则表达式中

Answer 1

解析器必须记下它解析的输入的每个元素。例如，当它看到一个

expression

时，它必须告诉后续阶段是否只有一个

item

，或者是否有多个

item

以及中间的

adding operator

以及哪个

adding operator

那是。 （最有可能的是，解析是通过构建语法树来实现的。）

同时，解析器还可以记录在第一个

+

之前是否看到了

-

、

item

，或者没有看到它们。就这么简单。