编译原理_03词法分析

1、1第第4 4章章 词法分析词法分析24.1 4.1 词法分析程序的设计词法分析程序的设计4.2 4.2 单词的描述工具单词的描述工具4.3 4.3 有穷自动机有穷自动机4.4 4.4 正规式和有穷自动机的等价性正规式和有穷自动机的等价性4.5 4.5 正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换4.6 4.6 词法分析程序的自动构造工具词法分析程序的自动构造工具主要内容主要内容3课题：课题：正规文法与正规式及其等价变换目的要求：目的要求： 1.理解词法分析在编译过程中的重要性； 2.掌握正规式的定义，正规式与正规文法的等价变换 教学重点：教学重点： 1.正规式的定义； 2.正规式与

2、正规文法的等价变换教学难点教学难点 ： 正规式与正规文法的等价变换教学课时：教学课时： 2教学方法：教学方法：多媒体教学教学内容和步骤教学内容和步骤 ：（如下）第第 五五 讲讲4 词法分析：是编译过程的第一个阶段，在语词法分析：是编译过程的第一个阶段，在语法分析前进行。也可以和语法分析结合在一起法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。来获得当前单词供语法分析使用。主要任务：从左到右逐个字符地对源程序进行主要任务：从左到右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。扫描

3、，产生一个个单词序列，用以语法分析。并把源程序转换为等价的内部表示形式。并把源程序转换为等价的内部表示形式。4.1 4.1 词法分析程序的设计词法分析程序的设计5 单词是语言中具有独立意义的最小语法单词是语言中具有独立意义的最小语法单位，包括保留字、标识符、运算符、单位，包括保留字、标识符、运算符、标点符号和常量等。标点符号和常量等。 词法分析工作独立的原因：词法分析工作独立的原因： 简化设计简化设计 改进编译效率改进编译效率 增加编译系统的可移植性增加编译系统的可移植性 6 一一. 正规文法（回顾）正规文法（回顾） 文法文法G=(Vn,Vt,P,S)，P中每一规则有中每一规则有AaB或或Aa

4、 ，A,B Vn，a Vt*，称，称G(S)是正规文法。是正规文法。4.2 4.2 单词的描述工具单词的描述工具7几类单词的描述几类单词的描述标识符：标识符：标识符标识符l | l字母数字字母数字字母数字字母数字l | d | l字母数字字母数字| d字母字母数字数字无符号整数：无符号整数：无符号整数无符号整数d | d无符号整数无符号整数运算符：运算符：运算符运算符 + | - | * | / | = | =界符：界符：界符界符 , | ; | ( | ) |8无符号实数：无符号实数：无符号实数无符号实数 d 余留无符号数余留无符号数| . 十进小数十进小数| e指数部分指数部分余留无符号数

5、余留无符号数 d 余留无符号数余留无符号数| . 十进小数十进小数| e指数部分指数部分|十进小数十进小数 d 余留十进小数余留十进小数余留十进小数余留十进小数 e指数部分指数部分| d 余余留十进小数留十进小数| 指数部分指数部分 d 余留整指数余留整指数| s整指整指数数整指数整指数 d 余留整指数余留整指数余留整指数余留整指数 d 余留整指数余留整指数 |其中其中s表示正或负号。表示正或负号。如如 125.55e+15 和和 232.1479 二二. 正规式（正则表达式）正规式（正则表达式） 是表示正规集的工具，也是用以描述单词是表示正规集的工具，也是用以描述单词符号的方便工具。符号的方

6、便工具。 正规式表示字符串的格式。正规式正规式表示字符串的格式。正规式r 完全完全由它所匹配的串集来定义。这个集合称为由由它所匹配的串集来定义。这个集合称为由正规式生成的语言，写作正规式生成的语言，写作L（r）。该语言首）。该语言首先依赖于适用的字符集，它一般是先依赖于适用的字符集，它一般是A S C I I 字符的集合或它的某个子集。集合的元素称字符的集合或它的某个子集。集合的元素称作符号。这个正规符号的集合称作字母表。作符号。这个正规符号的集合称作字母表。 可以将正规表达式理解成程序设计语言中可以将正规表达式理解成程序设计语言中的单词的词型公式，它比正规文法更容易让的单词的词型公式，它比正

