编译原理-总复习

1编译程序是将一种语言（源语言,通常是高级语言）翻译为另一种语言（目标语言，通常用汇编语言或机器语言表示）的计算机程序。目标程序翻译源程序一个编译程序涉及到三个方面的语言，即源语言、目标语言和编译程序的书写语言。为了描述方便通常用T型图来表示这三个方面的语言。T型图的左上角表示源语言，右上角表示目标语言，底部表示书写语言(实现语言)STI■第一章2词法分析源程序目标程序语法分析语义分析目标代码生成文字表、符号表处理错误处理中间代码优化中间代码生成前端后端1.2编译过程和编译程序的基本结构3第二章2.2.1字母表和符号串字母表是元素的非空有穷集合。例如：

={a，b，c}

字母表中至少包含一个元素。字母表中的元素可以是字母、数字或其他符号。符号（字符）字母表中的元素称为符号，或称为字符。43.字符串（字）

符号的有穷序列称为符号串。例如有字母表

={a，b，c}，则有字符串a,b,ab,ba,……

符号串总是建立在某个特定字母表上的，且只能由字母表上的有穷多个符号组成。符号串中符号的顺序很重要，例如ab和ba就是两个不同的符号串。不包含任何符号的符号串，称为空符号串，用ε表示。空符号串由0个符号组成，其长度

|ε|＝05注意：

ε是符号串，而不是集合

{ε}表示由空符号串ε所组成的集合，但这样的集合不是空集合Φ＝{}6符号串的长度：符号串中所包含的符号的个数例s=string,|s|=6,|ε|＝0符号串的连接：设α、β是两个符号串，则αβ称为α与β的连接例α=some,β=thing,αβ=something εα=αε=α符号串的乘积：设A、B是两个符号串的集合，AB表示A与B的乘积。

2.2.2符号串的运算7例：A={ab,cd},B={ef,gh}AB={abef,abgh,cdef,cdgh}

特别地，{ε}A=A{ε}=A符号串集合的正则闭包A+A+＝AA2A3…An，即A+为集合A上所有符号串的集合符号串集合的闭包记为A*定义A*={ε}

A+=A+

{ε}显然，A+=AA*=A*A8符号串的幂运算设x是符号串，则x的幂运算定义为

x0=ε x1= x x2= xx ……

xn

= xx…x=xxn-1(n>0)例如，设x=abc

9集合的幂运算设A是符号串的集合，则集合A的幂运算定义为

A0={ε} A1= A A2= AA …… An= AA…A=AAn-1(n>0)例如，设A={a,b},则A2=?A+?A*?102.文法文法是产生式的非空有穷集合，通常表示成四元组G=(VN,VT,P,S)。其中:VN是产生式中非终结符的集合。VT是产生式中终结符的集合。VN∩VT＝ØP是文法规则的集合。S是一个非终结符，称为文法的开始符号，它至少要在一条规则的左部出现。由它开始，识别出我们所定义的语言。11复杂的产生式往往用一些基本的产生式组合而成。①基本式：Aα，这里α是终结符组成的串，这个语法所定义的语言只有一个符号串。例：A0②嵌套式:AαBβ，α、β是终结符串，B是一个非终结符串，A所定义的终结符串是每个B定义的语句（可推出的终结符串）前边加α串并且后边加β串。例：

AiBchina

Blove一些基本的产生式重点掌握给定的文法，能够写出文法所表示的语言。12③递归式：有两个常用的产生式都能表示递归式。

AAα|α,A

αA|α

它们定义的串集合为：{α，αα，α…ααα}α…ααα可写成αn，所以L(A)={αn|n≥1}例：(i)D

bD|ε(ii)AaA|d④成对符号递归：可用下述产生式表示成对符号递归：

AαAβ|αβA定义的语言可记为L(A)={αnβn|n≥1}例：AabAcd|abcd一些基本的产生式13

推导从开始符号开始，经过有限次的推导后得到一个终结符串（句子）。从开始符到句子间，每步推导所得到的含有非终结符的符号串是一个句型，一个文法G经过推导所能获得的全部句子的集合就是这个文法语言L(G). =>*表示经过0步或若干步推导

=>+表示经过1步或若干步推导14■语言的形式定义4、句型和句子G=(VT,VN,P,S)，S=>*a，a∈(VTVN)*

称a为句型。a∈VT*，称a为句子。句型与句子区别：句型由终结符和非终结符构成，句子只由终结符构成。联系：仅含终结符的句型是一个句子。即：句子必定是句型，但句型不一定是句子。例：设有文法G[S]:S01|0S1请分别判断：01，000S111，0SS0，0011，0S1是该文法的句子还是句型？15■句型与句子举例例：设有文法G[E]: EE+E|E*E|(E)|i试证明符号串

i+i*i(i*i+i)是文法G[E]的句子。16例2.5设有文法G[S]: S01|0S1有

S=>*01 S=>*0S1 S=>*00S11 S=>*000111问:哪些字符串是文法G的句子?哪些是文法的句型?如何由规则推导句子？推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。直到所有的非终结符号都由终结符号替代为止。17由此可见，从已知文法确定语言的中心思想是：从文法的开始符号出发，反复连续地使用规则（产生式），对非终结符施行替换和展开，找出句子的规律，用式子或自然语言描述出来。注意：（1）给定一个文法，就能唯一地确定其语言，即

