编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法

Presentation on theme: "编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法"— Presentation transcript:

1 编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法 第六章 自底向上优先分析方法 第七章 LR分析方法 第八章 语法制导翻译和中间代码生成 第九章 符号表 第一○章 代码优化 第一一章 代码生成

2 词法分析 词法分析是编译过程的第一个阶段。 主要任务：从左到右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。
词法分析的基本思路： 将单词符号的语法用有效的工具描述； 基于该描述建立单词的识别机制； 设计和实现词法分析程序

3 单词的描述技术 单词的识别机制 词法分析程序的自动构造原理 正规文法 正规式 确定有穷自动机 不确定有穷自动机 正规式和有穷自动机的等价性
词法分析程序的自动构造工具

4 单词的描述工具 某种程序设计语言中的所有单词构成一种语言。该语言的语法都能用正规文法表示。正规文法是描述单词的一种工具。 1、正规文法（回顾） 文法G=(VN,VT,P,S)，P中每一规则有A→aB或A→a ，A,BVN，aVT*，称G(S)是正规文法。 <标识符> →l|l <字母数字> <字母数字> → l|d|l<字母数字>| d <字母数字> <无符号整数> → d|d<无符号整数> l表示a-z中的任何英文字母，d表示0-9中的任何数字 由正规文法产生的语言称为正规集 除单词外，程序中包括的表达式及语句的语法需要用上下文无关文法表示。

5 2、正规式（正则表达式） 是表示正规集的工具，也是用以描述单词符号的方便工具。 正规式与正规集的定义： 设字母表为Σ，辅助字母表Σ'={，，|，·，*，（，）} ； 和都是Σ上的正规式，表示的正规集分别为{}和； 任何aΣ,a是Σ上的一个正规式，表示的正规集为{a};

6 假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2),则(e1),e1|e2,e1·e2和e1
假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2),则(e1),e1|e2,e1·e2和e1*也都是正规式，所表示的正规集分别为L(e1),L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*。 仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的集合才是Σ上的正规集。 例： ＝{a,b}， 上的正规式和相应的正规集为：

7 (a|b)*(aa|bb) (a|b)*   a b ----------- (a) 一个正规式可以表示若干个符号串,
(a|b)* a*|b* aba* (a|b)*(aa|bb) (a|b)*

8 (a|b)*(aa|bb) (a|b)* *上所有含有两个相继的a或两个相继的b组成的串
 {}   a {a} b {b} (a) {a} 一个正规式可以表示若干个符号串, (b) {b} 其正规集就是这些符号串的集合 a|b {a,b} ab {ab} a* {,a,aa,aaa,aaaa,….} b* {,b,bb,bbb,bbbb,….} (a|b)* a和b组成的所有串 a*|b* {,a,aa,aaa,aaaa,….,b,bb,bbb,bbbb,….} aba* 以ab开头后接若干个(包括0个)a组成的串 (a|b)*(aa|bb) (a|b)* *上所有含有两个相继的a或两个相继的b组成的串

9 设r，s，t为正规式，正规式服从代数规律有：
例：令＝｛d， ，e，＋，－｝，则上的正规式d*(.dd*| )(e(+|-|)dd*|)表示的是所有无符号数。 其中d为0～9中的数字。 比如：2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。 设r，s，t为正规式，正规式服从代数规律有： 1、r|s＝s|r 交换律 2、r|(s|t)＝(r|s)|t 结合律 3、(rs)t=r(st) 结合律

10 4. r(s|t) = rs|rt 分配律 (s|t)r = sr|tr 分配律 5. r=r 零一律 r=r 零一律
程序设计语言中的单词既能用正规文法表示，又能用正规式来表示. 正规式？ 正规文法: <标识符> →l|l <字母数字> <字母数字> → l|d|l<字母数字>| d <字母数字> <无符号整数> → d|d<无符号整数> l表示a-z中的任何英文字母，d表示0-9中的任何数字

