《词法分析》ppt课件

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

1、第四章词法分析考查重点基本概念：正规式、正规集、有穷自动机(DFA与NFA）基本方法：由正规文法或自然语言描述求正规式由正规式构造有穷自动机(FA)确定化(NFA→DFA)，DFA最小化正规文法与有穷自动机转换4.1词法分析程序的设计1、词法分析（lexicalanalysis）逐个读入源程序字符并按照构词规则切分成一系列单词。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。2、词法分析程序源

2、程序词法分析程序语法分析程序Tokengettoken….主要任务：读源程序，产生单词符号其他任务：滤掉空格，跳过注释、换行符追踪换行标志，标志出错源程序，宏展开，……单词符号一般可分为下列五种：1、基本字（关键字）：if,while,等2、标识符：如常量名、变量名、过程名等3、常数（量）：25,3.1415,TRUE,“ABC”等4、运算符：如+-*/<<=等5、界符：逗号，分号，括号等输出表示（单词类别，单词自身的值）例：A:=B+2(2,指向A的符号表的入口指针）(4,‘:=’)(2,指向B的符号表的入口指针)(4,‘+’)(3,‘2’)词法分析工作独立的原因：

3、简化设计：词法分析比语法分析简单，如果与语法分析一起，会导致程序结构复杂。改进编译效率：编译的大部分时间花在扫描字符区分单词上，专门的词法分析可加快编译速度。增加编译系统的可移植性。4.2单词的描述工具词法：单词符号的文法，用来描述高级语言中的：标识符、常数、运算符、分界符、关键字单词的描述工具：正规文法      正规式一、正规文法与单词描述1、正规文法G=（VN，VT，P，S），P中每一产生式的形式都为：右线性：A→aBA→a左线性：A→BaA→a其中A∈VN，B∈VN，a∈VT注：正规文法中可能既右线性文法又左线性文法?。2、程序设计语言几类单词的描述如：程序设计

4、语言(l表示a～z中的任一英文字母,d表示0～9中的任一数字。)<标识符>→l<字母数字>

5、l<字母数字>→l

6、d

7、l<字母数字>

8、d<字母数字><无符号整数>→d

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

10、-

11、*

12、/

13、=

14、<<等号>

15、><等号><等号>→=<关键字>→if

16、while

17、else无符号实数：（其中s表示正或负号)〈无符号实数〉→d〈余留无符号数〉

18、.〈十进小数〉

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

20、.〈十进小数〉

21、e〈指数部分〉

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

23、d〈余留十进小数〉

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

25、

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

27、ε如25.55e+5和2.1思考：以上文法为几型文法？二、正规式和正规集1、正规式和正规集递归定义：字母表，辅助表‘={，，，，，，}和都是上的正规式，它们所表示的正规集分别为{}和；任何a，a是上的一个正规式，它所表示的正规集为{a}；假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(

28、e1))。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。相关说明：其中“”读“或”（也可用“+”代替“”的）“”读“连接”；“”读“闭包”（任意有限次的自重复连接）连接符“”一般可省略不写。“(”,“)”并非正规式的运算符。规定算符的优先顺序为“”、“”、“”。“”、“”和“”都是左结合的。在不致混淆时，括号可省去。如：((r·(s*))

29、r)=r·s*

30、rr*(s*

31、r)圆括号不可略去例4.2令={a，b}，上的正规式和相应的正规集的例子有：正规式正规集（特点）a{a}ab{a,b}a

32、b{ab}a{,a,a,……任意个a的串}(ab){,a,b,aa,ab……所有由a和b组成的串}(ab)(ab){aa,ab,ba,bb}(ab)(aabb)(ab){上所有含有两个相继的a或两个相继的b组成的串}思考：表示上所有以a开始，以b结尾串的正规式？程序设计语言中的单词都可由正规式来定义：例={l，d}，r=l(ld)定义的正规集:{l,ll,ld,ldd,……}（标识符）例4.3={d，.，e，+，-},则上的正规式dd(.dd)(e(+-)dd)表示的是无符号数