第3章


编译器前端




编译器前端是整个编译器的第一个阶段，它负责读入被编译程序的源代码，对其进行词法分析、语法分析和语义分析，并为程序构建合适的中间表示，供编译器的后续阶段进一步处理。词法分析将程序字符流解析为记号流，并检查词法单元的正确性； 语法分析读入词法分析阶段输出的记号流，并根据程序语言的语法规则，对程序进行语法检查，对于语法检查通过的程序，编译器将为其构建抽象语法树作为中间表示； 语义分析遍历程序的抽象语法树，并检查抽象语法树是否满足语言的语义规范。本章对编译器前端的词法分析、语法分析和语义分析等阶段进行深入讨论。


3.1词法分析




词法分析器的主要任务是读入源程序的字符流，生成词法记号流，同时去除源程序的注释和空白(包括空格、制表或换行符等字符)。本节深入讨论词法分析器构建的理论和技术，先介绍正则表达式和有限状态自动机的概念，再给出由正则表达式构建有限状态自动机的算法。
3.1.1记号
词法记号(lexical token)是一个二元组(k,s)，其中第一元k是词法记号所属的类别，第二元s是组成该词法记号的具体字符序列。词法记号是词法分析阶段使用的基本数据结构，接下来将其简称为记号。
程序设计语言的记号可以归类为有限的记号类型。例如，表31给出了典型程序设计语言的一些记号。其中 ID 代表标识符记号，典型的例子包括程序可以使用的标识符(但一般不包括关键字)； INT 代表整型常量记号； REAL 代表浮点型常量记号； 关键字是程序设计语言预先确定了含义的词法单元，程序员不可以对这样的词法单元重新声明它的含义，如表31中的 IF、RETURN 等都是关键字。一般地，编译器将每个运算符和分隔符也都单独归为一类。


表31典型程序设计语言的一些记号



类型k字符序列s类型k字符序列s

IDx y area dfsCOMMA,
INT3 65 921 684NEQ!=
REAL34.8 1e67 5.5e-10LPAREN (
IFifRPAREN)
RETURNreturn


词法分析器的主要任务是读入程序的源代码的字符流，将其分割成记号流并返回记号流。例如，对于下面一段C语言示例程序： 


1．float match0(char *s){ /* find a zero */

2．if(!strncmp(s, "0.0", 3))

3．return 0.;

4．} 


词法分析器将返回下列记号流： 
FLOAT  ID(match0)  LPAREN  CHAR  STAR  ID(s)  RPAREN  LBRACE IF  LPAREN  BANG ID(strncmp)  LPAREN  ID(s)  COMMA  STRING(0.0)  COMMA  INT(3)  RPAREN  RPAREN RETURN  REAL(0.)  SEMI  RBRACE  EOF
需要注意，由于有些记号类别(如 IF)只有单一的记号，因此并不需要记录对应的字符序列s； 另外，记号 EOF表示结束符，代表输入的结束。
接下来将介绍如何用正则表达式来给出记号的形成规则，并基于确定有限状态自动机来实现词法分析器。
3.1.2正则表达式
语言是字符串组成的集合，字符串是字符的有限序列，字符来自字母表。例如，Pascal 语言是所有组成合法 Pascal 程序的字符串的集合，C 语言关键字是C 程序设计语言中不能作为标识符使用的所有字母、数字和字符串组成的集合。这两种语言中，前者是无限集合，后者是有限集合。这两种语言的字母表都是 ASCII 字符集。
毕昇编译器原理与实践
0
第3章编译器前端
0

利用正则表达式 (Regular Expression，RE)这一数学工具，可以使用有限的描述来指明这类有可能是无限的语言，每个正则表达式给出了一个字符串集合。
对于给定的字符集

Σ={c1,c2,…,cn}

正则表达式由以下规则归纳定义。
(1) 空串是正则表达式，它表示{}。
(2) 对于任意c∈Σ，c是正则表达式，它表示语言{c}。
(3) 如果M和N都是正则表达式，则以下也是正则表达式： 
① 选择： M|N={M,N}，一个字符串属于语言M或者语言N，则它属于语言M|N，即M|N组成的串包含M和N这两个集合的字符串的并集。
② 连接： MN={mn|m∈M,n∈N}，如果一个字符串m属于语言M，一个字符串n属于语言N，则字符串的连接mn属于MN组成的语言。
③ 闭包： M={,M,MM,MMM,…}，即如果一个字符串是由M中的字符串经过零次至任意多次连接运算得到，则该字符串属于M。例如，((a|b)a)表示无穷集合{,aa,ba,aaaa,baaa,aaba,baba,…}。
约定括号具有最高优先级，以下依次为闭包、选择和连接，则可以省略正则表达式中一些不必要的括号。例如，((a)(b))|(c)等价于ab|c。
还可以引入一些更简洁的缩写形式： ［abcd］ 表示(a|b|c|d)； ［bg］表示［bcdefg］；［bgM Qkr］表示［bcdefgMNOPQkr］；M？表示(M|)； M+表示(MM)。表32总结了正则表达式的基本操作符(包括缩写形式)。正则表达式的这些缩写形式，在正则表达式库或者词法分析器自动生成工具中都得到了广泛的应用。


表32正则表达式的基本操作符



缩 写 形 式含义
a表示字符本身
空字符串
M|N选择，在M和N之间选择
MN连接
M·N连接的另一种写法
M克林闭包(Kleene closure)，重复0次或任意多次
M+正闭包，重复1次或1次以上
M？M出现0次或1次
［azAZ］字符集
.句点，表示除换行符之外的任意单个字符
“ a.+*”引号中的字符串，表示文字字符串本身

用正则表达式可以方便地表达程序语言中记号的形成规则。例如，C 语言的标识符是由字母或下画线开头，后跟零个或多个字母、数字或下画线的串，则可以用下面的正则表达式定义C语言标识符： 

［azA Z_］(［azAZ09_］)

3.1.3有限状态自动机
定义有限状态自动机(Finitestate Automaton，FA)是一个五元组： 


(S，Σ，δ，s0，SA)

其中各分量的含义如下： 
(1) S是一个有限状态集。
(2) Σ 是有限字母表，通常Σ是有限状态机中边的标签的集合，并且该集合和具体的语言相关，例如，在C语言中，Σ是ASCII字符集。
(3) δ是状态转移函数，它将每个状态s∈S和每个字符c∈Σ的二元组(s,c)映射到下一状态集合T，这意味着有限状态自动机如果在状态s遇到字符c，将转移到δ(s,c)中的任一状态上。
(4) s0∈S是指定的起始状态，有限状态自动机的转换将从这里开始。
(5) SAS是接收状态集合，当有限状态自动机转换到接收状态集合SA中的某个状态时，自动机可终止执行。
根据状态转移函数δ的值域不同，有限状态自动机可分为确定有限状态自动机 (Deterministic Finitestate Automata，DFA)和非确定有限状态自动机(Nondeterministic Finitestate Automata，NFA)。
在确定的有限状态自动机中，有

δ(s,c)={s′} 

即对于状态s和任意输入字符c，确定有限状态自动机只会转移到一个确定的状态s′，而不会转移到零个或超过一个状态。确定有限状态自动机以如下方式接受或拒绝一个字符串： 确定有限状态自动机从初始状态出发，对于输入字符串的每个字符，自动机都将沿着一条确定的边到达另一状态，这条边必须标有输入字符。确定有限状态自动机对输入的n个字符进行了n次状态转换后，如果自动机到达了接收状态，则自动机将接受该字符串； 如果到达的不是接收状态，或者在中间某个状态，自动机找不到与输入字符匹配的转移边，那么自动机将拒绝接收这个字符串。一个自动机识别的语言是该自动机接受的字符串的集合。图31是接收由正则表达式 (a|b)  abb 给出的字符串集合的 DFA。
非确定有限状态自动机的状态转移函数满足


δ(s,c)=T，且c≠，|T|≠1(3.1)

或

δ(s,)=T(3.2)

方程(3.1)说明非确定有限状态自动机对于非空字符c，可以转移到多于一个状态的集合T，这意味着此时非确定有限状态自动机需要对多条标有相同符号的转移边进行选择。方程(3.2)说明非确定有限状态自动机还可能存在标有的边，这种边可以在不接受输入字符的情况下进行状态转换。图32是接受由正则表达式(a|b)abb给出的字符串集合的NFA。



图31DFA




图32NFA


3.1.4Thompson算法
编译器要从正则表达式得到词法分析器，第一步可将正则表达式转换成一个非确定有限状态自动机。这一步骤将使用 Thompson 构造算法，该算法基于对正则表达式语法的模式匹配进行，即对于基本正则表达式(包括基本字符和空串)，算法直接构造其对应的非确定有限状态自动机； 而对于复合正则表达式(包括连接、选择和闭包)，算法以递归的方式构造其非确定有限状态自动机。
图33给出了用于和a的简单NFA，以及用a和b的NFA组成ab、a|b、a所需的转换。这种转换适用于任意的NFA。


图33用于正则表达式运算符的简单NFA


Thompson构造算法首先为正则表达式中的每个字符构造简单的NFA，再按照优先级和括号规定的顺序，对这些简单NFA应用选择、连接和闭包等转换。对于正则表达式a(b|c)，构造法首先分别为a、b和c构建简单的NFA。因为括号的优先级最高，所以接下来为括号中的表达式b|c构建NFA。又因为闭包的优先级比连接高，所以接下来为闭包(b|c)构建NFA。最后将a和(b|c)的NFA连接起来。构造过程如图34所示。


