语法分析

编译原理第四部分

语法分析的任务：按照文法，从源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。

语法分析程序的定义：执行语法分析任务的程序称为语法分析程序，也称为==语法分析器==，它是编译程序的主要部分之一。

分析器的输入：单词符号

分析器的输出

分析树
出错处理:定位、续编译

语法分析方法

自顶向下 (top-down)
- 不确定法-回溯
- 确定法
  - 递归子程序
  - 预测分析(LL)
自底向上 (bottom-up)
- 算符优先
- LR(0)、SLR(1) 、LR(1)、LALR(1)

自顶向下

自顶向下分析法

从文法开始符号为树根进行推导，试图自上而下地为期望的终结符串构造一棵语法树

每一步推导是对当前句型中剩余的某个非终结符进行扩展，即用该非终结符的一个产生式的右部替换该非终结符（最左推导）

如果每一步选择产生式来匹配的时候都能够每选必中，则这种方法称为==确定的分析方法==；否则在选择产生式时面临多种可能，不知道选择哪一个产生式合适，就是==不确定的分析方法==

如果不存在任何一个可以产生出所期望的终结符串的推导，则表明存在语法错误

不确定分析方法示例：

$G_1[S]:$ $S→aAB \\ A→bA|c \\ B→dBe|de$

输入串$abbcde$的最左推导：$S \Rightarrow aAB \Rightarrow abAB \Rightarrow abbAB \Rightarrow abbcB \Rightarrow abbcde$ 是该文法$G_1$的句子

语法树：

穷举的试探方法效率低、代价高

确定的自顶向下分析法

先要解决从文法的开始符号出发，如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。

由于相同左部产生式，需要计算首终结符号集

首终结符号集（开始符号集）

设$G＝( V_N, V_T, P, S)$是上下文无关文法，$α$是由非终结符与终结符组成的任意符号串，用$FIRST(α)$表示$α$的首终结符集，则$FIRST(α)＝\{a|α\Rightarrow aβ, a∈V_T,α,β∈(V_N∪V_T)^*\}$
若$α＝ε$，则规定$FIRST(α)＝\emptyset $ (空集)

	最左推导过程	所选产生式	输入串	(当前要替换的非终结符,输入符)
1	S		aca#	(S,a)
2	aAB	S→aAB	aca#	(A,c)
3	acAB	A→cA	aca#	(A,a)
4	acεB	A→ε	aca#	(B,a)
5	aca	B→a	aca#	推导成功

由于空产生式如：$A\rightarrow ε$，需要计算首终结符号集

后随符号集

设$G＝( V_N, V_T , P, S)$是上下文无关文法，$A$是$G$中的非终结符，用$FOLLOW(A)$表示$A$的后随符号集，则有：$FOLLOW(A)＝\{a|S \stackrel{*}{\Rightarrow} …Aa…，a∈V_T\}$
特别地，若有$S\Rightarrow …A$,则规定$＃∈FOLLOW(A)$。

换句话说，$FOLLOW(A)$是指在$G$的各个句型中位于$A$后面的那些终结符或‘＃’。用‘＃’作为输入串的结束符，或称为句子括号，如：＃输入串＃

可选集

给定上下文无关文法的产生式$A→α，A∈V_N,α∈V^*$,则定义：

如果$α \not\stackrel{*}{\Rightarrow} ε$, 则$SELECT(A→α)= FIRST(α)$；

如果$α\stackrel{*}{\Rightarrow} ε$，则$SELECT(A→α)=FIRST(α)∪FOLLOW(A)$；

特别地，如果$α＝ε$，则$SELECT(A→ε)=FOLLOW(A)$。

可选集的含义如下：在自顶向下分析过程中，如果当前要替换的最左非终结符为$A$，面临输入符为$a∈SELECT(A→α)$时，则可以选择产生式$A→α$来匹配。因此，只要文法$G$的某一个非终结符$A$的各个可选集互不相交，则语法分析程序就可以根据当前输入符和$A$的可选集来唯一正确的选择$A$的某个产生式去匹配。

LL(1)文法

第一个“L”, 代表从左（Left）向右扫描单词
第二个“L”,代表产生的是最左（Leftmost）推导
“1”代表向前查看（lookahead）一个单词

