初识语法制导翻译

本文将介绍关于文法的基础部分，有关词法和语法分析的大部分内容将在后续文章中介绍。

文法与产生式

为了分析一门语言，至关重要的是了解并形式化地描述这门语言的语法。 为了表示一门语言的语法，我们使用一种叫做“上下文无关文法”，简称“文法”的表示方法。

上下文无关文法指由产生式、非终结符号、终结符号和开始符号的集合。
  • 产生式是由一个非终结符号的“头部”和一个由终结符号和非终结符号有序排列组成的“尾部”构成的，通常写成$A \to BCD \dots$的形式。 产生式表明了非终结符号如何由一个序列产生。
  • 非终结符号，也称“语法变量”。 在上下文无关文法中，所有非终结符号，通过递归地将其用产生式替换，最终会变成一个终结符号的集合。
  • 终结符号，即该文法所规定的语言的所有基本符号的集合。
  • 开始符号是一个非终结符号，通过开始符号，由产生式，可生成该文法的所有合法内容，这一个由终结符号构成的集合称为该文法定义的语言。

这种文法叫做上下文无关的，因为凡是非终结符号出现的任何地方，都可以将其用对应的产生式代换，而与其所处的上下文无关。 特别注意，尽管几乎所有程序语言都可以用上下文无关文法表示，这个文法的语言不一定是有效的程序。 考虑以下C语言程序片段：

int main()
{
	void main = 1;
}

这个程序片段显然符合C语言的文法，但是几乎不可能通过编译。

通俗地说，如果一个符号可以由产生式产生，那么它就是非终结符号；否则它就是终结符号。 我们规定终结符号用黑体（$\mathbf{while}$）表示，如果不加说明，那么其按字面匹配。 如果产生式有序地列出，那么我们规定第一条产生式的头部为开始符号。 由零个终结符号组成的串称为空串，记为$\varepsilon$。

如果一个非终结符号是多个产生式的头部，那么可以把这些产生式的尾部用竖线分隔连接在一起。

语法分析树

在编译器前端，终结符号的识别通常由词法分析器执行； 而语法分析则是将终结符号串转化成由一个产生式的集合，通过这个集合可以由开始符号产生对应的终结符号串。

语法分析树以图形的方式展示了如何从开始符号推导出（或曰产生）对应的输入。

语法分析树是这样的一棵树：
  • 其根节点的标号是开始符号；
  • 其叶子节点的标号是终结符号；
  • 其内部节点的标号是非终结符号；
  • 如果存在一个结点的标号是非终结符号，那么一定存在一个产生式，使该非终结符号可由其子节点从左至右产生。

一棵语法分析树的叶子节点从左至右连接形成了这棵树的“结果”，即从根节点的开始符号推导生成的终结符号串。

结合性与优先级

如果有多棵树可生成同一终结符号串，那么我们称这个文法是有“二义性”的。 考虑文法： \(string \quad \to \quad string - string \; | \; string + string \; | \; digit\) 其中$digit$表示一个数位。 那么表达式$1-1+4$可有两种推导方式： \(\begin{aligned} string \quad \to \quad string - \underbrace{string}_{string + string} \quad \to \quad string - string + string \\ string \quad \to \quad \underbrace{string}_{string - string} + string \quad \to \quad string - string + string \\ \end{aligned}\) 两者对应两棵不同的语法分析树。 虽然我们默认加减运算是从左至右依次进行的，但是如果按照语法分析树自底向上地进行计算（我们几乎总是这么做），那么第一种推导显然不能导出正确的结果。

为降低文法的二义性，我们提出了结合性和优先级的概念。

优先级的概念非常清楚，因此不再阐述。 当一个运算分量的两侧同时具有同一优先级的运算符时，如果先计算左边的，那么称这个运算符是左结合的，否则则是右结合的。 在C语言中，典型的算术运算是左结合的，而赋值运算是右结合的。 通常同一优先级的运算符的结合性是相同的，否则会出现运算分量两侧的结合性不相同的尴尬情况。

