第4章词法分析ppt课件.ppt

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

1、第4章词法分析词法分析程序的设计单词的描述工具有限自动机正规式和有穷自动机的等价性正规文法和有穷自动机间的转换词法分析程序的自动构造工具返回目录逐个读入源程序字符并按照构词规则切分成一系列单词。4.1词法分析程序的设计词法分析（lexicalanalysis）单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词法分析程序源程序词法分析程序语法分析程序T

2、okengettoken….主要任务：读源程序，产生单词符号。滤掉空格，跳过注释、换行符。追踪换行标志，复制出错源程序。宏展开，……其他任务：单词符号单词符号一般可分为下列五种：基本字（关键字）：begin,end,if,while,var等。标识符：各种名称，如常量名、变量名、过程名等。常数（量）：25,3.1415,TRUE,“ABC”等运算符：如+-*/<<=等。界符：逗号，分号，括号等。输出表示（单词种别，单词自身的值）。单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5。如：程

3、序段ifi=5thenx∶=y；在经词法分析器扫描后输出的单词符号和它们的表示如下：程序段ifi=5thenx∶=y-保留字if(3，'if')　-标识符i(1，指向i的符号表入口)　-等号=(4，'=')　-常数5(2，'5')　-保留字then(3，'then')　-标识符x(1，指向x的符号表入口)　-赋值号∶=(4，'∶=')　-标识符y(1，指向y的符号表入口)　-分号；(5，'；')词法分析工作独立的原因：简化设计改进编译效率增加编译系统的可移植性单词的描述工具文法G=（VN，VT，P，S），P中每一

4、产生式的形式都为：A→aB或A→a，其中A∈VN，B∈VN，a∈VT。几类单词的描述标识符：〈标识符〉→l

5、l〈字母数字〉〈字母数字〉→l

6、d

7、l〈字母数字〉

8、d〈字母数字〉4.2正则表达式和正规集正规文法无符号整数：〈无符号整数〉→d

9、d〈无符号整数〉运算符：〈运算符〉→+

10、-

11、*

12、/

13、=

14、<〈等号〉

15、>〈等号〉……〈等号〉→=界符：〈界符〉→,

16、;

17、(

18、)

19、……无符号实数：〈无符号实数〉→d〈余留无符号数〉

20、.〈十进小数〉

21、e〈指数部分〉〈余留无符号数〉→d〈余留无符号数〉

22、.〈十进小数〉

23、e〈指数部分〉

24、ε〈十

25、进小数〉→d〈余留十进小数〉〈余留十进小数〉→e〈指数部分〉

26、d〈余留十进小数〉

27、ε〈指数部分〉→d〈余留整指数〉

28、s〈整指数〉〈整指数〉→d〈余留整指数〉〈余留整指数〉→d〈余留整指数〉

29、ε其中s表示正或负号。如25.55e+5和2.1正规式(regularexpression)正规式和它所表示的正规集设字母标为，辅助字母表'={，，，，，，}。1。和都是上的正规式，它们所表示的正规集分别为{}和；2。任何a，a是上的一个正规式，它所表示的正规集为{a}；3。假定e1和e2都是上的正规式

30、，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))。4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。说明：其中的“”读为“或”（也有使用“+”代替“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可

31、省略不写。“”、“”和“”都是左结合的。例4.2令={a，b}，上的正规式和相应的正规集的例子有：正规式正规集a{a}ab{a,b}ab{ab}(ab)(ab){aa,ab,ba,bb}a{,a,a,……任意个a的串}(ab){,a,b,aa,ab……所有由a和b组成的串}(ab)(aabb)(ab){上所有含有两个相继的a或两个相继的b组成的串}例={l，d}，r=l(ld)定义的正规集:{l,ll,ld,ldd,……}，其中l代表字母，d代表数字，正规式，即是字母(字母

32、数字)*

33、，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。例4.3={d，.，e，+，-},则上的正规式d(.dd)(e(+-)dd)表示的是无符号数的集合，其中d为0~9的