定义：

一个上下文无关文法是LL(1)文法的充分必要条件是==关于同一非终结符的各个产生式的可选集互不相交==。

类似地，也可以有LL(k)文法，也就是需要向前查看K个符号才能够确定选择哪个产生式。通常采用K=1，个别情况采用K=2。

特点

无二义性的
不含左递归
无公共左因子

递归文法

递归文法是指对文法中任一非终结符$A$，若存在一个推导序列，在推出的符号串中又出现了该非终结符本身，即$A\stackrel{+}{\Rightarrow}…A…$，则该文法是递归的。

若文法中对任一非终结符$A$有推导$A\stackrel{+}{\Rightarrow}A…$，则称该文法是左递归的。

若文法中对任一非终结符$A$有推导$A\stackrel{+}{\Rightarrow}…A$，则称该文法是右递归的。

左递归又可以分为直接左递归和间接左递归

直接左递归：若文法中的某一产生式形如$A→Aα，α∈V*$，则称该文法是直接左递归的。
间接左递归：若文法中存在某一非终结符$A$，使得$A\stackrel{+}{\Rightarrow}A…$至少需要两步推导，则称该文法是间接左递归的。

非LL(1)文法到LL(1)文法的等价变换

1、消除左递归

当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进人无穷循环之中。

消除直接左递归：只需将产生式进行改写，使之不含左递归。为此需要引进一个新的非终结符，把含有左递归的产生式改写成右递归的产生式。

一般情况

$A→Aα_1 |Aα_2 |…|Aα_{n-1} |Aα_n|β_1 |β_2 |…|β_{m-1} |β_m $

$α_i、β_j∈V^*，i=1,…,n，j=1,…,m$，且$β_j$不以$A$开头

消除直接左递归：引入一个新的非终结符$A^′$

$A →β_1A^′|β_2A^′|…|β_{m-1}A^′|β_mA^′ \\ A^′→α_1A^′|α_2A^′|…|α_n{-1}A^′|α_nA^′|ε$

消除间接左递归

采用代入法把间接左递归变成直接左递归
直接改写文法

2、消除回溯：提取左公因子

在自顶向下分析过程中，当某个非终结符$A$对应多个候选式时，如果其中有几个候选式的左端第一符号相同，那么就会使得语法分析程序无法根据当前要替换的非终结符和当前输人符唯一地决定选用哪个候选式来替换$A$，只能采用试探的办法，任选某个候选式去试探一次。如果不能导致最终正确地匹配，只得再换另一个候选式去试探，从而引起回溯。

一般情况

若A的产生式为：$A→αβ_1|αβ_2|…|αβ_k$

经过提取公共左因子α，原产生式变为：

$A→αA^′ \\ A^′→β_1|β_2|…|β_k $

如果$β_m、β_n$…（其中$1≤m、n≤k$）中仍然含有公共左因子，则可反复提取它们的共同左因子，直到每个新引入的非终结符的产生式再无公共左因子为止。

注意：不含左递归和左公因子的文法不一定是LL(1)文法

3、计算$SELECT$集，判断产生式左部相同的$SELECT$的交集是否为空

确定的自顶向下分析方法

特征——根据下一个输入符号为当前要处理的非终结符选择产生式

要求——文法是LL(1)文法

语法分析方法：

递归下降分析法
预测分析法

递归下降分析法

递归子程序法是比较简单直观易于构造的一种语法分析方法。

实现思想：文法中每个非终结符对应一个递归过程(子程序)，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时能够按LL(1)形式可唯一地确定选择某个候选式进行推导。

预测分析法

预测分析法用一个分析栈存放当前要替换的非终结符的某个候选式的符号串（倒放在栈内），当非终结符呈现在栈顶时，它就是当前非终结符；此外，还使用一张矩阵形式的==预测分析表==，它是根据可选集构造的，它的入口指出了某非终结符和某终结符匹配时所应选择的候选式和语义动作。预测分析程序的总控程序就是利用栈顶符号和当前输人符号对输人串进行预测分析，而预测的信息则存放在预测分析表的相应入口里。

预测分析表的构造算法是：