11 4. r(s|t) = rs|rt 分配律 (s|t)r = sr|tr 分配律 5. r=r 零一律 r=r 零一律
程序设计语言中的单词既能用正规文法表示，又能用正规式来表示. 正规式: 标识符:e1=字母(字母|数字)* 无符号整数:e2=dd* 正规文法: <标识符> →l|l <字母数字> <字母数字> → l|d|l<字母数字>| d <字母数字> <无符号整数> → d|d<无符号整数> l表示a-z中的任何英文字母，d表示0-9中的任何数字

12 3、正规文法和正规式的等价性 一个正规语言可以由正规文法定义，也可以用正规式定义。 对于任意一个正规文法，存在一个定义同一语言的正规式。对每一个正规式，存在一个生成同一语言的正规文法。 即正规式正规文法

13  正规式正规文法： （把正规式转换为正规文法所要求的规则形式）
将Σ上的一个正规式r转换为一个正规文法G=（VN，VT，P，S）的规则： 令VT=Σ， 对正规式r，选择一个非终结符S生成S→r，S为G的开始符号。不断拆分r直到符合正规文法要求的规则形式：  若x，y都是正规式，对形如A→xy的产生式，写成A→xB，B→y。其中B VN  对形如A→x*y的产生式，重写为： A→x A A→y B为新的非终结符，B VN 对形如A→x|y的产生式，重写为： A→x 不断利用上述规则进行变换即可。

14 例：将R＝a(a|d)*变换成正规文法。令S是文法开始符号。

15 例：将R＝a(a|d)*变换成正规文法。令S是文法开始符号。
解： S→aA A→(a|d)* A→(a|d) A A→  S→ a(a|d)* 

16 S→aA A→aA A→dA A→  最后得到：

17 转换为正规式 例：文法G[S]：  正规文法正规式：将一个正规文法转换为正规式的规则： 转换规则：
  正规文法正规式：将一个正规文法转换为正规式的规则： 转换规则：  A→xB，B→y 正规式为： A=xy  A→xA|y 正规式为： A=x*y A→x，A→y 正规式为： A=x|y 不断收缩产生式规则，直到剩下一个开始符号定义的正规式 S→ aA S→ a A→ aA A→ dA A→ a A→ d 转换为正规式 例：文法G[S]： S→ aA|a A→ (a|d)A A→ a|d ------ S→ a(A| ) A→ (a|d)+ S→ a (a|d)*

18 A→x，A→y 推出A=x|y S→ aA S→ a A→ aA A→ dA A→ a A→ d S＝aA|a A＝aA|dA
根据上述规则3 A→x，A→y 推出A=x|y S→ aA S→ a A→ aA A→ dA A→ a A→ d S＝aA|a A＝aA|dA A＝(aA|dA)|(a|d)  A＝(a|d)A|(a|d)  A＝(a|d)*(a|d) A＝a|d 将它化为正规文法 变成A→ (a|d)A|(a|d) 再根据上述 规则2转换 x＝y＝ (a|d) 将A代入S＝aA|a得到如下：

19 =a((a|d)+|)= a(a|d)*
S＝a( (a|d)*(a|d)) |a =a(a|d)+|a =a((a|d)+|)= a(a|d)* 二、有穷自动机 有穷自动机：是一种自动识别装置，能正确识别正规集； 是词法分析程序的工具和方法，可自动识别（且是正确识别）正规集。 确定的有穷自动机（DFA） 不确定的有穷自动机（NFA） 分为

20 含义：当前状态为Ki，输入字符a，转换为Kj状态
（一） 确定的有穷自动机DFA 自动识别装置 一个确定的有穷自动机M是一个五元组： M=（K，Σ，f，S，Z），其中： ① K是一个有穷集，每个元素表示一个状态； ②Σ是一个有穷字母表，每个元素是一个输入字符； ③ f是转换函数，是在K×Σ→K上的映象，如： f(Ki ，a)= Kj (Ki, KjK)； ④ S是初态，SK； ⑤ ZK，是终态集。 含义：当前状态为Ki，输入字符a，转换为Kj状态