接下来我们考虑如何把结合性用产生式表示出来。 左结合的产生式通常为： \(stmt \quad \to \quad stmt + comp \; | \; comp\) 而右结合的产生式通常为： \(stmt \quad \to \quad comp = stmt \; | \; comp\) 在进行推导时，我们总是利用产生式进行展开，因此左结合的总是会展开左边，而右结合的总是会展开右边，而后展开的总是在树的下层。 如果按照语法分析树自底向上地进行计算，那么后展开的先计算，因此达成了结合性。

接下来考虑一下优先级。 我们先考虑只有加减乘除四个运算、两个优先级的简单情况（C++中的优先级高达十七种之多）。 借助数学中的项和因子的概念，我们把对任何运算都不能再次分割的表达式称为因子（factor），能被乘除分开，而不能被加减分开的称为项（term），有： \(\newcommand\produce[2]{#1 \ \to \ #2} \newcommand\prodor{\; | \;} \begin{aligned} &\produce{expr}{expr + term \prodor expr - term \prodor term} \\ &\produce{term}{term * factor \prodor term \backslash factor \prodor factor} \\ &\produce{factor}{number \prodor ( expr )} \end{aligned}\) 更一般地，我们可以为每一种优先级定义一种“项”，从而需要实现n种优先级只需要n+1种非终结符号。

语法制导翻译

为了从产生式实现翻译，我们需要为其附加一些规则或程序片段。 比如，对产生式$\produce{expr}{expr_1+term}$，我们可以执行以下伪代码：

Translate(expr1);
Translate(term);
Process("+");

依靠文法进行的语法分析称为语法制导翻译。 为了进行这种翻译，我们来引入两个概念。

  • 属性表示某个与程序构造相关的任意量。 因为我们使用终结或非终结符号来表示程序，因此属性也可视为符号的属性。
  • 翻译方案是一种将程序片段附加到产生式上的表示法。 在语法分析中使用某一产生式时，其翻译方案中对应的程序片段就会执行。

综合属性和继承属性

为计算属性的值，我们需要语法制导定义（Syntax Directed Definition，简称SDD）。 语法制导定义指出每个文法符号对应的属性值以及如何根据产生式计算它们（计算方法也称为“语义规则”）。

为了方便地表示和使用这些属性，我们把每个文法符号的属性标注在其对应的语法分析树的结点上。 这种标注了属性的语法分析树称为注释语法分析树。

文法符号对应的属性分为两种：

  • 综合属性指由其本身为头的产生式上的SDD决定的属性，在语法分析树上只由其本身和子节点的属性决定；
  • 继承属性指由其父节点为头的产生式上的SDD决定的属性，在语法分析树上只由其父节点、本身和兄弟节点的属性决定。

如果一个SDD只含综合属性，那么称其为S属性的。 如果一个SDD的所有继承属性都能由其父节点的继承属性、左侧兄弟节点的继承和综合属性和自己的继承和综合属性决定，且属性之间的依赖不形成环，那么我们称其为L属性的。

这两种特殊的SDD中的属性值可以用简单的算法求出。 本文只考虑S属性的SDD，更复杂的情况将在以后的文章中说明。

显然，要求S属性的SDD中的所有属性值，我们只需要按自底向上的方式遍历注释语法分析树即可，而对于L属性则需要以特殊的顺序遍历。

利用综合属性，可以很方便地写出一个将中缀加法表达式转化成后缀表达式的SDD： \(\produce{expr}{expr_1 + term} \qquad expr.s = \mathrm{concat(expr_1.s, term.s, '+')}\) 注释语法分析树的根节点的s属性就是对应的后缀表达式。

翻译方案

通过在产生式中插入程序片段，我们可在不使用属性的情况下完成将中缀表达式转化成后缀的任务。 这些被插入的程序片段（称为“语义动作”）用花括号写在产生式的对应位置上，并在对应位置执行。 这相当于在语法分析树上加入了一个在遍历到时就会执行的程序片段结点。

下面这个翻译方案可以将中缀表达式转化成后缀： \(\begin{aligned} &\produce{expr}{expr_1 + term \; \{ \mathrm{print('+')} \} } \\ &\produce{expr}{expr_1 - term \; \{ \mathrm{print('-')} \} } \\ &\produce{term}{0 \prodor 1 \prodor \cdots \prodor 9 \; \{ \text{打印对应数字} \} } \end{aligned}\)

注意，在实现翻译方案时，一定要保证对语法分析树的遍历等同于后序遍历。 这相当于要求处理某个结点时已经处理过其所有子节点。

语法分析

我们在本文中并不介绍语法分析的具体方法，而只是大致介绍其分类。

语法分析可分为自顶向下的和自底向上的。

自顶向下的分析就是从开始符号开始，逐渐用可能的产生式来对应待分析字符串，从而以自顶向下，自左向右的方式构造语法分析树。 这种分析通常使用“递归下降”的方法，以回溯的方式进行构造。 对于一些特殊的文法，这种分析可以通过预测下一个文法符号来猜测可能的产生式，而不使用栈和递归，因此非常易于构思和调试。 但是无论采用哪种方法，自顶向下分析都可能陷入左递归之中。

自底向上的分析则是从待分析字符串开始，逐步寻找可能的产生式来将其化为头部，从而以自底向上的方式构造语法分析树。 自底向上的分析通常采用“移入-规约”的方法。 这种分析方法只对特别的文法有用，幸运的是，大部分程序设计语言都符合使用移入规约法的要求。

抽象语法树

最后我们来介绍一种常见的前端输出形式，也就是语法分析的输出：抽象语法树（abstract syntax tree）。

一个表达式的抽象语法树就是内部节点为运算符，叶子节点为运算分量的一棵树。 在某种意义上，抽象语法树和语法分析树非常相似，因此语法分析树也叫做具体语法树（concrete syntax tree）。

我们希望抽象语法树和具体语法树尽量相似，因此我们可以引入更一般的抽象语法树。 如果我们把所有关键字，如while、if等也看作运算符，那么就可以构造整个语句的抽象语法树。

我们还可以定义一种特殊的运算符seq来表示把两个语句连在一起。 如此，整个程序的抽象语法树都可以构造出来。

剩余内容

本文简单介绍了语法制导翻译有关的概念和基本内容，但是，要完成编译器前端（或称翻译器）还有许多内容是没有涉及的：

  • 词法分析：如何将字符流转化成词法单元，用于语法分析；
  • 语法分析的具体实现：如何实现一个高效的语法分析器；
  • 语法制导翻译的细节：如何处理L属性的SDD，如何在语法分析时执行指令，还是要等完成语法分析后再执行；
  • 静态检查：如何找出文法分析不能找出的错误（如标识符的重复声明、类型不匹配等）；
  • 中间代码生成：如何生成（并优化）传递给链接器的中间代码，如何告诉链接器变量的信息（符号表的构造）。

当然还有许多后端（链接器）的内容：

  • 运行时环境：如何搭建程序的运行时环境（堆栈空间分配、垃圾回收等）；
  • 目标代码生成：如何从中间代码生成目标机器上的代码。

编译器如何实现代码的优化也是值得探讨的一大问题。 以上问题中相当一部分都会出现在将来的文章之中。

更新时间:

猜您还喜欢

统计物理导论

本文主要介绍统计物理的基本概念——即通过研究大规模微观粒子（称为“系综”，ensemble）的状态描述宏观系统的一门科学。

摄动与变分理论

本文研究求解薛定谔方程的两种近似方法——摄动理论和变分方法。

傅里叶变换与采样

本文主要介绍从连续信号到离散信号的采样以及其和傅里叶变换之间的相互作用。