语法分析 1

程序设计语言构造的语法可以使用 上下文无关文法 或者 BNF (巴库斯-瑙尔范式) 表示法来描述，文法为语言设计者和编译器编写者提供了很大便利:

• 文法给出了一个程序设计语言的精确易懂的语法归约
• 对于某些类型的文法，我们可以自动构造出高效的语法分析器，它能够确定一个源程序的语法结构。同时，语法分析器的构造过程可以揭示出语法的二义性，同时还可能发现一些容易在语言的初始设计阶段被忽略的问题
• 一个正确设计的文法给出了一个语言的结构，该结构有助于把源程序翻译为正确的目标代码，也有助于检测错误
• 一个文法支持逐步加入可以完成新任务的新语言构造，从而迭代地演化和开发程序语言。如果对语言的实现遵循语言的文法结构，那么在实现中加入这些新构造的工作就会变得更加容易

语法分析器从词法分析器获得一个词法单元组成的串，并验证这个串可以由源语言的文法生成，我们期望语法分析器能够以易于理解的方式报告语法错误，并能够从常见的错误中恢复并继续处理程序的其余部分。从概念上来说，对于良构的程序，语法分析器构造出一棵 语法分析树，并把它传递给编译器的其他部分进一步处理。我们并不需要显式地构造出语法分析树，对于源程序的检查和翻译工作可以和语法分析过程交替完成，因此语法分析器和其他部分可以用一个模块实现。

错误处理程序检测出错误后，必须报告在源程序的什么位置检测到错误，程序可能有不同层次的错误

词法错误

包括标识符、关键字或运算符拼写错误，或没有在n字符串文本上正确的添加引号

语法错误

包括分号、花括号的多余、缺失等，或 if-else 语句不匹配等

语义错误

包括运算符和运算分量之间的类型不匹配

逻辑错误

因程序员的错误推理而引起的任何错误，包括良构程序但结果不符合预期

语法分析器在检测出错误后，一般将自己恢复到某个状态，且有理由预期从那里开始输入将提供有意义的诊断信息，通常也会发现更多的错误，而不是检测到一个错误就退出程序，当然如果错误过多最好让编译器在达到某个错误数量上限后退出

panic 的恢复

语法分析器一旦发现错误就不断丢弃输入的符号，直到找到同步词法单元 (synchronizing token) 为止，同步词法单元通常是界限符 (如 ; 或 })，它们在源程序中清晰、无二义性。panic 的错误纠正方法常常会跳过大量输入，不检查跳过部分可能包含的错误，但是实现足够简单且不会让语法分析陷入死循环

短语层次的恢复

当发现错误时，语法分析器可以在余下的输入上进行局部性纠正，即将余下输入的某个前缀替换为另一个串，使语法分析器可以继续分析。这个方法难以处理实际错误发生在检测位置之前的情况

错误产生式

通过预测可能遇到的常见错误，在当前语言的文法中加入特殊的产生式，这些产生式可以生产含有错误的构造，语法分析器就能检测到一个预期的错误，生成适当的错误诊断信息

全局纠正

处理一个错误的输入串时通过最少的改动将其转换为语法正确的串

上下文无关文法

一个上下文无关文法由 终结符、非终结符、一个 开始符号 和一组 产生式 组成

• 终结符：组成串的基本符号，与术语 词法单元名 为同义词，如 if-else 结构中的 if 和 else
• 非终结符：表示串的集合的语法变量，它们表示的串集合用于定义由文法生成的语言
• 开始符号：某个非终结符号，这个符号表示的串集合就是这个文法生成的语言
• 产生式：将终结符和非终结符组合为串的方法，每个产生式由以下元素组成
  • 一个被成为产生式头或左部的非终结符，头代表串的集合
  • 符号 \(\rightarrow\)，有时也使用 ::= 来表示
  • 一个由零或多个终结符与非终结符组成的体或右部，体代表头所对应的串的某种构造方法

例如有一组生成式它们的头都是 E，我们可以将其组合在一起成 E \(\rightarrow\) E + T | E - T | T 这种形式 \[\begin{aligned} E &\rightarrow E + T\\ E &\rightarrow E - T \\ E &\rightarrow T \end{aligned}\]

符号约定

在对文法符号进行表示时，为了方便区分终结符与非终结符，我们对文法中的符号做以下约定

• 终结符
  • 在字母表中排在前面的 小写字母，如a、b、c等
  • 运算符，如+、-等
  • 标点符号，如逗号、分号等
  • 数字
  • 黑体字符串
