编译原理ppt教学课件第3章词法分析

《编译原理ppt教学课件第3章词法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、S.PO.P语义分析及生成中间代码程序代码生成程序代码优化程序语法分析程序词法分析程序错误处理符号表管理第3章　词法分析本章介绍编译第一个阶段词法分析的设计原理和设计方法，要求明确此阶段的任务。理解通常的单词分类和构词规则。会使用单词的描述和识别机制。要求掌握正规文法、状态图、DFA、NFA、正规式和正规集的基本概念和它们之间的关系。掌握词法分析程序的手工实现方法。掌握词法分析程序的自动构造原理。教学目标3.1词法分析的任务3.2词法分析程序的输出形式3.3正规式与有穷自动机3.4词法分析程序的设计与实

2、现3.5词法分析程序的自动生成工具LEX教学内容（1）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符等；（2）跳过各种分隔符，如空格，回车，制表符等；（3）删除注释；（4）进行词法检查，报告所发现的错误；（5）建立符号表。3.1　词法分析的任务main()/*ADD*/{intx=10,y=20,sum;sum=x+y;}main、(、)、{、int、x、=、10、,、y、=、20、,、sum、;、sum、=、x、+、y、;、}词法分析实现方案：基本上有两种1.词法分析单独作为一遍2.

3、词法分析程序作为单独的子程序S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串优点:结构清晰、各遍功能单一缺点：效率低S.P.(字符串)词法分析程序语法分析程序取单词单词单词的种类（1）关键字：if、for、while（2）标识符：（3）常数：（4）运算符：+、-、*（5）分界符：,、;、(、)3.2　词法分析程序的输出形式词法分析程序的输出形式-----二元式单词类别单词的属性值单词类别可以用整数编码表示:一类一种或一字一种单词类别关键字标识符常数运算符分界符编码12345表3.1

4、intx=10,y=20,sum;词法分析的结果单词类别单词的属性值1int2指向x的符号表入口指针4=3105,2指向y的符号表入口指针4=3205,2指向sum的符号表入口指针5;表3.1intx=10,y=20,sum;词法分析的结果【例3.1】使用正规式来表示下列文法中的相应单词符号。<标识符>→字母

5、<标识符>字母

6、<标识符>数字<无符号整数>→数字

7、<无符号整数>数字<单界符>→+

8、*

9、<

10、,

11、;<双界符>→<=标识符：l(l

12、d)*无符号整数：dd*单界符：+

13、*

14、<

15、,

16、;双界符：<=S

17、→l

18、Sd

19、Sl左线性文法3.5字母表,定义在上的正规式和正规集递归定义如下:1.和都是上的正规式,它们所表示的正规集分别为:{}和;2.任何a,a是上的正规式,它所表示的正规集为:{a};3.假定e1和e2是上的正规式,它们所表示的正规集分别记为L(e1)和L(e2),那么e1

20、e2,e1•e2和e1*也都是上的正规式,它们所表示的正规集分别为L(e1)L(e2)、L(e1)•L(e2)和(L(e1))*4.任何上的正规式和正规集均由1、2和3产生。3.3　正规表达式与有穷

21、自动机3.3.1正规式与正规集正规式中的运算符：

22、-----或（选择）•----连接*或{}---重复（）----括号运算符的优先级：先*,后•,最后

23、•在正规式中可以省略.正规式相等这两个正规式表示的语言相等【例3.2】设Σ={a,b}正规式正规集ba*所有以b为首后跟任意多个a的符号串a(a

24、b)*所有以a为首的符号串(a

25、b)*abb所有以abb为尾的a，b符号串(a

26、b)*(aa

27、bb)(a

28、b)*所有含有两个相继的a或相继的b的符号串(aa

29、ab

30、ba

31、bb)*空串和任何长度为偶数的符号串(

32、a

33、b)(a

34、b)(a

35、b)*任何长度大于等于2的符号串设r，s，t均是正规式，则有以下性质：（1）交换律：r

36、s=s

37、r（2）结合律：r

38、(s

39、t)=(r

40、s)

41、t(rs)t=r(st)（3）分配律：(r

42、s)t=rt

43、st（4）同一律：εr=rε=r3.4　词法分析程序的设计与实现词法规则状态图词法分析程序结点代表状态，用圆圈表示，为非终结符有向弧表示状态转移弧上的标记表示在射出弧的结点状态下可能出现的输入字符，为终结符状态图：为识别单词而专门设计的有向图，是设计词法分析程序的一种好途径。SUVZ1

44、11000一张状态图包含有穷个状态，只能有一个初态，至少要有一个终态（用双圈表示）3.4.1状态图3.4.2有穷自动机标识符无符号整数单界符双界符S1非字母数字字母字母、数字2非数字数字数字3其他字符+*，（）出口4其他字符<5=非=出错其他读字符查保留字表返回S状态图的形式化描述有穷自动机是一种数学模型，具有离散的输入与输出，系统可处于有穷状态中的任何一个它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合引入有穷自动机这