GL(G)（2）给定一种语言，能确定其文法，但这个文法不一定是唯一的。文法和语言的关系■规范推导和规范归约最左（右）推导：指对于一个推导序列中的每一步直接推导α=>β,都是对α中的最左(右)非终结符进行替换规范推导:指最右推导规范句型:用规范推导推导出的句型称为规范句型规范归约(最左归约):规范推导的逆过程例：设有文法G[S]:SAB AA0|1B B0|S1请给出句子1000的最左、最右推导。练习：给出句子101001的最左推导。19◆例2.12考虑文法G[N1]：

N1N NND|D D0|1|2该文法是左递归的，它所描述的语言是无穷集合。当一个语言是无穷集合时，则定义该语言的文法一定是递归的。{0,1,2}+202.5.1推导和语法树对句型的推导过程给出一种图形表示，这种表示称为语法树，也称推导树。2.5语法树与文法的二义性与推导相对应的语法树是一个作了标记的树，其中内部的节点由非终结符标出，树叶节点由终结符标出，每个内部节点都表示推导的一个步骤中的相关非终结符的替换。树根结点是文法的开始符号。21语法树的特点：如果句子中有括号的话，括号在文法中表示了操作的优先次序，这个次序在语法树中已经被树的层次体现出来了。靠近根结点的计算总是较迟处理，靠近叶子的结点被优先处理。22短语、简单短语G=(T,N,P,S)，w=xuy

∈(T

N)*

为文法的句型,若S=>xUy,且U=>+u,则u是句型w相对于U的短语；若S=>xUy,

且

U=>u,则u是句型w相对于U的简单短语;其中U∈N，u∈(T

N)+,x,y∈(T

N)*

句柄任一句型的最左简单短语称为该句型的句柄。

短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。Note23子树：由某一结点连同所有分支组成的部分。简单子树：指只有单层分支的子树。短语/直接短语/句柄在语法树中的直观解释：短语----子树的末端结点形成的符号串是相对于子树根的短语直接短语----简单子树的末端结点形成的符号串是相对于简单子树根的短语句柄----最左简单子树的末端结点形成的符号串是句柄24例：有文法G[E]：

ET|E+T|E-T

TF|T*F|T/F

Fi|(E)请判断(E+T)*i+F是G的一句型吗？如果是，请画出它的推导的分析树，并写出该树的短语、简单短语、句柄。解：∵E=>*(E+T)*i+F

∴(E+T)*i+F是G的一句型E+ETTF+ET)E(F*TiF25简单短语(每棵简单子树的叶组成简单短语):E+T是句型(E+T)*i+F相对于E的简单短语；i是句型(E+T)*i+F相对于F的简单短语；F是句型(E+T)*i+F相对于T的简单短语。E+ETTF+ET)E(F*TiF短语(每棵子树的叶组成短语):(E+T)*i+F是句型(E+T)*i+F相对于E的短语；(E+T)*i是句型(E+T)*i+F相对于E、T的短语；(E+T)是句型(E+T)*i+F相对于T、F的短语；E+T是句型(E+T)*i+F相对于E的短语；i是句型(E+T)*i+F相对于F的短语；F是句型(E+T)*i+F相对于T的短语。句柄(最左简单子树的叶组成句柄):E+T是句型(E+T)*i+F相对于E的最左简单短语。26◆例2.13.设有文法G[S]=({S,A,B},{a，b},P,S)其中，P为

SAB

AAa|bB

Ba|Sb请判断baSb是G的一句型吗？如果是，请画出它的推导的分析树，并写出该树的短语、简单短语、句柄。■文法的二义性引例：已知简单整型算术表达式文法：

exp

expopexp|(exp)|iop

+|-|*

请画出串i

-i

*i

的语法树!解：1)推导

2)根据推导画语法树同一个句子若可生成两棵不同的语法树，则定义该句子的文法叫二义性文法。注意理解：若一个文法中存在某个句子，它有两个不同的最左（最右）推导，这个文法是二义性文法。■文法二义性的消除◆不修改文法，指定正确的语法树；◆修改文法(考虑优先级、结合性等)注意：文法的二义性和语言的二义性是两个不同的概念。只要某文法定义的语言中，有一个句子有2棵以上的语法树，该文法就是二义性的；而二义性语言是指，对它不存在无二义性的文法，这样的语言称为先天二义性的语言。文法G[E]：

E→T|E+T|E-T T→F|T*F|T/F

F→(E)|i文法G[E]:EE+E|E*E|(E)|i29注意：文法的二义性和语言的二义性是两个不同的概念。通常我们只说文法的二义性，而不说语言的二义性，这是因为可能有两个不同的文法G和G’，一个是二义性的，一个不是二义性的，但他们所描述的语言却是一样的，即L(G)=L(G’).

将一个语言说是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。人们已经证明，不存在一个算法，它能在有限步骤内确切地判定任给的一个上下文无关文法是否是二义性文法。30

文法和语言分类：0型、1型、2型、3型（乔姆斯基层次）

0型文法称为短语结构文法（非限制）。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。●0型：P：u

v

其中u∈(T

N)+

，v∈(T

N)*

■乔姆斯基层次2.6文法和语言的分类31