图34对a(b|c)应用Thompson构造算法



3.1.5子集构造算法
在非确定有限状态自动机中，从一个状态出发可能有多条标有相同符号的边，因此自动机需要进行选择，这种状态转移的不确定性导致算法在实现时往往需要用到回溯，回溯会影响程序执行效率。与非确定有限状态自动机的执行相比，确定有限状态自动机的每一步都只有一个可能的转换，因此其执行要容易得多。所以，词法分析器的下一步是使用子集构造算法将非确定有限状态自动机转换为等价的确定有限状态自动机。
算法1给出了子集构造算法，该算法接受非确定有限状态自动机(N,Σ,δN,n0,NA) 为输入，生成一个等价的确定有限状态自动机(D,Σ,δD,d0,DA)，这两个自动机使用同样的字母表Σ。公式在算法中出现时用正体表示，本书余下算法也使用此约定。








算法1子集构造算法


输入：  非确定有限状态自动机 (N,Σ,δN,n0,NA)

输出：  确定有限状态自动机 (D,Σ,δD,d0,DA)

1. procedure Subset (N, Σ, δN, n0, NA )

2. q0 = Closure({n0} , δN)

3. Q = {q0}

4. W = {q0}

5. while W ≠ do

6. 从工作表 W 中删除一个状态集合 q

7. for 对字母表 Σ 中的每个字符 c do

8. t = Edge(q, c, δN)

9. δD (q, c) = t

10. if t  Q then

11. 将 t 添加到 Q 和 W 中

12. procedure Edge(T, c, δ)

13. R = 

14. for 对于 S 中的每一个状态 s do



15. R ∪ = δ(s, c)

16. return Closure(R, δ)

17. procedure Closure(T, δ)

18. while 状态集合 T 仍在变化 do

19. for T 中的每个状态 s do

20. T ∪ = δ(s, ε)

21. return T



该算法构造了一个集合Q，其每个元素都是状态集合N的一个子集，并且对应确定有限状态自动机中的一个状态。这个构造算法通过模拟非确定有限状态自动机的状态转移，来构建确定有限状态自动机。
该算法首先调用闭包函数Closure({n0},δN )，得到一个初始状态集合q0。闭包函数Closure(T,δ) 是一个辅助函数，它计算给定的状态集合T仅通过转移就能到达的所有状态集合。接着将q0加入确定有限状态机的状态集合Q。最后使用工作表算法，每次循环都从工作表W中删除一个状态集合q，并对字母表Σ中的每个字符c，分别计算从集合q中可以转移到的集合t，并把状态转移关系记录在转移函数δD中。
子集构造算法是一个不动点算法，即集合Q是单调递增的，而Q中的每个集合只在工作表W上出现一次，所以算法一定会运行终止。
由于集合Q中的元素最多有2N个，所以理论上该算法的最坏时间复杂度为O(2N)。但并不是每个子集都会出现Q中，所以这种情况实际很少发生。

当子集构造算法停止后，可以利用Q和T来构建DFA。每个qi∈Q都用一个状态di∈D来表示。如果qi包含非确定有限状态自动机的某个接受状态，那么di就是确定有限状态自动机的接受状态之一。基于q0构建的状态称为d0，即确定有限状态自动机的初始状态。
对于正则表达式 a(b|c)，执行该算法的步骤如下： 
(1) 初始化时，将q0设置为Closure(s0)，刚好为q0。While循环的第一次迭代计算Closure(δ(q0,a))，其中包含了6个NFA状态，还计算了Closure(δ(q0,b))和Closure(δ(q0,c))，二者都为空集。
(2) while循环的第二次迭代考查q1，生成了两个集合，称为集合q2 和 q3。
(3) while循环的第三次迭代考查q2，构造出了两个集合，与集合q2和q3相同。
(4) while循环的第四次迭代考查q3，又构造出了两个集合，与集合q2和q3相同。
表33详细列出了子集构造算法的各次迭代过程。图35给出了由此产生的DFA，其状态对应于表33中得出的DFA状态，转移函数由生成这些状态的δ操作给出。由于集合q1、q2 和q3都包含s9(NFA的接受状态)，因此在DFA中，这三个状态都是接受状态。


表33子集构造算法的各次迭代过程



集合名称DFA状态NFA状态
Closure(δ(q,))
abc

q0d0s0s1,s2,s3
s4,s6,s9
q1d1s1,s2,s3
s4,s6,s9s5,s8,s9
s3,s4,s6
s7,s8,s9
s3,s4,s6

q2d2s5,s8,s9
s3,s4,s6q2q3

q3d3s7,s8,s9
s3,s4,s6
q2q3




图35对NFA应用子集构造法



3.1.6Hopcroft算法
用子集构造算法构建的确定有限状态自动机可能存在大量状态，这样会增加词法分析器占用的内存空间，所以需要对确定有限状态自动机进行化简，这个过程被称为自动机的最小化。为了最小化确定有限状态自动机 (D,Σ,δD,d0 ,DA )，需要检测两个状态 di,dj ∈D是否等价，即二者是否对任何输入字符串都产生相同的行为。
算法2根据确定有限状态自动机状态的行为来找到状态中的各个等价类，并从这些等价类出发，构造一个最小的确定有限状态自动机。





算法2Hopcroft 算法


输入： 确定有限状态自动机 (D,Σ,δD ,d0 ,DA )

输出： 最小化后的确定有限状态自动机

1. procedure MinimizeDFA (D, Σ, δD , d0 , DA )

2. T = DA, D - DA

3. P = 

4. while P ≠ T do

5. P = T

6. T = 

7. for 每个集合 p ∈ P do

8. T = T ∪ Split(p);

9.  return T

10. procedure Split(S)

11.  for 每个字符 c ∈ Σ do

12. if c 将集合 S 划分为 S1 和 S2 then

13. return {S1, S2}

14. return S



这个算法的目标是构造出所有确定有限状态自动机状态的一个集合划分

P=p1,p2,…,pm


其构造依据是根据状态的行为分组： 即对于两个状态dx,dy∈pi和任意字符c，如果

dx c du

dy c dv


则都有du,dv∈pj，则状态dx,dy∈pi可看成是等价的。
在行为等价性的约束下，编译器为了最小化确定有限状态自动机，应该使每个集合pi∈P尽可能大。因此，算法使用的初始划分包括两个集合p0=DA和p1=D-DA，这样的划分确保在同一个集合中不会同时包含接受和非接受两种状态。
然后，算法重复地考查每个pi∈P，寻找pi中对某个输入字符c具有不同行为的状态，以此来改进初始划分。划分的条件是： 给定字符c∈Σ，c对于每个状态di∈ps都必须产生相同的行为，如果不满足这个条件，算法将围绕c来划分pi。
集合p1={di,dj,dk} 中的各个状态是等价的，其充分必要条件为： c∈Σ，各状态处理输入字符c时，所转移到的各个目标状态也属于同一个等价类。如图36所示，每个状态对a都有一个转移： diadx，dj a dy，dka dz。如果dx、dy和dz在当前划分中属于同一个集合，那么 di、dj和dk应该同时保留在p1中，a不会导致拆分p1。


图36围绕a进行拆分


如果 dx、dy和dz属于两个或更多不同的集合，那么a将导致拆分p1。如果dx∈p2且dy和dz∈p3，则必须拆分p1并构造两个新集合p4={di} 和p5={dj,dk}，以反映DFA对符号a开头的字符串的不同输出。如果di对a没有转移，也会导致同样的拆分。算法会考查每个状态p∈P和每个字符c∈Σ。如果字符c导致p发生拆分，算法会根据p构造两个新集合并添加到P。重复这个过程，直至得到的划分中所有集合均无法拆分为止。


图37最小DFA

接下来依据最终的划分P来构造新的DFA，首先分别创建一个状态来表示每个集合p∈P，然后在这些新的状态之间增加适当的转移。对于表示pl 的状态，如果某个dj ∈pl 对输入字符c转移到某个dk∈pm，那么针对输入c添加一个转移，目标为表示pm的状态。
对于正则表达式 a(b|c)，最小化算法的第一步构造了一个初始划分 {{d0},{d1,d2,d3}}。由于p1只有一个状态，所以它不能拆分。p2中任何状态都没有针对输入a的转移。对于b和c，p2中的每个状态都有一个转移，只是转移的目标又回到了p2 中。因此，Σ中任何符号都不会导致p2发生拆分，最终划分是{{d0} ,{d1,d2,d3}}。产生的最小 DFA 如图37所示。



3.2语法分析





语法分析是编译器前端的第二个重要阶段。语法分析器的任务是读入词法分析阶段生成的记号流，判断该记号流是否满足程序设计语言的语法规则。如果语法分析器确认源程序不合法，则返回出错信息来指导程序员对源程序进行修改； 如果语法分析器确认记号流符合相应语言的语法规则，它将为该程序构建一个合适的数据结构表示(一般是抽象语法树)，供编译的后续阶段使用。
本节将讨论编译器实现语法分析的主要理论和技术。首先介绍描述语言语法规则的数学工具： 上下文无关文法； 然后分别介绍两类语法分析算法： 自顶向下分析和自底向上分析。在自顶向下分析中，将重点介绍递归下降分析算法和 LL 分析算法，而在自底向上分析中，将重点介绍LR分析算法。
3.2.1上下文无关文法
上下文无关文法(ContextFree Grammar，CFG)是一种形式化地描述程序设计语言语法规则的数学抽象，上下文无关文法G是一个四元组

