语法分析器原理简介

上下文无关语法（CFG）

为描述程序设计语言语法，传统的解决方案是使用上下文无关语法（Context Free Grammar, CFG）。对于语言L，其CFG定义了表示L语言中有效语句的符号串的集合。语句即是从语法规则G中推导出的一个字符串。

上下文无关语法G是一组规则，描述了语句是如何形成的。可以冲G导出的语句称为G定义的语言，记作$L(G)$L(G)。上下文无关语法定义语言的集合称为上下文无关语言的集合。

几个重要的概念：

1. 产生式：CFG中的每个规则都称为一个产生式
2. 非终结符：语法产生式中使用的语法变量
3. 终结符：出现在语句中的单词。单词包含了一个词素（Lexeme）及范畴（Syntactic Category)。在语法中，单词通过其语法范畴表示。
4. 推导：一系列重写步骤，从语法的起始符号开始，结束于语言中的一个语句。

在原型符号串中，我们选择一个非终结符$\alpha$α，并选择一个语法规则$\alpha \rightarrow \beta$α→β，然后将原型符号串中的$\alpha$α重写为$\beta$β。我们会重复这个重写过程，直至原型符号串不包含非终结符为止，此时它完全有单词（或称终结符）组成，已经变为语言中的一个语句。

在推导过程中的每一个点上，该符号串都是终结符和非终结符的一个集合。如果这样的一个符号串出现在某个有效推导过程中的某一步骤，则称为句型（sentential form）。任何句型都可以从起始符号出发，用零或多个步骤推导出来。类似地，从任何句型出发，我们都可以用零或多个步骤推导出一个有效的语句。

形式上，上下文无关语法G是一个四元组$(T, NT, S, P)$(T,NT,S,P)，其中各元素解释如下：

• $T$T：是终结符或语言$L(G)$L(G)中单词的集合。终结符对应于词法分析器返回的语法范畴。
• $NT$NT：是G的产生式中出现的非终结符的集合。非终结符是语法变量，引入非终结符用于在产生式中提供抽象和结构。
• $S$S：是一个非终结符，被指定为语法的目标符号或起始符号。$S$S表示$L(G)$L(G)中语句的集合。
• $P$P：是G中产生式或重写规则的结合。$P$P中的每个规则形如$NT \rightarrow {(T \cup NT)}^+$NT→(T∪NT)+，即每次将一个非终结符替换为一个或多个语法符号构成的串。

例子

以下面的CFG为例来展现它的强大功能和复杂性。
$\begin{aligned} Expr\rightarrow&(Expr)\\ &|\ Expr\ Op \ name\\ &|\ name\\ Op \rightarrow& +\\ &| \ -\\ &| \ *\\ &| \ / \end{aligned}$Expr→Op→​(Expr)∣ Expr Op name∣ name+∣ −∣ ∗∣ /​
从其实符号$Expr$Expr开始，我们可以生成两种子项：用规则1生成带括号的子项，或用规则2生成普通的子项。为了生成语句$(a + b) * c$(a+b)∗c，我们可以使用下列重写序列（2,6,1,2,4,3），如下表所示。请记住，语法处理的是name这样的语法范畴（Syntactic Category），而不是a、b或c之类的词素（Lexeme）。

规则	句型
	$Expr$Expr
2	$Expr\ Op\ name$Expr Op name
6	$Expr * name$Expr∗name
1	$(Expr) * name $
2	$(Expr\ Op\ name) * name$(Expr Op name)∗name
4	$(Expr + name) * name$(Expr+name)∗name
3	$(name + name) * name$(name+name)∗name

将推导过程表示为图的树称为语法分析树（parse tree）。如下图所示：

在$(a+b)*c$(a+b)∗c的推导过程中，每一步都重写了最右侧剩余的非终结符。这种系统性的行为只是一种选择而已，其他的选择同样也是可能的。最容易想到的一种备选方案是在每一步重写最左边的非终结符。对同一语句使用最左选择方式，将产生一个不同的推导序列。两种推导得到的语法分析树是相同的。

$(a+b)*c$(a+b)∗c的最左推导是（2,1,2,3,4,6）的序列，如下表：

规则	句型
	$Expr$Expr
2	$Expr\ Op\ name$Expr Op name
1	$(Expr)\ Op\ name$(Expr) Op name
2	$(Expr\ Op\ name)\ Op\ name $
3	$(name\ Op\ name)\ Op\ name$(name Op name) Op name
4	$(name + name)\ Op\ name$(name+name) Op name
6	$(name + name) * name$(name+name)∗name

将推导过程表示为图的树称为语法分析树（parse tree）。如下图所示：

Note：

