北大编译原理讲义Chapter3.ppt

《北大编译原理讲义Chapter3.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章词法分析3.1词法分析程序的设计：词法分析器的功能，输出，把它组织成单独程序3.2词法分析器的手工构造：用DFA能识别单词，构造DFA并用程序实现它3.3有限自动机：有限自动机的等价性，一个FAm,min(DFAm’)L(m)=L(m’)3.4正规表达式：单词能用正规表达式描述，能用DFA识别3.5正规文法与有限自动机的等价性3.6词法分析程序自动构造工具LEX简介1=80;0134256eniL字母字母字母字母数字数字数字==；；0124563Line=80;id,‘Line’=,num,‘80’

2、;,数字数字字母字母11==0003;;1输入输出有限控制器23.1词法分析程序的设计3.1.1词法分析程序的功能源程序单词序列3.1.2单词的词类和属性（词类符号，单词的属性值）3.1.3词法分析程序作为一个独立子程序（1）语法分析程序的子程序；（2）组织成一遍扫描。词法分析器3Whilei＜＞jdoifi＞jtheni:＝i-jelsej:=j－I‘while’，‘i’，‘＜＞’，‘j’，‘do’，‘if’，‘i’，‘＞’，‘j’,‘then’,'i',':=’,'i',’-’,'j','else','j',':=

3、','j','-',‘i'词法分析器4词类和属性computatorn.Calcculatingmachine.程序语言单词的分类：1．关键字(保留字或基本字)：begin,end2．标识符：用来表示各种名字3．字面常数：256，3.14，true,‘abc’4．运算符：如，＋、－、*、/等等5．分界符：如逗号，分号，冒号等5词法分析器的输出：（词类编码，单词自身的属性值）词类编码提供给语法分析程序使用；单词自身的属性值提供给语义分析程序使用。具体的分类设计以方便语法分析程序使用为原则。关键字可分成一类，也可以一个关键字分成

4、一类。常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。单词自身的属性值提供的内容，是由词法分析和语义分析的任务划分决定的。6例如：图3．1的源程序经词法分析器〈while，——〉〈id，指向j的符号表人口的指针〉〈relational－op，NE〉〈id，指向j的符号表人口的指针〉〈do，——〉〈if，——〉〈id，指向i的符号表入口的指针〉〈id，指向j的符号表入口的指针〉73.1.3把词法分析设计成一个独立程序（1）组织成一遍扫描；（2）作为语法分析和语义分析的子程序词法分析语法分析

5、语义分析和中间代码生成源程序中间代码符号表管理错误的诊查处理832词法分析器的手工构造为了构造词法分析器，要研究构词法，每种词类的结构模式以及识别它的数学模型——有限自动机。它的模拟程序可以作为词法分析器的控制程序。321确定的有限自动机（DFA）322构造识别单词的DFA323编写词法分析程序93.2.1确定的有限自动机DFA(DeterministicFiniteAutomata)一.设计一个奇偶校验器二.DFA的定义三.DFA的三种表示四.DFA接受的语言五.DFA判定w是否属于L(m)的模拟算法结论：如

6、果我们能构造一个DFAM，使得L(M)是编译器处理的程序语言中的单词，那么模拟DFAM的程序将可以用作词法分析器的控制程序。10一设计一个奇偶校验器DFA是由集合，序列和函数定义的数学模型，它对于上的w，判定是可接受的还是不可接受的。例如，设计一个DFAm，奇偶校验器，首先，w是由0，1组成的字符串，因此，1.={0,1}且w在一条输入带上。01011$读头112.状态集：它记忆已读入w子串的状态,m是奇偶校验器，它应该记住，初始序列是奇数个1还是偶数个1。因此，m有even和odd两个状态.3.even为开始状态。4

7、.转换函数，（qold,,a)=qnewm有:(even,,0)=even（even,1)=odd(odd,0)=odd（odd,1)=even5.接受状态（或终止状态）集{odd}若w使m从初始状态出发，最后到达一个接受状态，则w被m接受；否则w被m拒绝。12二定义3．1一个确定的有限自动机M（记作DFAM）是一个五无组Ｍ＝（Σ，Ｑ，ｑ0，Ｆ，δ），其中（ａ）Ｑ是一个有限状态集合。（ｂ）Σ是一个字母表，它的每个元素称为一个输入符号。（ｃ）ｑ0∈Ｑ，ｑ0称为初始状态。（ｄ）Ｆ∈Ｑ，Ｆ称为终结状态集合。（ｅ）δ是一

8、个从Ｑ×Σ到Ｑ的单值映射δ(ｑ，ａ)＝ｑ’（ｑ,ｑ’∈Ｑ，ａ∈Σ）表示当前状态为q,输入符号为a时，自动机将转换到下一个状态ｑ’，ｑ’称为ｑ的一个后继。13例3．3设ＤＦＡ　Ｍ＝（｛ａ，ｂ｝，｛０，１，２，３｝，０，｛３｝，δ）其中δ（０，ａ）＝１，δ（１，ａ）＝3δ（２，ａ）＝１，δ（３