PL/0编译器中负号与减号区分求助——表达式分析栈溢出问题

问题场景 #

我正在编写一个小型PL/0编译器用于实践，在表达式求值部分遇到了问题。示例表达式为：

-2 + 1

当前处理流程 #

1. 词法分析：PL/0中无“负整数”概念，-2被解析为-和2，得到token序列：-、2、+、1
2. 语法分析：采用SLR1分析法，表达式语法正确无异常
3. 语义分析：通过运算符栈与操作数栈协作构建抽象语法树，但代码会将负号当作减号处理，引发两个问题：
   • 表达式求值结果错误
   • 触发空栈pop操作导致程序崩溃

核心逻辑代码 #

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

相关PL/0 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>}

注：|对应正则中的|；{...}对应正则中的*；[...]表示零次或一次，类似正则中的?

解决方案 #

根据PL/0的表达式EBNF规则，[+|-]<item>表示表达式开头的正负号是一元运算符，和作为二元运算符的加减号是不同的语法元素，需要在语义分析阶段区分处理：

1. 区分一元/二元运算符的判断逻辑 #

处理-时，通过上下文判断其类型：

• 当-出现在表达式开头时，是一元负号
• 当-出现在另一个运算符或左括号(之后时，是一元负号
• 其他情况（出现在操作数或右括号)之后），是二元减号

2. 修改语义分析代码 #

步骤1：标记一元负号

用特殊符号（比如'~'）区分一元负号和二元减号，避免混淆。

步骤2：修改运算符处理逻辑

在遍历token时，对-进行额外判断并调整优先级：

// 在operator处理分支中修改
else {
  char op = token[0];
  bool is_unary = false;
  // 判断是否为一元运算符
  if (op == '+' || op == '-') {
    // 栈为空（表达式开头）或前一个是运算符/左括号
    if (opStack.empty() || opStack.top() == '(' || 
        (opStack.top() == '+' || opStack.top() == '-' || opStack.top() == '*' || opStack.top() == '/')) {
      is_unary = true;
      op = (op == '-') ? '~' : '+'; // 一元加号可忽略，这里统一标记
    }
  }

  // 调整一元运算符优先级（高于所有二元运算符）
  while (!opStack.empty() && opStack.top() != '(') {
    char top_op = opStack.top();
    if (is_unary) {
      // 一元运算符优先级最高，栈顶若为二元运算符则停止弹出
      if (top_op != '~') break;
    } else {
      // 原有二元运算符优先级判断
      if (!is_prior(op, top_op)) break;
    }

    // 弹出运算符并构建节点
    shared_ptr<ASTNode> right = nodeStack.top();
    nodeStack.pop();
    if (top_op == '~') {
      // 一元负号仅需右子节点
      shared_ptr<ASTNode> node = make_shared<ASTNode>('~', 0, nullptr, right);
      opStack.pop();
      nodeStack.push(node);
    } else {
      // 二元运算符原有逻辑
      shared_ptr<ASTNode> left = nodeStack.top();
      nodeStack.pop();
      shared_ptr<ASTNode> node = make_shared<ASTNode>(top_op, 0, left, right);
      opStack.pop();
      nodeStack.push(node);
    }
  }
  opStack.push(op);
}

步骤3：修改栈剩余运算符处理逻辑

最后处理栈中剩余运算符时，区分一元和二元运算符：

while (!opStack.empty()) {
  char op = opStack.top();
  opStack.pop();
  shared_ptr<ASTNode> right = nodeStack.top();
  nodeStack.pop();
  if (op == '~') {
    // 一元负号节点仅需右子节点
    shared_ptr<ASTNode> node = make_shared<ASTNode>('~', 0, nullptr, right);
    nodeStack.push(node);
  } else {
    // 二元运算符原有逻辑
    shared_ptr<ASTNode> left = nodeStack.top();
    nodeStack.pop();
    shared_ptr<ASTNode> node = make_shared<ASTNode>(op, 0, left, right);
    nodeStack.push(node);
  }
}

步骤4：AST求值时的处理

遍历AST计算值时，对一元负号做特殊处理：

int evaluate(ASTNode* node) {
  if (node->_op == ' ') {
    return node->_val;
  } else if (node->_op == '~') {
    return -evaluate(node->_right.get());
  } else {
    int left_val = evaluate(node->_left.get());
    int right_val = evaluate(node->_right.get());
    switch(node->_op) {
      case '+': return left_val + right_val;
      case '-': return left_val - right_val;
      // 其他运算符（如*、/）的处理逻辑
      default: return 0;
    }
  }
}

3. 可选优化：词法分析阶段标记一元运算符 #

如果允许修改词法分析器，可以直接生成不同的token类型（比如UNARY_MINUS和MINUS），语义分析阶段直接根据token类型处理，避免额外的上下文判断。

内容的提问来源于stack exchange，提问作者LiuYuan