最右推导：在每个步骤都重写最右侧的非终结符

最左推导：在每个步骤都重写最左侧的非终结符

二义性语法

最左和最右推导使用同一组规则，但两者运用规则的顺序不同。因为语法分析树指标是应用了哪些规则，而未指定按何种顺序应用规则，因此两种推导得到的语法分析树是相同的。

从编译器角度来看，重要的是，在CFG定义的语言中，每个语句都有唯一的最右（最左）推导。如果某个语句存在多个最右（最左）推导，那么在推导过程中的某一个点上，对最右（最左）非终结符的多个不同的重写必定导致生成同一个语句。如果在某个语法中，一个语句存在多个最右（最左）推导，则该语法称为二义性语法。一个二义性语法可以生成多个推导以及多个语法分析树。由于转换过程的后续阶段会将语义关联到语法分析树的细部形状，存在多个语法分析树意味着同一程序有多种可能的语义，对程序设计语言来说，这是一个不良性质。如果编译器无法肯定一个语句的语义，就无法将其转换为一个确定的代码序列。

一个经典的例子：
$\begin{aligned} Statement \rightarrow&\ \text{if}\ Expr\ \text{then} \ Statement\ \text{else}\ Statement\\ &|\text{if}\ Expr\ \text{then} \ Statement\\ &|Assignment\\ &|\ \ ...other statements... \end{aligned}$Statement→​ if Expr then Statement else Statement∣if Expr then Statement∣Assignment∣  ...otherstatements...​
从这个语法片段可以看出，else是可选的。不幸的是，下列代码片段：

$\text{if}\ Expr1\ \text{then}\ \text{if}\ Expr2\ \text{then}\ Assignment1\ \text{else}\ Assignment2$if Expr1 then if Expr2 then Assignment1 else Assignment2

这两种不同的最右推导，两者之间的差别很简单。

第一个推导用内层的if控制$Assignment2$Assignment2，因此当$Expr1$Expr1为true且$Expr2$Expr2为false时，将执行$Assignment2$Assignment2。

第二个推导将else子句关联到第一个if，因此当$Expr1$Expr1为false时将执行$Assignment2$Assignment2，$Expr2$Expr2的值不起作用。

出现二义性，是原来语法中的缺陷所致，为了消除二义性，必须修改该语法，引入新的规则，来确定到底由哪个if来控制特定的else子句。重写如下：
$\begin{aligned} Statement \rightarrow&\ \text{if}\ Expr\ \text{then} \ Statement\\ &|\text{if}\ Expr\ \text{then} \ WithElse\ \text{else}\ Statement\\ &|Assignment\\ WithElse \rightarrow&\ \text{if}\ Expr\ \text{then} \ WithElse\ \text{else}\ WithElse\\ &|Assignment\\ \end{aligned}$Statement→WithElse→​ if Expr then Statement∣if Expr then WithElse else Statement∣Assignment if Expr then WithElse else WithElse∣Assignment​
这个解决方案限制了在if-then-else结构的then部分可以出现在那些语句。它接受的语句集合与原来的语法相同，但可以确保每个else都无歧义地匹配到某个if。它在语法中编入了一条简单的规则：将每个else绑定到最内层、尚未闭合的if。下表是修改后语法的最右推导：

规则	句型
	$Statement$Statement
1	$\text{if}\ Expr\ \text{then} \ Statement$if Expr then Statement
2	$\text{if}\ Expr\ \text{then} \ \text{if}\ Expr\ \text{then} \ WithElse\ \text{else}\ Statement$if Expr then if Expr then WithElse else Statement
3	$\text{if}\ Expr\ \text{then} \ \text{if}\ Expr\ \text{then} \ WithElse\ \text{else}\ Assignment$if Expr then if Expr then WithElse else Assignment
5	$\text{if}\ Expr\ \text{then} \ \text{if}\ Expr\ \text{then} \ Assignment\ \text{else}\ Assignment$if Expr then if Expr then Assignment else Assignment

将运算优先级的信息编码到语法中:

基于表达式$a + b * c$a+b∗c的的最右推导，如下表所示：

规则	句型
	$Expr$Expr
2	$Expr\ Op\ name$Expr Op name
6	$Expr\ *\ name$Expr ∗ name
2	$Expr\ Op\ name * name$Expr Op name∗name
4	$Expr + name * name$Expr+name∗name
3	$name + name * name $

对应的语法分析树，如下图所示：