G=(T,N,P,S)

其中：
(1) T 是终结符集合，终结符是组成句子的基本符号，在语法分析中，终结符一般可理解为词法记号。
(2) N是非终结符集合，非终结符用于定义由文法生成的语言，给出了语言的层次结构。
(3) P是一组产生式规则，产生式规则描述了将终结符和非终结符组合成串的方法。每条产生式规则都具有以下类似的语法形式

X→β1β2…βn

其中X∈N且βi∈(T∪N∪{})，1≤i≤n。
(4) S∈N是唯一的开始符号，按照惯例，P中首先列出开始符号S的产生式。
下文对文法符号的表示一般使用以下约定： 非终结符一般用大写字母表示； 终结符一般用小写字母或数字表示。例如，下述符号是终结符。
(1) 小写字母： 如 a、b、c 等。
(2) 运算符号： 如+、-、、/等。
(3) 数字： 如 0，1，…，9。
(4) 分隔符： 如标点符号或括号等。
一般用希腊字母 α、β、γ  等表示一个符号既有可能是非终结符，也有可能是终结符。接下来，在不引起混淆的情况下，把上下文无关文法简称为文法。
下面文法给出了表达式的语法


E→E+T|E-T|T

T→TF|T/F|F

F→(E)|id


其中，非终结符 N={E,T,F }。E是开始符号； 终结符T={+,-,,/,(,),id}； 产生式规则一共3条。
3.2.2推导
推导(derivation)是一系列重写步骤，从语法的开始符号开始，结束于语言中的一个语句。对于给定文法 G=(T,N,P,S)，推导从G的开始符号S开始，用产生式P的右部替换左侧的非终结符，不断重复，直到串不出现非终结符为止，最终的串称为句子。
在推导过程中，根据选择被替换非终结符的方式的不同，可以将推导分为最左推导(leftmost derivation)和最右推导(rightmost derivation)。最左推导总是选择产生式右侧最左边的非终结符进行替换，最右推导总是选择最右边的非终结符替换。
例如，给定文法

E→E+E|EE|-E|(E)|id

对于句子-(id+id) 存在最左推导


E-E

-(E)

-(E+E)

-(id+E)

-(id+id)


和最右推导

E-E

-(E)

-(E+E)

-(E+id)

-(id+id)

3.2.3分析树
分析树(parse tree)是对推导的树状表示，它和推导所用的顺序无关。分析树的每个内部节点代表非终结符，每个叶节点代表终结符，每一步推导代表如何从双亲节点生成它的直接孩子节点。语法分析根据给定的文法规则，对输入的字符串产生分析树，如果字符串中的各个部分能够从左至右地排在语法分析树的叶节点上，那么输入的字符串就是该文法定义的语言的一个句子，否则就不是。
给定文法G，如果存在某个句子s，它有两棵或多棵不同的分析树，则称文法G是二义性文法。这意味着二义性文法就是对同一个句子有多个最左推导或最右推导。例如，给定文法

E→E+E|EE|-E|id

句子id+idid具有两个不同的最左推导： 


EE+E

id+E

id+EE

id+idE

id+idid


和


EEE

E+EE

id+EE

id+idE

id+idid

这两个推导对应的分析树如图38所示。


图38id+idid的两棵语法树


一个二义性的文法可以生成多个推导以及多个分析树。由于后续阶段会将语义关联到分析树的细节，所以存在多个分析树就意味着同一程序有多种可能的语义。从编译器的角度看，二义性文法将导致同一个程序有不同的含义，从而使程序运行的结果不唯一，故编译器设计者需要通过文法的重写解决二义性问题。
基于文法和推导的概念，语法分析器的任务就是对于给定的文法G和句子s，判断是否存在对句子s的推导，如果存在，语法分析器将根据推导的过程构建分析树； 如果不存在，语法分析器将返回语法错误信息。
3.2.4自顶向下分析
自顶向下分析就是从文法G的开始符号S出发，不断地挑选合适的产生式对非终结符进行替换，最终展开到给定的句子。从构造分析树的角度看，语法分析器是从分析树的根节点开始，系统化地向下扩展分析树，直到分析树的叶节点与词法分析器返回的记号流相匹配。在分析的过程中，编译器从分析树的下边缘选择一个非终结符，并选择一个以该非终结符为左部的产生式，用该产生式右侧相对应的子树来扩展该节点，如果推出的句子中的终结符与输入匹配，则可继续进行分析； 如果不匹配，则需要回溯，尝试下一个产生式。这个过程一直持续到分析树的下边缘只包含终结符，且输入记号流耗尽为止。
基于最左推导的自顶向下语法分析由算法3给出。算法接受文法G=(T,N,P,S)和记号流 tokens 作为输入参数，并返回语法分析的结果。算法使用变量i指向记号流tokens中下一个将要匹配的记号，栈stack中存放所有终结符和非终结符的序列。算法的主体是一个while循环，当栈顶元素是一个终结符时，将它与当前将要进行匹配的tokens［i］比较，如果二者相等，则将该终结符弹出栈； 如果二者不相等则需要进行回溯。如果栈顶元素是一个非终结符T，则编译器将T弹出栈，并将该非终结符T的下一个没有匹配过的右部逆序压入栈。这个循环过程一直进行到栈stack空为止。






算法3基于最左推导的自顶向下分析


输入： 文法 G=(T,N,P,S)和记号流 tokens

输出： 语法分析的结果

1. procedure TopDownAnalysis(T, N, P, S, tokens)

2. i = 0

3. top = 0

4. stack = ［S］

5. while stack ≠ ［］ do

6. if stack［top］ 是一个终结符 t then

7. if (t == tokens［i++］) then

8. pop()

9. else

10.backtrack()

11.else // stack［top］ 是非终结符 T

12.pop()

13.push(β) // β 是 T 的下一个没有匹配过的右部


在上述算法的最后一步中，算法所选择的非终结符 T 的下一个没有匹配过的右部可能是错的，此时算法无法完成对输入的匹配，所以需要用到回溯。但在实际应用中，编译器编译大型程序时，如果反复进行回溯会大大影响编译器的效率，因此需要避免回溯来实现线性时间的分析算法。接下来将讨论对这个基本算法的改进： 递归下降分析算法和 LL(1) 分析算法。
1. 递归下降分析
递归下降分析(recursive decedent analysis)算法也称为预测分析(predicative analysis)算法，该算法为文法中的每个非终结符构造一个分析函数。非终结符A的分析函数可以识别输入流中A的一个实例。为了识别A的某个产生式右侧的非终结符B，语法分析器递归调用B的分析函数。因此，递归下降语法分析器在结构上呈现为一组相互递归的过程。
为了举例说明这种算法，将为下面的文法构建一个递归下降分析器：


S→if E then S else S|begin S L|print E

L→end|; S L

E→num=num


递归下降语法分析器为非终结符S、L和E分别构造一个分析函数，非终结符的每个产生式对应分析函数中的一个子句。


1． enum token{

2．IF,THEN,ELSE,BEGIN,END,PRINT,SEMI,NUM,EQ

3． };

4． extern enum token getToken(void);

5． enum token tok;

6．

7． void advance(){

8．tok = getToken();

9． }

10．

11． void eat(enum token t){

12．if(tok == t)

13．advance();

14．else error();

15． }

16．

17． void S(){

18．switch(tok){

19．case IF: eat(IF); E(); eat(THEN); S();

20．eat(ELSE); S(); break;

21．case BEGIN: eat(BEGIN); S(); L(); break;

22．case PRINT: eat(PRINT); E(); break;

23．default: error();

24．}

25． }

26．

27． void L(){

28．switch(tok){

29．case END: eat(END); break;

30．case SEMI: eat(SEMI); S(); L(); break;

31．default: error();

32．}

33． }

34．

35． void E(){

36．eat(NUM); eat(EQ); eat(NUM);

37． }


分析函数中调用了词法分析器的接口getToken()来从输入流中读取下一个记号。递归下降分析器构建了分析函数S()、L()和E()分别分析非终结符S、L和E。递归下降语法分析器的优点在于算法实现简单，有利于手工构造。
但递归下降分析算法对文法提出了苛刻的要求，即同一个非终结符的右侧产生式之间不能包括同样的非终结符。例如，如果要为如下文法构建一个递归下降语法分析器： 


S→E

E→E+T|E-T|T

T→TF|T/F|F 

F→id|num|(E)

则在构建以下分析函数E()时：


1． void E(){

2．switch(tok){

3．case ?: E(); eat(PLUS); T(); break;

4．case ?: E(); eat(MINUS); T(); break;

5．case ?: T(); break;

6．default: error();

7．}

8． }


遇到了一个困境： 假设当前的记号是整型数字(例如 33)，则函数E()不知道该使用哪个子句来进行递归，因为函数E()和T()都能接受整型数字。
因此，递归下降语法分析只适合这样的文法： 每个子表达式的第一个终结符号都能够为产生式的选择提供足够信息。为此，需要形式化 FIRST集合的概念，然后给出一个能自动构建语法分析器的算法。
2. LL(1)分析算法
在一个递归下降分析器中，非终结符X的分析函数X()对X的每个产生式都有一个子句，因此，该函数必须根据下一个输入符号 T 来选择其中的一个子句。如果能够为每一个(X，T) 的二元组都选出正确的产生式，就能够写出一个无冲突的递归下降分析器。因此，编译器可以将需要的所有信息，用一张关于产生式的二维表来记录，此表以文法的非终结符X和终结符T作为索引，称为预测分析表(predictive parsing table)。采用这张表的分析算法称为LL(1)分析算法，其中第一个L表示从左向右读入被分析的源程序，第二个L表示产生最左推导，(1)表示编译器需要向前看1个终结符号来辅助进行决策。

