sun编译原理第3章词法分析与有穷自动机(第5-8讲)

资源描述

《sun编译原理第3章词法分析与有穷自动机(第5-8讲)》由会员分享，可在线阅读，更多相关《sun编译原理第3章词法分析与有穷自动机(第5-8讲)（54页珍藏版）》请在金锄头文库上搜索。

1、2017/7/22,信息学院孙丽云,1,3.1 词法分析程序的功能,所谓词法，即构成词的规则。词法分析的任务是对字符串表示的源程序从左到右进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号。词法分析是编译过程中的一个阶段，在语法分析前进行，可以作为单独的一遍，将源程序转换成单词符号序列供下一遍使用。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序获得当前记号，供语法分析使用。,2017/7/22,信息学院孙丽云,2,3.2 单词符号及输出单词的形式,单词符号是语言中具有独立意义的最小单位，包括保留字、标识符、常量、运算符和界符等。,词法分析程序输出的

2、单词符号通常表示成如下的二元式：（单词种别，单词自身的值）,2017/7/22,信息学院孙丽云,3, 正规式与正规集,3.3 语言单词符号的两种定义方式,多数程序设计语言的单词符号都能用正规文法或正规式来定义。,设有字母表=a1，a2，an，在字母表上的正规式和它所表示的正规集可用如下规则定义：（1）是上的正规式，它所表示的正规集是，即空集（2）是上的正规式，它所表示的正规集是（3）ai是上的正规式，它所表示的正规集由单个符号ai组成，即ai,2017/7/22,信息学院孙丽云,4, 正规式与正规集,（4）如果e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，则e

3、1|e2是上的一个正规式，它所表示的正规集为L(e1|e2) = L(e1) L(e2)e1e2是上的一个正规式，它所表示的正规集为L(e1e2)=L(e1) L(e2)(e1)*是上的一个正规式，它所表示的正规集为L(e1)*) =L(e1)*,正规式描述了单词符号的构成规则，正规集是正规式能描述的所有的单词的集合。,2017/7/22,信息学院孙丽云,5,设有字母表=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)*是

5、=a,b,bc,bcc,bccc, 正规式与正规集举例,思考：L(ab|c*d)=？,2017/7/22,信息学院孙丽云,7,设A,B,C均为正规式,则正规式有如下性质:A|B = B |A(交换律)A|(B|C) = (A |B)|C(结合律)A(BC)=(AB)C(结合律)A(B|C)=AB|AC(分配律)(A|B)C=AC|BC(分配律)A|A=AA*=AA*|=A|A*=(A|)*(A*)*=A*, 正规式的性质,2017/7/22,信息学院孙丽云,8,正规文法与正规式,正规文法与正规式都是描述正规集的工具。对任意一个正规文法，存在定义同一语言的正规式；反之，对每个正规式存在一个生

6、成同一语言的正规文法。, 3型（正规文法）：(左线性) P：Ut 或 UWt 其中 U、WN tT(右线性) P：Ut 或 UtW 其中 U、WN tT,2017/7/22,信息学院孙丽云,9,正规文法到正规式的转换,(1)将正规文法中的每个非终结符表示成关于它的一个正规式方程，获得一个联立方程组。(2)依照求解规则: 若x=x|(或x=x+)，则解为x=*; 若x=x|(或x=x+)，则解为x=*;以及正规式的分配律、交换律和结合律求关于文法开始符号的正规式方程组的解.这个解是关于该文法开始符号S的一个正规式，显然它表示了由该正规文法所描述的语言。,2017/7/22,信息学院孙丽云,1

8、语言的正规式。解 (1)联立方程组（用+代替正规式中的|） (2)依照求解规则求解,P28 (9),2017/7/22,信息学院孙丽云,13,正规式到正规文法的转换,字母表上的正规式到正规文法G=(VN,VT,P,S)的转换方法如下:(1) 令VT= ;(2)对任意正规式R选择一个非终结符Z生成规则ZR,并令S=Z;(3)若a和b都是正规式,对形如Aab的规则转换成AaB和Bb两规则,其中B是新增的非终结符;(4)在已转换的文法中,将形如Aa*b的规则进一步转换成AaA|b;(5)不断利用规则(3)和(4)进行变换,直到每条规则最多含有一个终结符为止.,2017/7/22,信息学院孙丽云,