表达式求值的一种自然方式是树的后序遍历（postorder tree walk）。它将首先计算$a + b$a+b，然后将其结果乘以$c$c，生成$(a + b) * c$(a+b)∗c的最终结果。这种求值顺序，与代数优先级的经典规则相矛盾，算术运算上要求按$a + (b * c)$a+(b∗c)的方式进行求值。由于解析该表达式的终极目标是生成实现表达式的代码，表达式的语法应该具备对语法分析树进行“自然”遍历求值即可得到正确的结果。

真正的问题在于语法结构没有考虑优先级问题。可以通过额外的产生式，为子表达式带括号，这会使语法树中的子表达式增加一个层次使得后序遍历过程中对子表达式按正确的优先级求值。

首先我们必须判断到底需要多少个优先级级别。在丹丹的表达式语法中，我们有三级优先级，（）为最高优先级，$*$∗和$/$/为中等优先级，$+$+和$-$−优先级最低。接下来，我们将运算符在不同的层次上分组，并使用非终结符来隔离语法中对应的部分。下表给出了最终的语法，它包含了一个唯一的起始符号$Goal$Goal，以及用于终结符num的一个产生式，我们还会在后续实例中使用这个终结符。
$\begin{aligned} Goal\ \rightarrow&\ Expr\\ Expr\ \rightarrow&\ Expr + Term\\ &|Expr - Term\\ &|Term\\ Term\ \rightarrow&\ Term * Factor\\ &|Term\ /\ Factor\\ &|Factor\\ Factor\ \rightarrow&\ (Expr)\\ &|num\\ &|name \end{aligned}$Goal →Expr →Term →Factor →​ Expr Expr+Term∣Expr−Term∣Term Term∗Factor∣Term / Factor∣Factor (Expr)∣num∣name​
在上面表达式语法中，$Expr$Expr表示对应于$+$+和$-$−的优先级级别，$Term$Term表示对应于$*$∗和$/$/的级别，$Factor$Factor表示对应于（）的级别。在这种形式下，使用该语法可以为$a + b * c$a+b∗c推导出符合标准代数优先级的语法分析树。推导结果如下表：

规则	句型
	$Expr$Expr
1	$Expr + Term$Expr+Term
4	$Expr + Term * Factor$Expr+Term∗Factor
6	$Expr + Term * name$Expr+Term∗name
9	$Expr + Factor * name$Expr+Factor∗name
9	$Expr + name * name$Expr+name∗name
3	$Term + name * name$Term+name∗name
6	$Factor + name * name$Factor+name∗name
9	$name + name * name$name+name∗name

解析的语法分析树，如下图：

这样就实现了算术优先级的标准规则。请注意，为了强制实施优先级而添加的非终结符，导致语法分析树也增加了对应的内部节点。类似地，替换掉原来语法中的$Op$Op，直接使用哥哥运算符，实际上消除了语法分析树的一部分内部结点。

上下文无关语法及对应语法分析器的类

根据语法分析的难度，将所有的上下文无关语法划分为一个层次结构。这个层次结构有许多级别。常见的四个等级为：CFG、LR(1)语法、LL(1)语法和正则语法（RG）。嵌套关系如下图：

与比较受限的LR(1)与LL(1)语法相比，任意CFG需要花费更多的时间进行语法分析。举例来说，Earley算法可以在$O(n^3)$O(n3)时间内解析任意CFG（最坏情况），其中n是输入流中单词的数目。当然，实际运行时间可能会好一些。历史上，在意识到“通用“技术的低效之后，编译器编写者便远离了此类技术。

LR(1)语法包含了无歧义CFG的很大一个子集。LR(1)语法可以通过从左至右的线性扫描自底向上进行语法分析，任何时候都只需要从当前输入符号前瞻最多一个单词。由于很多工具可以从LR(1)语法导出语法分析器，这使得LR(1)语法分析器成为”每个人都钟意的语法分析器“。

LL(1)语法是LR(1)语法的一个重要子集。LL(1)语法可以通过从左到右线性扫描自顶向下进行语法分析，只要前瞻一个单词。利用手工编码的递归下降语法分析器或生成的LL(1)语法分析器，都可以解析LL(1)语法。许多程序设计语言可以用LL(1)语法定义。

正则语法（RG）是生成正则语言的CFG。正则语法的产生式仅限于两种形式，即$A\ \rightarrow a$A →a或$A\ \rightarrow\ aB$A → aB，其中$A, B \in NT, a \in T$A,B∈NT,a∈T。正则语法等价与正则表达式，它们都恰好定义了DFA可以识别的那些语言。在构建编译器过程中，正则语言主要用于定义词法分析器。

几乎所有的程序设计语言结构都可以用LR(1)形式表达，通常也可以用LL(1)形式表达。因而，大多数编译器使用的快速语法分析算法，都是基于这两种CFG的受限类别之一。

参考

《Engineering a Compiler》