1型文法称为上下文敏感或上下文有关文法。也即只有在x,y这样的上下文中才能把U改写为u●1型：P：xUy

xuy

其中U∈N，x,y,u∈(T

N)*例：1型（上下文有关）文法文法G[S]： S→CD

C→aCA

C→ε

C→bCB

D→ε

AD→aD

BD→bD

Aa→bD322型文法称为上下文无关文法。也即把U推导为v时，不必考虑上下文。●2型：P：U

v

其中U∈N

，v∈(T

N)*

文法G[S]：

S→AB A→BS|0 B→SA|12型文法即上下文无关文法及相应的语言是我们主要研究的对象。33例：G[S]：S→0A|1B|0A→0A|1B|0SB→1B|1|03型文法称为正则文法，它是对2型文法进行进一步限制3型文法不能把非终结符嵌在终结符串里。如：S

aSb|ab不是3型文法，3型文法不能描述anbn这样的符号串。●3型：(左线性)P：U

t

或

U

Wt

其中

U、W∈Nt∈T(右线性)P：U

t

或

U

tW

其中

U、W∈Nt∈T34●0型、1型、2型、3型比较产生式左部范围右部范围|左部||右部|0型u

v(T

N)+(T

N)*>=1>=01型xUy

xuy(T

N)+(T

N)*>=1>=02型U

vN(T

N)*=1>=03型U

tU

WtNT

N=1<=2●3型：P：U

t或

U

Wt其中

U、W∈Nt∈T●2型：P：U

v

其中U∈N

，v∈(T

N)*

●0型：P：u

v

其中u∈(T

N)+

，v∈(T

N)*

●1型：P：xUy

xuy

其中U∈N，x,y,u∈(T

N)*L3

L2

L1

L0353.1词法分析程序的功能所谓词法，即构成词的规则。词法分析的任务是对字符串表示的源程序从左到右进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号。词法分析是编译过程中的一个阶段，在语法分析前进行，可以作为单独的一遍，将源程序转换成单词符号序列供下一遍使用。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序获得当前记号，供语法分析使用。363.2单词符号及输出单词的形式源程序词法分析程序单词符号单词符号是语言中具有独立意义的最小单位，包括保留字、标识符、常量、运算符和界符等。词法分析程序输出的单词符号通常表示成如下的二元式：（单词种别，单词自身的值）37■正规式与正规集3.3语言单词符号的两种定义方式多数程序设计语言的单词符号都能用正规文法或正规式来定义。设有字母表

={a1，a2，…，an}，在字母表上的正规式和它所表示的正规集可用如下规则定义：（1）Φ是上的正规式，它所表示的正规集是Φ，即空集{}（2）ε是上的正规式，它所表示的正规集是{ε}（3）ai是上的正规式，它所表示的正规集由单个符号ai组成，即{ai}38■正规式与正规集（4）如果e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，则e1|e2是上的一个正规式，它所表示的正规集为L(e1|e2)=

L(e1)∪L(e2)e1e2是上的一个正规式，它所表示的正规集为L(e1e2)=L(e1)L(e2)(e1)*是上的一个正规式，它所表示的正规集为L((e1)*)=L((e1))*正规式描述了单词符号的构成规则，正规集是正规式能描述的所有的单词的集合。39设有字母表

={a,b},根据正规式和正规集的定义有：■例3.1（1）a和b是正规式，相应正规集为L(a)={a}（2）a|b是正规式，相应正规集为L(a|b)={a,b}（3）ab是正规式，相应正规集为L(ab)={ab}（4）(a|b)*是正规式，相应正规集为L((a|b)*)={a,b}*={ε,a,b,ab,ba,…}（5）ba*是正规式，相应正规集为L(ba*)={b,ba,baa,baaa,…}（6）(a|b)*(aa|bb)(a|b)*是正规式，相应正规集为L={a,b}*{aa,bb}{a,b}*练习：若S=a|bb，则L((a|bb)*)=？40■正规式中运算的优先级括号优先，*次之，•（连接）再次之，|最后例：a|bc*≌a|(b(c*))

ab|c*d≌(ab)|((c*)d)

L(a|bc*)=L(a)∪L(bc*) =L(a)∪L(b)L(c*) =L(a)∪L(b)(L(c))* ={a}∪{b}{ε,c,cc,ccc……} ={a,b,bc,bcc,bccc,……}■正规式与正规集举例思考：L(ab|c*d)=？413.4正规式与有穷自动机有穷自动机是词法的识别工具，它的功能是：寻找（匹配）符合正规式要求的字符串，根据正规式确定正规集。有穷自动机是描述特定类型算法的数学模型，可分为确定性有穷自动机(DFA)和非确定性有穷自动机(NFA)。42■确定有穷自动机（DFA）数学定义（五元组形式）：严密；状态转换表：面向编程。状态转移图：直观；DFA有三种表示形式43结点代表状态(state)，用圆圈○表示。状态之间用箭头→(transition)连结，代表一个状态向另一个状态的转换。一个有穷自动机只包含有限个状态(即有限个结点)，其中只有一个为初态(startstate)（一个有开始状态的箭头指向），至少一个为终态(接受状态acceptingstate)(双圈表示)。例：标识符的有穷自动机。■有穷自动机的状态转移图表示方法44■确定有穷自动机（DFA）◆∑输入字母表◆Q有穷状态集◆f:Q×∑→Q(状态转换函数)◆S∈Q唯一的初始状态◆Z

