编译88教学ppt课件

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

1、温故知新源程序字符流顺序组合词法单元词法记号模式非形式化描述形式化描述正规式字母组合串语言集合集合字母表名字连接指数和LUM连接LM闭包L*正闭包L+?计算机实现状态转换图词法记号的识别词法记号的识别等同于对字符串的匹配过程这个匹配过程可以基于有限自动机来完成简单的正规式d->a01a开始正规式d->ab02a1b开始正规式d->a

2、b01ab开始正规式d->a*0a开始自动机的定义正规式d->a?字符a出现一次或者0次01a开始练习正规式d->a(a

3、b)*请画出它的状态转换图01aab开始2.2词法记号的描

4、述与识别2.2.4转换图关系算符的转换图051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)开始<=>=>=**otherotherrelop<

5、<=

6、=

7、<>

8、>

9、>=2.2词法记号的描述与识别标识符和保留字的转换图91011开始letterother*letter或digitreturn(install_id())idletter(letter

10、

11、digit)*1、检查保留字表，如果在表中发现该词法单元则返回相应的记号并退出，否则转向22、该词法单元是标识符，在符号表中查找，若找到该词法单元则返回该条目的指针并退出，否则执行33、在符号表中建立一个新的条目，把该词法单元填入，并返回此新条目的指针2.2词法记号的描述与识别无符号数的转换图开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/Edigitotherotherreturn(install_num())*numdigit+(.dig

12、it+)?(E(+

13、)?digit+)?2.2词法记号的描述与识别空白的转换图delimblank

14、tab

15、newlinewsdelim+2122开始delimother*delim202.3有限自动机正规式计算机实现状态转换图？有限自动机不确定有限自动机确定有限自动机等价4.3有限自动机标识符无符号整数单界符双界符S1非字母数字字母字母、数字2非数字数字数字3其他字符+*，（）出口4其他字符<5=非=出错其他读字符查保留字表返回S状态图的形式化描述2.3有限自动机识别器：是一个程序，取串x作为输入，当x

16、是语言的句子时，它回答“是”，否则回答“不是”。状态转换图（有限自动机）识别器确定/不确定有限自动机——时空权衡问题确定有限自动机：快，空间大2.3有限自动机2.3.1不确定的有限自动机（简称NFA）一个数学模型，它包括:状态集合S；输入符号集合；转换函数move:S({})P(S)；状态s0是开始状态；FS是接受状态集合。12开始a0abb识别语言(a

17、b)*ab的NFA缺点：1、输入字符包括2、一个状态对于某个字符，可能有多条输出边2.3有限自动机12开始a0abb识别语言(a

18、b)*ab

19、的NFA输入符号ab0{0,1}{0}1{2}2状态NFA的转换表优点：快速定位缺点：字母表过大或大部分转换状态为空集时浪费空间2.3有限自动机例识别aa*

20、bb*的NFA12开始a0abb342.3有限自动机2.3.2确定的有限自动机（简称DFA)一个数学模型，包括：状态集合S；输入字母表；转换函数move:SS；唯一的初态sS；终态集合FS；12开始a0abbab识别语言(a

21、b)*ab的DFA优点：1、输入字符不包括2、一个状态对于某个字符，只可能存在唯一条输出边2.3有限自动机2

22、.3.3NFA到DFA的变换子集构造法DFA的一个状态是NFA的一个状态集合读了输入a1a2…an后，NFA能到达的所有状态：s1,s2,…,sk，则DFA到达状态{s1,s2,…,sk}12开始a0abb2.3.3NFA到DFA的变换子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1a2…an后，NFA能到达的所有状态：s1,s2,…,sk，则DFA到达状态{s1,s2,…,sk}12a开始0abb{0}{0,1}a2.3有限自动机2.3.3NFA到DFA的变换子集构造法1、DFA的一个状态

23、是NFA的一个状态集合2、读了输入a1a2…an后，NFA能到达的所有状态：s1,s2,…,sk，则DFA到达状态{s1,s2,…,sk}12a开始0abb{0}{0,1}ab2.3有限自动机2.3.3NFA到DFA的变换子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1a2…an后，NFA能到达的所有状态：s1,s2,…,sk，则DFA到达状态{s1,s2,…,sk