资源描述
温故知新,编译原理的内容及学习意义 翻译器、编译器的定义 编译器的阶段划分及前端、后端的概念 “遍” 的概念,下列程序中哪些不是编译程序的组成部分？ A 词法分析 B代码读入 C 语法分析 D代码生成 对下列错误信息，请指出可能是编译的哪个阶段报告的。 else没有匹配的if 数组下标越界 声明和使用的函数没有定义 零做除数 在数中出现非数字字符,语法分析,语义分析或代码生成,语义分析,代码优化或语义分析,词法分析,B代码读入,判断 高级语编写的源程序都必顺通过编译,产生目标代码后才能运行. 多遍扫描的编译程序的多遍是指多次重复读源程序. 就执行速度而言,编译后再执行程序比解释执行程序慢.,(),(),(),第二章 词法分析,本章内容 词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务 围绕词法分析器的自动生成展开 介绍正规式、状态转换图和有限自动机概念,词法分析器的功能：,2.1 词法记号及属性,2.1.1 词法记号、模式、词法单元 词法单元：又称单词，是源程序中的字符串。 词法记号：满足某种规则的词法单元，采用同一种记法词法记号。该规则称为模式。 模式：描述词法单元与词法记号对应关系的规则。是描述源程序中某个记号的词法单元集合的规则。,2.1 词法记号及属性,历史上词法定义中的一些问题 忽略空格带来的困难 DO 8 I 3. 75 DO8I 3. 75 DO 8 I 3, 75 关键字是否保留 IF THEN THEN THEN=ELSE；ELSE ,2.1 词法记号及属性,2.1.1 词法记号、模式、词法单元,源程序字符流,顺序组合,词法单元,词法记号,模式,例：,var count : integer ; count = 5 ;,词法单元,C语言的标识符 ? x2, 12, _12, _abc 哪些是合法的C标识符？,C语言标识符的规则（模式）： 首字符必须是_或者字母，由_、字母或数字组成的字符串,2.1 词法记号及属性,2.1.1 词法记号、模式、词法单元 词法记号词法单元例举模式的非形式描述 var var var for for for relation , = , = , 或 = 或 = 或 id sum, count, D5由字母开头的字母数字串 num3.1, 10, 2.8 E12任何数值常数 literal “seg. error”引号“和”之间的任意字符 串，但引号本身除外,常见记号及模式的例子：,2.1 词法记号及属性,2.1.1 词法记号、模式、词法单元,词法记号词法单元例举模式的非形式描述 relation , = , = , 或 = 或 = 或 id sum, count, D5由字母开头的字母数字串,词法记号词法单元例举模式的非形式化描述 名词大连 软件 大黑山 表示名称的词 连词和 与 或 和 与 或 .,词法记号词法单元例举模式的非形式描述 中国人胡锦涛 毛泽东具有中国国籍的人 美国人奥巴马 克林顿具有美国国籍的人,词法记号的属性,存在的意义？,词法记号的属性,如果简单地把词法记号流传给语法分析器，会产生什么后果？ 语义被完全摒弃，只剩下一个语法结构,我是学生,Pronoun Verb Noun,翻译官,说了什么呀？,词法记号的属性,每个词法记号具有一定的含义（属性）,L1,:,x,=,ID,COLON,ID,ASSGN,y2,+,12,;,ID,PLUS,INT,SEMI-COL,第一个ID，名称是L1, 表示的是标号（Label）,第二个ID，名称是x, 表示的是一个变量，类型是int,第三个ID，名称是y2, 表示的是一个变量，类型是int,2.1 词法记号及属性,2.1.2 词法记号的属性 position := initial + rate * 60的记号和属性值： id，指向符号表中position条目的指针 assign _ op， id，指向符号表中initial条目的指针 add_op，+ id，指向符号表中rate条目的指针 mul_ op, * num，整数值60,2.1 词法记号及属性,2.1.2 词法记号的属性 练习题（要求使用伪代码给出算法）： 编写一个程序，用于统计文件中单词的总数，不同单词的数目。 eg: I love Dalian and I love DLUT 单词总数：7 不同单词数目：5,2.1 词法记号及属性,2.1.3 词法错误 词法分析器对源程序采取非常局部的观点,难以发现下面的错误 fi (a = f (x) ) 但是也有例外，如在实数是a.b格式下，可以发现下面的错误 123.,2.1 词法记号及属性,2.1.3 词法错误 恢复策略 “紧急方式” 错误修补尝试 删除一个多余的字符 插入一个遗漏的字符 用一个正确的字符代替一个不正确的字符 交换两个相邻的字符,2.2 词法记号的描述与识别,2.2.1 串和语言 字母表/字符类：符号（英文字母、标点符号等）的有限集合， 例： = 0,1 串：符号的有穷序列，例：0110, 语言：字母表上的一个串集 ,0,00,000, , 句子/字：属于语言的串,字母,组合,串,语言,集合,集合,字母表,词法单元,记号,模式,长度为0的空串,长度的表示|a|,2.2 词法记号的描述与识别,2.2.1 串和语言 串的运算 连接xy，s = s = s 积（指数）s0为，si为si -1s（i 0）,2.2 词法记号的描述与识别,语言的运算 和：LM = s | s L 或 s M 连接：LM = st | s L 且 t M 指数：L0是 ，Li是Li -1L 闭包：L = L0 L1 L2 正闭包： L+ = L1 L2 例2.2（p17） L: A, B, , Z, a, b, , z , D: 0, 1, , 9 LD, LD, L6, L*, L(LD )*, D+,2.2 词法记号的描述与识别,2.2.2 正规式 正规式：按照一组定义规则，由较简单的正规式构成的，每个正规式 r 表示一个语言 L(r).定义规则说明 L(r) 是怎样以各种方式从 r 的子正规式所表示的语言组合而成。正规式用来表示简单的语言，叫做正规集。,正规式是用于说明词法单元如何对应到词法记号的模式。与非形式化的描述相比，正规式更具形式化，更加精确。,2.2 词法记号的描述与识别,2.2.2 正规式 正规式 定义的语言 备注 a aa (r) | (s) L(r)L(s) r和s是正规式 (r)(s) L(r)L(s)r和s是正规式 (r)*(L(r)* r是正规式 (r)L(r) r是正规式 运算符的优先级： * 连接运算 | (a) (b)*)| (c)可以写成ab*| c,2.2 词法记号的描述与识别,正规式的例子 = a, b a | ba, b (a | b) (a | b )aa, ab, ba, bb aa | ab | ba | bbaa, ab, ba, bb a*由字母a构成的所有串集 (a | b)*由a和b构成的所有串集 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：01001101000010000010111001,2.2 词法记号的描述与识别,2.2.3 正规定义 对正规式命名，使表示简洁。 d1 r1 d2 r2 . . . dn rn 各个di的名字都不同 每个ri都是 d1, d2, , di-1 上的正规式,这样就保证了，每个名字对应的正规式中使用的各种符号已经在前面定义了，从而可以避免递归定义的情况。,2.2 词法记号的描述与识别,正规定义的例子 Pascal语言的标识符集合 letter A | B | | Z | a | b | | z digit 0 | 1 | | 9 id letter(letter|digit)*,2.2 词法记号的描述与识别,正规定义的例子 Pascal无符号数集合，例1946,11.28,63.6E8,1.99E6 digit 0 | 1 | | 9 digits digit digit* optional_fraction .digits| optional_exponent (E ( + | | ) digits ) | numdigits optional_fraction optional_exponent 简化表示 num digit+ (.digit+)? (E(+|)? digit+)?,简化规则： r+=rr* r?=r| a-z=a|b|c|z abc=a|b|c,2.2 词法记号的描述与识别,正规定义的例子,while while do do relop | | = id letter (letter | digit )* num digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+,前面所提到的词法记号，实际上就是正规式的名字！,小结,词法分析器工作原理：,习题,作业 习题 2.3 练习题（要求使用伪代码给出算法）： 编写一个程序，用于统计文件中单词的总数，不同单词的数目。（假设输入文件中只包含字母和空格） eg: I love Dalian and I love DLUT 单词总数：7 不同单词数目：5,
展开阅读全文