Q终止（接受）状态集合这里的字母表是问题固有的；状态集合是编写DFA时定义的，是用户所做的命名。DFAM是一个五元组（Q,∑,f,S,Z

）确定性有穷自动机(DFA)：下一状态由当前状态和当前输入字符唯一给出的自动机。（取决于f）“确定”即状态转移函数是单值函数——数学定义45■非确定有穷自动机（NFA）由M接受的语言L(M)

L(M)＝{c1c2c3….cn

|ci∈∑U{ε},s1=T(s0,c1),s2=T(s1,c2),…,sn=T(sn-1,cn),sn∈A.}“非确定”即状态转移函数是多值函数◆∑:输入字母表◆Q:有穷状态集◆f:Sx(

U{ε})℘(S)(状态转换函数)◆S

Q初始状态集◆Z

Q终止状态集NFAM也是一个五元组（Q,∑,f,S,Z

）46转换函数T初态NFAM(S,∑,T,S0,F)S×(

U{ε})

→S的子集多值映射S0

S非空初态集DFAM(S,∑,T,s0,F)S×∑→S的元素单值映射s0∈S唯一的初态●NFA与DFA的区别：47■由正规表达式R构造NFA

(a)对于正规式φ,所构造NFA:xy

(b)对于正规式ε,所构造NFA:xyε

(c)对于正规式a,a∈Σ,则NFA:xya1.基本正规表达式48■由正规表达式R构造NFA2、若r,s为正规式：123rssr13rsr|sr*例：构造与正规表达式R=ab*a(a|b)*等价的NFA。1r32εε49定义1：状态集合I的ε-闭包：令I是一个状态集的子集，定义ε-closure（I）为：1）若s∈I，则s∈ε-closure（I）；2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。状态集ε-closure（I）称为I的ε-闭包为了使得NFA确定化，给出两个定义：56432aεaaε1例：如图所示的状态图：令I={1}，求ε-closure（I）=？解：根据定义：ε-closure（I）={1，3}例：若I1={1,2}，则ε-closure（I1）={1,2,3,6}DFA的确定化50——J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合。——

Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过ε弧到达的状态。定义2:状态子集的构造：s∈I例：令I={1}，求Ia=?Ia=ε-closure(J)=ε-closure(T(1，a)）

=ε-closure({2，4}）

={2，4，6}56432aεaaε1令I是NFAM’的状态集的一个子集,a∈Σ定义:Ia=ε-closure(J)其中J=∪T(s,a)51例：有NFAM，求DFAM’。a1234startabaccε

IIa

Ib

Ic

{1,4}{2,3}φφ{2,3}{2}{4}{3,4}{2}{2}{4}φ{4}φφφ{3,4}φφ{3,4}初态I=ε-closure({1})={1,4}Ia=ε-closure(T(1,a)∪T(4,a))=ε-closure({2,3}∪φ）

=ε-closure({2,3})={2,3}Ib=ε-closure(T(1,b)∪T(4,b))=ε-closure(φ）

=φIc=ε-closure(T(1,c)∪T(4,c))=φI={2,3},Ia={2},Ib={4},Ic={3,4}……DFA的状态52

符号状态abc02341221________3344●DFAM’状态表将求得的状态转换矩阵重新编号start01423{1,4}{2,3}{4}{2}acabbc{3,4}

IIa

Ib

Ic

{1,4}{2,3}φφ{2,3}{2}{4}{3,4}{2}{2}{4}φ{4}φφφ{3,4}φφ{3,4}包含NFA终态的状态子集全都是DFA的终态53例:将该DFA最小化5724361srartaaaaaaabbbbbbb状态集的划分将所有DFA的终态与其它状态划分成两个子集G1,G2;分别从两个子集G1,G2中寻找不等价状态进行分割。“分割法”：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的.54解:(一)区分终态与非终态123456637315467374142ab567374142ab123463731546231区号5724361srartaaaaaaabbbbbbb将所有DFA的终态与其它状态划分成两个子集区号12123456637315467374142ab5512431243123456637315467374142ab5123456637315467374142ab区号区号12345ab5214355231155243aaaaabbbbb567374142ab123463731546123区号将区号代替状态号得:56正规文法正规式NFADFA最小化ABtA

tB(2)对终态Z增加Z

ε(1)右线性文法增加终态；左线性文法增加初态解方程组，若x=αx+β，则x=α*β;Aab

转换成AaB和BbAa*b转换成AaA|b;57为R=(a|b)*(aa|bb)(a|b)*构造最小化的DFA,使得L(N)=L(R)■课堂练习例：构造与正则表达式R=ba(a|b)*等价的状态最少的DFA，并写出该DFA的五元组形式。58语法分析程序的功能是以词法分析器生成的单词符号序列作为输入，根据语言的语法规则（文法），识别出各种语法成分，并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言的文法的一个句子。若是，则以该句子的某种形式的语法树作为输出；若不是，则表明有错误，并指出错误的性质和位置。4.1语法分析程序的功能语法分析程序的输入是单词符号序列；输出是语法树。59递归下降法LL(1)分析法回溯分析方法（不确定的分析法）预测分析方法(确定的分析法)LR(0)parsingSLR(1)parsingLR(1)parsingLALR(1)parsing自顶向下分析方法从根结点出发构造语法树

自底向上分析方法从叶结点出发构造语法树

语法分析方法L:由左向右的处理输入L:为输入串构造最左推导

60■文法左递归的消除4.2自上而下分析法左递归导致无限递归循环；解决无限递归循环的方法：消除左递归。（1）左递归改成右递归——简单直接左递归的消除

A→Aα|βA→βA’A’→αA’|ε解：exp→termexp’

exp’→addoptermexp’|ε例：将文法G：exp→exp

addopterm|term

消除左递归。左递归的消除不改变语言，但是改变了文法和分析树。确定的自上而下分析法对文法要求：(1)无左递归；(2)无回溯61将文法G：A→αβ|αγ提取左因子。解：A→αA’

A’→β|γ■提取左因子规则例：将文法G提取左因子。

stmt-sequence→stmt;stmt-sequence|stmt

stmt→s

提取左因子的结果：stmt-sequence→stmtstmt-seq’stmt-seq’→;stmt-sequence|εstmt→s注意：不可以这样提取：Aa(β|γ)文法中括号的含义与正规式中括号的含义不同。62First集合和Follow集合■First集合定义：FIRST(α)={a|α=>*aβ，a

T,α,β

(T

N)*

}

若α=>*ε，则规定ε

FIRST(α)该集合称为α的头符号集合631.若X

,则FIRST(X)={X}2.若X

N,且有产生式X

a…，则把a加入到FIRST(X)中;若X

也是一条产生式,则把

也加到FIRST(X)中.3.若X

Y…是一个产生式且Y

N,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X

Y1Y2…YK

是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有

(即Y1..Y(i-1)

=>*

),则把FIRST(Yi)中的所有非

元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,j=1,2,…,K)均含有

,则把

加到FRIST(X)中.■First集合算法P69令X为一个文法符号或

，则集合First(X)由终结符组成，此外还可能有

，定义如下：64■求First集合举例2求文法G的FIRST集合G:(1)M→TB (2)T→Ba|ε (3)B→Db|eT|ε (4)D→d|ε注意：有ε产生式时求First集，别漏元素！！First(M)={e,a,d,b,ε}

First(T)={e,a,d,b,ε}

First(B)=

{e,d,b,ε}

First(D)=

{d,ε}注意：除了求非终结符的First集外，还可求符号串的First集。例：求First(BaB)65定义：FOLLOW(A)={a|S=>*

…Aa…，a∈T}A∈N,S开始符号特殊地：若S=>*...A，则$∈FOLLOW(A)■Follow集合1.对于文法的开始符号S,置$于FOLLOW(S)

中;2.若Ａ

αBβ是一个产生式,则把FIRST(β)－{}加至FOLLOW(B)中;3.若Ａ

αB是一个产生式,或Ａ

αBβ是一个产生式而

FIRST(β)，则把FOLLOW（A）加至FOLLOW（B）中。算法：66练习4)求文法G的FOLLOW集合

E→TE’

E’→+TE’|ε

T→FT’T’→*FT’|ε

F→(E)|iFIRST(F)={(，i}FIRST(T’)={*,ε}FIRST(T)={(，i}FIRST(E’)={+,ε}FIRST(E)={(，i}FOLLOW(E)={$,)}FOLLOW(E’)={$,)}FOLLOW(T)={+,),$}FOLLOW(T’)={+,),$}FOLLOW(F)={*,+,),$}解：67■Select集合Select集合是针对规则（产生式）的。设A