7、规文法更容易让人理解单词是按怎样的规则构成的。人理解单词是按怎样的规则构成的。10 正规式与正规集的定义：正规式与正规集的定义： 设字母表为设字母表为，辅助字母表，辅助字母表= ， ，|，*，（，）（，） ； 和和 都是都是上的正规式，表示的正规集分上的正规式，表示的正规集分别为别为 和和 ； 任何任何a ,a是是上的一个正规式，表示的正上的一个正规式，表示的正规集为规集为a; 假定假定e1和和e2都是都是上的正规式，它们所表上的正规式，它们所表示的正规集分别为示的正规集分别为L(e1)和和L(e2),则则(e1),e1|e2,e1e2和和e1*也都是正规式，所表也都是正规式，所表示的正规集分

8、别为示的正规集分别为L(e1),L(e1)L(e2), L(e1)L(e2)和和(L(e1)*。11 4. 仅由有限次使用上述三步骤而定义的表达仅由有限次使用上述三步骤而定义的表达式才是式才是上的正规式，仅由这些正规式所上的正规式，仅由这些正规式所表示的子集才是表示的子集才是上的正规集。上的正规集。例：例： a,b， 上的正规式和相应的正规上的正规式和相应的正规集为：集为：12正规式正规式正规集正规集aaa|ba,babab(a|b)(a|b)aa，bb,ab,baa* ，a,aa, ，aaaa(a|b)* ,a,b,aa,ab,aab,abab, (a|b)*(aa|bb) (a|b)* *

9、上所有含有两个相继的上所有含有两个相继的a或两个相继的或两个相继的b组成的串组成的串13例：令例：令 d, ,e,则则 上的正规式为：上的正规式为：d*(.dd*| )(e(+|-| )dd*| )表示的是无符号数。表示的是无符号数。 其中其中d为为09中的数字。中的数字。 比如：比如：2,12.59,3.6e2,471.88e-1等都是正规式等都是正规式表示集合中的元素。表示集合中的元素。 若两个正规式若两个正规式e1和和e2所表示的正规集相同所表示的正规集相同,则则说说e1和和e2等价等价,写作写作e1=e2。例如：例如： e1= (a b)和和 e2 = b a又如：又如： b(ab)

10、= (ba) b；(a b) = (ab ) 144. r(s|t) = rs|rt (s|t)r = sr|tr5. r=r r =r1. r|ss|r2. r|(s|t)(r|s)|t3. (rs)t=r(st)设设r，s，t为正规式，正规式服从代数规律有：为正规式，正规式服从代数规律有：15三三. 正规文法到正规式正规文法到正规式 对于任意一个正规文法，存在一个同一语言的对于任意一个正规文法，存在一个同一语言的正规式。对每一个正规式，存在一个正规文法。正规式。对每一个正规式，存在一个正规文法。即正规式即正规式正规文法正规文法文法文法G=（VN，VT，P，S），令），令VT=，对正，对正规

11、式规式r，选择一个非终结符，选择一个非终结符S生成生成Sr，S为为G的开始符号。的开始符号。1. 若若x，y都是正规式，对形如都是正规式，对形如Axy的产生式，的产生式，写成写成AxB，By。其中。其中B VN正规式正规式正规文法正规文法162. 对形如对形如Ax*y的的产生式，重写为：产生式，重写为： AxB Ay BxB By B为新的非终结符，为新的非终结符，B VN3. 对形如对形如Ax|y的产的产生式，重写为：生式，重写为： Ax Ay 不断利用上述规则进不断利用上述规则进行变换，直到每个产行变换，直到每个产生式最多只含有一个生式最多只含有一个终结符为止。终结符为止。17例：将例：将

12、Ra(a|d)*变换成正规文法。令变换成正规文法。令S是文是文法开始符号。法开始符号。解：解：S a(a|d)*SaAA(a|d)*A(a|d)BA B(a|d)BB 根据上述规则根据上述规则1xa，y(a|d)* 根据上述规则根据上述规则2x(a|d)y 18最后得到正规文法为：最后得到正规文法为：SaAAaBAdBA BaBBdBB Gs:19转换规则：转换规则：1. AxB，By 正规式为：正规式为：A=xy 2. AxA|y 正规式为：正规式为： A=x*y 3. Ax，Ay 正规式为：正规式为： A=x|y 例：文法例：文法GS：S aA S aA aA A dAA a A d正规文

13、法正规文法正规式正规式转换过程如下转换过程如下20S aAS aA aAA dAA aA dSaA|aAaA|dAAa|dA(aA|dA)|(a|d) A(a|d)A|(a|d) A(a|d)*(a|d)根据上述规则根据上述规则3Ax，Ay推出推出A=x|y将它化为正规文法将它化为正规文法变成变成A (a|d)A|(a|d) 再根据上述再根据上述规则规则2转换转换xy (a|d)21Sa( (a|d)*(a|d) |a =a(a|d)*(a|d) | ) =a(a|d)*将将A代入代入SaA|a得到如下：得到如下：22 词法分析是编译的第一个阶段，它的主要功能是词法分析是编译的第一个阶段，它的

14、主要功能是识别单词。识别单词。正规式也叫正则表达式，是表示正规集的工具，是单正规式也叫正则表达式，是表示正规集的工具，是单词的词型公式。词的词型公式。对于任意一个正规文法，存在一个同一语言的正规式。对于任意一个正规文法，存在一个同一语言的正规式。对每一个正规式，存在一个正规文法。即正规式对每一个正规式，存在一个正规文法。即正规式正正规文法。规文法。教学总结23教材教材P73-74练习练习: 8，12(1)作 业24课题：课题：DFA与NFA目的要求：目的要求： 1.理解并掌握有穷自动机的定义； 2. 掌握DFA最小化方法教学重点：教学重点： 1.有穷自动机的定义； 2.DFA的最小化教学难点教

15、学难点 ： DFA的最小化教学课时：教学课时：2教学方法：教学方法：多媒体教学教学内容和步骤教学内容和步骤 ：（如下）第第 六六 讲讲25 4.3 4.3 有穷自动机有穷自动机 有穷自动机：是词法分析程序的工具有穷自动机：是词法分析程序的工具和方法，可自动识别（且是正确识别）正和方法，可自动识别（且是正确识别）正规集。规集。分为分为确定的有穷自动机（确定的有穷自动机（DFA）不确定的有穷自动机（不确定的有穷自动机（NFA） 26一一 . . 确定的有穷自动机确定的有穷自动机DFADFA一个确定的有穷自动机一个确定的有穷自动机M是一个五元组：是一个五元组： M=（K，f，S，Z），其中），其中

16、K是一个有穷集，每个元素表示一个状态；是一个有穷集，每个元素表示一个状态；为有穷字母表，每个元素是一个输入字符；为有穷字母表，每个元素是一个输入字符； f为转换函数，是在为转换函数，是在KK上的映象，如：上的映象，如： f(Ki ，a)= Kj (Ki, Kj K)； S是唯一初态，是唯一初态，S K； Z K，是终态集。是终态集。 含义：当前状态为含义：当前状态为Ki，输，输入字符入字符a，转换为，转换为Kj状态状态271. DFA的表示方法有两种：的表示方法有两种： 状态图表示和矩阵表示状态图表示和矩阵表示例例1：DFA M(S,U,V,Q,a,b,f,S,Q)其中其中f为：为：f(S,a

17、)=U, f(S,b)=V, f(U,a)=Qf(U,b)=V, f(V,a)=U, f(V,b)=Qf(Q,a)=Q, f(Q,b)=Q28 初始态用初始态用 “”或或“”表示；表示； 终态点用终态点用 “” 或或“” 表示；表示； 若若f(Ki ，a)= Kj ，则从状态点，则从状态点Ki 到到Kj画弧，画弧，标记为标记为a。bSUVQaaaba,bb状态图表示状态图表示29 行表示状态；列表示输入字符行表示状态；列表示输入字符元素表示相应状态行和输入字符下的新状态元素表示相应状态行和输入字符下的新状态 “” 标明初态，默认第一行是初态标明初态，默认第一行是初态 终态行在表右端标终态行在表

18、右端标1，非终态标，非终态标0 矩阵表示矩阵表示0100abSUVUQVVUQQQQ字符字符状态状态30例例2：转换函数：转换函数：f(S,a)=Zf(S,b)=Zf(Z,a)=Zf(Z,b)=ZabSZZZZZ01其状态图表其状态图表示和矩阵表示和矩阵表示如右图：示如右图：字符字符状态状态baSZa,b312. 接受（识别）的概念：接受（识别）的概念： 对于对于*中的任何字符串中的任何字符串t，若存在一条初态到某，若存在一条初态到某一终态的道路，且这条路上所有弧的标记符连接一终态的道路，且这条路上所有弧的标记符连接成的字符串等于成的字符串等于t，则称，则称t可为可为DFA M所接受。所接受。

19、 若若M的初态同时又是终态，则空字可为的初态同时又是终态，则空字可为M所接受所接受 接受（识别）的理解：接受（识别）的理解： 设设Q K，函数，函数f(Q, )=Q，空串不改变状态；，空串不改变状态； 输入字符串输入字符串t（t表示成表示成Tt1形式，形式，T ， t1 *），在），在DFA M上运行的定义为：上运行的定义为：f（Q，Tt1）=f(f(Q,T),t1)，其中，其中Q K。 32例：证明例：证明t=baab被如下的被如下的DFA所接受。所接受。DFA M=（S,U,V,Q, a,b, f, S, Q）其中）其中 f 定义为：定义为： f（S，a）=U，f（V，a）=Uf（S，b）

20、=V，f（v，b）=Q，f（U，a）=Qf（Q，a）=Q，f（U，b）=V，f（Q，b）=QbSUVaaaba , bbQ33证明如下：证明如下： 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）=QQ属于终态。得证。属于终态。得证。我们把我们把DFA M所能接受的字符所能接受的字符串的全体记为串的全体记为L（M）称为语言）称为语言 （也即句子的集（也即句子的集合）合） 343. DFA的确定性：的确定性： 当当f：kK是一个单值函数，即对任是一个单值函数，即对任何状态何状态K R，输入

21、符号，输入符号a K，f(k,a)唯一唯一确定下一状态。确定下一状态。“确定确定”的含义：下一个输入字符唯的含义：下一个输入字符唯一地确定了下一个当前状态一地确定了下一个当前状态 35二二. . 不确定的有穷自动机不确定的有穷自动机NFA NFA 一个不确定的有穷自动机一个不确定的有穷自动机NFA M是一个五是一个五元组元组:：M=（K，f，S，Z），其中），其中 K是一个有穷集，每个元素表示一个状态；是一个有穷集，每个元素表示一个状态； 是一个有穷字母表，每个元素是一个输入是一个有穷字母表，每个元素是一个输入字符；字符； f是一个从是一个从K*到到K上的子集的映象；上的子集的映象； S K，

22、是一个非空初态集；是一个非空初态集； Z K，是一个终态集。是一个终态集。36例：已知例：已知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状态图表示如下：状态图表示如下：37说明：说明： DFA是是NFA的特例的特例 对于每个对于每个NFA M，存在一个，存在一个DFA M ，使得，使得L(M)=L(M )； 对于任何两个有穷自动机对于任何两个有穷自动机M和和M ，如果，如果L(M)=L(M )，则称，则称M与与M 是等

23、价的。是等价的。 03412abbba,ba,ba,b38三三. DFA的化简的化简(最小化）最小化） DFA的最小化可以通过消除多余状态和的最小化可以通过消除多余状态和合并等价状态来实现。合并等价状态来实现。 多余状态及其消除多余状态及其消除 1. 多余状态包括不可到达的和不可终止的多余状态包括不可到达的和不可终止的两种情况。两种情况。 2. 例例. 下述下述DFA中状态中状态S4 、S6、 S8都是多都是多余的。分析如下：余的。分析如下： 39s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s

24、8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7消除多余状态后消除多余状态后DFA401. 状态状态S和和T等价的条件等价的条件 一致性条件一致性条件 : 状态状态S和和T必须同时为可接受必须同时为可接受状态或不可接受状态。状态或不可接受状态。 蔓延性条件蔓延性条件 : 对于所有输入符号，状态对于所有输入符号，状态S和和状态状态T必须转换到等价的状态里。必须转换到等价的状态里。2. 等价状态

25、的合并（分割法）等价状态的合并（分割法） 将将DFA（不含多余状态）的状态分割成一些（不含多余状态）的状态分割成一些互不相交的子集。使得处于同一子集的状态均互不相交的子集。使得处于同一子集的状态均等价，而处于不同子集的状态是可区别的。等价，而处于不同子集的状态是可区别的。 状态等价的条件与合并状态等价的条件与合并413. 分割算法分割算法步骤步骤1：按照一致性条件，将所有状态分割为：按照一致性条件，将所有状态分割为终态集和非终态集；终态集和非终态集；步骤步骤2：按照蔓延性条件，对每一个子集进行：按照蔓延性条件，对每一个子集进行细分，直到不能再细分为止：细分，直到不能再细分为止：步骤步骤3：将处

26、于同一子集的状态（即等价状态）：将处于同一子集的状态（即等价状态）进行合并进行合并421643257aaaaaaabbbbbbb例：将下图中的例：将下图中的DFA M最小化最小化431. 分析可知，分析可知，DFA中不含多余状态；中不含多余状态；2. 将将M分成两个初始子集：终态集和非终态集分成两个初始子集：终态集和非终态集 P0(1,2,3,4,5,6,7)3. 对于对于P0中子集中子集1,2,3,4读入读入a后，状态后，状态1,2分别到达状态分别到达状态6,7；而状态；而状态3,4分别到达状态分别到达状态1,4；在在P0中状态中状态6,7 和和3,4分属于不同的子集，因此分属于不同的子集，

27、因此状态状态1,2和和3,4应分属于不同的子集，于是应分属于不同的子集，于是 P1(1,2,3,4,5,6,7)步骤如下：步骤如下：444. 同理，对同理，对P1中的每个子集输入符号中的每个子集输入符号a或或b，继，继续分割如下：续分割如下： 对子集对子集3,4 分割可得分割可得 P2(1,2,3,4,5,6,7) 对子集对子集5,6,7 分割可得分割可得 P3(1,2,3,4,5,6,7)P3剩余子集剩余子集1,2,6,7经分析不能再分割，也即经分析不能再分割，也即子集中的状态等价。分割完毕。子集中的状态等价。分割完毕。5. 合并：每个子集中只取一个状态。（如图）合并：每个子集中只取一个状态

28、。（如图）45DNA最小化之后的状态图如下最小化之后的状态图如下16435aaaaabbbbb出弧删除出弧删除入弧转移入弧转移46 有穷自动机是词法分析程序的工具，可分为确定有穷自动机是词法分析程序的工具，可分为确定的有穷自动机（的有穷自动机（DFA）和不确定的有穷自动机）和不确定的有穷自动机（NFA）。）。 DFA是是NFA的特例，对于每个的特例，对于每个NFA M，存在一个，存在一个DFA M ，使得，使得L(M)=L(M ) 。 NFA DFA的确定化方法：子集法。的确定化方法：子集法。 DFA的最小化可以通过消除多余状态和合并等价的最小化可以通过消除多余状态和合并等价状态来实现。状态来

29、实现。教学总结47教材教材P72-73练习练习: 4(2)，7作 业48课题：课题：正规式、正规文法和有穷自动机的等价性目的要求：目的要求： 掌握正规式、正规文法和有穷自动机之间的变换方法教学重点：教学重点： 正规式、正规文法和有穷自动机之间的等价变换教学难点教学难点 ： 正规式和有穷自动机之间的等价变换教学课时：教学课时：2教学方法：教学方法：多媒体教学教学内容和步骤教学内容和步骤 ：（如下）第第 七七 讲讲49 正规式和有穷自动机的等价性由以下两点正规式和有穷自动机的等价性由以下两点说明说明 ： 对于对于上的上的NFA M，可以构造一个，可以构造一个上的正上的正规式规式R，使得，使得L(R

30、)=L(M)。 对于对于上的每个正规式上的每个正规式R，可以构造一个，可以构造一个上上的的NFA M，使得，使得L(M)=L(R)。 4.4 4.4 正规式和有穷自动机的等价性正规式和有穷自动机的等价性 50在在NFA M上构照正规式上构照正规式R： L(M) L(R )步骤如下：步骤如下： 第一步：在第一步：在M的状态转换图上加进两个结，一的状态转换图上加进两个结，一个为个为x结点，一个为结点，一个为y结点。从结点。从x结点用结点用弧连接弧连接到到M的所有初态结点，从的所有初态结点，从M的所有终态结点用的所有终态结点用弧连接到弧连接到y结点。形成一个与结点。形成一个与M等价的等价的M ，M

31、只有一个初态只有一个初态x和一个终态和一个终态y。 第二第二步：逐步消去步：逐步消去M 中的所有结点，直至只剩下中的所有结点，直至只剩下x和和y。最后最后x和和y结点间的弧上的符号串即为所求的正结点间的弧上的符号串即为所求的正规式规式R。51转换规则如下：转换规则如下：123R1R213R1 R213R1R213R1| R2123R1R3R213R1 R2* R352例：如图所示例：如图所示NFA M，求正规式，求正规式R03124a,baaa,ba,bbb解题过程如下：解题过程如下：53(a)03124a,baaa,ba,bbbxy54(b)024a|baaa|ba|bbbxy55a|baa

32、(a|b)*bb(a|b)*a|baa(a|b)* |bb(a|b)*(d)(c)0 xy0 xy56所以，所求正规式所以，所求正规式R=(a|b)* (aa |bb)(a|b)*(e)xy(a|b)* (aa |bb)(a|b)*57从正规式从正规式R构造等价的构造等价的NFA :L(R) NFA语法制导法，规则如下：语法制导法，规则如下： 正规式正规式 ，所构造的，所构造的NFA为：为： 正规式正规式 ，所构造的，所构造的NFA为：为： 正规式正规式a，所所构造的构造的NFA为：为： xyxyxya58 若若s,t是正规式，相应是正规式，相应NFA为为N(s),N(t) (下同下同) 则正

33、规式则正规式R=s|t，所构造的，所构造的NFA(R) 为：为： s,t是正规式，相应是正规式，相应NFA为为N(s),N(t)，则正，则正规式规式R=st，构造，构造NFA(R) 为：为：xy N(t)N(s)yN(t)xN(s)59 s,t是正规式，相应是正规式，相应NFA为为N(s),N(t)，则正规，则正规式式R=s*，构造，构造NFA(R) 为：为：下面通过一个具体的例子来学习下面通过一个具体的例子来学习L(R) NFA xy N(s) 60例：为例：为R=(a|b)*abb构造构造NFA N，使得，使得L(N)=L(R)R=aR=bR=a|b分析如下：分析如下：4b2354ab16

34、52a361R=(a|b)*2354ab160762aR=(a|b)*abb2354ab1601089b7b63其他方法：其他方法：xiy(a|b)*abbxjyabbia|bxjyaiablbkb644.5 4.5 正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换 构造规则如下：构造规则如下： 字母表与字母表与G的终结符集相同；的终结符集相同；为为G中的每个非终结符生成中的每个非终结符生成M的一个状态，的一个状态， G 的开始符号是初态的开始符号是初态S； 增加一个新状态增加一个新状态Z，作为，作为NFA的终态；的终态；对对G中的形如中的形如AtB的产生式（其中的产生式（其中t为终结符为终结符或或，A和和B为非终结符），构造为非终结符），构造M的一个转换