21 例：DFA的M＝({S,U,V,Q},{a,b},f,S,{Q}) 其中f为：
1、用状态图表示： 方法如下： 初始态用 “”或“－”表示； 终态点用 “＋” 或“” 表示； 若f(Ki ，a)= Kj ，则从状态点Ki 到Kj画弧，标记为a。 例：DFA的M＝({S,U,V,Q},{a,b},f,S,{Q}) 其中f为： f(S,a)=U, f(S,b)=V, f(U,a)=Q f(U,b)=V, f(V,a)=U, f(V,b)=Q f(Q,a)=Q, f(Q,b)=Q 画出状态图

22  元素表示相应状态行和输入字符下的新状态。
－ ＋ a b S U V Q 状态图如下： a,b a,b 2、用矩阵表示DFA : 方法： 行表示状态  列表示输入字符  元素表示相应状态行和输入字符下的新状态。

23 “” 标明初态，默认第一行是初态。 终态行在表右端标1，非终态标0 上例矩阵表示如下： a b S U V Q 字符 状态 1

24 例： 表示：f(S,a)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=Z a b S Z 写成正规式是： (a|b)(a|b)*
－ ＋ Z b 表示：f(S,a)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=Z a b S Z 1 写成正规式是： (a|b)(a|b)*

25 3、接受（识别）的概念： 自动识别单词 对于Σ*中的任何字符串t，若存在一条初态到某一终态的路，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFA M所接受。 若M的初态同时又是终态，则空字可为M所接受。 4、接受（识别）的理解： ① 设QK，函数f(Q,)=Q，则输入字符串是空串，并停留在原状态上。 ② 输入字符串t（t表示成Tt1形式，TΣ，t1 Σ*），在DFA M上运行的定义为：f（Q，Tt1）=f(f(Q,T),t1)，其中QK。

26 例如：baab字符串被DFA所接受，DFA见上例。
f(S，baab)=f(f(S，b)，aab)=f(V,aab) ＝f(f(V，a)，ab)=(f(U，ab)=f(f(U，a)，b) =f(Q，b)=Q （Q是终态） ③DFA M所能接受的字符串的全体记为L（M）—称为语言 （也即句子的集合） 5、DFA的确定性： 当f：k×Σ→K是一个单值函数，即对任何状态KR，输入符号a  K，f(k,a)唯一确定下一状态。

27 DFA的行为很容易用程序来模拟. DFA M=（K，Σ，f，S，Z）的行为的模拟程序 K:=S； c:=getchar; while c<>eof do {K:=f(K,c); }; if K is in Z then return (‘yes’) else return (‘no’)

28 自动识别单词的方法： （1）把单词的结构用正规式描述； （2）把正规式转换为一个NFA； （3）把NFA转换为相应的DFA； （4）基于DFA构造词法分析程序。

29 （二） 不确定的有穷自动机NFA 一个不确定的有穷自动机NFA M是一个五元组:：M=（K，Σ，f，S，Z），其中：
②Σ是一个有穷字母表，每个元素是一个输入字符； ③ f是一个从K×Σ*到K上的子集的映象； f：k×Σ* →2k ④ SK，是一个非空初态集； ⑤ Z K，是一个终态集。 与DFA区别：多值函数 f( Ki,a)=Kj f( Ki,a)=Kt；允许输入字符为

30 例：一个NFA， M＝({0,1,2,3,4},{a,b},f,{0},{2,4}) 其中：f(0,a)={0,3} f(2,b)={2} f(0,b)={0,1} f(3,a)={4} f(1,b)={2} f(4,a)={4} f(2,a)={2} f(4,b)={4} 状态图表示如下：

31 对于每个NFA M，存在一个DFA M’，使得L(M)=L(M’)。
3 4 1 2  a b a,b 说明：一个初态，二个终态。 DFA是NFA的特例。 对于每个NFA M，存在一个DFA M’，使得L(M)=L(M’)。 对于任何两个有穷自动机M和M’，如果L(M)=L(M’)，则称M与M’是等价的。

32 NFA 转换为等价的DFA 从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.

33 定义对状态集合I的几个有关运算： 1. 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。 状态集合I的任何状态S都属于ε-closure(I)。 2. 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。

34 状态集合I的有关运算的例子 I={1}, -closure(I)=?； I={5}, -closure(I)=?；
move({1,2},a)=? -closure({5,3,4})=?； 1 2 5 3 4 6 8 7 a 

35 状态集合I的有关运算的例子 I={1}, -closure(I)={1,2}； I={5}, -closure(I)={5,6,2}；
move({1,2},a)={5,3,4} -closure({5,3,4})={2,3,4,5,6,7,8}； 1 2 5 3 4 6 8 7 a 

36 NFA确定化算法: 假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个DFA M=(S, ,d,S0,St)，使得L(M)=L(N)： 1. 构造DFA M的状态，选择NFA N的状态的一些子集构成： M的状态集S由K的一些子集组成。用[S1 S2... Sj]表示S的元素，其中S1, S2,,... Sj是K的状态。并且约定，状态S1, S2,,... Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]；