• 非终结符
  • 在字母表中排在前面的 大写字母，如A、B、C等
  • 字母S，它通常表示开始符号
  • 小写的斜体字符串
• 字母表中排在后面的大写字母表示 文法符号，即表示非终结符或终结符，如X、Y、Z 等
• 字母表中排在后面的小写字母表示 可能为空的终结符号串，如x、y、z等
• 除非特殊说明，第一个产生式的头就是开始符号

例如以下文法中我们可知，E、T 和 F 是非终结符，其中E是开始符号，其余符号是终结符

\[\begin{aligned} E &\rightarrow E + T | E - T | T\\ T &\rightarrow T * F | T / F | F \\ F &\rightarrow (E) | \textbf{id} \end{aligned}\]

推导

推导就是由一连串的产生式组成，从开始符号开始，经过一系列产生式替换，从而形成了推导过程。考虑一个文法 \(\alpha A\beta\)，其中 \(\alpha\) 和 \(\beta\) 是任意的文法符号串，A是非终结符，假设 \(A \rightarrow \gamma\) 是一个产生式，那么可以推导出 \(\alpha A \beta \Rightarrow \alpha\gamma\beta\)，我们经常说的 经过零或多步推导出 使用符号 \(\xRightarrow{*}\) 表示，经过一步或多步推导出 使用符号 \(\xRightarrow{+}\) 表示，并且有以下推论

1. 对于任何串 \(\alpha\)，\(\alpha \xRightarrow{*} \alpha\)
2. 如果 \(\alpha \xRightarrow{*} \beta\) 且 \(\beta \xRightarrow{*} \gamma\)，那么 \(\alpha \xRightarrow{*} \gamma\)

如果 \(S \xRightarrow{*} \alpha\)，其中 S 是文法G的开始符号，我们说 \(\alpha\) 是 G 的一个 句型 (句型可能即包含终结符又包含非终结符，也可以是空串)，文法生成的语言是它所有句子的集合 (句子是不包含非终结符的句型)，由文法生成的语言被成为上下文无关语言，如果两个文法生成的语言相同那么这两个文法等价。推导过程有多种，我们最关心的是 最左推导 和 最右推导，即总是选择句型的最左/最右的非终结符进行替换，直到推导出句子，最左推导与最右推导存在一对一的关系，最左推导写作 \(\alpha \xRightarrow[lm]{} \beta\)，最右推导写作 \(\alpha \xRightarrow[rm]{} \beta\)。

语法分析树是推导过程的图形化表示，其中每个内部结点表示一个产生式的应用，标号为产生式的头，该结点的子结点的标号从左到右组成了推导过程中替换这个产生式的体。一棵树的叶子结点可以是终结符或非终结符， 从左到右将叶子结点排列起来就可以得到一个句型，这个句型被成为 结果 (yield) 或 边缘 (frontier)。例如产生式 E \(\rightarrow\) E + E | E * E | -E | (E) | id ，则 -(id + id) 的语法分析树如下

二义性

如果一个文法可以为某个句子生成多棵语法分析树，那么它就是有 二义性 (ambiguity)，即对同一个句子存在多个最左或最右推导文法。语法分析器都期望文法是无二义性的，需要消除文法中的二义性，可以选择抛弃不需要的语法生成树为每个句子留下一棵语法分析树。譬如上面产生式，可以推导出两种 id + id * id 的语法分析树，很明显第一棵树是正确的，乘法优先于加法进行计算，第二棵语法分析树错误的处理了加法与乘法的优先级。

设计文法

文法能够描述程序设计语言的大部分语法，语法分析器接受的词法单元序列构成了程序设计语言的超集，编译器后续步骤必须对语法分析器的输出进行分析，以保证源程序遵守那些没有被语法分析器检查的规则。

文法是比正则表达式表达能力更强的表示方法，每个可以使用正则表达式描述的构造都可以使用文法来描述，反之不成立。为什么使用正则表达式来定义一个语言的词法语法？

1. 将一个语言的语法结构分为词法和非词法两个部分，可以很方便的将编译器前端模块化，将编译器分为词法分析器和语法分析器两个大小适中的部分
2. 一个语言的词法规则通常很简单，不需要使用像文法这样的功能强大的表示方法来描述
3. 与文法相比，正则表达式通常提供了 简洁 且 易于理解 的表示词法单元的方法
4. 根据正则表达式自动构造得到的词法分析器效率要高于任意文法自动构造的到的分析器

