后缀翻译

编译器设计中的后缀翻译简介

众所周知，在现代世界中，编译器设计主要被认为是其中最重要的步骤之一，它用于将表达式从人类通常编写的方式（称为中缀表示法）转换为计算机可以轻松理解和处理的形式。 一种常见的方法称为后缀表示法，也称为“逆波兰表示法（RPN）”。

尽管如此，在日常数学或编程语言中，个人通常会写出像B + C或6 *（8 + 10）这样的表达式。 这种格式称为中缀，因为它通常将运算符（如+或*）放置在操作数（数字或变量）之间。 虽然这对于人类阅读很容易，但对于计算机评估来说可能很棘手，因为它们需要了解运算的顺序以及括号。

此外，后缀表示法只需将运算符放置在操作数之后即可改变这一点。

例如，中缀表达式B + C在后缀中变为B C +。 类似地，6 *（8 + 10）变为6 8 10 + *。 这种形式不需要括号，因为运算的顺序可以从运算符的位置清楚地看出。

将中缀表达式转换为后缀的过程称为“后缀翻译”。 它是编译过程中的一项关键任务，因为它主要简化了编译器的表达式解析和评估。 通过简单地使用后缀，编译器可以轻松生成机器代码或中间代码，因为运算的顺序已经明确。 为了实现后缀翻译，编译器使用堆栈等数据结构来临时保存运算符，并输出正确的后缀形式。 这种翻译确保编译后的程序正确有效地工作。

后缀翻译的工作

后缀翻译是编译器设计中的一个重要步骤，其中数学或逻辑表达式被转换为后缀形式，也称为逆波兰表示法。 但是，此格式通过消除对括号的需求并明确定义操作发生的顺序，帮助个人简化表达式的评估方式。

该过程与编译器在解析期间使用的语法规则密切相关。 每个语法规则表示编译器在分析代码时查找的模式。 当在解析期间匹配到其中一个规则时，就说它被“规约”。 在该时刻，会触发称为语义动作的特殊动作。 这些动作写在每个规则的末尾，因此它们会在应用规则后立即运行。

这些动作有三个主要目的

• 评估属性：在本节中，语法的每个部分，例如数字、变量或运算符，可能都有附加到它的额外信息，称为属性。 这些可能是数字的值或负责表示运算符的符号。 这些动作使用所有这些属性来确定表达式的含义。
• 生成代码：在理解表达式之后，该动作会以后缀格式创建它的一个版本。

例如，如果原始输入是B + C，则生成的输出可能是BC +。

• 更新堆栈：当解析器工作时，它会跟踪正在使用堆栈的所有可用符号。 一旦规则被规约，语义动作就会使用刚刚有效处理的表达式的新信息来更新堆栈。

产生式规则

在产生式A → α中，A.CODE的翻译规则由α中非终结符的CODE翻译的连接组成，其顺序与非终结符在α中出现的顺序相同。

可以分解产生式以实现后缀形式。

while语句的后缀翻译

生产

可以分解为

合适的转换方案将是

for语句的后缀翻译

生产

可以分解为

示例：将中缀转换为后缀

为了更好地理解该概念，我们将采用算术表达式的简单语法规则

Expr -> Expr + Term | Term

以后缀形式，翻译可能是

Expr.CODE = Expr1.CODE Term.CODE "+"

Term.CODE = Factor.CODE

在这里，Expr.CODE表示表达式的输出，而Term.CODE表示项。 当在解析期间应用规则Expr -> Expr + Term时，我们通常组合Expr1和Term的代码，然后在末尾添加+。 这样，像B + C这样的中缀在后缀中变为B C +。

常见问题解答/FAQ

以下是关于后缀翻译的使用的一些常见问题

问题1：为什么编译器使用后缀表示法？

回答：编译器通常使用后缀，因为它负责消除对括号的需求并使运算的顺序清晰。 这有助于简化表达式的评估，并使代码生成更加简单。

问题2：在后缀翻译期间会发生什么？

回答：在后缀翻译期间，编译器读取以通常的中缀格式编写的表达式，并将其转换为后缀。 这是通过将动作附加到语法规则来实现的，这些规则然后在解析期间运行，以便有效地构建后缀表达式。 

问题3：后缀仅用于算术表达式吗？

回答：不，虽然它在算术中很常见，但后缀也可以用于各种逻辑表达式和其他运算。 只要需要清晰简单的评估顺序，它都会有所帮助，尤其是在编译器中有效地生成代码期间。