递归下降：中缀到后缀转换重复运算符

Question

我们最近在 uni 的编程课程中学习了如何使用堆栈将中缀转换为后缀。我有一段时间想写我的解析器，所以我决定使用递归下降。我跟着这个：Parsing Expressions by Recursive Descent Theodore Norvell 。这是他使用的语法：

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-" | "+"

我曾尝试在 C 中实现它并且它有效。但是，如果我给它以下输入，运算符像这样一个接一个地尾随：

---+-1-(-(2-1)+3)*-2

它输出这个：

---+-1.00 -2.00 1.00  - 3.00  +  - -2.00 *

以下似乎是错误的：

- -2.00 * 应该是 + -2 * -（基于我的堆栈实现）

我得到的另一个奇怪的结果是 2+(2^4*(7+2^6)) 我得到了：

2.00 2.00 4.00 ^ 7.00 2.00  + 6.00 ^* +

当我期望得到：

 2.00 2.00 4.00 ^ 7.00 2.00 6.00 ^ + * +

我不确定，但我可能需要一个优先爬升解析器 - 也建议 in the linked article。然而，主要问题是我将如何简化尾随的一对操作```---+``？任何帮助将不胜感激。非常感谢。这一切仍然是初学者。

代码如下：

#include <stdio.h>
#include <stdlib.h>

void expr();
void term();
void match(int t);
void error();
void parseNumber();
//E --> P {B P}
//P --> v | "(" E ")" | U P
//B --> "+" | "-" | "*" | "/" | "^"
//U --> "-" | "+"
//
// Erecognizer is
//    E()
//    expect( end )
// 
// E is
//     P
//     while next is a binary operator
//        consume
//        P

char lookahead;

int main() {
  lookahead = getchar();
  expr();
return 0;
}
// E is
//     P
//     while next is a binary operator
//        consume
//        P
void expr() {
  term();
 /* optimized by inlining rest() and removing recursive calls */
  while (1)  {
    if (lookahead == '+') {
      match('+');
      term();
      printf(" + ");
    } else if (lookahead == '-') {
      match('-');
      term();
      printf(" - ");
    }else if (lookahead == '*') {
      match('*');
      term();
      putchar('*');
    } else if (lookahead == '/') {
      match('/');
      term();
      putchar('/');
    } else if (lookahead == '^') {
      match('^');
      term();
      putchar('^');
    }  
    else break;
  }
}

// P is
//     if next is a v
//          consume
//     else if next = "("
//          consume
//          E
//          expect( ")" )
//     else if next is a unary operator
//          consume
//          P
//     else
//          error

void term() {
  if (isdigit(lookahead)) {
      parseNumber();
     // printf("lookahead at %c",lookahead);
  } else if(lookahead =='('){
      match('(');
      expr();
      match(')');
  }
  else if (lookahead =='-' ||lookahead =='+') {
      char sign = lookahead;
      match(lookahead);
      (sign=='+'?putchar('+'):putchar('-'));
      term();
  }else {
      error();
      }
}

void match(int t) {
  if (lookahead == t)
    lookahead = getchar();
  else error();

}
void parseNumber() {
  double number = 0;
  // TODO consume spaces
  if (lookahead == '[=15=]'|| lookahead=='\n') return;
  while (lookahead >= '0' && lookahead <= '9') {
    number = number * 10 + lookahead - '0';
    match(lookahead);
  }
  if (lookahead == '.') {
    match(lookahead);
    double weight = 1;
    while (lookahead >= '0' && lookahead <= '9') {
      weight /= 10;
      number = number + (lookahead - '0') * weight;
      match(lookahead);
    }
  }
  printf("%.2f ", number);
  //printf("\ncurrent look ahead at after exiting parseNumber %c\n",lookahead);
}
void error() {
  printf("Syntax error at lookahead %c\n",lookahead);
  exit(1);
}

Answer 1

您引用的文章非常清楚地表明所提供的递归下降算法不是解析器：（强调）

Let's look at a recursive descent recognizer based on this grammar. I call this algorithm a recognizer rather than a parser because all it does is to recognize whether the input is in the language of the grammar or not. It does not produce an abstract syntax tree, or any other form of output that represents the contents of the input.

完全正确；该语法仅适用于识别器。没有提到的是，如果您尝试修改算法以产生某种形式的输出（除了简单的“是”或“否”，表明表达式是否使用目标语言），您将得到一个结构化的答案不正确。

那是因为事实并非如此：

We can transform G to an equivalent non-left-recursive grammar G1…

或者至少，您需要非常注意“等效”的含义。新语法是等效的，因为它识别相同的语言。但它不以相同的方式解析表达式，而且 left-recursion 消除算法从语法中消除了产生正确解析所必需的信息。（在这种情况下，必要的信息——每个运算符的优先级和结合性——已经从语法中删除，大概是为了简化。但即使语法一开始是准确的，left-recursion 删除也会删除了 left-associative 和 right-associative 运算符之间的区别。）

在本演示文稿的稍后部分，在经典解决方案 的标题下，Norvell 描述了一个递归下降解析器，它确实正确地解析了表达式。 [注 1] 这可能是您想要编写的代码。

顺便说一下，您的输出不是逆波兰表示法（没有括号也不是明确的），因为您输出一元运算符 before 它们的操作数。 RPN 总是将运算符放在它们的操作数之后——这就是它在没有括号的情况下明确的原因——并且要求每个操作数明确地指定它需要的操作数的数量。这通常意味着以不同的方式编写一元和二元取反，以便可以区分它们，尽管另一种选择是只输出一个额外的 0 操作数并让 RPN 评估器将它们视为二元运算符。

但是 RPN 并不是真正有用的解析器输出。解析器的常见输出是 抽象语法树 ，它是描述已解析文本句法结构的图形结构。另一个常见的输出是 so-called “三地址代码”，它是具有无限（或至少非常大）数量的寄存器的假想机器的虚拟机器代码。（并非所有 VM 操作码都有三个地址，但其中很多都有，包括所有二进制算术运算符，它们命名两个源寄存器和一个目标寄存器。）当然，对于计算器，您可以边计算边计算产生任何结构化表示。

备注：

如果 Norvell 选择了一个不那么特殊的优先顺序，那么说语法 G2 将正确地解析表达式可能会更好。我们通常将一元取反运算符放在乘法和求幂之间，而不是放在加法和乘法之间。只要你只实现乘法和精确除法，Norvell 的优先级选择并不重要，但如果你实现底除法或取模（即 // 和 % 的 Python 语义)，您会发现一元否定的低优先级会导致意外的评估。这个错误是可能的，因为否定分布在乘法和精确除法上。但是(-3) // 2和-(3 // 2)不一样，-3 // 2的预期结果是第一个，而Norvell的优先顺序产生第二个。

我应该补充一点，C 中的整数除法是截断除法，而不是底除法，并且 C 的 % 运算符是余数，而不是模数，因此 C 中的问题并不明显。另一方面，C缺少求幂运算符，因此您可以采用更简单的解决方案，即赋予一元取反比任何二元运算符更高的优先级，这实际上是 C 所做的。

递归下降：中缀到后缀转换重复运算符

Recursive descent: infix to postfix conversion repeating operators

algorithm

parsing

bnf

infix-notation

recursive-descent

备注：