编译原理
复 习
? 题型：填空、选择、简答题、综合题
第一章 编译器概述
复习要点：
1、编译程序的总框架，编译程序工作的大致过程。
2、理解一下概念：编译、解释、翻译、编译前端、后端、遍
? 计算机执行用高级语言编写的程序主要有两种途径：解释和编译
? 编译：专指由高级语言转换为低级语言
? 编译和解释的区别： 是否产生目标程序
? 编译程序的五个阶段：词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成
? 此外还包括：表格处理和出错处理
第二章 词法分析
复习要点：
1、了解词法分析器的任务
2、掌握状态转换图
3、正规式：与正规集的转换，判断等价
4、有限自动机：NFA确定化、DFA最简化、正规式到DFA的转换
? 词法分析器（扫描器）的任务：从源程序中识别出一个个具有独立含义的最小语法单位。
? 扫描器的输出格式：二元式序列（单词种别，单词符号的属性值）
? 状态转换图：结点代表状态，用圆圈○表示。
状态之间用箭弧→连结，弧上的标记指明在射出弧的结点状态下可能出现的输入字符
初始状态 接受状态
? 正规式和有限自动机
? 正规式和正规集的转换
? 给出正规式，要求写出相应的NFA、DFA
? 给出正规集，要求写出相应的NFA、DFA
1、正规式和正规集
? 三种运算： “?”读为“或”， “? ”读为“连接” “*”读为“闭包”
? 转换
? 正规式等价： 两个正规式所表示的正规集相同，则称两个正规式等价
令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:
1. ε和?都是Σ上正规式，它们表示的正规集为{ε}和?
2. 若a是Σ上的字符，则a是正规式，它表示的正规集为{a}
3. 若r和s都是Σ上的正规式，他们表示的正规集记为L(r)和L(s)，则
（a） r|s是正规式，表示集合L(r)∪L(s)，
（b） rs是正规式，表示集合L(r)L(s)，
（c） r*是正规式，表示集合(L(r))*，
（d）(r)是正规式，表示的集合仍然是L(r)。（加括弧改变优先级、结合性）
? 有限自动机
1、确定的有限自动机 M=(S，Σ，δ，S0，F) 其中:
1. S —有穷状态集
2. Σ —输入字母表
3. δ —映射函数(也称状态转换函数) S×Σ→S δ(s,a)=S’ , S, S’ ∈S, a∈Σ
4. s0 —唯一的初始状态 s0 ∈S
5. F—终止状态集 ZíS
2、不确定的有限自动机 M= (S, Σ,δ,S0, F) 其中:
1. S —有限状态集（非终极符集合）；
2. Σ —输入字母表（终极符集合）；
3. δ —转换函数S ′ (è?{e}) ? P(S)， 即S ′ ?*到S的幂集(2S)的一种映射；
4. S0 —唯一的初始状态集合 （非空）S0∈S
5. F—终止状态集合 FíS
DFA
是NFA的特例，对于每个NFA M存在一个DFA M”，使L(M)=L(M”)。
? NFA的确定化 ：子集法
具有e转移的NFA确定化
? DFA的化简：分割法
●一个有穷自动机是化简的 ? 它没有多余状态并且它的状态中没有两个是互相等价的。
●对于任一个DFA，存在一个唯一的状态最少的等价的DFA
不含ε弧的NFA确定化举例
例：把右图确定化
I0 = {0}
(I0,a) = {0,1} = I1
(I0,b) = {1} = I2
(I1,a) = {0,1} = I1
(I1,b) = {1} = I2
(I2,a) = {0} = I0
(I2,b) =?
? 例：化简下图，使其最小化。
? 从正规式到有限自动机
1、从正规式构造NFA
2、把NFA变成DFA
3、将DFA化简
? 正规式分裂规则：
第三章 语法分析（自上而下）
? 语法分析器的任务：
按照语言的语法构成规则，识别输入的符号串能否构成一个句子
? 语法分析的理论基础
上下文无关文法和下推自动机
文法：描述语言语法结构的形式规则。
乔姆斯基（Chomsky）对文法的分类：
0型文法 1型文法 2型文法 3型文法
文法 G = (VT , VN, S, P)
0型文法：a ? b，a , b ? (VN èVT)*, | a | 3 1
1型文法：| a | ￡ | b |，但S ? e可以例外
2型文法：A ? b，A?VN , b ? (VN ∪VT)*
3型文法：A ? aB或A ? a，A, B?VN , a ?VT
短语文法、上下文有关文法、上下文无关文法、正规文法
? 分析树：表示语言的句子结构，推导的图形表示
（1）子树：除叶子结点之外的任意结点连同它的所有子孙结点构成子树。
（2）句型：在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。
（3）短语：子树的末端符号自左到右连成串，相对于子树树根而言称为短语。
? 简单短语（直接短语）：若短语事某子树根经过1步推导得到的，则称之为该子树根的简单短语。
（4）句柄：句型中的最左简单短语。 注：句柄是最左归约时要寻找的简单短语。
? 自上而下：
消除左递归：
消除直接左递归： P ?Pa|b
消除后：P b?P’
P’ ? aP’|e
消除间接左递归：
? 自上而下语法分析包括：递归下降分析程序和预测分析程序
预测分析程序：
预测分析表
是一矩阵M[A,a]，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素M[A,a]是存放A的一个侯选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。
? 求首符集（First集）
假定a是文法G的一个符号串， a ?V* ，则First(a)＝{a| a ?a……,a ?VT }
注：1)若a e?,那么?e First(a)。
2)First(a)集合是a的所有可能推导出的开头终结符或e所组成的集合。
? 求随符集（Fol
low集）
假定S是文法G的开始符号，对于G的任何非终结符A，Follow(A)＝{a|S ?…Aa…,a ?VT }
注：1)若 S?…A,则规定：#? Follow(A)。
2)Follow(A)集合是指在所有句型中紧跟A之后的终结符或#所组成的集合。
? LL(1)文法：
若文法G的预测分析表M中不含有多重定义项，则称G为LL (1)文法。
注：1)LL(1)文法是无二义的，二义文法一定不是LL(1)文法。
2) LL的含义是从左到右扫描输入串，采用最左推导分析句子。
3)数字1表示分析句子时需向前看一个输入符号。
证明定理
文法G是LL(1)文法当且仅当对于G的每个非终结符A的任何两个不同产生式A a?|b有：
1）First(a) ∩First(b)=F
2）若?e First(b) ，则First(a) ∩Follow(A)= F
第四章 自下而上语法分析
? 分析过程思想：
是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到达到文法的开始符号为止的过程。
? LR：自左至右扫描，最右推导的逆过程。
? LR分析法寻找可归约句柄的依据
历史： 记录在栈内的符号串移进、归约的历史情况
展望： 预测句柄之后可能出现的信息；
现实： 读头下的符号。
? LR分析法通过LR分析器来实现。
? LR分析器包括两部分：总控程序和分析表；
分析表——LR分析器的核心
? 分析表构成：
动作表(ACTION) 、转向表(GOTO)
注：Si表示状态， ai表示终结符，Ai表示非终结符。
? 动作表ACTION
ACTION[S,a]表示在当前状态S下，面临读头下的符号a所应采取的动作。
注：该动作有四种可能：移进、归约、出错、
接受
? 转向表GOTO
GOTO[S,X]：若X ?VT ，表示在当前状态下，读入X应转向什么状态；若X ? VN ，表示当前栈顶句柄归约成X后，应转向什么状态。
? 注：表中符号的含义：
Sj ： Shift j，指将读入符号a移进栈内并转到j状态，栈顶变成（j,a）；
rj ： Reduce j,按第j号产生式进行归约；
acc ： accept , 分析成功；
空白格 ：出错标志，若填入相应出错处理程序的编号，便转到相应程序处理。
? 构造LR(0)分析表的基本思想：
只根据历史信息识别呈现于栈顶的句柄。
注：LR(0)分析表构造的思想和方法是构造其它LR分析表的基础。
? 构造LR(0)分析表的基本策略：
构造文法G的一个有限自动机，它能识别文法中的所有活前缀。
活前缀的概念：
指规范句型的一个前缀，这种前缀不含句柄之后的任何符号
活前缀有两种类型：
1）归态活前缀： 活前缀的尾部正好是句柄之 尾，这时可以进行归约。归约之后又成为另一句型的活前缀。
2）非归态活前缀：句柄尚未形成，需要继
续移进若干符号之后才能形成句柄。
? 构造自动机识别活前缀
对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀。
由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，此“状态”称为“项目”。这些自动机的全体就是能识别所有活前缀的有限自动机。
项目: 在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目（简称项目）。
注：圆点在产生式中的位置不同则是不同项目。
（1）可以把圆点理解为栈内外的分界线。
（2）产生式右部符号串的长度为n，则可以分解为n+1个项目。
（3）产生式A?ε只有一个项目A??。
LR(0)分析表的构造算法
? 构造LR(0)分析表
设C={I0,I1,…In},以各项目集Ik(k＝0，…,n)的k作为状态序号，并以包含S`??S的项目集作为初始状态，同时将G`文法的产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：
1)若项目A?α?aβ属于Ik状态且GO(Ik,a)= Ij,a为终结符，则置ACTION[k,a]=Sj; 即：移进a，并转向Ij状态。
2)若项目A?α??Ik,则对任何终结符a(包括语句结束符＃),置ACTION[k,a]=rj; 其中，j为产生式Aa? 的编号，即根据j号产生式进行归约。
3)若项目S` ? S?属于Ik, 则置ACTION[k,＃]=accept,简写为acc;
4)若GO(Ik ，A)= Ij,A是非终结符，则置GOTO[k,A]=j;
5)分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。
? LR(0)文法
定义：若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是LR(0)文法。
SLR分析表
SLR是LR(0)的一种改进，它在归约 时除了考虑历史情况之外还考虑了一点现实。
? 构造SLR分析表的算法
设C={I0,I1,…In},以各项目集Ik(k＝0，…,n)的k作为状态序号，并以包含S` ??S的项目集作为初始状态，同时将产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：
1)若项目A?α?aβ属于Ik状态且GO(Ik,a)= Ij,a为终结符，则置ACTION[k,a]=Sj; 即：移进a，并转向Ij状态。
2)若项目A?α? ?Ik,则对任何终结符a ? Follow(A),置ACTION[k,a]=rj；其中j为产生式Aa?的编号，即根据j号产生式A?α进行归约。
3)若项目S` ? S?属于Ik, 则置ACTION[k,＃]=acc;
4)若GO(Ik ，A)=Ij,A是非终结符，则置GOTO[k,A]=j;
5)分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。
注：1）若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是SLR文法。
2)二义文法决不是LR文法。
3)
SLR分析法包含的展望信息是体现在利用了Follow(A)信息，可以解决“归约-归约”冲突
4) SLR分析法没有包含足够的展望信息，不能完全解决“移进-归约”冲突，需要改进。
语法制导翻译和中间代码生成
? 中间代码四种形式
? 逆波兰式
? 四元式：最常用的形式
? 三元式
? 树形表示法
后缀表示式(逆波兰表达式)
Operand1 Operand2 Operator
四元式形式:
(Operator,Operand1,Operand2,Result)
控制语句中布尔式E翻译成的四元式为以下三种：
? (jnz,A1,_,P)
If A1 then goto P
? (jθ,A1, A2,P)
If A1θA2 then goto P
? (j, _, _ ,P)
Goto P
注：这些四元式都是转移四元式，其中P为出口的四元式序号。与E的真假值相对应的分别为“真出口”和“假出口”两类四元式。
例如：把语句if A∨B
(2)(j,__,(3)) ;若A为假，看∨右边的表达式值
(3)(j<,B,D,(5)) ;真出口; ∨右边的表达式值为真
(4)(j,_,_,(P+1)) ;假出口; ∨右边的表达式值为假
(5) S1语句的第一个四元式 ……
(P)(j,_,_,(q)) ;执行完S1代码后跳过S2代码段
(p+1) S2语句的第一个四元式 ……
(q)此语句的后继语句
运行时存储空间的组织和管理
? 存储单元分配策略
1、静态存储分配
2、动态存储分配
? 栈式存储分配
? 堆式存储分配
? 栈式存储管理
1、允许过程(函数)递归调用的数据存储管理
2、程语言的栈式存储管理
1)根据嵌套过程语言的规定，由变量的最小作用域原则，一个过程可以引用包围它的任意外层过程所定义的变量和数组。所以，运行时过程必须知道它所有直系外层过程的最新活动记录的地址。
2)由于允许递归，过程活动记录的位置是动态变化的。因此，每个活动记录中必须设法记住直系外层的最新活动记录的位置，以处理递归。
层次显示表display
每进入一个过程，在建立其活动记录区的同时，为它建立一张层次显示表，以登记它所有直系外层最新活动记录的首址和本过程活动记录的首址
注：直系外层是指从0层开始直到当前过程，即当前过程的所有直系祖先；
第一章 引论
翻译器：能够将一种语言转换成另一种语言的软件，而且后者与前者在逻辑上是等价的。源语言—>目标语言
编译：专指由高级语言转换为低级语言。程序设计语言——>编译程序——>机器语言
解释：接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。
特点：
1．编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数PL采用此种方法翻译
2．解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Java等。
基本功能：二者相同
所采用的技术：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。
1.1 词法分析
任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。
单词：是高级语言中有实在意义的最小语法单位，它由字符构成。
词法分析依照词法规则，识别出正确的单词，转换成统一规格，备用。
转换
对基本字、运算符、界限符的转换
标识符的转换
常数的转换
转换完成后的格式：（单词种别，单词符号的属性值）
二元式表示
（单词种别，单词符号的属性值）
描述词法规则的有效工具是正规式和有限自动机。
1.2 语法分析
任务：根据语言的语法规则，把单词流组成各类语法单位，如：短语、句子、过程、程序
语法规则：语言的规则，又称为文法；规定单词如何构成短语、语句、过程和程序。
语法规则通常用上下文无关文法描述。
position := initial + rate * 60;
表达式的语法特征：
? 任何一个标识符都是表达式；
? 任何一个数都是表达式；
? 如果e1和e2都是表达式，那么
? e1 + e2
? e1 * e2
? (e1)
也都是表达式
? 语法分析有两种方法：
推导(Derive)和规约(Reduce)
? 语法分析过程也可以用一棵倒着的树来表示，这棵树叫做分析树
1.3 语义分析
? 任务：检查程序的语义正确性，以保证程序各部分能有意义的结合在一起，为以后的代码生成阶段收集类型信息
? 语义分析阶段的重要工作：类型检查
1.4 中间代码生成
? 任务：根据语义规则产生一种介于源语言与目标代码之间的一种中间代码。
中间代码是不依赖于机器但是又便于生成依赖于机器的目标代码的一种结构简单、含义明确的记号系统
? 中间代码形式：逆波兰式、 四元式、三元式
1.5 代码优化
任务：对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码。
原则：等价变换
主要方面：公共子表达式的提取、合并已知量、删除无用语句、循环优化等。
1.6 目标代码生成
任务：把经过优化的中间代码转化成特定 机器上的低级语言代码
目标代码的形式
? 绝对指令代码:可立即执行的目标代码。
? 汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行。
? 可重定位指令代码：先将各目标模块连接起来，确定变量、常数在
主存中的位置，装入主存后才能成为可以运行的绝对指令代码。
1.7 符号表管理
表格作用：用来记录源程序的各种信息以及编译过程中的各种状况。
与编译前四阶段有关的表格有：
符号表、常数表、标号表、分程序入口表、中间代码表等。
符号表：用来登记源程序中的常量名、变量名、数组名、过程名等，记录它们的性质、定义和引用情况。
1.8 错误诊断和报告
任务：如果源程序有错误，编译程序应设法发现错误，并报告给用户。
完成：由专门的出错处理程序来完成
错误类型：
? 语法错误:在词法分析和语法分析阶段检测出来。
? 语义错误：一般在语义分析阶段检测。
1.9 阶段的分组
编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化
编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成
遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。
注：遍与阶段的含义毫无关系。
要在某机器上为某种语言构造一个编译程序，必须掌握下面三个方面的内容：源语言，目标语言，编译方法。
本章小结：基本概念：翻译器、编译器、解释器、源语言、目标语言、前端、后端、遍。编译过程分哪些阶段？各个阶段完成的主要功能和采用的主要方法。
第二章 词法分析
? 词法分析器：实现词法分析的程序
? 词法分析的任务：从左至右扫描源程序的字符串，按照词法规则识别出源程序中具有独立含义的最小语法单位——单词。
? 和用户接口的其他任务：
---滤掉注释和（由空格、制表符等引起的）空白
---其他预处理工作
? 词法分析器作为一个独立的子程序
2.1 单词及属性
2.1.1 词法记号、模式、词法单元
词法记号：按照某个模式（或规则）识别出的元素（一组）。 如：关键字、算符、标识符、常数、标点符号、字符串
词法单元：被识别出的元素，又称单词，源程序中具有独立含义的最小语法单位。
模式：产生和识别元素的规则。
词法记号 词法单元举例 模式的非形式描述
var var var
for for for
relation < , < = , = , … < 或 <= 或 = 或 …
id sum, count, D5 由字母开头的字母数字串
num 3.1, 10, 2.8 E12 任何数值常数
literal “seg. error” 引号“和”之间的任意字符串，但引号本身除外
2.1. 2 单词的属性
词法分析器的输出形式： 二元式（单词种别，单词符号的属性值）
例：position := ini
tial + rate * 60的记号和属性值：
?id，指向符号表中position条目的指针?
?assign _ op， ?
?id，指向符号表中initial条目的指针?
?add_op，+?
?id，指向符号表中rate条目的指针?
?mul_ op, *?
?num，整数值60?
2.1.3 词法错误
? 词法分析器对源程序采取非常局部的观点难以发现下面的错误： fi (a == f (x) ) …
? 错误恢复策略
---紧急方式的恢复
---错误修补
2.2 单词的描述和识别
2.2.1 串和语言
首先表述一些基本 术语和概念
---符号：一个抽象实体,是语言中最基本的不可再分的单位。例如字母是符号,数字也是符号。
---字母表：符号的非空有限集合，因此字母表也称为字符类或符号集。例：? = {0, 1}
---串：符号的有穷序列，例：00 11 10 是字母表? ={0, 1}上的符号串
---符号串的长度： 如果某符号串x中有m个符号，则称其长度为m，表示为｜x｜=m，如001110的长度是6。
---空符号串：即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0
---语言：字母表上的一个串集 。例：{?, 0, 00,000, …}, {?}, ?
---句子：属于语言的串
? 串的运算：
---连接：xy， s? = ?s = s
---积（指数）：s0为?，si为si -1s（i > 0）
例1：例如 x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5
例2：符号串自身连接n次得到的符号串 an 定义为 aa…aa n个a a1=a, a2=aa且a0=ε
例3：若x=AB 则：x0 = ε，x1 =AB，x2 = ABAB，x3 = ABABAB，xn = xxn-1 = xn-1x (n>0)
? 语言的运算
---合并：L ? M = {s | s ?L 或 s ? M }
---连接：LM = {st | s ? L 且 t ? M}
---指数：L0是{? }，Li是Li -1L
---闭包：L? = L0 ? L1 ? L2 ? …
---正闭包： L+ = L1 ? L2 ? …
例：若 L={a, b}, M={c, d}则 LM={ac, bc, ad, bd}， L*={ε, a, b, aa, bb, ab, ba, aaa, ...}，L+={ a, b, aa, bb, ab, ba, aaa, ...}。
2.2.2 正规式
正规式：又称正规表达式，是描述单词构造方法的一种形式化工具，每个正规式r表示一个语言L(r)，正规式表示的语言叫正规集。
? 下面是正规式和它所表示的正规集的递归定义。
令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:
1. ε和?都是Σ上正规式，它们表示的正规集为{ε}和?
2. 若a是Σ上的字符，则a是正规式，它表示的正规集为{a}
3. 若r和s都是Σ上的正规式，他们表示的正规集记为L(r)和L(s)，则
（a） r|s是正规式，表示集合L(r)∪L(s)，
（b） rs是正规式，表示集合L(r)L(s)，
（c） r*是正规式，表示集合(L(r))*，
（d）(r)是正规式，表示的集合仍然是L(r)。（加括弧改变优先级、结合性）
注：1） “?”读为“或”（也有使用“+” 代替 “?” 的）； “? ”读为“连接”，一般可省略
２）仅由有限次使用上述三个步骤而得到的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。二者关系：正规式定义正规集，正规集构造正规式
? 运算的优先级与结合性
若正规式优先级和结合性做下述约定:
1. 三种运算均具有左结合性质；
2. 优先级从高到低顺序排列为: 闭包运算、连接运算、或运算。
3.括号可以改变运算的优先次序
则正规式中不必要的括号可以被省略。
例如，(a)|(((b)*)(c))可以简化成a|b*c。
? 正规式的例子 ? = {a, b}
正规式 正规集
---a | b {a, b}
---(a | b) (a | b ) {aa, ab, ba, bb}
---aa | ab | ba | bb {aa, ab, ba, bb}
---a* 由字母a构成的所有串集,包括ε
---(a | b)* 由a、b构成的所有串集,包括ε
? 正规式的等价：不同算术表达式可以表示同一个数，如3+5、5+3、2+6等均表示8。不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。
? 正规式等价的判定：利用正规式的等价性可以化简复杂的正规式。正规式的等价性判定可以采用两种方法：
---根据定义，证明不同的正规式表示同一集合
---根据下述正规式的代数性质进行运算
? 正规式的代数性质
--- 1．r?s=s?r “或”服从交换律
--- 2．r?(s?t)=(r?s)?t “或”的可结合律
--- 3．(rs)t=r(st) “连接”的可结合律
--- 4．r(s?t)=rs?rt (s?t)r=sr?tr 分配律
--- 5． ?r=r, r?=r ?是“连接”的恒等元素
---６． r* = (r|ε) * *和?之间的关系
---７． r* *＝ r* *是幂等的
例：试证 b(ab)* = (ba)*b
证明：L(b(ab)* ) ={b, bab, babab, …}，L((ba)* b) ={b, bab, babab, …}。正规集的前n 项相同，可知它们的正规集是相等的，所以正规式b(ab)* = (ba)*b
2.2.3 正规定义
对正规式命名，使表示简洁。
d1 ? r1，d2 ? r2，….，dn ? rn
各个di的名字都不同，是被定义的正规表达式的名字
每个ri都是? ?{d1, d2, …, di-1 }上的正规式
? 简化正规式描述：
（１）一个或多个实例：＋，若r是表示L(r)的正规式，则r+是表示一个或多个ｒ的所有串的集合，且下述等式成立:
r+ = rr* = r*r，r* = r+|ε +与*具有相同的运算结合性和优先级
（２）零个或多个：？ 若r是正规式，则（r）?是表示L(r)∪{ε}的正规式，且下述等式成立: r?=r|ε
?也可以与*具有相同的运算结合性和优先级
注意：引入算符？的主要目的是为了回避不可以直接通过键盘输入的字符ε。例如： E(+|-|ε) 可以改写为：E(+|-)?
例：可以用num ? digit+ (.digit+)? (E(+|?)? digit+)?表示无符号数
（３）字符组：可以有如下两种形式：枚举:如[abc]，
它等价于a|b|c分段: 如[0-9a-z]，它等价于：[0123456789abcdefghijklmnopqrstuvwxyz]
2.2.４ 状态转换图
? 状态转换图是设计词法分析程序的一种好的途径。
? 结点代表状态，用圆圈○表示。
? 状态之间用箭弧→连结，箭弧上的标记(字符)代表在射出结点(即箭弧始结点)状态下可能出现的输入字符或字符类。
? 一张转换图只包含有限个状态(即有限个结点)，其中一个为初态，至少一个为终态(双圈表示)。
2.3 有限自动机（FA）
? 是一种识别装置，准确识别正规集
? 具有离散输入输出系统的数学模型。这种系统具有有限数目的内部状态，系统的当前状态概括了过去的输入处理的信息。系统只需要根据当前所处的状态和面临的输入字符就可以决定系统后继的行为。
? 有穷自动机分为两类：
确定的有穷自动机(Deterministic Finite Automata)--DFA
不确定的有穷自动机(Nondeterministic Finite Automata)--NFA
2.3.1 确定的有限自动机（DFA）
一个确定的有穷自动机（DFA）M是一个五元式：M=(S,Σ,δ,s0, F) 其中:
1. S —有穷状态集
2. Σ —输入字母表
3. δ —映射函数(也称状态转换函数) S×Σ→S δ(s,a)=S’ S, S’ ∈S, a∈Σ
4. s0 —唯一的初始状态 S0 ∈S
5. F—终止状态集（可空） Z?S
还可以表示成状态转换图
DFA的确定性表现在：
? 对任何状态s∈S，在读入了输入符号a ∈ Σ 之后，能够唯一地确定下一个状态
? 从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。
? DFA M对字符串的识别：对于Σ中的任何字符串α，若存在一条从初态结点到终态结点的通路，且这条通路上所有弧的标记符号连接成的串等于α。
? 若M的初态结点又是终态结点，则空字ε可为M所识别。
? DFA M所能识别语言：能被DFA M所接受的字符串的集合，记为L(M).
对于任何两个有穷自动机M和M′，如果L(M)=L(M′)，则称M与M′是等价的.
? DFA的构造
例：构造一个DFA ，他接受字母表{a,b,c}上以a或b开始的字符串，或以c开始所含一个a的字符串。
所以，DFA M=({0,1,2,3},{a,b,c},f,0,{1,2,3})
2.3.2 不确定的有限自动机（NFA）
? 一个不确定有限自动机（NFA)是一个五元式：M= (S, Σ,δ,S0, F) 其中:
1. S —有限状态集（非终极符集合）；
2. Σ—输入字母表（终极符集合）；
3. δ —转换函数S ? (??{?}) ? P(S)， 即S ? ?*到S的幂集(2S)的一种映射；
4. S0 —唯一的初始状态集合 （非空）S0∈S
5. F—终止状态集合 F?S
? 一个NFA的例子
例：设NFA M=（{0， 1 ，2 ，3，4}，{a，b}，δ，{0 }，{2，4}）其中δ定义为
δ（0
，a）={0，3}
δ（0，b）={0，1}
δ（1，b）={2}
δ（2，a）={2}
δ（2，b ）={2}
δ（3，a ）={4}
δ（4，a ）={4}
δ（4，b ）={4}
? 非确定性是指读入相同的输入字符后继状态可以有多个
? DFA是NFA的特例，对于每个NFA M存在一个DFA M”，使L(M)=L(M”)。
（1）没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边；
（2）对每一个状态s和每一个字符a，最多有一个下一状态。
? 正规式 正规集 有限自动机
2.3.3 NFA到DFA的变换
? 非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的
NFA M’ ——构造成一个——> DFA M 使得L(M)=L(M’)
? 主要思想：DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.
? 变换方法：子集法
? 不含ε的NFA确定化算法
由NFA M= (S, Σ,f,S0, Z)构造一个等价的DFA ） M’= (Q, Σ,δ,I0, F)
（1） 取I0=S0， I0∈Q ；
（2）若状态集Q中有状态Ii={S0，S1，……Sj}, Sk ∈ S，0≤k ≤j, 而且M机中有f=（ {S0，S1，……Sj}, a）= f(S0,a)? f(S1,a) ? ……? f(Sj,a) ={S0, S1 , ……St}=It 若It不在Q中，则将It加入Q中；
（3） 重复步骤（2），直到Q中无新状态加入为止
（4） 取终态F={I|I ∈Q,且I∩Z<>Φ}
? 不含ε弧的NFA确定化举例．例：把右图确定化
I0 = {0}
(I0,a) = {0,1} = I1
(I0,b) = {1} = I2
(I1,a) = {0,1} = I1
(I1,b) = {1} = I2
(I2,a) = {0} = I0
(I2,b) =?
? DFA的状态转换表
? 具有?转移的NFA确定化过程
对任何一个具有?转移的不确定的有穷自动机NFA N，一定存在一个不具有?转移的确定的有穷自动机NFA Ｍ ，使得L(M)=L(N)。
方法：求?闭包（ ? -closure）,将此闭包（状态子集）作为DFA的一个状态使用，而将NFA上的状态之间的转换变为闭包之间的转换。
运算：s代表NFA的状态，T代表NFA的状态集
? -closure（s）：从NFA的状态s出发，只用? 转换能到达的状态集合
? -closure（T）: NFA的状态集合{s|s ∈ ? -closure（t）&t ∈T}
move(T,a): NFA的状态集合{s|s=move(t,a) &t ∈T} 记作Ta = ε-closure(S)
例：
I={1}, ?-closure(I)={1,2}；
I={5}, ?-closure(I)={5,6,2}；
move({1,2},a)={2,3,4,5,6,7,8}；
? 过程：
（1） 取I0= ?-closure(S0)， I0 ∈Q；
（2）若状态集Q中有状态Ii={S0，S1，?-?-Sj},
Sk=S，0≤k ≤j,而且有It= ?-closure(f(Ii,a))
若It不在Q中，则将It加入Q中；
（3） 重复步骤（2），直到Q中无新状态加入为止
（4） 取终态F={I|I ∈Q,且I∩Z<>Φ}
? 具有?转移的NFA确定化例子：
2.3.4 DFA的化简（最小化）
? 一个有穷自动机是化简的 ? 它没有多余状态并且它的状态中没有两个是互相等价的。
? 一个有穷自动机可以
通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。
? 对于任一个DFA，存在一个唯一的状态最少的等价的DFA
? 多余状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。——死状态
? 等价状态 ：状态s和t的等价条件是:
1) 一致性条件：状态s和t必须同时为终态或非终态
2) 蔓延性条件：对于所有输入符号,状态s和t必须转换到等价的状态里.
DFA的最小化的方法（分割法）
? 方法：将DFA的状态分割成一些互不相交的子集。
? 算法：
（1）将所有状态分成两个子集－－－终态集和非终态集
（2）运用判定状态等价原则分别对两个子集的状态进行分析和划分，把互相等价的状态构成一个子集，若发现不等价，继续划分，这样FA的状态被分成互不相交的若干子集。
（3）从每个子集中选出一个状态做代表，即可构成简化的FA
? DFA化简的例子：
方法
1. {A, B, C}, {D}
move({A, B, C}, a} = {B}
move({A, B, C}, b} = {C, D}
2. {A, C}, {B}, {D}
move({A, C}, a} = {B}
move({A, C}, b} = {C}
? 例：化简下图，使其最小化。
2.4 从正规式到有限自动机
? 从正规式构造NFA（本节介绍）
? 把NFA变成DFA （子集构造法，已介绍）
? 将DFA化简 （划分法，已介绍）
? 方法：
(1)由正规式α构造一个仅有两个节点x,y的状态图；——>
(2)按所引入的三条正规式分裂规则分裂α；
(3) 重复步骤（2）直到每个弧上的标记是Σ上的一个字符为止；
(4) 将得到的NFA M（因为包含? 弧）进行确定化和化简就得到DFA
? 正规式分裂规则：
? 对于加括号的正规式(s)，使用N(s)本身作为它的NFA。
例：根据正规式（a|b)*(aa|bb)(a|b)*构造
DFA M
第三章 语法分析
? 语法分析器
? 功能：按照语言的语法构成规则，识别输入的符号串能否构成一个句子，规则用文法的产生式来定义。对给定的一个输入串，通过建立与输入串匹配的语法分析树来识别是否是句子。
3.1 上下文无关文法
? 文法：描述语言的语法结构的形式规则。
例：一个句子，Young man like pop music.
〈句子〉 ——> 〈主语〉〈谓语〉
〈主语〉 ——> 〈形容词〉〈名词〉
〈谓语〉 ——> 〈动词〉〈宾语〉
〈宾语〉 ——> 〈形容词〉〈名词〉
〈形容词〉——> Young | pop
〈名词〉 ——> men｜music
〈动词〉 ——> like
? 文法的相关概念
（1）非终结符：出现在规则的左部、用<>括起来、表示一定语法概念的词。非终结符集合用VN表示。
（2）终结符：语言中不可再分割的字符串(包括单个字符组成的串)。注：终结符是组成句子的基本单
位。终结符集合用VT表示。
(3) 开始符号：表示所定义的语法范畴的非终结符。 注：开始符号又称为识别符号。
(4) 产生式：是用来定义符号串之间关系的一组(语法)规则。形式：A ? ? （A产生? ）
（5）推导：推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。
最左（右）推导：每次使用一个规则，以其右部取代符号串最左（右）非终结符。注：最左推导和最右推导称为规范推导。
（6）归约：归约是推导的逆过程，即，从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程。
最左(右)归约是最右(左)推导的逆过程。注：最左归约和最右归约称为规范归约。
(7)句型、句子和语言
句型：是从文法的开始符号S开始，每步推导（包括0步推导）所得到的字符串?。
记作：S ?，其中? ? （VN? VT ）* 句子：是仅含终结符的句型。
语法规则为：
<句子>?<主语><谓语>
<主语> ?<形容词><名词>
<谓语> ?<动词><宾语>
<宾语> ? <形容词><名词>
<形容词> ?Young | pop
<名词> ?men | music
<动词> ?like
例如：根据英语的语法规则，看能否用最左推导得出“Young men like pop music”是个语法正确的句子；在推导过程中有哪些句型。
性质：
? 如果A→γ是产生式， α和β是文法的任意符号串，那么可以说：αAβ=>αγβ；
? 如果对于任意文法符号序列α1，α2，...αn，有α1=>α2=>...=>αn，则我们称这个序列是α1到αn的一个推导；
? ?α，有α=*>α，即推导具有自反性；若α=*>β，β=*>γ，则α=*>γ，即推导具有传递性。
E ? E + E | E * E | (E ) | ? E | id
最左推导
E ? lm ?E ? lm ?(E) ? lm ?(E + E)
? lm ?(id + E) ?lm ?(id + id)
最右推导
E ? rm ?E ? rm ?(E) ? rm ?(E + E)
? rm ?(E + id) ?rm ?(id + id)
(8)文法规则的递归定义 非终结符的定义中包含了非终结符自身。使用文法的递归定义要谨慎.
例如：字母表A＝{0,1}, 语法规则为： <整数> → <数字><整数>|<数字> ,<数字> →0|1
再如：字母表A＝{0,1}, 语法规则为： <整数> → <数字><整数> ,<数字> → 0|1
? 上下文无关文法是四元组（VT , VN , S, P）
VT : 终结符集合
VN : 非终结符集合
S : 开始符号
P : 产生式集合， 产生式形式 : A ? ?
例：简单算术表达式的上下文无关文法可表示如下：
VN ={E} VT ={+，*，(，)，-，id} S=E
P: E → E + E （1）
E → E * E （2）
E →（E） （3） (G3.1)
E → -E （4）
E → id （5）
例：G： S→0S1， S→01
S ?0S1 ?00S11 ?000S111 ?00001111
G的句型S,0S1 ,00S11 ,000S111,00001111
G的句子00001111, 01
? 上下文无
关文法如何定义语言：:从文法的开始符号出发,反复连续使用产生式,对左边的非终结符进行替换和展开
3.1.3 分析树：推导的图形表示，它的表示很直观，并且同时反映语言结构的实质和推导过程。
? 分析树被定义为具有下述性质的一棵树。
（1） 根由开始符号所标记；
（2） 叶结点: 由终结符或非终结符标记，这些标记从左至右构成一个句型
（3） 内部结点: 由非终结符标记,
? 分析树中的概念
（1）子树：除叶子结点之外的任意结点连同它的所有子孙结点构成子树。
（2）句型：在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。
（3）短语：子树的末端符号自左到右连成串，相对于子树树根而言称为短语。
简单短语（直接短语）：若短语事某子树根经过1步推导得到的，则称之为该子树根的简单短语。
（4）句柄：句型中的最左简单短语。注：句柄是最左归约时要寻找的简单短语。
? 二义性：一个句子对应多于一个语法树
例：id*id + id
E ? E * E E ? E + E
? id * E ? E * E +E
? id * E + E ? id * E + E
? id * id + E ? id * id + E
? id * id + id ? id * id + id
先进行*运算 先进行+运算
? 二义性的消除
? 文法二义不能说明程序设计语言是二义。程序设计语言不能二义。
? 消除语言二义的两种方法：
① 改写二义文法为非二义文法；
② 在分析过程中规定一些规则，在出现二义时根据这些规则确定哪棵分析树是正确的；
问题：如何将二义文法改写为非二义文法？
? 改写二义文法的关键步骤：
(a) 引入一个新的非终结符，增加一个子结构并提高一级优先级；
(b) 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。
例：E → E + E （1）
| E * E （2）
|（E） （3）
| -E （4）
| id （5）
3.2 语言和文法
? 文法的优点
? 文法给出了精确的，易于理解的语法说明
? 自动产生高效的分析器
? 可以给语言定义出层次结构
? 以文法为基础的语言的实现便于语言的修改
? 文法的问题：文法只能描述编程语言的大部分语法.
3.2.9 形式语言鸟瞰
? 文法 G = (VT , VN, S, P)根据对产生式施加的限制不同，文法可分为四类：
0型文法：? ? ?，? ? (VN ?VT)+, 且至少含有一个非终结符，? ? (VN ?VT)*
1型文法：| ? | ? | ? |，但S ? ?可以例外
2型文法：A ? ?，A?VN , ? ? (VN ∪VT)*
3型文法：A ? aB或A ? a，A, B?VN , a ?VT
? 短语文法、上下文有关文法、上下文无关文法、正规文法
? 四种文法之间的逐级“包含”关系
? 文法的简化
1、由于同一语言
可以用不同的文法来描述，显然应当选择产生式的个数最少，最符合语言特征的来描述。
2、在文法中，有些产生式对推导不起作用，要删除掉。
? 如某个产生式在推导过程中永远不会被用到，即由开始符号推导，永远推不到的左部的非终结符。
? 再如永远导不出终结符串的产生式。
? 如形如P?P的产生式。
? 简化步骤：
? 查找有无形如P?P的产生式，若有则删除；
? 若某个产生式在推导过程中永远不会被用到，删除它；
? 若某个产生式在推导过程中不能从中导出终结符，删除它。
? 最后，整理所有剩余产生式，就得到简化的文法。
构造无?产生式的上下文无关文法
? 无?产生式的上下文无关文法要满足条件
? P中要么不含有?产生式，要么只有S ? ?；
? 若S ? ?，则S不出现在任何产生式右部。
? 构造无?产生式的上下文无关文法变换算法：
G=(VN,VT,P,S) ??———> G’=(V’N,V’T,P’,S’)
（1）由文法G找出所有经过若干步推导能推出?的非终结符，放在V’N集合中。
（2）再按下列步骤构造G’的产生式集合P’；
A)若V’N集合中的某元素出现在某产生式的右端，则将它变成两个产生式：分别以?和其原型代入；将新产生式加入P’
B)不满足上一条的P中其他产生式除去?产生式后也加入P’
C)如果P中有产生式S ? ?，将它在P’中改为S ‘? ? | S，S’是新的开始符号，把它加入V’N
，形成V’N
例11：设G1=({S},{a,b},P,S),其中
P ：(0) S ? ? (1) S ?aSbS (2) S ?bSaS
(1) V’N={S}
(2)P’: (1) ? S ?abS|aSbS|aSb|ab
(2) ? S ?baS|bSaS|bSa|ba
(0) ? S’ ? ? | S
故：文法G1’=({S’,S},{a,b},P’,S’),其中
P’: (0) S’ ? ? | S
(1) S ?abS|aSbS|aSb|ab
(2) S ?baS|bSaS|bSa|ba
3.3 自上而下分析
? 语法分析的地位：是编译程序的核心部分。
? 语法分析的任务：识别由词法分析得出的单词序列是否是给定文法的句子。
? 语法分析的理论基础：上下文无关文法和下推自动机
语法分析的方式
? 自上而下语法分析
反复使用不同产生式进行推导以谋求与输入符号串相匹配。
? 自下而上语法分析
对输入符号串寻找不同产生式进行归约直到文法开始符号。
注：这里所说的输入符号指词法分析所识别的单词。
? 下推自动机模型
注：1）PDA和FA的模型相比，多了一个下推栈。
2）PDA的动作由三个因素来决定：当前状态、读头所指向符号、下推栈栈顶符号。
3）一个输入串能被PDA所接受，仅当输入串读完，下推栈变空, 控制器到达某些终态。
? 自上而下分
析的一般方法
设下推栈的初始状态包含两个符号：‘#S’，其中‘#’为栈底，‘S’为文法开始符号。整个分析过程在语法分析程序控制下进行。在语法分析中用到的文法产生式的表，称为语法表。
算法
（1）若栈顶符号x是非终结符，查询语法表，找出一个以x作为左部的产生式，x出栈，并将其右部反序入栈，且输出带记下产生式编号——推导。
（2）若栈顶符号x是终结符，且读头下的符号也是x，则x出栈，读头指向下一个符号——匹配。
（3）若栈顶符号x是终结符，但读头下的符号不是x，则匹配失败。这说明可能前面推导时选错了候选式，退回到上次推导现场(包括栈顶符号、读头的指针和输出带上信息)——回溯。
（4）回溯后选取另一候选式进行推导，若没有候选式可选，则进一步回溯。若回溯到开始符号又已无候选式可选，则识别失败。
（5）若栈内仅剩下“＃”，且读头也指向“＃”，则识别成功。
? 例：文法产生式如下，请分析符号串x*y的过程
1) S ? xAy 2) A ?** 3)A ? *
? 带回溯的自上而下分析法的缺陷
1）如果文法存在左递归，语法分析会无限循环下去。
2）若产生式存在多个候选式，选择哪个进行推导完全是盲目的。
3）回溯会引起时间和空间的大量消耗。
4）如果被识别的语句是错的，算法无法指出错误的确切位置。
? 不带回溯的自上而下分析算法
消除左递归
1)什么是左递归？左递归：文法存在产生式P ?P ?
? 直接左递归： P ?P ?
? 间接左递归： P ?A ? , A?Pb
2)消除左递归
? 消除直接左递归
? 消除间接左递归
? 消除直接左递归
设有文法G=(VN, VT ,P,S)，其中产生式P为 P ?P?|? , ? ?V+ ， ? ?V+ 且?不以P开头 将它转换为等价式：
P ??P’
P’ ? ?P’|?
一般地： 将P ?P ? 1| P ? 2|…. |P ? m|?1| ?2|….| ?n 转换为：
P ? ?1P`| ?2 p`|……| ?n P`
P` ? ? 1P`| ? 2P`|……| ? mP`| ?
? 例：文法G： (1)E ? E+T|T
(2)T ? T*F|F
(3)F ?(E)| i
转化为G`:
(1) ? E ?TE` E` ?+TE`| ?
(2) ? T ?FT` T` ?*FT`| ?
(3) ? F ?(E)| i
? 例：文法G:P ? PaPb|BaP
转化为：P ?BaPP`
P` ?aPbP`| ?
注：只有最左边的P参加变换。
? 消除左递归算法
1）把文法G的所有非终结符按任意顺序排列成
P1,P2,…,Pn,然后按此顺序执行步骤2。
2）For (I=1,I<=n,I++)
{for (k=1,k<=I-1,k++)
{把形如Pi ?Pk?的规则改写为
Pi ??1 ? |? 2 ? |……| ?n ?
/* 其中Pk
??1| ?2|……| ?n*/ }
消除Pi规则的直接左递归；}
3)删去从文法开始符号不可达的非终结符产生式。
例：对下面文法消除左递归：
(1) S ? Qc|c
(2)Q ? Rb|b
(3) R ? Sa|a
注：1）若非终结符排列顺序不同，改写后的文法也不同，但它们是等价的。
2）开始符号不能改变。
? 消除回溯
产生回溯的原因：进行推导时，若产生式存在多个候选式，选择哪个候选式进行推导存在不确定性。
消除回溯的基本原则：对文法的任何非终结符，若能根据当前读头下的符号，准确的选择一个候选式进行推导，那么回溯就可以消除。
? 消除回溯的方法：预测与提左因子
1）预测：根据读头下符号选择候选式，使其第一个符号与读头下符号相同，或该候选式可推导出的第一个符号与读头下符号相同。这相当于向前看了一个符号，所以称为预测。
注：使用了预测之后，选择候选式不再是盲目的了，所以也就无需回溯。
? 求候选式的终结首符集
令G是一个不含左递归的文法，对G的所有非终结符的各候选式?可求出它的终结首符First(?).
First(?)＝{a| ? ?a……,a ?VT }
特例:若? ??,那么?? First(?)。即， First(?)集合包括了?的所有可能推导的开头终结符或可能的?。
设A是非终结符，且A??|?，当A出现在下推栈的栈顶，且输入符号为a时，应如何选择A的候选式进行推导？这里分为四种情况：
(a)若a?First(?),而a?First(?)，则选A??
(b)若a ? First(?),而a ? First(?)，则选A??
(c) 若a ? First(?),且a ?First(?),则表示输入有错
(d)若a?First(?),且a ? First(?),则表示终结首符集相交，需改写文法，进行公因子提取。
2）提取公共左因子
将某产生式A???1| ??2|…. | ??n| ?
改写为 A??A`
A`??1|?2|…. |?n|ε
注：1)通过反复提取左因子，就能把所有非终结符的所有候选首符集变为两两不相交。
2)反复提取左因子也有一定代价，因为在提取过程中会大量引入非终结符和?产生式，增加语法分析的复杂性。
? 预测分析程序
带预测分析的PDA：在PDA中加入预测分析之后，可以消除自上而下分析中出现回溯的现象。
预测分析表
是一矩阵M[A,a]，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素M[A,a]是存放A的一个侯选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。
预测分析程序算法描述：
设栈顶符号为X，读入符号为a，则
1)若X=a=‘#’，则表示识别成功，退出分析程序；
2)若X=a?’#’，则表示匹配，弹
出栈顶符号X，读头前进一格，让读头指向下一个符号，以读入下一个符号；若X是终结符，但X?a，则调用error处理；
3)若X?VN，则查预测分析表M。若M[X,a]中存放着关于X的产生式，则弹出X，且将相应产生式右部以自右向左的顺序压入栈，在输出带上记下产生式编号；若M[X,a]中存放着出错标记，则调用相应Error处理。
? 求串?的终结首符集和非终结符A的随符集
求串?的终结首符集First(?)
? 定义：假定?是文法G的一个符号串， ? ?V* ，则First(?)＝{a| ? ?a……,a ?VT }
注：1)若? ??,那么?? First(?)。
2)First(?)集合是?的所有可能推导出的开头终结符或?所组成的集合。
? 算法：设?=X1X2…Xn，其中Xi?(VN?VT),1?i ?n,为了求?的首符集，分两步：首先求Xi的首符集，然后再求?的首符集。
1）求出文法中每个文法符号的首符集；
(1)若x ?VT ，则First(x)={x};
(2)若X?VN ，且有产生式X ?a……，则将a加到 First(X)中;若X ??, 则?也加入到 First(X)；
(3)若X ? Y1Y2…Yk，其中Yj?(VN?VT),1?j ?k,则按如下算法求First(X)
j=0; FIRST(X)={}; //初始化
REPEAT j=j+1;
FIRST(X)=FIRST(X)?(FIRST(Yj)-{?})
UNTIL ?? FIRST(Yj) 或j=k
IF (j=k 且?? FIRST(Yk))
THEN FIRST(X)=FIRST(X) ? {?}
2）求First(?)
设? =X1X2…Xn，其中Xi?(VN?VT),1?i ?n ,则按如下算法求First(?)
i=0; FIRST(?)={}; //初始化
REPEAT i=i+1;
FIRST(?)=FIRST(?)?(FIRST(Xi)-{?})
UNTIL ?? FIRST(Xi) 或i=n
IF (i=n 且?? FIRST(Xn))
THEN FIRST(?)=FIRST(?)?{?}
? 求非终结符A的随符集Follow(A)
? 定义：假定S是文法G的开始符号，对于G的任何非终结符A，
Follow(A)＝{a|S ?…Aa…,a ?VT }
注：1)若 S?…A,则规定：#? Follow(A)。
2)Follow(A)集合是指在所有句型中紧跟A之后的终结符或#所组成的集合。
? 算法：1)对文法开始符号S，将‘#’加入到Follow(S)中；
2)若B ??A?是文法G的一个产生式，则将First(?)-?加入到Follow(A)中;
3)若B ??A是文法G的一个产生式,或B ??A?是文法G的一个产生式,且? ??，则将
Follow(B)加入到Follow(A)中；
注：这里的文法必须是消除了左递归且提取了左因子后的文法。
例：对如下文法G(已加上编号)：
1.E ? TE` 2.E` ? +TE`
3.E` ?? 4.T ? FT`
5.T` ? *FT` 6.T` ??
7.F ? i 8.F ?(E)
求各非终结符号的终结首符集和随符集。
解： First(E)=First(T)=First(F)={(, i}
First(E`)={+, ?}
First(T`)={*, ?}
Follow(
E)= Follow(E`)={),#}
Follow(T)= Follow(T`)={+,),#}
Follow(F)={*,+,),#}
构造预测分析表
? 基本思想
1）若A ? ? 是一个产生式，a? First(?),那么当A是栈顶符号且将读入a时，选择?取代A匹配成功的希望最大。故，M[A,a]元素为A ? ? 。
2）若A ? ? ，而?＝ ? ，或? ? ? ；当A是栈顶符号且将读入a时，若a? Follow(A),则栈顶的A应被?匹配；此时读头不前进，让A的随符与读头下的符号进行匹配，这样输入串匹配成功的可能最大。故M[A,a]元素为A ? ? (这里?＝ ?或? ? ? )。
? 构造算法
1）假定A ??是一个产生式，a? First(?),那么当A是栈顶符号且将读入a时， A ??就应作为选用的侯选式， A ??应填入 M[A,a]中。
2）若A ??，而 ? ? First(?) ,对每个a? Follow(A), 在M[A,a]元素中应填A ??(一般填A ? ?)。
3）把所有无定义的M[A,a]都填上出错标志。
注：1）用此算法可以为任意文法G构造其分析表M。
2）若是二义文法或没有消除左递归和提取左因子的文法，构造出的M包含有重定义项。即，它们的M[A,a]中填有一个以上的产生式。
例：对如下文法G, 构造预测分析表
1.E ? TE` 2.E` ? +TE`
3.E` ? ? 4.T ? FT` 5.T` ? *FT`
6.T` ? ? 7.F ? i 8.F ?(E)
解：1）求出各非终结符的First集和Follow集
First(E)=First(T)=First(F)={(, i}
First(E`)={+, ?}
First(T`)={*, ?}
Follow(E)= Follow(E`)={),#}
Follow(T)= Follow(T`)={+,),#}
Follow(F)={*,+,),#}
2）根据算法构造预测分析表
LL(1)文法
? 定义：若文法G的预测分析表M中不含有多重定义项，则称G为LL (1)文法。
注：1)LL(1)文法是无二义的，二义文法一定不是LL(1)文法。
2) LL的含义是从左到右扫描输入串，采用最左推导分析句子。
3)数字1表示分析句子时需向前看一个输入符号。
? 证明定理
文法G是LL(1)文法当且仅当对于G的每个非终结符A的任何两个不同产生式A ??|?有：1）First(?) ∩First(?)=?
2）若?? First(?) ，则First(?) ∩Follow(A)= ?
注：可以使用这个定理直接根据首符集、随符集来判断文法是否是LL(1)。但判断之前，必须消除左递归和提取公共左因子,因为包含左递归和公共左因子的文法肯定不是LL(1)文法。
例：判断下面文法是不是LL(1)文法： S ? if E then S else S
| if E then S
| other
E ?b
3.4 自下而上分析
? 分析过程思想：是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到达到文法的开始符号为止的过
程。
注：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列。
? 分析树中的概念
（1）子树：除叶子结点之外的任意结点连同它的所有子孙结点构成子树。
（2）句型：在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。
（3）短语：子树的末端符号自左到右连成串，相对于子树树根而言称为短语。
简单短语（直接短语）：若短语事某子树根经过1步推导得到的，则称之为该子树根的简单短语。
（4）句柄：句型中的最左简单短语。注：句柄是最左归约时要寻找的简单短语。
? 自下而上分析的PDA
工作方式： 移进——归约
注：初态时，栈内仅有栈底符号“#”，读头指在最左边的单词符号上
分析过程执行的动作：
移进: 读入一个单词并压入栈，读头后移；
归约：检查栈顶若干个符号能否进行归约，若能，就以产生式的左部代替该符号，同时输出产生式的编号；
识别成功：移进——归约的结局式栈内只剩下栈底符号“#”和文法开始符号S，读头也指向语句的结束符
识别失败
例：有文法如下：
（1）S ?aAcBe (2) A ?b
(3) A ?Ab (4) B ?d
问：语句abbcde是不是该文法的合法语句
LR分析器
LR：自左至右扫描，最右推导的逆过程。
注：一般地说，大多数用上下文无关文法描述的程序设计语言均可用LR分析器予以识别。
? LR分析法的优点
? 适应文法范围更广，能力更强，与普通不带回溯的自上而下预测技术相比也要好些。
? 在自左向右扫描输入串时就能发现其中错误，并能准确指出出错位置。
? LR分析法的缺点
若用手工构造分析程序，工作量太大，且容易出错，所以必须使用自动产生这种分析程序的产生器。
? LR分析法通过LR分析器来实现。LR分析器包括两部分：总控程序和分析表；
LR分析法的基本思想：在规范归约过程中，一方面记住已移进和归约出的整个符号串，另一方面根据所用的产生式推测未来可能碰到的输入符号。
? LR分析法寻找可归约句柄的依据
? 历史：记录在栈内的符号串移进、归约的历史情况
? 展望：预测句柄之后可能出现的信息；
? 现实：读头下的符号。
注：1）LR分析法是规范归约，而规范归约的关键问题是找句柄。
2）LR分析法的基本思想符合人的思维习惯，但实现上有困难，因为基于“历史”对未来的“展望”可能存在多种可能，当把“历史”和“展望”材料综合在一起时复杂性就大大增加。
3）一般会简化对“展望”的要求，以获得切实可行的分析算法。
? 下推栈：
下推栈用于存放分