与后缀表达式相比，为什么编译器在解析中缀表达式时遇到问题？

Question

我在读编译器设计书，它说 "compilers have problem solving infix expression because it has trouble with determining the priority of operands and you should always convert it to postfix then parse the expression" .

与后缀表达式相比，为什么编译器在解析中缀表达式时遇到问题？

Answer 1

考虑 a + b * c / d e。根据约定的优先级规则，这应该被解析为a + ((b * c) / d)。简单地从右到左阅读会产生 ((a + b) * c)/d，这不是您想要的。编译器需要知道每个运算符的优先级（和结合性）并将它们考虑在内。

另一方面，后缀表达式具有明确的优先级。例如，上面的第一个表达式等同于 b c * d / a +.

不确定我是否知道作者对 "should always convert it to postfix then parse the expression" 的理解，但这就是要点。（在我看来，转换为后缀已经需要解析）。

Answer 2

您可能认为编译器要确定括号的位置是一个问题。

考虑两个运算符，* 和 +

如果你有一个中缀符号，你可以有这样的语句

X = A * B + C

在不了解操作顺序的情况下，编译器可能会解释为

X = ( A * B ) + C

或

X = A * ( B + C )

如果用post-fix 表示法写就没有歧义。它就像旧的 HP 计算器。有一个堆栈，运算符从堆栈中弹出两个操作数，并将结果推回

所以第一个公式看起来更像（忽略对 X 的赋值，技术上是另一个运算符）

A B * C +

而第二个是

A B C + *

也就是说，你的说法让我有点困惑，因为我认为从 in-fix 到 post-fix 是制作编译器的一个意图，而不是编译器所做的简单操作

Answer 3

使用递归下降解析器，中缀解析非常简单，如下面的简短 Java 示例所示。类似的东西可以很容易地用于表达式树生成。

有很多事情可以推迟到不同的阶段，但我从未见过这种重新排序在构建解析树之前对原始输入进行转换很有意义的情况。

也许这本书已经过时了？这句话出自哪本书？

public class InfixProcessor {
  static final String[] OPERATORS = {"-+", "/*"};
  static StreamTokenizer tokenizer;

  static double process(String s) throws IOException {
    tokenizer = new StreamTokenizer(new StringReader(s));
    tokenizer.ordinaryChar('-');
    tokenizer.ordinaryChar('/');
    tokenizer.nextToken();
    return processInfix(0);
  }

  static double processInfix(int precedence) throws IOException {
    if (precedence >= OPERATORS.length) {
      return processPrimary();
    }
    double result = processInfix(precedence + 1);
    while (OPERATORS[precedence].indexOf((char) tokenizer.ttype) != -1) {
      int op = tokenizer.ttype;
      tokenizer.nextToken();
      double right = processInfix(precedence + 1);
      switch (op) {
        case '+': result += right; break;
        case '-': result -= right; break;
        case '*': result *= right; break;
        case '/': result /= right; break;
        default: throw new RuntimeException();
      }
    }
    return result;
  }

  static double processPrimary() throws IOException {
    if (tokenizer.ttype != StreamTokenizer.TT_NUMBER) {
      throw new RuntimeException("Number expected");
    }
    double result = tokenizer.nval;
    tokenizer.nextToken();
    return result;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    while (true) {
      System.out.print("Expression> ");
      String expr = reader.readLine();
      if (expr == null || expr.isEmpty()) break;
      System.out.println("Result: " + process(expr));
    }
  }
}

Answer 4

编译器在按前缀、中缀或后缀顺序解析表达式时没有任何问题。编译器可以轻松处理语法.

不过，您并没有看到很多编译器使用前缀或后缀表示法。那是因为人们不习惯那样。几乎只有 Forth 的人摆脱了 postfix，他们的编译器几乎是微不足道的，这使得它非常适合它运行在其中的非常小的机器。 Forth 程序员学会了爱上 postfix，并且随着一些经验相处得很好。

[我不知道是谁说的 "you should always convert it to postfix then parse the expression" 但那是胡说八道。

与后缀表达式相比，为什么编译器在解析中缀表达式时遇到问题？

Why does a compiler have trouble parsing infix expressions compared to postfix expressions?

parsing

data-structures

compiler-construction

postfix-notation

infix-notation