1) 架构
LL(1)分析算法是基于表驱动的算法，其架构如图39所示。语法分析器自动生成器读入语法，然后生成一张分析表。语法分析器工作时通过查询分析表来决定将要进行的动作。有了分析表的指导，LL(1)分析算法就可以避免回溯。


图39基于表驱动的 LL(1)分析算法架构


为了构造预测分析表，需要先讨论 FIRST 集合和 FOLLOW 集合。
2) FIRST 集合和 FOLLOW集合
给定一个由终结符和非终结符组成的字符串γ，FIRST(γ)是由可以从γ推导出的句子开头的所有可能终结符组成的集合。例如，在上面的文法中，令γ=TF，则任何可从γ推导出的由终结符组成的句子，都必定以id、num或(开始，因此，有：

FIRST(TF)={id，num，(}


FIRST集合的计算初看并不复杂，若γ=XYZ，则似乎可以忽略Y和Z，只需计算FIRST(X)。但是考虑下面的文法就可以看出情况并非如此： 


X→Y|a

Y→|c

Z→XYZ|d


因为Y可能产生空串，所以X也可能产生空串，于是可以推出FIRST(XYZ)一定包含FIRST(Z)。因此，在计算FIRST集合时，必须跟踪能产生空串的符号，这种符号称为可空(nullable)符号。同时，还必须跟踪有可能跟随在可空符号之后的其他符号。
对于一个特定的文法，当给定由终结符和非终结符组成的字符串 γ 时，下述结论成立： 
(1) 如果X可以导出空串，则nullable(X)为真。
(2) FIRST(γ)是可从γ推导出的句子开头的所有可能终结符的集合。
(3) FOLLOW(X)是可直接跟随于X之后的终结符集合。如果存在着任一推导包含Xt，则 t∈ FOLLOW(X)，当推导包含XYZt，其中Y和Z都能推导出时，也有t∈FOLLOW(X)。
FIRST、FOLLOW和nullable可定义为满足如下属性的最小集合： 


对于每个终结符 Z，FIRST ［Z］=  Z

for每个产生式 X → Y1Y2... Yk

for每个 i 从1到 k，每个j从 i+1 到 k

if所有 Yi 都是可为空的

then nullable［X］=true

if Y1... Yi-1 都是可为空的

then FIRST ［X］=FIRST ［X］ ∪ FIRST ［Yi］

if  Yi+1... Yk 都是可为空的

then FOLLOW ［Yi］=FOLLOW ［Yi］∪FOLLOW ［X］

if Yi+1... Yj-1 都是可为空的

then FOLLOW ［Yi］=FOLLOW ［Yi］∪FIRST ［Yj］


计算FIRST、FOLLOW和nullable的算法遵循的正是上述步骤，因此只需要简单地用一个赋值语句替代每一个方程，并一直迭代到不动点，就可以计算出每个串的FIRST、FOLLOW和nullable，这个迭代过程由算法4给出。算法接受文法G=(T,N,P,S)作为输入，计算该文法的FIRST、FOLLOW和nullable。从实现的角度看，这三个集合不必同时计算，可先计算nullable，然后计算FIRST，最后计算FOLLOW。这样做可以加快算法的执行速度。







算法4FIRST、FOLLOW和nullable的迭代计算


输入： 文法 G=(T,N,P,S)

输出： FIRST、FOLLOW 和 nullable

1.  procedure FirstFollow(T, N, P, S)

2. 将所有的 FIRST 和 FOLLOW 初始化为空集合，将所有的 nullable 都初始化为 false

3. for 每一个终结符 Z do

4.FIRST［Z］={Z}

5. repeat

6.for每个产生式 X → Y1Y2 ... Yk do

7.for每个i从1到k，每个j从i+1到k do

8.if所有Yi都是可为空的then

9.nullable［X］=true;

10. if Y1 ... Yi-1  都是可为空的then  

11. FIRST［X］=FIRST［X］ ∪ FIRST ［Yi］;

12. if Yi+1 ... Yk都是可为空的  then

13. FOLLOW ［Yi］=FOLLOW ［Yi］ ∪ FOLLOW ［X］;

14. if  Yi+1 ... Yj-1都是可为空的then

15. FOLLOW ［Yi］=FOLLOW ［Yi］ ∪ FOLLOW ［Yj］;

16.until FIRST、FOLLOW 和nullable在此轮迭代中没有改变




图310用于表达式的示例文法

将这一算法用于图310中给出的文法，首先计算这6个非终结符是否可为空，可以得到

nullable(E′)=nullable(T′)=true

即 E′ 和 T′ 是可为空的。接着将这个结果代入算法迭代计算6个非终结符的 FIRST 和 FOLLOW 集合，算法运行结束时，得到最终结果如表34所示。


表34nullable、FIRST和FOLLOW的计算结果



非 终 结 符nullableFIRSTFOLLOW

Sno(id num
Eno(id num)$
E′yes+-)$
Tno(id num)+-$
T′yes*/)+-$
Fno(id num)*/+-$

可进一步将 FIRST 集合推广到符号串Xγ上： 

FIRST(Xγ)=FIRST［X］,nullable［X］=no

FIRSTX∪FIRSTγ,nullable［X］=yes


并且，如果γ 中的每个符号都是可为空的，则符号串 γ 可为空。
利用FIRST集合和FOLLOW集合，可以构造预测分析表： 对每个T∈FIRST(γ)，在表的第X行第T列，填入产生式X→γ。此外，如果γ是可为空的，则对每个T∈FOLLOW(X)，在表的第X行第T列，也填入该产生式X→γ。
表35给出了图310中文法的预测分析表，其中省略了num、/和-等终结符对应的列，它们和表中的其他项类似。对于一个给定的文法G=(T,N,P,S)，我们可以使用工具自动构造出其预测分析表，这类工具被统称为语法分析器自动生成器。
根据预测分析表，可给出语法分析的LL(1)算法，如算法5所示。该算法接受文法G=(T,N,P,S)和记号流tokens作为输入，输出对tokens的分析结果。算法在分析过程中，需要根据分析表来决定产生式的选择(第13行)，因此避免了回溯的问题。


表35文法的预测分析表



非终结符+*id()$

SS→E$S→E$
EE→TE′E→TE′
E′E′→+TE′E′→E′→
TT→FT′T→FT′
T′ T′→T′→FT′T′→T′→
FF→idF→(E)






算法5LL(1)分析算法


输入： 文法G=(T,N,P,S)和记号流 tokens

输出： 对 tokens 的语法分析结果

1. procedure LL1(T, N, P, S, tokens)

2. i = 0

3. top = 0

4. stack = ［S］

5. while stack != ［］  do

6. if stack［top］ 是一个终结符 t  then

7. if t == tokens［i ++］  then

8. pop()

9. else

10. error() 

11. else // stack［top］ 是非终结符 T

12. pop()

13. push(table［T, tokens［i］］)


3.2.5自底向上分析
一个自底向上的语法分析过程对应于为输入串构造语法分析树的过程，它从叶子节点(底部)开始构造，逐渐向上到达根节点(顶部)。可以将自底向上语法分析过程看成将一个串归约(Reduction)为文法开始符号S的过程。在每个规约步骤中，一个与某产生式 X→β 右部相匹配的特定子串 β，被替换为该产生式左侧的非终结符 X。

目前最重要的一类自底向上语法分析是 LR(k) 语法分析，其中符号 L 表示对输入进行从左到右的扫描，


图311直线式程序的语法


符号 R 表示构造一个最右推导序列，而符号(k)表示在进行语法分析决定时向前看k个输入符号。当LR（k）分析看到的输入记号（多于k个单词），与正在考虑的产生式的整个右部对应时，LR（k）分析才确定使用哪一个产生式。
表36举例说明了用图311给出的文法，对程序


a = 7;

b = c + (d = 5 + 6, d)



进行LR分析的过程。

该分析器有一个栈和一个输入，输入中的前k个记号为向前查看的记号。根据栈的内容和向前查看的记号，分析器执行移进和归约两种动作。
(1) 移进： 将第一个输入记号压入至栈顶。
(2) 归约： 选择一个产生式 X→ABC，依次从栈顶弹出C、B、A，然后将 X 压入栈。
开始时栈为空，分析器位于输入的开始。移进文件终结符$的动作称为接受(Accepting)，它表示分析过程成功结束。
表36列出了在每一个动作之后的栈和输入，也指明了所执行的动作，其中栈列的数字下标是 DFA 的状态编号。将栈和输入合并起来形成的一行总是构成一个最右推导。事实上，表36自下而上地给出了对输入字符串的最右推导过程。


表36一个句子的移进归约分析



栈待分析字符串输 入 动 作

1a=7;b=c+(d=5+6,d)$移进
1id4=7;b=c+(d=5+6,d)$移进
1id4=67;b=c+(d=5+6,d)$移进
1id4=6num10;b=c+(d=5+6,d)$归约 E→num
1id4=6E11;b=c+(d=5+6,d)$归约S→id=E
1S2;b=c+(d=5+6,d)$移进
1S2;3b=c+(d=5+6,d)$移进
1S2 ;3 id4=c+(d=5+6,d)$移进

1S2 ;3 id4=6c+(d=5+6,d)$移进
1S2;3 id4=6 id20+(d=5+6,d)$归约 E→id
1S2 ;3 id4=6E11+(d=5+6,d)$移进
1S2 ;3 id 4=6E11+16(d=5+6,d)$移进

1S2 ;3 id4=6E11+16( 8d=5+6,d)
$移进


续表




栈待分析字符串输 入 动 作

1S2 ;3 id4=6E11+16( 8id 4=5+6,d)
$移进
1S2 ;3id4=6E11+16( 8id4=6
5+6,d)$移进
1S2 ;3 id4=6E11+16(8 id4=6num10+6,d)$归约E→num
1S2 ;3id4=6E11+16(8id4=6E11+6,d)$移进
1S2 ;3id4=6E11+16(8id4=6E11+166,d)$移进
1S2 ;3id4=6E11+16(8id4=6E11+16 num 10,d)$归约 E→num
1S2 ;3 id4=6E11+16(8id4=6E11+16E17,d)$归约 E→E+E
1S2 ;3 id4=6E11+16(8id4=6E11
,d)$归约S→id=E
1S2 ;3 id4=6E11+16(8S12,d)
$移进
1S2 ;3id 4=6E11+16(8S12,18d)$移进
1S2 ;3 id4=6E11+16(8S12,18 id 20)$归约 E→id
1S2 ;3 id4=6E11+16(8S12,18E21)$移进
1S2 ;3 id4=6E11+16(8S12,18E21)22$归约 E→(S,E)
1S2 ;3 id 4=6E11+16E17
$归约 E→E+E
1S2 ;3 id4=6E11$归约 S→id=E
1S2 ;3S5$归约 S→S;S
1S2$接受

1. LR 分析
LR分析器通过确定的有限状态自动机来判断何时移进、何时归约。这种 DFA 不是作用于输入，而是作用于栈。DFA 的边用可以出现在栈中的符号(终结符和非终结符)来标记。表37是图311给出的文法的转换表。
这个转换表中的元素标有下面4种类型的动作。
(1) sn： 移进到状态 n。
(2) gn： 转换到状态 n。
(3) rk： 用规则k规约。
(4) acc： 接受。
(5) error： (用表中的空项来表示)。
为了使用该表进行分析，要将移进和转换动作看成是 DFA 边，并查看栈的内容。例如，若栈为 id=E，则 DFA 将从状态1依次转换到 4、6 和 11。若下一个输入记号是一个分号，例如状态11的“;”所在列则指出将根据规则2进行归约，因为文法的第二个规则是 S→id=E，于是栈顶的 3 个记号被弹出，同时S被压入栈顶。
在状态11中对于+的动作是移进，因此，如果下一个记号是+，它将从输入中被移出并压入栈中。对于每一个输入，分析器不是重新扫描栈，而是记住每一个栈元素所到达的状态。因此，分析算法通过查看栈顶状态和输入符号，从而得到对应的动作。对应的动作如下。


表37LR分析表



状态idnumprint;.+=()$SEL

1s4s7






g2


2



s3





a



3
s4

s7







g5


4






s6






5



r1
r1




r1

6
s20
s10





s8



g11
7







s9
8
s4

s7







g12

9











g15
g14
10



r5
r5
r5


r5
r5

11



r2
r2
s16



r2
12



s3
s18
13



r3
r3




r3
14




s19



s13
15




r8



r8

16
s20
s10





s8



g17

17



r6
r6
s16


r6
r6

18
s20
s10





s8



g21

19
s20
s10





s8



g23

20



r4
r4
r4


r4
r4

21








s22

22



r7
r7
r7


r7
r7

23




r9
s16


r9



(1) 移进(n)： 将n压入栈，并继续处理下一个输入记号。
(2) 归约(k)： 从栈顶依次弹出符号，弹出符号的个数与规则k的右部符号个数相同。令X是规则k的左部符号，在栈顶现在所处的状态下，查看X得到动作“转换到n”，则将n压入栈顶。
(3) 接受： 停止分析，报告成功。
(4) 错误： 停止分析，报告失败。
2. LR(0)分析算法
LR(k)分析器利用栈中的内容和输入中的前k个记号来确定下一步采取什么动作。表37说明了使用一个前看符号的情况，而当k=2时，这个表的每一列是由两个输入记号组成的序列，以此类推。在实际中，编译器很少需要使用k>1的表，一方面是因为这个表需要的存储空间非常大，另一方面是因为程序设计语言的文法都可以用LR(1)文法来描述。

LR(0)文法是LR(k)文法中最简单的一类，它只需查看分析栈就可完成分析，不必使用前看符号来决定进行移进还是归约。以图312中的文法为例来说明LR(0)分析器的生成过程。一开始，分析器的栈为空，输入是满足S的完整句子并以$结束，即规则S′→S$的右部都将出现在输入中。用一种扩展的产生式

S′→·S$

来记录这一事实，其中产生式中的圆点·指出了分析器的当前位置。文法规则与指出其右部位置的圆点组合在一起称为项目(item)，由于正在讨论LR(0)分析，因此也被称为LR(0)项目。

在这个状态下，输入以S开始意味着它可能以产生式S的任何一个右部开始。用图313中的项目组成的集合来表示这种状态，其中1是项目集的编号。该项目集包括 3 条项目。

1) 移进动作
在状态 1，考虑当编译器移进(shift)一个终结符x的状态。此时栈顶为x，并且项目S→·x中的圆点将移到x之后。规则 S′→·S$和S→·(L)与这个动作无关，因此忽略它们。于是得到状态2，如图314所示。


