编译原理课程第2讲.ppt

温故知新温故知新 编译原理的内容及学习意义编译原理的内容及学习意义 翻译器、编译器的定义翻译器、编译器的定义 编译器的阶段划分及前端、后端的概念编译器的阶段划分及前端、后端的概念 “ “遍遍” ” 的概念的概念 下列程序中哪些不是编译程序的组成部分 ？ A 词法分析 B代码读入 C 语法分析 D代码生成 对下列错误信息，请指出可能是编译的哪 个阶段报告的。 else没有匹配的if 数组下标越界 声明和使用的函数没有定义 零做除数 在数中出现非数字字符 语法分析 语义分析或代码生成 语义分析 代码优化或语义分析 词法分析 B代码读入 判断 高级语编写的源程序都必顺通过编译,产生 目标代码后才能运行. 多遍扫描的编译程序的多遍是指多次重复 读源程序. 就执行速度而言,编译后再执行程序比解释 执行程序慢. () () () 第二章第二章 词法分析词法分析 本章内容本章内容 词法分析器：把构成源程序的字符流翻译成词法分析器：把构成源程序的字符流翻译成 记号流，记号流，还完成和用户接口的一些任务还完成和用户接口的一些任务 围绕词法分析器的自动生成展开围绕词法分析器的自动生成展开 介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念 词法分析器词法分析器 语法分析器语法分析器 符号表符号表 记号记号 取下一个记号取下一个记号 源程序源程序 词法分析器的功能：词法分析器的功能： 词法分析器词法分析器 记号（记号（tokentoken）流）流 源代码源代码 2.1 2.1 词法记号及属性词法记号及属性 2.1.1 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 词法单元：又称单词，是源程序中的字符串。词法单元：又称单词，是源程序中的字符串。 词法记号：满足某种规则的词法单元，采用同一种记法词法记号：满足某种规则的词法单元，采用同一种记法 词法记号。该规则称为词法记号。该规则称为模式模式。 模式：描述词法单元与词法记号对应关系的规则。模式：描述词法单元与词法记号对应关系的规则。是描是描 述源程序中某个述源程序中某个记记记记号的号的词词词词法法单单单单元集合的元集合的规则规则规则规则 。 源程序字源程序字 符流符流 顺序顺序 组合组合 词法词法 单元单元 词法词法 记号记号 模式模式 2.1 2.1 词法记号及属性词法记号及属性 历史上词法定义中的一些问题历史上词法定义中的一些问题 忽略空格带来的困难忽略空格带来的困难 DO 8 I DO 8 I 3. 75 3. 75 DO8I DO8I 3. 75 3. 75 DO 8 I DO 8 I 3, 75 3, 75 关键字是否保留关键字是否保留 IF THEN IF THEN THENTHEN THENTHEN=ELSE=ELSE；ELSE ELSE 2.1 2.1 词法记号及属性词法记号及属性 2.1.1 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 源程序源程序 字符流字符流 顺序顺序 组合组合词法词法 单元单元 词法词法 记号记号 模式模式 例：例： varvar countcount : : integerinteger ; ; countcount = 5 5 ; ; 词法单元词法单元 C语言的标识符 ? x2, 12, _12, _abc 哪些是合法的C标识符？ C C语言标识符的规则（模式）：语言标识符的规则（模式）： 首字符必须是首字符必须是_ _或者字母，由或者字母，由_ _、字母或数字组成的字符串、字母或数字组成的字符串 2.1 2.1 词法记号及属性词法记号及属性 2.1.1 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 词法记号词法记号词法单元例举词法单元例举模式的非形式描述 模式的非形式描述 varvar varvar varvar for for forfor forfor relation relation 0 0） 2.2 2.2 词法记号的描述与识别词法记号的描述与识别 语言的运算语言的运算 和：和：L LM M = = s s | | s s L L 或或 s s MM 连接连接：LM LM = = stst | | s s L L 且且 t t MM 指数：指数：L L 0 0 是是 ，L L i i 是是L Li i -1 -1 L L 闭包：闭包： L L = = L L 0 0 L L 1 1 L L 2 2 正闭包正闭包： L L+ + = = L L 1 1 L L 2 2 例例2.22.2（p17p17） L L: : A A, , B B, , , , Z Z, , a a, , b b, , , , z z , , D D: : 0, 1, , 9 0, 1, , 9 L LD D, , LDLD, , L L 6 6 , , L L * * , , L L( (L LD D ) ) * * , , D D + + 2.2 2.2 词法记号的描述与识别词法记号的描述与识别 2.2.2 2.2.2 正规式正规式 正规式：按照一组定义规则，由较简单的正规式正规式：按照一组定义规则，由较简单的正规式 构成的，每个正规式构成的，每个正规式 r r 表示一个语言表示一个语言 L(rL(r).).定定 义规则说明义规则说明 L(rL(r) ) 是怎样以各种方式从是怎样以各种方式从 r r 的子的子 正规式所表示的语言组合而成。正规式所表示的语言组合而成。 正正规规规规式式用来表用来表 示简单的语言，示简单的语言，叫做叫做正规集正规集。 正规式是用于说明词法单元如正规式是用于说明词法单元如 何对应到词法记号的模式。与何对应到词法记号的模式。与 非形式化的描述相比，正规式非形式化的描述相比，正规式 更具形式化，更加精确。更具形式化，更加精确。 2.2 2.2 词法记号的描述与识别词法记号的描述与识别 2.2.2 2.2.2 正规式正规式 正规式正规式 定义的语言定义的语言 备注备注 a a a a a a ( (r r) | () | (s s) ) L L( (r r) )L L( (s s) ) r r和和s s是正规式是正规式 ( (r r)( )(s s) ) L L( (r r) )L L( (s s) )r r和和s s是正规式是正规式 ( (r r) ) * * ( (L L( (r r) )* * r r是正规式是正规式 ( (r r) ) L L( (r r) ) r r是正规式是正规式 运算符的优先级：运算符的优先级： * * 连接运算连接运算 | | (a) (b)a) (b) * * )| (c)| (c)可以写成可以写成abab * * | c| c 2.2 2.2 词法记号的描述与识别词法记号的描述与识别 正规式的例子正规式的例子 = = a a, , b b a a | | b b a a, , b b ( (a a | | b b) () (a a | | b b ) ) aaaa, , abab, , baba, , bbbb aaaa | | abab | | baba | | bbbb aaaa, , abab, , baba, , bbbb a a * * 由字母由字母a a构成的所有串集构成的所有串集 ( (a a | | b b) ) * * 由由a a和和b b构成的所有串集构成的所有串集 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：01001101000010000010111001 2.2 2.2 词法记号的描述与识别词法记号的描述与识别 2.2.3 2.2.3 正规定义正规定义 对正规式命名，使表示简洁。对正规式命名，使表示简洁。 d d 1 1 r r 1 1 d d 2 2 r r 2 2 . . . . . . d dn n r r n n 各个各个d d i i 的名字都不同的名字都不同 每个每个r r i i 都是都是 d d 1 1 , , d d 2 2 , , , , d di i-1 -1 上的正规式 上的正规式 这样就保证了，每个名这样就保证了，每个名 字对应的正规式中使用字对应的正规式中使用 的各种符号已经在前面的各种符号已经在前面 定义了，从而可以避免定义了，从而可以避免 递归定义的情况。递归定义的情况。 2.2 2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 Pascal语言的标识符集合 letter A | B | | Z | a | b | | z digit 0 | 1 | | 9 id letter(letter|digit)* 2.2 2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 PascalPascal无符号数集合，例无符号数集合，例 19461946, ,11.2811.28, ,63.663.6E8E8, ,1.991.99E E 6 6 digitdigit 0 0 | 1 | | 9| 1 | | 9 digitsdigits digitdigit digitdigit * * optional_fractionoptional_fraction . .digitsdigits| | optional_exponentoptional_exponent (E ( + | (E ( + | | | ) digits ) | ) digits ) | numnumdigitsdigits optional_fractionoptional_fraction optional_exponentoptional_exponent 简化表示简化表示 numnum digitdigit+ + ( (. .digit digit + + )? (E(+|)? (E(+| )? digit)? digit + + )?)? 简化规则：简化规则： (1) r+=rr* (2) r?=r| (3) a-z=a|b|c|z (4) abc=a|b|c 2.2 2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 while while while while do do do do reloprelop | | = | | = id id letter (letter | digit ) letter (letter | digit ) * * num num digit digit+ + ( (. .digit digit + + )? (E (+ | )? (E (+ | )? digit)? digit + + )?)? delimdelim blankblank | | tabtab | | newlinenewline wsws delimdelim + + 前面所提前面所提 到的词法到的词法 记号，实记号，实 际上就是际上就是 正规式的正规式的 名字！名字！ 小结小结 词法分析器 记号（token）流 源代码 词法分析器工作原理：词法分析器工作原理： 源程序 字符流 顺序顺序 组合组合 词法 单元 词法 记号 模式模式 非形式 化描述 形式化 描述 正规式 字母 组合组合 串语言 集合集合 集合集合 字母表 名