[编译原理课件第3章..ppt

第3章? 词法分析 3.1 词法分析器的功能 3.2 单词的描述 3.3 单词的识别 3.4 词法分析程序的自动生成 3.5 本章小结 3.1 词法分析器的功能 功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成“等价的”单词(记号)序列 根据词法规则识别及组合单词，进行词法检查 对数字常数完成数字字符串到二进制数值的转换 删去空格字符和注释 例3.1 语句if count7 then result := 3.14的单词符号序列 (IF，0) (ID，指向count 的符号表入口) (GT，0) (INT，7) (THEN，0) (ID，指向result的符号表入口) (ASSIGN，0) (REAL，3.14) (SEMIC，0) 3.1.3 源程序的输入缓冲与预处理 超前有哪些信誉好的足球投注网站和回退 双字符运算符（**, /*,:=,…） DO 90 k=1,10 DO 90 k=1.10 缓冲区 假定源程序存储在磁盘上，这样每读一个字符就需要访问一次磁盘，效率显然是很低的。 空白字符的剔除 剔除源程序中的无用符号、空格、换行、注释等 3.1.4 词法分析阶段的错误处理 1．非法字符检查 2．关键字拼写错误检查 3．不封闭错误检查 4．重复说明检查 5．错误恢复与续编译 紧急方式恢复(panic-mode recovery) 反复删掉剩余输入最前面的字符，直到词法分析器能发现一个正确的单词为止。 3.1.5 词法分析器的位置 以语法分析器为中心的优点：比较简单 以词法分析作为独立的一个阶段： 简化编译器的设计。 提高编译器的效率。 增强编译器的可移植性。 3.2 单词的描述3.2.1 正则文法 正则文法G = (V，T，P，S)中，对?α?β∈P，α?β均具有形式A?w或A?wB(A?w或A?Bw)，其中A，B∈V，w∈T+。 例3.2 标识符的文法 id ? A|B|…|X|a|b|…|z id ? idA|idB| … |idZ id ? ida|idb| … |idz id ? id0|id1|id2|… |id9 例3.2 标识符的文法或者定义为 约定：用digit表示数字：0,1,2,…,9; 用letter表示字母：A,B,…,Z,a,b,…,z id ? letter | iddigit | idletter letter ? A | B | … | Z | a | b | … | z digit ? 0 | 1 | 2 | … | 9 例3.3 无符号数的文法 3.2.2 正则表达式 例3.2：标识符的另一种表示 letter(letter|digit)* | 表示或 * 表示Kleene闭包 + 表示正闭包 ？表示“0或1个” Letter和(letter|digit)*的并列表示两者的连接 正则式r表示正则集,相应的正则集记为 L(r) 3.2.2 正则表达式(续)—RE 定义3.1 设∑是一个字母表，则∑上的正则表达式及其所表示的正则语言可递归地定义如下： ⑴ ?是∑上的一个正则表达式，它表示空集； ⑵ ε是∑上的一个正则表达式，它表示语言{ε}； ⑶ 对于?a(a∈∑)，a是∑上的一个正则表达式，它表示的正则语言是{a}； ⑷ 假设r和s都是∑上的正则表达式，它们表示的语言分别为L(r)和L(s)，则： ① (r)也是∑上的正则表达式，它表示的语言为L(r)； ② (r|s)也是∑上的正则表达式，它表示的语言为L(r)∪L(s)； ③ (r?s)也是∑上的正则表达式，它表示的语言为L(r)L(s)； ④ (r*)也是∑上的正则表达式，它表示的语言为(L(r))*； ⑸ 只有经有限次使用上述规则构造的表达式才是∑上的正则表达式。 正则表达式中的运算优先级 运算优先级和结合性: *高于“连接” 和| ， “连接” 高于 | |具有交换律、结合律 “连接” 具有结合律、和对|的分配律 ( )指定优先关系 意义清楚时，括号可以省略 例子 令?={a，b}， ?上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} a?b {a,b} ab {ab} (a?b)(a?b) {aa,ab,ba,bb} a? {? ,a,a, ……任意个a的串} (a?b)? {? ,a,b,aa,ab ……所有由a和b组成的串} (a?b)?(aa?bb)(a?b)? {??上所有含有两个相继的a或两 个相继的b组成的串} 设r,s,t为正规式，正规式服从的代数规律有： 1.r?s=s?r “或”服从交换律 2.r?(s?t)=(r?s)?