第四讲词法分析ppt课件.ppt

《第四讲词法分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四讲词法分析本章学习目标词法分析程序的主要任务是对源程序进行扫描，从中识别出单词。它是编译程序的第一步，也是编译过程中不可缺少的部分。理论基础：有限自动机理论和正则表达式正则表达式和有限自动机文法、正规表达式、正规集及自动机的相互转换词法分析器的自动生成完成实验1词法分析词法分析是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个一个的单词。编译程序中完成词法分析任务的程序段，称为词法分析程序。词法分析程序对源程序进行扫描，从中识别出一个个的单词符号，因此，词法分析程序又称

2、为词法分析器，又称扫描器。词法分析程序与语法分析程序之间接口方式一种方式是词法分析程序独立工作，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件称为语法分析程序的输入而继续编译。另一种方法，也是常用的一种方法就是把词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，就调用该程序。词法分析程序每得到一次调用，就从源程序文件中读入一个字符，直到识别出一个单词为止。这种方法省去了中间文件。取符号源程序词法分析程序语法分析程序词法分析作为语法分析子程序送符号源程序词法分析程序单词序列词法分析单独作为一遍词法分析程序的输出单词符号是程序设

3、计语言的基本语法单位和最小语义单位。程序设计语言的单词符号一般分为五类。（1）关键字（又称保留字或基本字）如if，then，else，while，do，begin和end。（2）标识符，用于表示变量名、过程名等。（3）常数，如123，实数型45.67，TRUE和“ABC”等。（4）运算符，如+，-，*，/，<，=等。（5）界限符，如逗号、分号和括号等。程序设计语言中的关键字、运算符和界限符的数量都是确定的。而常数和标识符的数量是不确定的。词法分析程序的输出词法分析程序所输出的单词符号采用二元式标识（单词种类，单词自身的值），形式如：单词类别是语法分析

4、需要的信息，单词自身的值则是编译其他阶段需要的信息。标识符有多种属性，常常记录在符号表中。单词类别单词自身值程序段ifi=5thenx:=y关键字if（3，‘if’）标识符i（1，指向i的符号表入口）等号=（4,’=’）关键字then（3,’then’）标识符x(1,指向x的符号表入口)赋值号：=（4，‘：=’）标识符y（1，指向y的符号表入口）分号;（5，‘；’）将词法分析工作分离的考虑使整个编译程序的结构更简洁、清晰和条理化编译程序的效率会改进增强编译程序的可移植性词法分析程序除了识别单词的任务外，还有一些其他任务，比如滤掉注释和空白等等单词的描

5、述工具正规文法（Chomsky3型文法）正规文法是描述正规集的文法，可用于描述程序设计语言的词法部分。正规集由正规文法产生的语言注：正规集是集合，可有穷也可无穷。也可通过正规式来形式化表示。正规文法定义的几类单词标识符<标识符>→l

6、l<字母数字><字母数字>→l

7、d

8、l<字母数字>

9、d<字母数字>其中l表示a~z中的任何一个英文字母，d表示0~9中的任何一个数字无符号整数<无符号整数>→d

10、d<无符号整数>运算符<运算符>→+

11、-

12、*

13、、

14、=

15、<<等号>

16、><等号><等号>→=界符<界符>→=,

17、;

18、(

19、)

20、…….关键词无符号实数正规式也称正规表达

21、式，表示正规集的工具。描述单词的另外一种工具。递归定义设有限字母表∑，∑’={,,

22、,.,*,(,)}则(1)，都是∑上的正规式，它表示的正规集{}和ф(2)对于任何a∈∑，a是正规式，它表示的正规集是{a}(3)若、是正规式，它们表示的正规集为L(),L()，则()、

23、、•、*、*也是正规式。它们代表的正规集分别是L(),L()UL(),L()•L(),L()*,L()*(4)仅由有限次使用上述三步骤而定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集。例：∑={a，b}正规式a表

24、示的正规集{a}正规式(a

25、b)表示的正规集{a，b}正规式ab表示的正规集{ab}正规式(a

26、b)(a

27、b)表示的正规集{aa,ab,ba,bb}正规式a*表示的正规集是{，a，aa，aaa，…..任意个a的串}正规式（a

28、b）*表示的正规集是{，a，b，aa，ab，…..所有ab组成的串}正规式(a

29、b)*(aa

30、bb)(a

31、b)*表示包含两个相继a或两个相继b组成的串无符号小数∑={d，.,e,+,-},则∑的正规式d*(.dd*

32、)(e(+

33、-

34、)dd*

35、)表示的是无符号数。其中d为0~9中的数字。正规式满足的代数规律若两个正规式e

36、1和e2所表示的正规集相同，则说e1和e2等价，写作e1=e2正规式服从的代数规律有：r

37、s=s

38、rr

39、(s