对每个终结符$a∈SELECT（A→α）$，把$A→α$填入$M[A，a]$中；把所有无定义的$M[A，a]$均填上“出错标志”。
把所有无定义的$M[A，a]$均填上“出错标志”。

上述算法可应用于任何文法$G$以构造它的分析表$M$。但对于某些文法，有些$M[A，a]$中可能有若干个产生式，或者说有些$M[A，a]$可能是多重定义的。

一个文法$G$的预测分析表$M$不含多重定义入口，当且仅当该文法是$LL(1)$文法。

示例：$E → TE^′ \\
E^′ →十TE^′|ε \\
T → FT^′ \\
T^′ → *FT^′|ε \\
F → i |(E) $

预测分析表

	i	+	*	(	)	#
E	E → TE’			E→TE’
E’		E’→+TE’			E’→ε	E’→ε
T	T→FT ‘			T→FT ‘
T ‘		T ‘→ε	*T ‘→FT ‘**		T ‘→ε	T ‘→ε
F	F → i			F→(E)

分析过程输入串 i+i

	分析栈	(栈顶符,输入符)	剩余输入串
1	#E	( E,i)查表E → TE’	i+i#
2	#E’T	(T,i)查表T→ FT’	i+i#
3	#E’T’F	( F,i)查表F →i	i+i#
4	#E’T’i	( i,i) 匹配	+i#
5	# E’T’	( T ‘,+)查表T ‘ → $\varepsilon $	+i#
6	#E’	( E’, +)查表E ‘ →+TE’	+i#
7	#E’T+	( +,+)匹配	i#
8	# E’T	( T,i)查表T → FT’	i#
9	#E’T’F	( F,i)查表F → i	i#
10	#E’T’i	( i,i )匹配	#
11	#E’T’	( T’, #)查表T’ → $\varepsilon $	#
12	#E’	( E’, #)查表E’ → $\varepsilon $	#
13	#	( #, #) 成功接收	#

自底向上

自底向上语法分析的基本思想是从左向右扫描输入串，一边将输入符移进分析栈内，一边检查位于栈顶的一串符号是否与某个产生式的右部相同，若发现相同，就把栈顶的这串符号替换为相应产生式的左部的非终结符（这种替换就称为==归约==）；若不相同，则继续移进输入符。并继续判断。重复这一过程直到输入串已到达串尾，而栈内恰好为==给定文法的开始符号==（假定未发现错误）时为止。此时表明分析成功，也就确认输入串是文法的句子。这种分析方法也称为==移进-归约分析法==。

可归约串

可归约串：即每次归约的那串符号（是各个产生式的右部），称为==句柄==。

自底向上语法分析的关键：在自底向上语法分析的过程中，最关键的问题就是如何识别句柄

规范规约

规范推导：即最右推导

规范归约：规范推导的逆过程。

规范句型：由最右推导推导出的句型

分析过程的不确定性

两种动作：移进归约

若在自底向上的分析过程中，语法分析程序每次只面临一种动作选择，要么移进，要么归约，则这个分析过程就是确定的，不会产生错误归约。

若在某一步的分析中，既可移进又可归约或者同时可选择两种归约动作，则语法分析程序的动作就是不确定的。

存在的问题

移进_归约冲突
归约_归约冲突

句柄，短语，最左素短语

【短语】若$S\stackrel{*}{\Rightarrow} αAδ$且$A\stackrel{+}{\Rightarrow} β$，则称$β$是相对于非终结符$A$的句型$αβδ$的短语。

【直接短语】若$S\stackrel{*}{\Rightarrow}αAδ$且$A→β$，则称$β$是相对于非终结符$A$的句型$αβδ$的直接短语(也称为简单短语)。

直接短语是某个产生式右部的符号串

【句柄】位于句型最左边的直接短语称为该句型的句柄。

利用语法树求短语、直接短语、句柄

子树：由语法树中的某一个结点连同其所有下层的后代结点组成的部分。

简单子树：只有单层分支（即父子两代）的子树。

短语：每棵子树的各端末节点从左向右排列形成一个短语。

直接短语：每棵父子两代的子树（即简单子树）的各端末节点从左向右排列形成一个直接短语。

句柄：位于语法树最左边的父子两代的子树的各端末节点从左向右排列形成句柄。

