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

Question

我正在阅读编译器设计书，它说“编译器有解决中缀表达式的问题，因为它在确定操作数的优先级方面有困难，你应该总是把它转换成postfix然后解析表达式”。

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

Answer 1

考虑a + b * c/d e。根据传统的优先规则，这应该被解析为a + ((b * c)/d)。只需从右向左阅读将产生((a + b) * c)/d，这不是你想要的。编译器需要知道每个操作员的优先级（和关联性）并将其考虑在内。

另一方面，后缀表达式显式优先。例如，上面的第一个表达式相当于b c * d/a +。

不知道我是否知道作者在做什么“应该始终将其转换为postfix然后解析表达式”，但这是主旨。 （在我看来，转换到后缀需要解析已经）。

Answer 2

你可能会认为它是编译器找出括号内容的问题。

考虑两个运营商，*和+

如果你有一个中间符号，你可以有之类的语句

X = A * B + C 

其与操作顺序的无知，编译器可能会解释为

X = (A * B) + C 

或

X = A * (B + C) 

如果以后缀表示法编写，则不存在不和谐情绪。这就像旧的惠普计算器。有一个栈，一个操作员弹出两个操作数出栈，并推动将结果返回

所以第一个公式将看起来更像（忽略分配给X，技术上另算）

A B * C + 

而第二个

A B C + * 

这就是说，你的发言弄得我一点，因为我觉得修复张贴在修复将是做一个编译器，而不是一个简单的动作编译器的一个意向

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

编译器在解析前缀，中缀或后缀顺序中的表达式时没有任何问题。语法是easy供编译器处理。

虽然你看不到很多使用前缀或后缀表示法的编译器。那是因为人不习惯。几乎所有的Forth人都逃避了Postfix，他们的编译器几乎是微不足道的，这使得它成为运行它的小型机器的理想选择。第四，程序员学会了热爱postfix，并且凭借一点经验相处得很好。

[我不知道是谁告诉“你应该总是把它转换为postfix然后解析表达式”，但这是无稽之谈。