图312满足LR(0)的示例文法




图313状态1





图314移进x到状态 2



或者在状态1也可考虑移进一个左括号“(”，将圆点“·”移到左括号的右边，得到项目S→(·L)。此时栈顶一定为左括号“(”，并且输入中开头的应当是可从 L 推导出来的某个输入记号串，且其后跟随一个右括号“)”。通过将L的所有产生式都包含在项目集合中，可以确定什么样的记号可以作为输入中的开头记号。但是，在这些L的项目中，有一个项目的圆点“·”正好位于非终结符S之前，因此还需要包含所有S的产生式，最终得到的项目集合如图315所示。
2) 转换动作
如果在状态1已经分析过由非终结符S导出的记号串，则可以通过将状态1的第一个项目中的圆点“·”移到S之后来模拟这种情况，从而得到状态4，如图316所示。这种情况发生在移进一个x求左括号，并随之用一个S产生式执行了规约时，然后该产生式的所有右部符号都将被弹出，并且分析器将在状态1对S执行转换（goto）动作。


图315移进左括号到状态3



图316在状态1对S执行转换动作



3) 归约动作
在状态2可以发现圆点“·”位于一个项的末尾，这意味着栈顶一定对应着产生式S→x完整的右部，并准备进行归约(Reduce)。在这种状态下，分析器可能会执行一个归约动作。
LR（0）分析算法中的两个基本操作是Closure(I) 和 Goto(I,X)，其中I是一个项目集合，X是一个文法符号(非终结符N或终结符T)。当一个非终结符X的左侧有圆点时，函数Closure将更多的项目添加到项集合中； 而函数Goto将圆点移到所有项目中的符号X之后。

算法6给出了计算Closure(I)和Goto(I,X)集合的算法。计算项目集 I 的Closure(I)，首先将 I 状态中的核心项(除S′→·S$外)中，所有的·不在最左端的项加入； 然后对于每个项而言，如果有新的产生式，就把新的产生式加入进去。






算法6计算Closure(I)和Goto(I,X)


输入： 项目集合I，文法符号X

输出： I的闭包和I对于文法符号X的后继项目集合闭包


1. procedure Closure(I, X)

2. repeat

3. for I 中的任意项 A → α · X β do

4. for 任意产生式 X → γ do 

5. I = I ∪ {X → ·γ}

6. until I 没有改变

7. return I

8. procedure Goto(I, X)

9. 将 J 设为空集

10. for I 中的任意项 A → α · X β do

11. 将 A → αX · β加入 J 中

12. return Closure(J)


Goto(I,X)是项目集I对应于文法符号X的后继项目集闭包。首先将J初始化为空，然后对于项目集I中的每个项A→α·X β，将 A→αX·β加入集合J，最后计算Closure(J)。

算法7给出了LR(0)分析器的构造算法。算法给文法增加一个辅助的开始产生式S′→S$。令B是目前为止看到的状态集合，E 是目前为止已找到的(移进或转换)边集合。






算法7LR(0)分析


输入： 文法 G=(T,N,P,S)

输出： 文法的 LR(0) 分析器

1. procedure LR0(G = (T, N, P, S))