α是文法的任一条规则，则定义：Select(A

α)=First(α) 若α=>*

First(α)-{}

∪Follow(A)

若α=>*

例：求下列文法的每个规则的Select集合：

AaB|d

BbBA|

68一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则A

α

β满足：Select(A

α)∩Select(A

β)=

■LL(1)文法的要求69■预测分析表的构造算法（1）计算每一非终结符的First集和Follow集；（2）对于First(α)中的每个记号a，都将A→α添加到表项M[A,a]中；（3）若ε在First(α)中，则对于Follow(A)的每个元素a(记号或是$)，都将A→α添加到M[A,a]中;（4）把分析表中没有填入内容的空白格都标上出错标志error。例：文法：Sa|^|(T) TT,S|S试判断该文法是否是LL(1)文法，若不是请转换，并求转换后LL(1)文法的预测分析表。70●练习1Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number}Follow(term)={$,+,-,)}Follow(term’)={$,+,-,)}Follow(mulop)={(,number}Follow(factor)={$,+,-,*,)}(1)First集和Follow集First(exp)={(,number}First(exp’)={+,-,ε}First(addop)={+,-}First(term)={(,number}First(term’)={*,ε}First(mulop)={*}First(factor)={(,number}文法：exp→expaddop

term∣term

addop

→

+|- term→termmulop

factor∣factor

mulop

→* factor→(exp)

∣

number

注意：先消除左递归71Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number)Follow(term)={$,+,-,)}Follow(term’)={$,+,-,)}Follow(mulop)={(,number)Follow(factor)={$,+,-,*,)}(2)First集和Follow集First(exp)={(,number)First(exp’)={+,-,ε}First(addop)={+,-}First(term)={(,number)First(term’)={*,ε}First(mulop)={*}First(factor)={(,number)11109788886654223311factormulopterm’termaddopexp’exp$*-+)Number(M[N,T](3)LL(1)分析表解

(1)文法1exp→termexp’2exp’→addoptermexp’3exp’→ε4addop

→+5addop

→-6term→factorterm’7term’→

mulopfactorterm’8term’→ε9mulop

→*10factor→(exp)11factor→number（1）对于First(α)中的每个记号a，都将A→α添加到表项M[A,a]中；（2）若ε在First(α)中，则对于Follow(A)的每个元素a(记号或是$)，都将A→α添加到M[A,a]中。4.5LR分析

LR分析法是一种自上而下进行规范规约的语法分析方法。这里的L是指从左到右扫描输入符号串，R是指构造最右推导的逆过程。这种分析法比递归下降分析法、预测分析法和算府优先分析法对文法的限制要少的多，也就是说，对大多数无二义性的上下文无关文法描述的语言都可以用LR分析法进行分析，而且分析速度快，并能准确及时地指出输入串的语法错误和出错位置。缺点：构造LR分析器的工作量大734.5LR分析法本节介绍四种LR分析法：LR(0)、SLR(1)、LR(1)、LALR，这四种方法的区别只有分析表不同。LR分析法是一种自下而上进行规范归约的语法分析方法。这里L是指从左向右扫描输入符号串，R是只构造最右推导的逆过程。优点：对文法的限制少的多，分析速度快；缺点：构造LR分析器的工作量大，实现困难。4.5.1LR分析器的工作原理和过程

LR分析法是一种规范规约分析方法，这种分析法的关键是在分析过程中如何确定分析栈栈顶的符号串是否可形成句柄。

LR分析法确定句柄的基本思想是在规范规约分析过程中，根据分析栈中记录的已移进和规约出的整个字符串（历史）和根据使用规则推测未来可能遇到的输入符号（即展望），以及现读到的输入符号这3方面的信息来确定分析栈的栈顶的符号串是否构成句柄。75输入

a1...ai...an$LR驱动程序分析表输出栈smXmsm-1Xm-1...s0actiongoto

LR分析器的结构和工作过程■LR分析器的工作原理和过程

LR分析表是LR分析器的核心部分。一张LR分析表由分析动作（ACTION）表和状态转换表（GOTO）两部分组成，他们都是二维数组。状态转换表元素GOTO[Si，X]规定了当状态Si面临文法符号X时，应该转移到的下一个状态。分析动作表元素ACTION[Si,a]规定了当状态Si面临输入符号a时应执行的动作。有如下4种可能的动作：（1）移进：把状态Sj＝GOTO[Si,a]和输入符号a移入分析栈。（2）规约：当栈顶符号串a形成句柄，且文法中有A

的规则，其中|α|=β，则规约动作是从分析栈栈顶去掉β个文法符号和β个状态，并把规约符A和GOTO[Si-β,A]=Sj移入分析栈中（3）接受（acc)：表示分析成功。此时，分析栈中只剩文法开始符号S‘和当前读到的输入符号$，即输入的符号串已经结束。（4）报错：表示输入串有错误，此时出现栈顶的某一状态遇到了不该遇到的输入符号。78在文法产生式右部某个位置标有‘.’的产生式，称为文法的一个LR(0)项目。形如A.的项目称为初始项目；形如A.的项目称为归约项目；形如A.B（B∈N）的项目称为待约项目；形如A.a（a∈T）的项目称为移进项目；形如S’S.的项目称为接受项目，其中S’为文法的唯一的开始符号■项目分类79设I是文法G的一个LR(0)项目集合，I的项目闭包closure(I)定义为：(1)Iclosure(I)。

(2)若项目A.Bclosure(I)，且B是G的产生式，则项目B.closure(I)。

(3)closure(I)仅包含上述两条规则确定的LR(0)项目。项目闭包：转移函数：若I是文法G的一个LR(0)项目集，X是G中的文法符号。go(I,X)=closure(J)其中J={AX.|A.XI}称函数go(I,X)为转移函数。项目AX.称为项目A.X后继。■构造识别文法所有规范句型活前缀DFA的方法80■LR(0)分析表的构造若对于一个文法G的拓广文法G’的LR(0)项目集规范族中的每个项目集，不存在移进项目和归约项目同时并存或多个归约项目同时并存，则称G为LR(0)文法。即LR(0)文法中不能存在移进－归约冲突或者归约－归约冲突。E'→·EE→·E+nE→·nE→n·E'→E·E→E·+nE→E+n·En+n012E→E+·n34根据右图某文法识别活前缀的DFA判断该文法是否为LR(0)文法81■LR(0)分析表的构造LR(0)分析表包含两个子表：ACTION表和GOTO表假定项目集规范族C={I0,I1,…,In}，令每个项目集Ik的下标k作为分析器的状态，两个子表的构造过程如下：（1）若项目A.a

属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTION[k,a]为”sj”；（2）若项目A.

属于Ik，则对任何终结符a（包括终结符$），置ACTION[k,a]为”rj”（注：j是产生式A的编号，而不是状态集的状态号）；（3）若项目S’→S·属于Ik(S·表示整个句子已输入并归约结束)，则置ACTION[k,$]为“acc”，表示接受。（4）若GO[Ik,A]=Ij，A为非终结符，则置GOTO[k,A]=j;（5）分析表凡不能用规则(1)-(4)填入的空白格均置为“error”。例：S(S)|a状态序号ACTIONGOTO终结符和$非终结符0……n分析表格式82例x：已知文法G[S]，求其LR(0)的分析表。

SaA|bB

AcA|d

BcB|dS

b.BB

.cBB

.d解:(1)识别文法活前缀的DFAA

d.A

c.AA

.cAA

.dS

a.AA

.cAA

.dB

c.BB

.cBB

.dS

.SS

.aAS

.bBstartS

S.A

cA.S

aA.AddAcabSS

bB.B

cB.B

d.BddBccc0123456789101183状态actiongotoabcd$SAB01234567891011s2s3accs5s6s8s9r1r1

r1

r1

r1s5s6r4r4

r4

r4

r4r2r2

r2

r2

r2s8s9r6r6

r6

r6

r6r3r3

r3

r3

r3r5r5

r5

r5

r51

4710

11(2)LR(0)分析表(1)识别文法活前缀的DFAA

d.A

c.AA

.cAA

.dS

a.AA

.cAA

.dS

b.BB

.cBB

.dB

c.BB

.cBB

.dS

.SS

.aAS

.bBstartS

S.A

cA.S

aA.AddAcabSS

bB.B

cB.B

d.BddBccc012367891011450SS1SaA2SbB

3AcA4Ad

5BcB6Bd84例：已知文法G[E]，分析i*i+i∈L(G[E])?EE+T|TTT*F|FF(E)|i出现问题：由该文法识别活前缀的DFA看的出来，有的有效项目集中存在着移进－归约冲突，不能用LR(0)分析方法进行分析。解决方法：对含有冲突的项目集向前查看一个输入符号，这种分析方法称为SLR(1)分析方法。复习：LR(0)文法中不能存在移进－归约冲突或者归约－归约冲突。■引例85解：(1)拓广文法G的拓广文法G[E]：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fi(3)TT*F

(2)识别文法的活前缀的DFA(3)SLR(1)分析表

(4)分析过程例：已知文法G[E]，并用SLR(1)方法分析i*i+i∈L(G[E])?EE+T|TTT*F|FF(E)|iSLR(1)的分析过程与LR(0)的分析过程完全一样，唯一不同的是分析表！E’EEE+TETTT*FTFF(E)FidEE’EEE+TTETTT*F(F(E)EE+TETTT*FTFF(E)FidI0I1I2I6FTFI3FididI5TI2FI3idI5(EE+TTT*FTFF(E)Fid+*TT*FF(E)FidI7F(E)EE+TEI8TEE+TTT*FI9FI3idI5(FTT*FI10idI4(I4*I7)F(E)+I6I11G

：(0)EE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fid

(2)识别文法的活前缀的DFA87若有效项目集中存在冲突动作:I={X.b,A.,B.}将b移进栈将

归约为A将

归约为B解决方法：设当前输入符号为x,1.若x=b,则移进;2.若xFollow(A),则用A进行归约;3.若xFollow(B),则用B进行归约;4.其余情况报错.要求：移进项目的符号集FOLLOW(A)FOLLOW(B)=■SLR(1)分析法88对于表达式文法的例子，FOLLOW集如下：G

：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fid(3)TT*FI2:FOLLOW(E)∩{*}=ΦI9:FOLLOW(E)∩{*}=Φ∴可用SLR(1)方法实现FOLLOW集E’$E$，），+T$，），+，*F$，），+，*EE+TTT*FETTT*FI2:I9:89●SLR分析表的构造算法输入：一个拓广文法G

输出：对于G

的分析表的action子表和goto子表方法：1.构造G

的LR(0)项目集规范族。2.对于状态Ii的分析动作如下：

(a)若A.aBIi且go(Ii,a)=

Ij

action[i,a]=shiftj(b)若A.Ii,对于所有aFollow(A)

action[i,a]=reduceA,AS(c)若SS.Ii,action[i,$]=accept3.若go(Ii,A)=Ij,AVN,则goto[i,A]=j4.分析表其余位置为error90(3)SLR分析表Follow(E)={$,+,)}ACTIONGOTO+*()id$ETF0S4S51231S6ACC2R2S7R2R23R4R4R4R44S4S58235R6R6R6R66S4S5937S4S5108S6S119R1S7R1R110R3R3R3R311R5R5R5R591(4)id*id+id的LR分析过程分析栈输入串动作(1)0(2)0id5(3)0F3(4)0T2(5)0T2*7(6)0T2*7id5(7)0T2*7F10(8)0T2(9)0E1(10)0E1+6(11)0E1+6id5(12)0E1+6F3(13)0E1+6T9(14)0E1id*id+id$*id+id$*id+id$*id+id$id+id$+id$+id$+id$+id$id$$$$$

shiftreducebyF

idreducebyTFshiftshiftreducebyFidreducebyTT*FreducebyETshiftshiftreducebyFidreducebyTFreducebyEE+Taccept92例：已知文法G[S]：S→(S)S|ε，求其SLR(1)的分析表，并判断()()∈L(G)?(3)SLR(1)分析表(2)构造识别文法活前缀的DFA，并判断用何种方法进行分析解:(1)拓广文法(4)分析过程注意：|ε|=0，所以用S→ε进行归约时，不用出栈，直接将S入栈即可。LR(0)分析不了的，SLR(1)有可能能分析；LR(0)能分析的，SLR(1)都能分析！■课堂练习●example例：已知文法G[S]，求其SLR(1)的分析表，并判断()()∈L(G)?

S→rD

DD,i|i(3)构造分析表(2)识别文法活前缀的DFA解:(1)拓广文法(4)分析过程94SLR(1)方法与LR(0)方法的区别仅在于有效项目集中有归约项目时：在LR(0)方法中，若项目集Ik含有A

，则在状态k时，无论面临什么输入符号都用“A

”进行归约——即假定A

产生式编号为j，则在分析表ACTION部分，对应状态k行的所有栏目都填”rj”。在SLR(1)方法中，若项目集Ik含有A

，则在状态k时，仅当输入符号为a∈FOLLOW(A)时，才用”

A

”进行归约，这样在分析表ACTION部分状态k行，所有b不属于FOLLOW(A)的栏目将空出来。若正好在b这一列有移进项目不会产生冲突。SLR(1)方法比LR(0)优越，它可以解决更多的冲突。95例：已知文法G[S]，请判断id:=id∈L(G)?S→id|V:=EV→idE→V|n■引例该文法的SLR[1]分析表中存在归约－归约冲突，该文法不能用SLR[1]分析方法进行分析。所以要采用另一种新的方法——LR[1]分析方法对该文法进行语法分析。4.5.4一般的LR(1)分析由于用SLR(1)方法解决动作冲突时，它仅孤立地考察对于规约项目Aα.，只要当前面临输入符号a∈FOLLOW(A)时，就确定使用规则Aα进行规约，而没有考察符号串α所在规范句型的环境。因为如果栈里的符号串为$δa，规约后变成$δA，当前读到的输入符号是a，若文法中不存在以δAa为前缀的规范句型，那么，这种规约无效。

LR(1)分析法的思想是在分析过程中，当试图用某一规则Aα规约栈顶的符号串α时，不仅应该查看栈中符号δα，还应向前扫视一个输入符号a，只有当δAa的确构成文法某一规范句型的前缀时，才能用此规则进行规约。为此，可以考虑在原来LR(0)项目集中增加更多的展望信息，这些展望信息有助于克服动作冲突和排除无效规约。一个LR(1)项目是一个二元组[Aα.β,a]，其中Aα.β是一个LR(0)项目，每个a是终结符，称它为展望符或搜索符。当β≠ε时，搜索符是无意义的；当β＝ε时，搜索符a明确指出当[Aα.,a]是栈顶状态的一个LR(1)项目时，仅在输入符号是a时才能用Aα规约，而不是对FOLLOW(A)中的所有符号用Aα规约。99

■LR(1)分析法LR(1)项：LR(1)项是由LR(0)项和一个先行记号组成的对，利用中括号将LR[1]项写作：

[A

，a]其中A

是一个LR[0]项，称为“心”；而a则是一个记号（先行），称为“向前搜索符”。a∈FOLLOW(A)。100假设有LR[1]项目[AX，a]，其中X是任意符号（终结符或非终结符），那么X就有一个到项目[AX，a]的转换。转换函数（1）I的任何项目都属于CLOSURE(I);（2）若项目[AB，a]属于CLOSURE(I)，B

是文法中的一条规则，b属于

First（a），则项目[B,b]属于CLOSURE(I);（3）重复（2）直到CLOSURE(I)不再增大为止。项目集I的闭包函数■LR(1)分析法101■LR(1)分析表的构造(1)若项目[Aa

，b]属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTION[k,a]为“sj”；(3)若项目[S’S，$]属于Ik，则置ACTION[k,$]为“acc”;(4)若GO[Ik,A]=Ij,A为非终结符，则置GOTO（Ik,A）=j；(5)分析表中凡不能用规则(1)-(4)填入信息的空白栏均置为“error”。(2)若项目[A

，a]属于Ik，则置ACTION[k,a]为“rj”，其中j是产生式的编号;102例：已知文法G[S]:S→id|V:=E V→id E→V|n求其LR(1)的分析表，并判断id:=id∈L(G)?(3)LR(1)分析表(2)识别文法活前缀的DFA解:(1)拓广文法(4)分析过程103解:(1)拓广文法并对产生式进行编号0：S’→S1：S→id2：S→V:=E3：V→id4：E→V5：E→n(2)识别文法活前缀的DFA[S→V.:=E,$][S→V:=.E,$][E→.V,$][E→.n,$][V→.id,$][Sid.,$][Vid.,:=][S’→.S,$][S→.id,$][S→.V:=E,$][V→.id,:=]start[S

S.,$][E→V.,$]V:=idVS[S→V:=E.,$][E→n.,$]nE01234567[V→id.,$]id8104(3)LR(1)分析表id := n $ S V E 012345678Action gotoS2 1 3 ACC R3 R1 S4 S8 S7 6 5 R2 R4 R5 R30S’→S1S→id2S→V:=E3V→id4E→V5E→n[S→V.:=E,$][S→V:=.E,$][E→.V,$][E→.n,$][V→.id,$][Sid.,$][Vid.,:=][S’→.S,$][S→.id,$][S→.V:=E,$][V→.id,:=]start[S

S.,$][E→V.,$]V:=idVS[S→V:=E.,$][E→n.