注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。

【素短语】有以下3个特征；

它首先是一个短语，
它至少含一个终结符号，
除自身外，不再包含其他素短语。

【最左素短语】 (LPP_leftmost Prime Phrase)：位于句型最左边的素短语。

示例1：文法$G_2[S]：$$S→AB \\ A→bB \\ A→Aa \\ B→a \\ B→Sb$

求句型$baSb$的全部短语、直接短语、句柄

句型baSb的短语：ba，a，Sb，baSb。
直接短语：a，Sb
句柄：a

示例2：

在任何自底向上的分析法中，语法分析器的设计必须解决下面两个问题：

如何保证所找到的直接短语（即某个产生式右部的符号串）是最左的。
如何确定句柄在句型中的开始位置和结束位置，从而可以抽取它。

解决最左性

分析器自左向右地逐个读入输入串，使用分析栈存放读入的符号，并同时检查栈顶是否形成直接短语。任何时刻，栈内符号串和剩余输入串都形成一个规范句型，并且栈内符号串构成句型的左部。因此，一旦栈顶部形成直接短语，它必定是最左直接短语，即句柄。

确定句柄的起始位置

对于第二个问题的不同解决方法产生了不同类型的文法

优先法：利用归约的先与后来识别句柄。有简单优先分析法，算符优先分析法。

状态法：用状态的概念来描述不同时刻下所形成的那部分句柄。例如对于产生式：$A→aBC$，对应4种不同的识别状态：$A → ·aBC，A → a·BC，A → aB·C，A → aBC· $ ，基于此种思想的有LR分析法。

简单优先方法

简单优先方法是一种简单直观，广为使用的自底向上的分析方法。这种方法特别有利于分析表达式。

简单优先方法就是根据算术运算的计算原理（运算符之间的优先顺序）而设计的一种语法分析方法。

基本思想

首先规定文法符号之间的优先关系，然后再利用这种关系，通过比较句型中两个相邻的符号之间的优先关系来确定句型的“句柄”并进行归约

相邻关系

设$S_i$和$S_j$是文法$G$的任意两个符号，那么它们在句型中可相邻出现的充要条件是必须满足下列条件之一

1、有形如 $U→… S_iS_j…$的产生式

2、有形如 $U→…S_i W…$的产生式，且有$ W \stackrel{+}{\Rightarrow} S_j…$

3、有形如 $U→…VS_j…$的产生式，且有$ V \stackrel{+}{\Rightarrow} …Si $

4、有形如 $U→…VW…$的产生式，且有 $V\stackrel{+}{\Rightarrow} …S_i$和$W \stackrel{+}{\Rightarrow} S_j…$

优先关系矩阵

示例：设有文法$G_z：$ $Z → bMb \\ M→a︱( L \\ L→Ma)$

优先关系矩阵

构造优先矩阵

STEP 1 : 对每个非终极符$W$求下面两种集合

$HEAD(W)=\{S|W\stackrel{+}{\Rightarrow}S…, \quad S\in(V_N,V_T) \}$

$LAST(W)=\{S|W\stackrel{+}{\Rightarrow}…S, \quad S\in(V_N,V_T) \}$

STEP 2 : 对每个符号对$S_i,S_j$填写优先关系矩阵元素(其中$W,V∈V_N$)

算符优先分析法

简单直观，特别便于手工实现。只考虑终结符之间的关系

【算符文法】对于上下文有关文法$G$，如果它的每个产生式的右部没有两个非终结符直接相邻，即没有$P →…QR…（Q、R∈VN ）$形式的产生式，则$G$是一个算符文法 (operator grammar)。

$FIRSTVT(P) = \{a | P \stackrel{+}{\Rightarrow} a… 或 P\stackrel{+}{\Rightarrow} Qa…\}$

$LASTVT(P) = \{a|P\stackrel{+}{\Rightarrow} … a 或P\stackrel{+}{\Rightarrow} …aQ\}$

示例：算术表达式文法$G _4[E]：$ $E→E +T | T \\ T→T ^* F | F \\ F→i |（E）$

算符优先矩阵

输入串 $i+i ^* i$ 的分析过程

规定 # < 所有的文法符号 >＃

LR分析法

LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程，每一步归约的都是真正的句柄。

LR(k)分析法的含义是：

L：表示自底向上分析过程中是从左到右扫描输入串

R：表示在分析过程中采用最右推导底逆过程

K：表示需要向前查看k个输入符号

LR(0)分析法中的0表示不需向前查看输入符

LR(1)分析法中的1表示只需向前查看一个输入符

基本原理：把每个句柄的识别过程划分为若干状态，利用DFA来识别

分析栈：存放“状态”和移进、归约的文法符号。

分析表：分为两个子表。

动作表：指出DFA每个状态下应采取的动作：移进、归约、接收或报错。
状态转向表：指出DFA的转向状态，即分析栈应转换到的下一个状态（栈顶的新状态）。

总控程序：依据分析表驱动语法分析的进程

【规范句型的活前缀】规范句型的一个前缀，如果它不含句柄后的任何符号，则称它是该规范句型的一个活前缀。

活前缀示例：

$G[S]$为：$S → v I : T \\ I → I , i \\ I → i \\ T → r$

句子 v i，i：r 的规范推导：$S \Rightarrow v I : T \Rightarrow v I : r \Rightarrow v I，i : r \Rightarrow v i，i：r$

句子 v i，i：r 的前缀有：ε, v ，v i ，v i , ，v i , i ，……

句子 v i，i：r 的活前缀有：ε, v ，v i

句型 v I，i：r 的前缀有：ε, v ，v I ，v I, ，v I,i ， v I,i :， ……

句型 v I ，i：r 的活前缀有：ε, v ，v I ，v I, ， v I , i

活前缀和句柄之间有三种关系

活前缀不含有句柄的任何符号

活前缀只包含句柄的部分符号

活前缀包含句柄的全部符号

$A→ \cdot β$ 刻划没有句柄的任何符号在栈顶，此时期望$A→β$的右部所推出的符号串

$A→β_1\cdot β_2$ 刻划$A→β_1β_2$的右部子串$β_1$已出现在栈顶，期待从输入串中看到$β_2$推出的符号

$A→β\cdot $ 刻划产生式$A→β$的右部$β$已出现在栈顶

LR(0)

在文法G中每个产生式的右部适当位置添加一个圆点构成LR(0)项目。

例如产生式：$A→aBC$，有4个LR(0)项目：$A →\cdot aBC，A →a \cdot BC，A →aB \cdot C，A →aBC \cdot$

一个产生式的项目个数是其右部符号的长度加1。

每个项目的含义与圆点的位置有关，

圆点的左部：表示分析过程的某时刻用该产生式归约时句柄已识别过的部分；
圆点的右部：表示待识别的部分。

注意：空产生式$A→ε$仅有LR(0)项目$A→ \cdot $

LR(0)项目的分类

移进项目，形如 $A→\alpha \cdot a \beta $，a是终结符, $\alpha ,\beta \in V^* $表示下一步要从输入串中移进一个终结符

待约项目，形如 $A→\alpha \cdot B \beta $，表示等待栈顶归约出所需的非终结符来

初始项目，形如$S’→ \cdot S$ ，表示开始识别一个句子。

归约项目，形如 $A→\alpha \cdot $，表示句柄已识别完毕，应该归约的项目

接收项目，形如 $S’→S \cdot $ ，表示整个句子已识别完毕

【后继项目】表示同属于一个产生式的项目，但是圆点的位置仅相差一个文法符号，则称后者为前者的后继项目

例如：项目 $S → v \cdot I : T$ 是 $S → \cdot v I : T$的后继项目

$A→ε$的LR(0)项目只有$A→ \cdot $ ，是归约项目

第一步：文法拓广

为保证开始符号仅出现在一个产生式的左边，即使得接收项目唯一

第二步：构造识别活前缀的DFA

第一种方法是求出文法的所有产生式的LR(0)项目，每个项目都为NFA的一个状态，按一定规则构造识别活前缀的NFA，再确定化为DFA

第二种方法是把拓广文法的第一个项目$\{S^′→ \cdot S\}$作为初态集的核，通过求核的闭包和转换函数，求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA

寻找等价项目

LR(0)项目集的闭包$CLOSURE(I)$

GO函数——状态转换函数