37 2 M和N的输入字母表是相同的，即是； 构造DFA M的转换函数，根据新构造的状态和字母表中的字符构造： 转换函数是这样定义的： d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = -closure(move({S1, S2,,... Sj},a)) 4 S0=-closure(K0)为M的开始状态； 5 St={[Si Sk... Se]，其中[Si Sk... Se]S且{Si , Sk,,... Se}Kt}

38 构造NFA N的状态K的子集的算法： 把多值转换函数所转换到的多值（多状态）的集合作为一个子集，映射到DFA的一个新的状态 假定所构造的子集族为C，即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。 1 开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。

39 2 while （C中存在尚未被标记的子集T）do. {. 标记T；. for 每个输入字母a do. {
2 while （C中存在尚未被标记的子集T）do { 标记T； for 每个输入字母a do { U:= -closure(move(T,a))； if U不在C中 then 将U作为未标记的子集加在C中 } }

40 NFA的确定化 例子 4 f 3 5 6 2 1 i  a b

41 4 f 3 5 6 2 1 i  a b

42 等价的DFA a C D B A E F S b a a b F

43 三、确定有穷自动机DFA的化简 （消除多余状态+合并等价状态）： 将多余状态消除而形成一个最小的等价的DFA 1、多余状态的概念：
从该自动机的开始状态出发，任何输入串也不能到达的那个状态。 下图中的哪些状态是多余的？

44 化简后的结果： 1 S0 S1 S5 S2 S7 S3 S4 S6 S8 左右等价

45 化简后的结果： 1 S0 S1 S5 S2 S7 S3 S4 S6 S8 1 S0 S1 S5 S2 S7 S3 左右等价

46 合并等价状态：发现等价状态，并将这些等价状态合并成一个状态。
2、等价的条件（状态S和T）    一致性条件 —— 状态S和T必须同时为可接受状态或不可接受状态（终态还是非终态）。  蔓延性条件 —— 对于所有输入符号，状态S和状态T必须转换到等价的状态里。 3、合并等价状态的方法（分割法） 方法：将DFA的状态分割成一些互不相交的子集。不同子集的状态是可区别的，同一子集中的任何两个状态是等价的。

47 1 6 4 3 2 5 7  a b 例子：将图中的DFA M最小化。

48  将M分成两个子集： 一个终态（可接受态）组成，一个非终态组成。 P0＝({1,2,3,4},｛5,6,7})  第1个子集｛1,2,3,4｝中： ｛1,2}中的状态和｛3,4}中的任何状态在读入a后到达了不等价的状态，两个状态都是不可区别的。 P1＝({1,2},｛3,4},｛5,6,7})  P1中的｛3,4}对应输入符号a或b，将再分割： P2＝({1,2},{3},{4},{5,6,7})  P2中的{5,6,7}可有输入符号a或b，分割为：

49 P3＝({1,2},{3},{4},{5},{6,7}) {1,2},{6,7}不能再分割，也即等价的。 a a 4 6 b 1 6 4 3
 a b a a b a  1 7 b b 5 a b a b 3 2 b

