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

《sun编译原理第3章词法分析与有穷自动机(第5-8讲).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、

4、e2是上的一个正规式，它所表示的正规集为L(e1

5、e2)=L(e1)∪L(e2)e1e2是上的一个正规式，它所表示的正规集为L(e1e2)=L(e1)L(e2)(e1)*是上的一个正规式，它所表示的正规集为L((e1)*)=L((e1))*正规式描述了单词符号的构成规则，正规集是正规式能描述的所有的单词的集合。9/30/20214信息学院孙丽云设有字母表={a,b},根据正规式和正规集的定义有：■例3.1（1）a和b是正规式，相应正规集为L(a)={a}（2）a

6、b是正规式，相应正规集为L(a

7、b)={a,b}（3）ab是正规式，相应正规集为L(ab)={ab}（4）(a

8、

9、b)*是正规式，相应正规集为L((a

10、b)*)={a,b}*={ε,a,b,ab,ba,…}（5）ba*是正规式，相应正规集为L(ba*)={b,ba,baa,baaa,…}（6）(a

11、b)*(aa

12、bb)(a

13、b)*是正规式，相应正规集为L={a,b}*{aa,bb}{a,b}*练习：若S=a

14、bb，则L((a

15、bb)*)=？9/30/20215信息学院孙丽云■正规式中运算的优先级括号优先，*次之，•（连接）再次之，

16、最后例：a

17、bc*≌a

18、(b(c*))ab

19、c*d≌(ab)

20、((c*)d)L(a

21、bc*)=L(a)∪L(bc*)=L(a)∪L(b)L(c*)=L(a)∪L

22、(b)(L(c))*={a}∪{b}{ε,c,cc,ccc……}={a,b,bc,bcc,bccc,……}■正规式与正规集举例思考：L(ab

23、c*d)=？9/30/20216信息学院孙丽云设A,B,C均为正规式,则正规式有如下性质:A

24、B=B

25、A(交换律)A

26、(B

27、C)=(A

28、B)

29、C(结合律)A(BC)=(AB)C(结合律)A(B

30、C)=AB

31、AC(分配律)(A

32、B)C=AC

33、BC(分配律)Aε

34、εA=AA*=AA*

35、ε=A

36、A*=(A

37、ε)*(A*)*=A*■正规式的性质9/30/20217信息学院孙丽云■正规文法与正规式正规文法与正规式都是描述正规集的工具。对任意一个正规文

38、法，存在定义同一语言的正规式；反之，对每个正规式存在一个生成同一语言的正规文法。●3型（正规文法）：(左线性)P：Ut或UWt其中U、W∈Nt∈T(右线性)P：Ut或UtW其中U、W∈Nt∈T9/30/20218信息学院孙丽云■正规文法到正规式的转换(1)将正规文法中的每个非终结符表示成关于它的一个正规式方程，获得一个联立方程组。(2)依照求解规则:若x=αx

39、β(或x=αx+β)，则解为x=α*β;若x=xα

40、β(或x=xα+β)，则解为x=βα*;以及正规式的分配律、交换律和结合律求关于文法开始符号的正规式方程组的解.这个解是关于该文法开始符号S的一个正规式，显然它表

41、示了由该正规文法所描述的语言。9/30/20219信息学院孙丽云■正规文法到正规式的转换举例◆例3.4设有正规文法G：Z0AA0A

42、0BB1A

43、ε试给出该文法生成语言的正规式。解(1)联立方程组（用+代替正规式中的

44、）(2)依照求解规则求解9/30/202110信息学院孙丽云■正规文法到正规式的转换举例◆例3.5设有正规文法G：AaB

45、bBBaC

46、a

47、bCaB试给出该文法生成语言的正规式。解(1)联立方程组（用+代替正规式中的

48、）(2)依照求解规则求解练习9/30/2