资源描述：
《词法分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章 词法分析本章介绍编译第一个阶段词法分析的设计原理和设计方法，要求明确此阶段的任务。理解通常的单词分类和构词规则。会使用单词的描述和识别机制。要求掌握正规文法、状态图、DFA、NFA、正规式和正规集的基本概念和它们之间的关系。掌握词法分析程序的手工实现方法。掌握词法分析程序的自动构造原理。教学目标1.词法分析的任务2.词法分析程序的输出形式3.词法分析程序的设计与实现4.正规式与有穷自动机5.词法分析程序的自动生成工具LEX6.PL/0编译程序的词法分析教学内容（1）分析和识别单词及属性，包括识别
2、语言的关键字、标识符、常数、运算符等；（2）跳过各种分隔符，如空格，回车，制表符等；（3）删除注释；（4）进行词法检查，报告所发现的错误；（5）建立符号表。4.1 词法分析的任务main()/*ADD*/{intx=10,y=20,sum;sum=x+y;}main、(、)、{、int、x、=、10、,、y、=、20、,、sum、;、sum、=、x、+、y、;}词法分析实现方案：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍
3、第二遍单词串优点:结构清晰、各遍功能单一缺点：效率低S.P.(字符串)词法分析程序语法分析程序取单词单词单词的种类（1）关键字：if、for、while（2）标识符：（3）常数：（4）运算符：+、-、*（5）分界符：,、;、(、)4.1.2 词法分析程序的输出形式词法分析程序的输出形式-----二元式单词类别单词的属性值单词类别可以用整数编码表示:一类一种或一字一种单词类别关键字标识符常数运算符分界符编码12345表3.1intx=10,y=20,sum;词法分析的结果单词类别单词的属性值1int2指向
4、x的符号表入口指针4=3105,2指向y的符号表入口指针4=3205,2指向sum的符号表入口指针5;表4.1intx=10,y=20,sum;词法分析的结果3.5字母表,定义在上的正规式和正规集递归定义如下:1.和都是上的正规式,它们所表示的正规集分别为:{}和{};2.任何a,a是上的正规式,它所表示的正规集为:{a};3.假定U和V上的正规式,它们所表示的正规集分别记为L(e1)和L(e2),那么e1
5、e2,e1•e2和e1*也都是上的正规式,它们所表示的正规集分别为L(e1
6、)L(e2)、L(e1)•L(e2)和(L(e1))*4.任何上的正规式和正规集均由1、2和3产生。4.2 单词的描述工具4.2.1正规式与正规集正规式表示的语言称为正规集注:正规集中的每个元素就是正规文法中的一个句子正规式中的运算符：
7、-----或（选择）•----连接*或{}---重复（）----括号运算符的优先级：先*,后•,最后
8、•在正规式中可以省略.正规式相等这两个正规式表示的语言相等【例4.1】设Σ={a,b}正规式正规集ba*所有以b为首后跟任意多个a的符号串a(a
9、b)*所有以a为
10、首的符号串(a
11、b)*abb所有以abb为尾的a，b符号串(a
12、b)*(aa
13、bb)(a
14、b)*所有含有两个相继的a或相继的b的符号串(aa
15、ab
16、ba
17、bb)*空串和任何长度为偶数的符号串(a
18、b)(a
19、b)(a
20、b)*任何长度大于等于2的符号串【例4.2】使用正规式来表示下面文法中的相应单词符号。<标识符>→字母
21、<标识符>字母
22、<标识符>数字）<无符号整数>→数字
23、<无符号整数>数字<单界符>→+
24、*
25、<
26、,
27、;<双界符>→<=标识符：l(l
28、d)*无符号整数：dd*单界符：+
29、*
30、<
31、,
32、;双界
33、符：<=设r，s，t均是正规式，则有以下性质：（1）交换律：r
34、s=s
35、r（2）结合律：r
36、(s
37、t)=(r
38、s)
39、t(rs)t=r(st)（3）分配律：(r
40、s)t=rt
41、st（4）同一律：εr=rε=r1.正规文法正规式规则1规则2规则3文法产生式正规式A→xB,B→yA→xA
42、yA→x,A→yA=xyA=x*yA=x
43、y步骤1将每条产生式改写为正规式；步骤2用代入法解正规式方程组，最后只剩下一个开始符号定义的正规式，其中不含非终结符。4.2.2正规文法与正规式【例4.3】G[S]:S→aA
44、aA
45、→dA
46、d规则1规则2规则3文法产生式正规式A→xB,B→yA→xA
47、yA→x,A→yA=xyA=x*yA=x
48、yS=aA
49、aA=d*d代入:S=ad*d
50、a＝ad*2.正规式正规文法步骤1构造S→r步骤2不断利用表3.4的规则做变换,直到每个产生式最多含有一个终结符为止规则1规则2规则3文法产生式正规式A→xB,B→yA→xA
51、yA→x,A→yA=xyA=x*yA=x
52、y【例4.4】求正规式(a
53、b)(a
54、b
55、0
56、1)*对应的正规文法S
