编译原理第3讲.ppt

《编译原理第3讲.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)*请画出它的状态转换图01aab2.2词法记号的描述与识别2.2.4转换图关系算符的转换图051624837return(relop,LE)retu

4、rn(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、digit)*1、检查保留字表，如果在表中发现该词法单元则返回相应的记号并退出，否则转向22、该词法单元是标识符，在符号表中查找，若找到该词法单元则返回该条目的指针并退出，否则

11、执行33、在符号表中建立一个新的条目，把该词法单元填入，并返回此新条目的指针2.2词法记号的描述与识别无符号数的转换图开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/Edigitotherotherreturn(install_num())*numdigit+(.digit+)?(E(+

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

13、tab

14、newlinewsdelim+2122开始delimother*delim202.3有限自动机正规式计算机实现状态转换图？有限自动机不确定

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

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

17、b

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

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

20、b)*ab的DFA优点：1、输入字符不包括2、一个状态对于某个字符，只可能存在唯一条输出边2.3有限自动机2.3.3NFA到DFA的变换子集构造法DFA的一个状态是NFA的一个

21、状态集合读了输入a1a2…an后，NFA能到达的所有状态：s1,s2,…,sk，则DFA到达状态{s1,s2,…,sk}2.3有限自动机19开始0abab6782345输入符号ab状态2.3有限自动机19开始0abab6782345输入符号abA状态A={0,1,2,4,7}2.3有限自动机19开始0abab6782345输入符号abAB状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}2.3有限自动机19开始0abab6782345输入符号abABB状态A={0,1,2,4,7}B={1,2,3,4,6,7

22、,8}2.3有限自动机19开始0abab6782345输入符号abABCB状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自动机19开始0abab6782345输入符号abABCBC状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自动机19开始0abab6782345输入符号abABCB