相较来说，正则表达式更适合描述如标识符、常量、关键字等这样的语言构造的结构，文法最适合描述 嵌套结构，这样的嵌套结构不适合正则表达式描述。

消除二义性

一个二义性文法有时也可以被改写为一个无二义性的文法，给出一个 if-then-else 文法， other 表示任何其他语句，这个文法在 悬空-else 结构中会出现二义性

\[\begin{aligned} \textit{stmt}\ &\rightarrow\ \textbf{if}\ \textit{expr}\ \textbf{then}\ \textit{stmt}\\ \ &\rightarrow\ \textbf{if}\ \textit{expr}\ \textbf{then}\ \textit{stmt}\ \textbf{else}\ \textit{stmt}\\ \ &\rightarrow\ \textbf{other}\\ \end{aligned}\]

可以构造出条件语句 if \(E_{1}\) then if \(E_{2}\) then \(S_{1}\) else \(S_{2}\) 的两棵不同的语法分析树，通常规则是每个 else 和最近且尚未匹配的 then 匹配，这个消除二义性规则可以用一个文法直接表示，但实践中很少用产生式表示这个规则。

这里我们给出 if-then-else 结构无二义性的文法

\[\begin{aligned} \textit{stmt}\ &\rightarrow\ \textit{matched\_stmt}\ |\ \textit{open\_stmt}\\ \textit{matched\_stmt}\ &\rightarrow\ \textbf{if}\ \textit{expr}\ \textbf{then}\ \textit{matched\_stmt}\ \textbf{else}\ \textit{matched\_stmt}\ |\ \textbf{other}\\ \textit{open\_stmt}\ &\rightarrow\ \textbf{if}\ \textit{expr}\ \textbf{then}\ \textit{stmt}\ |\ \textbf{if}\ \textit{expr}\ \textbf{then}\ \textit{matched\_stmt}\ \textbf{else}\ \textit{open\_stmt}\\ \end{aligned}\]

消除左递归

如果一个文法中存在一个非终结符A使得对某个串 \(\alpha\) 存在一个推导 \(A \xRightarrow{+} A\alpha\) ，那么这个文法就是 左递归的，即产生式的右部的最左符号是非终结符A本身，自顶向下语法分析方法不能处理左递归的文法，因此需要一个方法来消除左递归。

左递归产生式 \(A \rightarrow A\alpha\,|\,\beta\)，不断应用这个产生式将在 A 的右边生成一个 \(\alpha\) 的序列，当 A 最终被替换为 \(\beta\) 时，就得到一个在 \(\beta\) 后跟0或多个 \(\alpha\) 的序列。使用一个新的非终结符 R，并按照以下方法改写 A 的产生式可以达到同样的效果，对于新产生式 \(R \rightarrow \alpha R\) 来说这是一个 右递归的。

\[\begin{aligned} A\ &\rightarrow\ \beta R\\ R\ &\rightarrow\ \alpha R \ |\ \varepsilon\\ \end{aligned}\]

现在我们给出消除左递归的算法，如果文法中不存在 环 (如 \(A \xRightarrow{+} A\) 的推导) 或 \(\varepsilon\) 产生式 (如 \(A \rightarrow \varepsilon\) 的产生式)，就能保证能够消除左递归，伪代码如下

提取左公因子

提取左公因子是一种文法转换方法，它可以产生适用于预测分析技术或自顶向下分析技术的文法。当不清楚应用在两个A产生式中如何选择时，我们可以通过改写产生式来推后这个决定，等我们读入了足够多的输入，获得足够信息后再做出正确选择。

如有文法 \(A \rightarrow \alpha\beta_{1} | \alpha\beta_{2}\)，输入的开头是从 \(\alpha\) 推导得到的一个非空串，那么我们就不知道应该将A展开为 \(\alpha\beta_{1}\) 还是 \(\alpha\beta_{2}\)，我们可以先将 A 展开为 \(\alpha{}B\)，从而将作出决定的时间推迟，在读入了从 \(\alpha\) 推导得到的输入前缀之后，我们再决定将 B 展开为 \(\beta_{1}\) 或 \(\beta_{2}\)。

其中 \(\gamma\) 表示所有不以 \(\alpha\) 开头的产生式体，\(A’\) 代表新的非终结符，不断应用这个转换，直到所有非终结符的任意两个产生式体都不存在公共前缀为止。