2. B = {Closure(S' →·S$)}

3. E = 

4. repeat

5. for B中的每个状态 I do

6.  for I 中的每一项 A → α·X β do

7. J = Goto(I, X)

8. B = B ∪ {J}

9. E = E ∪{I XJ}

10.until E 和 B 在本轮迭代中没有改变

11.return I



但是对于符号$，不计算 Goto(I,$)，而是选择了接受动作。图317以图312的文法为例说明了该分析器的分析过程。



图317图312文法的LR(0)状态



现在可以通过算法8来计算 LR(0) 的归约动作集合 R，并且能够为该文法构造一个分析表(表38)。对于每一条边I XJ，若 X 为终结符，则在表位置(I,X)中放置动作移进J(sJ)； 若 X 为非终结符，则将转换J(gJ) 放在位置(I,X) 中。对于包含项S′→S·$的每个状态I，在位置(I,$) 中放置动作接受(a)。对于包含项A→γ·(尾部有圆点的产生式 n)的状态，对每一个记号Y，放置动作归约n(rn)于(I,Y)中。





算法8计算归约动作集合


输入： 目前为止看到的状态集合 B

输出： 规约动作集合 R

1. procedure reduceset(B)

2. R = {}

3. for B 中的每个状态 I do

4. for I 中的每个项A →α·∈ I do

5. R = R ∪ {(I, A → α)}




表38图312文法的LR(0)分析表



状态()x,$SL

1s3s2g4
2r2r2r2r2r2
3s3s2g7g5
4a
5s6s8
6r1r1r1r1r1
7r3r3r3r3r3
8s3s2g9
9r4r4r4r4r4


因为LR(0)不需要向前查看，所以原则上每个状态只需要一个动作： 要么移进，要么归约，但不会两者兼有。在实际应用中，由于还需要知道要移进至哪个状态，所以表38以状态号作为行，以文法符号作为列。
3. SLR分析算法
尝试构造如图318所示文法的LR(0)分析表，它的LR(0)状态如图319所示。


图318表达式的示例文法




图319图318所示文法的 SLR 分析表




在状态3，对于符号+，有一个多重定义的项： 分析器必须移进到状态4，同时又必须用产生式2进行归约。这是一个冲突，它表明该文法不是LR(0)的，因为它不能用LR(0)分析器分析，因此需要一种能力更强的分析算法。
比LR(0)更好的一种简单的分析器为SLR，即Simple LR的简称。SLR分析器的构造几乎与LR(0)相同，区别是只在FOLLOW集合指定的地方放置归约动作。
算法9是在 SLR 表中放置归约动作的算法。





算法9计算归约动作集合


输入： 目前为止看到的状态集合 T

输出： 规约动作集合 R

1. procedure reduceset

2. R = {}

3. for T 中的每个状态 I do

4. for I 中的每个项 A → α·do

5. for FOLLOW (A)中的每个记号 X do

6. R = R ∪ {(I, X, A → α)}


动作(I,X,A→α)指出，在状态I，对于前看符号X，分析器将用规则A→α进行归约。
因此，对于图318所示文法，尽管使用相同的状态图(图319)，但如表39所示，在SLR表中放置的归约动作要少些。
SLR文法类是其 SLR 分析表不含冲突(多重表项)的那些文法。图318所示文法即属于这一类，很多常用的程序设计语言的文法也属于这一类。


表39图318所示文法的SLR分析表



状态x+$ET
1s5g2g3
2a
3s4r2
4s5g6g3
5r3r3
6r1


4. LR(1) 分析算法
比SLR更强大的是LR(1)分析算法。大多数用上下文无关文法描述其语法的程序设计语言含有一个LR(1)文法。构造LR(1)分析表的算法与构造LR(0)分析表的算法相似，只是项的概念要复杂一些。
一个LR(1)项由一个文法产生式、一个右部位置(用圆点表示)和一个前看符号组成。项(A→α·β,x)指出： 序列 α在栈顶，且输入中开头的是可以从βx导出的符号串。
LR(1)状态是由LR(1)的项组成的集合，并且存在着合并该前看符号的LR(1)的Closure和Goto操作。算法10给出了计算Closure(I)和Goto(I,X)集合的算法。






算法10计算Closure(I)和Goto(I,X)


输入： 项目集合I，前看符号 z

输出： I的闭包和后继项目集合闭包

1. procedure Closure(T)

2.  repeat

3. for I 中的任意项 (A → α · Xβ, z) do

4. for 任意产生式 X → γ  do

5. for 任意 ω ∈ FIRST (βz)  do

6. I = I ∪ {(X → · γ, ω)}

7. until I 没有改变

8. return I

9. procedure Goto(I, X)

10. J = {}

11. for I 中的任意项 (A → α · Xβ, z) do

12. 将 (A → αX · β, z) 加入 J 中

13. return Closure(J)


开始状态是项 (S′→·S$,?) 的闭包，其中前看符号?具体是什么不重要，因为文件结束标志绝对不会被移进。
对于Closure(I)的计算，对I中的任意项(A→α·Xβ,z)，任意产生式X→γ，如果ω属于FIRST(βz)，则将(X→· γ,ω)加入I，直到I中的项不再发生变化。
对于Goto(I,X)的计算，首先将J初始化为空，然后对于项目集I中的每个项(A→α·Xβ,z)，将(A→αX·β,z)加入集合J，最后计算Closure(J)。
归约动作用算法11来选择。动作(I,z,A→α)指出，在状态I看到前看符号z时，分析器将用规则A→α进行归约。








算法11计算归约动作集


输入： 目前为止看到的状态集合 T，前看符号 z

输出： 规约动作集合 R

1. procedure reduceset(T , z)

2. R={}

3. for T 中的每个状态 I do

4. for I 中的每个项 (A → α·, z) do

5. R = R ∪ {(I, z, A → α)}


图320所示文法不是 SLR，但它属于 LR(1) 文法，图321 给出了该文法的 LR(1) 状态。图320所示文法中有几个项有相同的产生式，但其前看符号不同(如左图所示)，可以将它们简化为右图所示。


图320一个描述C语言中的表达式、变量和指针访问运算(*)的文法




图321图320所示文法的LR(1)状态


图320所示文法的LR(1)状态表（表310(a)）是从图321 导出的 LR(1) 分析表。只要在产生式的末尾有圆点，在LR(1)表中与状态号对应的行和与项的前看符号对应的列的位置，就存在着那个产生式的一个归约动作(在这个例子中，前看符号是$)。只要圆点位于终结符或非终结符的左边，在LR(1)分析表中就存在相应的移进或转换动作。


表310图320所示文法的LR(1)分析表和LALR(1)分析表



状态x
*
=
$
S
E
V
状态
x
*
=
$
S
E
V
1
s8
s6


g2
g5
g3
1
s8
s6


g2
g5
g3

2



a



2



a

3


s4
r3



3


s4
r3

4
s11
s13



g9
g7
4
s8
s6



g9
g7

5



r2



5



r2

6
s8
s6



g10
g12
6
s8
s6



g10
g7
7



r3



7


r3
r3

8


r4
r4



8


r4
r4

9



r1



9



r1
10


r5
r5



10


r5
r5

11



r4











12


r3
r3
13
s11
s13



g14
g7
14



r5

(a) LR(1)(b) LALR(1)


5. LALR(1)分析算法
LR(1)分析表有很多状态，因此非常大，但是通过合并除前看符号集合外其余部分都相同的两个状态，可得到一个较小的表。由此得到的分析器称为LALR(1)分析器，即前看LR(1)(LookAhead LR(1))。
例如，在图320所示文法的LR(1)状态(图321)中，如果忽略前看符号集合，状态6和状态13的项是相同的。状态7和状态12，状态8和状态11以及状态10和状态14也都如此。合并这些状态对，就得到表310(b)所示的LALR(1)分析表。
对于某些文法，LALR(1)表含有归约归约冲突，而在LR(1)表中却没有这种冲突。不过，实际中这种可能性很小，重要的是和LR(1)表相比，LALR(1)分析表的状态要少得多，因此它需要的存储空间要少于LR(1)表。


3.3语义分析




语法正确的输入程序仍然可能包含其他错误，导致编译无法完成。为了检测这样的错误，编译器就需要进行更深层的语义分析(semantic analysis)。语义分析需要将程序结构放到实际的上下文中进行检查，发现类型等方面的错误。语义分析根据源语言的语义规则，对语法分析阶段生成的抽象语法树的属性进行上下文相关检查； 如果检查出错，则返回错误信息给程序员，供程序员修改代码； 如果检查通过，编译器生成一个中间表示供编译的后续阶段使用。本节首先讨论抽象语法树的定义和生成技术，然后介绍在抽象语法树上进行语义分析的主要技术。
3.3.1抽象语法树
语法分析树(parse tree)编码了句子的推导过程，每个输入记号对应着语法分析树中的一个叶子节点，分析期间被归约的每一个语法规则都对应着树中的一个内部节点。例如，算术表达式15(3+4)对应的一棵语法分析树如图322所示。
语法分析树包含了很多不必要的信息，这些节点会占用额外的存储空间。此外，语法分析树的结构高度依赖文法细节，而各种文法转换又会引入新的非终结符和产生式，这些细节本应被限制在语法分析阶段，不应该对语义分析造成困扰。
因此，在编译器设计中，通常要对语法分析树进一步抽象，去掉无关信息，形成更紧凑的内部表示——抽象语法树(Abstract Syntax Tree，AST)。抽象语法树保留了语法分析树的基本结构，表达式的优先级和语义仍保持原样，但剔除了其中非必要的节点。对于同样的算术表达式15(3+4)，其抽象语法树如图323所示。


图32215(3+4)对应的语法分析树





图32315(3+4)对应的抽象语法树



抽象语法(abstract syntax)是编译器用来表达程序语法结构的内部数据结构表示，现代编译器一般都采用抽象语法作为编译器前端(语法分析和词法分析)和后端的接口。语义分析阶段使用程序的抽象语法树分析程序中存在的语义错误。
在编译器中，为了定义抽象语法树，需要使用实现语言来定义一组数据结构。例如，对于如下的文法(做了适当抽象，略去了文法中不重要的分隔符等)：


E→n|id|E+E|EE

S→id=E|if (E,S,S)|while (E,S)|return E
可以定义如下数据结构(类C语言描述)来编码该文法：


1． enum E_kind {E_INT, E_ID, E_ADD, E_TIMES};

2． struct Exp{

3． enum E_kind kind;

4． };

5． struct Exp_Int{

6． enum E_kind kind;

7． int n;

8． };

9． struct Exp_Id{

10． enum E_kind kind;

11． char *id;

12． };

13． struct Exp_Add{

14． enum E_kind kind;

15． struct Exp *left;

16． struct Exp *right;

17． };

18． struct Exp_Times{

19． enum E_kind kind;

20． struct Exp *left;

21． struct Exp *right;

22． };


首先定义一个枚举类型E_kind，它包括四个不同的枚举类型的值，分别表示表达式的四种情况。再定义一个结构体Exp来编码表达式产生式左部的非终结符E，该结构体中只有一个kind字段。接下来，为非终结符 E 的每个右部都定义一个结构体，例如，用Exp_Int 来编码产生式的第一个右部，即整型立即数表达式，该结构体的第一个域kind表示表达式的类型，第二个域n记录了这个整型数具体的值； 用结构体Exp_Add来表示加法表达式，其中第一个域 kind 表示表达式的类型，第二个域left和第三个域right表示加法运算的两个表达式操作数，这两个操作数的类型都是指向结构体Exp的指针。
对于语句S，可以类似地定义抽象语法树的数据结构： 


1．  enum S_kind {S_ASSIGN, S_IF, S_WHILE, S_RETURN};

2．  struct Stm{

3． enum S_kind kind;

4．  };

5． struct Stm_Assign{

6． enum S_kind kind;

7． char *id;

8． struct Exp *exp;

9． };

10． struct Stm_If{

11． enum S_kind kind;

12． struct Exp *exp;

13． struct Stm *thenn;

14． struct Stm *elsee;

15． };

16． struct Stm_While{

17． enum S_kind kind;

18． struct Exp *exp;

19． struct Stm *body;

20． };


这些数据结构的含义和表达式的类似，在此不再赘述。
编译器需要实现合理的内存分配接口，为这些数据结构分配合理的内存空间。下面给出了典型的分配接口的实现：


1． struct Exp_Int *Exp_Int_new(int n){

2． struct Exp_Int *p = malloc(sizeof(*p));

3． p->kind = E_INT;

4． p->n = n;

5． return p;

6． }

7． 

8． struct Exp_Add *Exp_Add_new(struct Exp *left, struct Exp *right){

9． struct Exp_Add *p = malloc(sizeof(*p));

10． p->kind = E_ADD;

11． p->left = left;

12． p->right = right;

13． return p;

14． }

15．

16． struct Stm_If *Stm_If_new(struct Exp *exp, struct Stm *thenn, struct Stm *elsee){

17． struct Stm_If *p = malloc(sizeof(*p));

18． p->kind = S_IF;

19． p->exp = exp;

20． p->thenn = thenn;

21． p->elsee = elsee;

22． return p;

23． }


这些数据结构分配接口的实现类似，都是先申请内存空间，再进行合理的初始化。实际的生产级的编译器还要考虑分配中的错误处理，以及内存的回收等更多实现细节。
有了这些表达抽象语法树的数据结构，编译器就可以在语法分析的过程中自动构建程序对应的抽象语法树。具体地，在递归下降语法分析器中，语义动作分散在实现语法分析的代码中； 而在 LR 语法分析器中，编译器可以在分析器的语法动作中，加入生成语法树的代码片段，来自动生成抽象语法树。
在递归下降语法分析器中，抽象语法树自动生成的部分代码如下：


1． struct Exp *parse_E(){

2． E t = parse_E_term();

3． while(cur_token == '+'){

4． eat('+');

5． E t1 = parse_E_term();

6． t = Exp_Add_new(t, t1);

7． }

8． return t;

9． }

10．

11． struct Stm *parse_S(){

12． switch(cur_token){

13． case ID:

14． String x = cur_token; //remember the identifier

15． eat('=');

16． struct Exp *e = parse_E();

17． S s = Stm_Assign_new(x, e);

18． return s;

19． case IF:

20． eat(IF);

21． eat('(');

22． struct Exp *e = parse_E();

23． eat (')');

24． eat(THEN);

25． struct Stm *thenn = parse_S();

26． eat(ELSE);

27． struct Stm *elsee = parse_S();

28． struct Stm *iff = Stm_If_new(e, thenn, elsee);

29． return iff;

30． }

31． } 


以对条件语句 if 的语法分析核心过程为例，首先编译器递归调用 parse_E 得到条件语句表达式的抽象语法树 e，然后再递归调用两次 parse_S得到条件语句两个分支 thenn 和 elsee 的抽象语法树，最后构建并返回整个语句的抽象语法树 iff。
编译器对抽象语法树的各种处理，如语义检查、中间代码生成等，本质上都是对抽象语法树的某种形式的遍历过程。后续章节将深入讨论语义检查和中间代码生成等问题，这里首先考虑输出抽象语法树，这个功能对于验证语法树构建的正确性非常重要。


1． void print_exp(struct Exp *e){

2． switch(e->kind){

3． case E_INT:

4． printf("%d", e->n);

5． return;

6． case E_ADD:

7． printf("(");

8． print_exp(e->left);

9． printf(")");

10． printf("+");

11． printf("(");

12． print_exp(e->right);

13． printf(")");

14． return;	

15． other cases: /* similar	*/

16． }	

17． }		

18．

19． void print_stm(struct Stm *s){

20． switch(s->kind){

21． case S_ASSIGN:

22．  printf("%s", s->id);

23．  printf("=");

24．  print_exp(s->exp);

25．  return;

26．  case S_IF:

27．  printf("if(");

28．  print_exp(e->left);

29．  printf(")");

30．  printf("then");

31．  print_stm(s->thenn);

32．  printf("else");

33．  print_stm(s->elsee);

34．  return;

35． other cases: /* similar */

36． }

37． }


函数 print_exp 和 print_stm 分别完成对表达式 E 和语句S的打印，它们的实现机制类似，都是基于对语法树具体形式的分类讨论，并进行必要的递归调用。
最后要注意，抽象语法树是编译器前端和后端重要的数据结构接口，程序一旦被转换为抽象语法树，则源代码可能会被丢弃，编译器后续阶段只处理抽象语法树。所以抽象语法树只有编码源代码足够多的信息，例如，它必须编码每个语法结构在源代码中的位置(文件名、行号、列号等)，后续的编译检查阶段才能获得精确的源代码信息。
3.3.2符号表
符号表(symbol table)是编译器用来保存有关源程序各种信息的重要数据结构。在分析阶段，编译器把源程序的信息逐步收集到符号表中。符号表的每个条目包含与一个标识符相关的所有必要信息，比如它的符号名、类型、存储位置、作用域和其他相关信息。符号表中的信息会在编译的后续不同阶段用到，在语义分析阶段，符号表的内容将用于语义检查和产生中间代码。在目标代码生成阶段，当对标识符进行地址分配时，符号表是地址分配的依据。
在整个编译期间，编译器对符号表的操作大致可归纳为以下5类。
(1) 创建符号表： 在编译开始时或进入一个子程序时进行。
(2) 插入表项： 在遇到新的标识符声明时进行。
(3) 查询表项： 在引用声明过的标识符时进行。
(4) 修改表项： 在获得新的语义值信息时进行。
(5) 删除表项： 删除一个或一组无用的项时进行。
根据操作的需求，可给出一个符号表实现的接口，它指明了编译器对符号表的典型需求：


type SymTable, K, V;

SymTable create();

void insert(SymTable, K, V); 

V lookup(SymTable, K);

void update(SymTable, K, V); 

void remove(SymTable, K);


类型SymTable、K和V分别代表符号表类型、关键字类型和值类型。接口中的 5 个函数分别完成符号表的创建、插入、查找、更新和删除操作。
由于被编译程序中标识符的规模可以非常大，且在编译器的各个阶段，每当遇到一个标识符都要查找符号表，因此编译器需要合理组织符号表，使符号表本身占据的存储空间尽量少，同时尽量提高编译期间对符号表的访问效率。
在编译器的实际构造过程中，编译器实现者需要仔细权衡时间开销、空间开销、所编译程序语言的特点等因素，来合理选择实现符号表的数据结构。如果提高对符号表的访问效率优先级更高，编译器可以使用哈希表作为符号表的具体实现。哈希表为查找操作提供了常数时间O(1)的访问能力。在使用哈希表时，必须合理地处理碰撞，还要仔细地处理装载因子，避免哈希表浪费过多空间。而如果节约空间的优先级更高，编译器也可以使用红黑树等平衡树数据结构，尽管此时查找操作的时间复杂度变为O(log N)，但避免了空间浪费。
很多程序设计语言中的变量都有变量作用域(scope)的概念，该变量仅在其作用域中是可见的。当编译器到达每一个作用域的开始时，需要把涉及的变量放入符号表； 而到作用域结束时，需要将此作用域中的变量移除。为了处理作用域，编译器可以在哈希表上进行适当地记录，进入作用域时插入元素，退出作用域时删除元素； 为了提高效率，编译器还可以采用由符号表构成的栈来处理作用域，进入作用域时插入新的符号表到栈顶，退出作用域时，删除栈顶符号表。
3.3.3语义检查
编译器语义检查阶段的任务首先是将变量的定义与它们的各个使用联系起来，以检查程序(抽象语法树)的上下文相关的属性。例如变量在使用前先进行声明、每个表达式都有合适的类型、函数调用与函数的定义一致等。然后，编译器将抽象语法树转换成更简单的、适合于生成机器代码的中间表示。语义分析又称为上下文相关分析或类型检查。
语义分析器的输入是语法分析阶段生成的抽象语法树和程序语言的语义规则，输出是一个中间表示。传统上，大部分的程序设计语言采用自然语言来表达程序语言的语义，所以编译器的实现者必须对语言中的语义规则有全面的理解。
下面的文法：


P→D S

D→T id ; D|

T→int|bool

S→id=E|printi(E)|printb(E)

E→n|id|true|false|E+E|E&&E


给定了一个包含变量声明的简单程序设计语言的片段。文法中的P表示程序，它由声明D和随后的语句S组成； 变量声明D本质上是一个列表，包含一串由类型和变量构成的二元组； 类型 T 包括整型类型 int 和布尔类型 bool 两种； 语句S包括3种语句形式，即赋值语句、对整型的输出语句printi 和对布尔型的输出语句printb； 表达式 E 包括整型加法运算和布尔型的与运算。尽管这个语言并不复杂，但它能够很好地阐释语义检查中的关键问题。
对于这个语言，可以给出对表达式E的类型检查实现(用类C的代码实现)： 


1． enum type {INT, BOOL};

2． SymTable table;

3． enum type check_exp(struct Exp *e){

4． switch(e->kind){

5． case EXP_INT:

6． return INT;

7． case EXP_TRUE:

8． return BOOL;

9． case EXP_FALSE:

10． return BOOL;

11． case EXP_ID:

12． enum type t = SymTable_lookup(table, id)

13． if(id not found)

14． error("id not found");

15． else

16． return t;

17． case EXP_ADD:

18． enum type t1 = check_exp(e->left);

19． enum type t2 = check_exp(e->right);

20． if(t1!=INT || t2!=INT)

21． error ("type mismatch for +");

22． else

23． return INT;

24． case EXP_AND:

25． enum type t1 = check_exp(e->left);

26． enum type t2 = check_exp(e->right);

27． if(t1!=BOOL || t2!=BOOL)

28． error ("type mismatch for &&");

29． else

30． return BOOL;

31． }

32． }


函数check_exp完成对输入参数表达式e的类型检查，返回该表达式的类型。该函数本质上完成了对表达式e的后序遍历： 如果e是一个整型常量，则返回类型INT； 如果e是true或false，则函数返回类型BOOL； 如果e是一个标识符id，则函数首先在符号表table中查找这个标识符，如果查找成功，则返回标识符的类型t，如果查找失败，则输出合适的错误处理信息。对于复合表达式，函数先进行递归调用来检查两个子表达式left和right的类型t1和t2，对结果进行检查后，再返回表达式的类型(如果出错，则输出合适的错误信息)。
有了对表达式E的类型检查函数，编译器就可以类似地实现对语句S的类型检查功能： 


1． void check_stm(struct Stm *s){

2． switch(s->kind){

3． case STM_ASSIGN:

4． enum type t1 = SymTable_lookup(s->id);

5． enum type t2 = check_exp(s->exp);

6． if(t1!=t2)

7． error("type mismatch for =");

8． else

9． return INT;

10． case STM_PRINTI:

11． enum type t = check_exp(s->exp);

12． if(t!=INT)

13． error("type mismatch for printi()");

14． else

15． return;

16． case STM_PRINTB:

17． t = check_exp(s->exp);

18． if(t!=BOOL)

19． error("type mismatch for printb()");

20． else

21． return;

22． }

23．}


对于赋值语句，编译器从符号表中查找被赋值变量的类型t1，并将其与赋值右侧表达式的类型t2做比较； 对于打印语句，编译器递归检查打印参数的类型并做适当检查。
最后，给出对变量声明D和程序P的类型检查算法： 


1． void check_dec(enum type t, char *id){

2． SymTable_insert(SymTable, id, t);

3． }

4． 

5． void check_prog(struct Dec *d, struct Stm *s){

6． check_dec(d);

7． check_stm(s);

8． }


函数 check_dec 处理每一个变量声明，将其放入符号表SymTable 中； 函数 check_prog 先对变量声明d进行类型检查，再完成对语句s的类型检查。
尽管更实际的编程语言可能包括更复杂的语言机制，如作用域、命名空间、更复杂的类型规则等，对其进行语义检查实现起来会更加复杂，但对其进行类型检查的基本原理和技术和上述讨论类似，编译器都要围绕符号表，仔细检查每项语言特性是否满足语言语义规范的要求。


3.4小结




编译器前端负责读入程序的源代码，对其进行合法性检查，并编译到合适的中间表示。本章讨论了编译器前端的3个组成部分： 词法分析、语法分析和语义分析。词法分析负责读入程序的字符流，并输出记号流； 语法分析负责读入程序的记号流，对程序的语法合法性进行分析和检查，并构建抽象语法树的数据结构，抽象语法树是编译器前端最重要的数据结构表示； 语义分析负责检查程序是否符合语言的语义规则，并把程序进一步翻译成中间表示供后续阶段处理。


3.5深入阅读




Ravi Sethi等提出了通过在缓冲区末尾放置一个敏感标记(sentinel)，一个不属于任何记号的字符，词法分析器就有可能只对每个记号进行一次检查，而不是对每个字符都进行检查。Bumbulis和Cowan的方法只需对DFA中的每一次循环检查一次，当DFA中存在很长的路径时，这样可以减少检查的次数(相对每个字符一次)。
Conway在介绍一个递归下降(预测)分析器的同时，描述了FIRST集合和提取左因子的概念。LL(k)分析理论是由Lewis和Stearns形式化的。
LR(k)语法分析方法是由Knuth开发的。Backhouse给出了关于LL和LR分析法理论的介绍。Aho等说明了利用优先级指导命令解决其中的二义性，使得确定的LL或LR语法分析引擎能够处理二义性文法。Burke和Fisher发明了一种通过管理一个包含K个单词的队列和两个分析栈来实现错误修复的策略。
许多编译器将递归下降分析代码与语义动作混合在一起进行，Gries、Fraser 和Hanson 给出了采用这种方法的早期编译器和现代编译器的例子。抽象语法的表示最早由 McCarthy 提出。


3.6习题





1. 将下面正则表达式转换为上下文无关文法： 
(1) ((xyx)|(yxy))?。
(2) ((0|1)+″.″(0|1))|((0|1)″.″(0|1)+)。
2. 分别为下面语言写出一个无二义性的文法。
(1) 字母表a，b 上的回文(即无论顺读、倒读都相同的字符串)。
(2) 与正则表达式ab 相匹配且a多于b的字符串。
(3) 配对的圆括号和方括号，例如 (［［］(()［()］［］)］)。
(4) 配对的圆括号和方括号，但其中闭方括号也关闭未配对的开圆括号(一直到前一个开方括号)，例如 ［(［］(()［(］［］)］。提示： 首先，写出圆括号配对和方括号配对的语言，并允许有额外的开圆括号； 然后保证这个开圆括号必须出现在方括号内。
(5) 关键字public、final、static、synchronized、transient组成的所有子集和排列(无重复)。
3. 对于下面文法： 


S→uBDz

B→Bv|w

D→EF

E→y|

F→x|

(1) 计算文法的nullable、FIRST和FOLLOW集合。
(2) 构造LL(1)分析表。
(3) 给出证据说明该文法不是LL(1)文法。
(4) 尽可能少地修改该文法使它成为一个接受相同语言的LL(1) 文法。
4. 给定如下的文法： 


S→E$

E→id

E→id (E)

E→E+id

(1) 构造这个文法的LR(0)自动机。
(2) 它是LR(0)文法吗？给出理由。
(3) 它是SLR文法吗？给出理由。
(4) 它是LR(1)文法吗？给出理由。
5. 说明下面这个文法是LALR(1)，但不是SLR： 


S→X$

X→Ma|bMc|dc|bda

M→d


6. 说明下面这个文法是LL(1)，但不是LALR(1)： 


S→(X|E ］|F )

X→E )|F ］

E→A

F→A

A→

7. 假定你正在为一种简单的、具有词法作用域的语言编写编译器。考虑如下所示的程序。


1． procedure main

2． integer a,b,c;

3． procedure f1(w,x);

4． integer a,x,y;

5． call f2(w,x)；

6． end;

7． procedure f2(y,z)

8． integer a,y,z;

9． procedure f3(m,n)

10． integer b,m,n;

11． c=a*b*m*n;

12． end;

13． call f3(c,z);

14． end;

15． ...

16． call f1(a,b);

17． end;


(1) 编译器处理到11行时，请绘制对应的符号表及其内容。
(2) 在语法分析器进入一个新的过程和退出一个过程时，需要哪些操作来管理符号表？
8. 最常见的符号表实现技术是使用哈希表，其中插入和删除的预期代价是O(1)。
(1) 哈希表中插入和删除操作在最坏情况下的代价如何？
(2) 提议一种备选实现方案，以保证O(1)时间内完成插入和删除操作。