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

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 == '\0'|| 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

您引用的文章非常清楚地指出，所提供的递归下降算法不是解析器：（添加了强调）

让我们看一下基于此语法的递归血统识别器。我将此算法称为识别器而不是解析器，因为它所做的只是识别输入是否为语法语言。 它不会产生抽象的语法树，也不会代表输入内容的任何其他形式的输出。

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

因为那不是真的：

我们可以将G转换为等效非左递归语法G1…

或者至少，您需要非常注意“等效”的含义。新语法是等效的，因为它可以识别相同的语言。但是它不能以相同的方式解析表达式，此外，左递归消除算法从语法中消除了生成正确解析所必需的信息。 （在这种情况下，为简化起见，已经从语法中消除了必要的信息-每个运算符的优先级和关联性。大概是为了简化起见。但是，即使语法很准确，左递归消除也将被删除。左关联运算符和右关联运算符之间的区别。）

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

顺便说一句，您的输出不是反向波兰符号（并且也不用括号括起来），因为您输出的是一元运算符

之前其操作数。 RPN始终将运算符放在其操作数之后-这使得它在没有括号的情况下是明确的-并要求每个操作数都明确指定所需的操作数。这通常意味着以不同的方式写一元和二元取反，因此可以区分它们，尽管另一种选择是只输出一个额外的0操作数，然后让RPN评估程序将它们视为二进制运算符。

注意

1. 如果Norvell选择了一个不太特殊的优先顺序，则语法G2可以正确解析表达式。我们通常将一元求反运算符放在乘法和乘幂运算之间，而不放在加法和乘法运算之间。只要您仅实现乘法和精确除法，Norvell的优先级选择就无关紧要，但是，如果您实现地板除法或取模（即//和%的Python语义），您会发现一元否定的较低优先级会导致意外评估。错误的可能是因为否定分布在乘法和精确除法上。但是(-3) // 2与-(3 // 2)不同，并且-3 // 2的预期结果是第一个，而Norvell的优先顺序产生了第二个。

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