50 DFA的最小化算法 DFA M =（K,∑,f, k0,, kt),最小状态DFA M’ 构造状态的一初始划分： 终态kt 和非终态K- kt两组(group) 对∏施用过程PP 构造新划分∏new 如∏new =∏,则令 ∏final=∏ 并继续步骤4，否则∏:=∏new重复 为∏final中的每一组选一代表，这些代表构成M’的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=r

51 M’ 的开始状态是含有S0的那组的代表 M’ 的终态是含有F的那组的代表

52 过程PP : Construction of ∏new
For each group G of ∏ do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to states in the same group of ∏;/*at worst, a state will be in a subgroup by itself*/ 2.replace G in ∏new by the set of all subgroups formed end

53 自动识别单词的方法： （1）把单词的结构用正规式描述； （2）把正规式转换为一个NFA； （3）把NFA转换为相应的DFA； （4）基于DFA构造词法分析程序。

54 四、正规式和有穷自动机的等价性 正规式和有穷自动机的等价性由以下两点说明 ：
※对于Σ上的NFA M，可以构造一个Σ上的正规式R，使得L(R)=L(M)。 ※对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 1、在NFA M上构造正规式R。即从L(M)  L(R） 方法：在每一条弧上用一个正规式作标记。 规则如下：

55    1 2 3 R1 R2 R1R2 a. 1 3 1 2 R1 R2 2 1 R1|R2 b. R1+R2 或 1 2 R2 c.
给定有穷自动机，判断它识别的语言

56 例1: L(M)如下图： 求正规式R，使L(R)=L(M). 解： － ＋ a b a,b

57 例1: L(M)如下图： 求正规式R，使L(R)=L(M). 解： － ＋ a b a,b a b a,b   x y a|b 
因此： L(R)= (a+b)(a+b)* x y

58 例2：M状态图如下： 求正规式R，是L(R)=L(M). 3 4 1 2  a b a,b

59 解：加x,y结点。 a,b  a a x a,b 3 4 b  1 b y 2  a,b

60 a,b  aa x a,b 4 bb  2  y a,b a,b  aa(a+b)* x y bb(a+b)*

61 所以 L(R) =(a+b)*(aa+bb)(a+b)*
x y 所以 L(R) =(a+b)*(aa+bb)(a+b)*

62 2、L(R) NFA，从正规式R构造NFA
规则如下：  正规式，构造NFA为： 或：  对应正规式，构造NFA为：   对应正规式a，构造NFA为：   s,t是正规式，相应NFA为N(s),N(t)，则正规式R=s|t，构造NFA(R) 为： x y  x y  x y a x y N(s) N(t)  

63  s,t是正规式，相应NFA为N(s),N(t)，则正规式R=st，构造NFA(R) 为：
 x y  s,t是正规式，相应NFA为N(s),N(t)，则正规式R=s*，构造NFA(R) 为：     x y N(s)

64 例1：L(R) =(a+b)*abb，构造NFA使L(N)=L(R)
解：

65 例1：L(R) =(a+b)*abb，构造NFA使L(N)=L(R) 解：
x y  (a+b)* abb x  y abb  a,b  x  y abb  a b x  y  a b

66 例4： L(R) =(a+b)*(aa+bb)(a+b)* 构造L(N)使与L(R) 等价。
y  a 例4： L(R) =(a+b)*(aa+bb)(a+b)* 构造L(N)使与L(R) 等价。

67 (a+b)*(aa+bb)(a+b)*  x y x y  (a+b)* aa+bb x y  aa bb a,b 

68 x y  a b  - + a b

69 词法分析程序的自动构造 自动识别单词的方法： （1）把单词的结构用正规式描述； （2）把正规式转换为一个NFA；
 自动识别单词的方法： （1）把单词的结构用正规式描述； （2）把正规式转换为一个NFA； （3）把NFA转换为相应的DFA； （4）基于DFA构造词法分析程序。

70 本章小结 词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。
本章讲述了词法分析程序设计原则，并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具的原理。

71 课后作业 1。叙述正规式(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*描述的语言。
2。写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规式。 3。构造一个DFA，它接受∑={0,1}上0和1的个数都是偶数的字符串。 4。处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。