9、14,正规式到正规文法的转换举例,例3.8 将R=(a|b) (aa)*(a|b)转换成相应的正规文法.例3.9 将R= l(l|d)* 转换成相应的正规文法. 练习,2017/7/22,信息学院孙丽云,15,3.4 正规式与有穷自动机,有穷自动机是词法的识别工具，它的功能是：寻找（匹配）符合正规式要求的字符串，根据正规式确定正规集。有穷自动机是描述特定类型算法的数学模型，可分为确定性有穷自动机(DFA)和非确定性有穷自动机(NFA)。,2017/7/22,信息学院孙丽云,16,确定有穷自动机（DFA）,数学定义（五元组形式）：严密；状态转换表：面向编程。状态转移图：直观；,DFA有三种表

10、示形式,2017/7/22,信息学院孙丽云,17,结点代表状态(state)，用圆圈表示。状态之间用箭头(transition)连结，代表一个状态向另一个状态的转换。一个有穷自动机只包含有限个状态(即有限个结点)，其中只有一个为初态(start state)（一个有开始状态的箭头指向），至少一个为终态(接受状态accepting state) (双圈表示)。例：标识符的有穷自动机。,有穷自动机的状态转移图表示方法,2017/7/22,信息学院孙丽云,18,状态状态转移初始状态接受状态,两字符串的识别过程：,有穷自动机的状态转移图表示方法,2017/7/22,信息学院孙丽云,19,确定有穷

11、自动机（DFA）, 输入字母表 Q 有穷状态集 f : Q Q (状态转换函数) SQ 唯一的初始状态 Z Q 终止（接受）状态集合这里的字母表是问题固有的；状态集合是编写DFA时定义的，是用户所做的命名。,DFA M是一个五元组（ Q, , f, S, Z ）,确定性有穷自动机(DFA)：下一状态由当前状态和当前输入字符唯一给出的自动机。（取决于f）,“确定”即状态转移函数是单值函数,数学定义,确定有穷自动机（DFA）,例： M=(Q, f, S, Z )其中： =a,b,z,A,B,Z,0,1,9Q=1,2,3，S=1，Z=2，f=,f= Q Q 是如下的函数：f(1,a)=2，f(1,

12、z)=2f(1,A)=2，f(1,Z)=2f(2,a)=2，f(2,z)=2f(2,A)=2，f(2,Z)=2,f(2,0)=2f(2,9)=2f(1,0)=3f(1,9)=3f(3,a)=3f(3,z)=3f(3,A)=3f(3,Z)=3,2017/7/22,信息学院孙丽云,21,例：有DFA M=(0,1,2,3,a,b, f,0,3)其中f为:f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3,它所对应的状态表如图：,一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示T

13、(s,a)的值，这个矩阵称状态表（状态转移矩阵）。,状态,输入字符,后继状态,状态表,2017/7/22,信息学院孙丽云,22,DFA三种表示形式的转化,2017/7/22,信息学院孙丽云,23,DFA所识别的语言,给定DFA M，对于字符c1,c2,cn,当以下条件成立时，称M接受由c1,c2,cn组成的字符串c1c2cn：存在状态序列s0,s1,s2,sn,使得s1=f(S,c1), s2=f(s1,c2),sn=f(sn-1,cn)，且snZ。,例：判断abbbba是否是上页DFA M所定义的语言,由DFA M接受的语言L(M)是所有M接受的字符串组成的集合。,2017/7/22,信

14、息学院孙丽云,24,非确定有穷自动机（NFA）,由M接受的语言L(M) L(M) | ciU, s1= T(s0,c1), s2= T(s1,c2), , sn = T(sn-1,cn) , sn A. ,“非确定”即状态转移函数是多值函数, :输入字母表 Q:有穷状态集 f: S x ( U)(S)(状态转换函数) S Q 初始状态集 Z Q 终止状态集,NFA M也是一个五元组（ Q, , f, S, Z ）,2017/7/22,信息学院孙丽云,25, NFA与DFA的区别：,2017/7/22,信息学院孙丽云,26,判断下图是DFA还是NFA的状态转换图，并写出其他2种表示形式,2017/7/22,信息学院孙丽云,27,由正规表达式R构造NFA,(a)对于正规式,所构造NFA:,x,y,(b)对于正规式,所构造NFA:,x,y,(c)对于正规式a,a,则 NFA:,x,y,a,1.基本正规表达式,2017/7/22,信息学院孙丽云,28,由正规表达式R构造NFA,2、若r,s为正规式：,

展开阅读全文

sun编译原理第3章词法分析与有穷自动机(第5-8讲)

最新文档