正则表达式ppt课件.ppt

《正则表达式ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章词法分析SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重点：词法分析器的输入、输出，用于识别符号的状态转移图的构造，根据状态转移图实现词法分析器。难点：词法的正规文法表示、正规表达式表示、状态转移图表示，它们之间的转换。第3章词法分析3.1词法分析器的功能3.2单词的描述3.3单词的识别3.4词法分析程序的自动生成3.5本章小结2021/7/2723.1词法分析器的功能功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成“等价的”单词(记号)序列

2、根据词法规则识别及组合单词，进行词法检查对数字常数完成数字字符串到二进制数值的转换删去空格字符和注释2021/7/2733.1.1单词的分类与表示&3.1.2词法分析器的输出一、单词的种类1.关键字:也称基本字，begin、end、for、do...2.标识符:由用户定义，表示各种名字3.常数:整常数、实常数、布尔常数、字符串常数等4.运算符:算术运算符+、-、*、/等；逻辑运算符not、or与and等；关系运算符=、<>、、、和等5.分界符:，、；、（、）...2021/7/274二、单词的内部形式几种常用的单词内部形式：1、按单词种类

3、分类2、保留字和分界符采用一符一类3、标识符和常数的单词值又为指示字（指针值）种别属性值表示单词的种类，可用整数编码或记忆符表示不同的单词不同的值2021/7/275单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符类别编码1234567单词值内部字符串整数值数值0或1内部字符串保留字或内部编码分界符或内部编码1、按单词种类分类2021/7/2762、保留字和分界符采用一符一类单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO………:+*,(类别编码123456789……20212223……单

4、词值内部字符串整数值数值0或1内部字符串----……-----2021/7/277例3.1语句ifcount>7thenresult:=3.14的单词符号序列(IF，0)(ID，指向count的符号表入口)(GT，0)(INT，7)(THEN，0)(ID，指向result的符号表入口)(ASSIGN，0)(REAL，3.14)(SEMIC，0)跟实现有关2021/7/2783.1.3源程序的输入缓冲与预处理超前搜索和回退双字符运算符（**,/*,:=,…）DO90k=1,10DO90k=1.10缓冲区假定源程序存储在磁盘上，这样每读一个字符就需要访问

5、一次磁盘，效率显然是很低的。空白字符的剔除剔除源程序中的无用符号、空格、换行、注释等2021/7/2793.1.3源程序的输入缓冲与预处理(续)工作区(token)单词开始指针扫描指针正拼单词输入缓冲区2021/7/2710每次移动向前指针都需要做两次测试3.1.3源程序的输入缓冲与预处理(续)双缓冲区问题__超前扫描导致的效率问题问题：如何设计和实现扫描器？大小问题128Byte*2

6、1024Byte*2

7、4096Byte*2ifforward在缓冲区第一部分末尾thenbegin重装缓冲区第二部分;forward:=forward+1endels

8、eifforward在缓冲区第二部分末尾thenbegin重装缓冲区第一部分;将forward移到缓冲区第一部分开始endelseforward:=forward+1;forward:=forward+1;ifforward↑=eofthenbeginifforward在第一部分末尾thenbegin重装第二部分;forward:=forward+1endelseifforward在第二部分末尾thenbegin重装第一部分;将forward移到第一部分开始endelse/*eof在表示输入结束*/终止词法分析end2021/7/27113.1.4词

9、法分析阶段的错误处理1．非法字符检查2．关键字拼写错误检查3．不封闭错误检查4．重复说明检查5．错误恢复与续编译紧急方式恢复(panic-moderecovery)反复删掉剩余输入最前面的字符，直到词法分析器能发现一个正确的单词为止。2021/7/27123.1.5词法分析器的位置目标程序词法分析器语法分析器语义分析与代码生成目标代码整理图3.4以语法分析器为中心源程序符号表以语法分析器为中心的优点：简化编译器的设计。提高编译器的效率。增强编译器的可移植性。2021/7/27133.2单词的描述3.2.1正则文法正则文法G=(V，T，P，S)中，对

10、αβ∈P，αβ均具有形式Aw或AwB(Aw或ABw)，其中A，B∈V，w∈T+。例3.2标识符的