编译原理234词法剖析.pptx

引论复习 第二章主要内容 词法分析的软件工程 引入的数学模型 正规式 状态转换图 2 第二章 词法分析 while ，_ ( ，_ id ，指向i的符号表指针 = ，_ id ，指向j的符号表指针 ) ，_ id ，指向i的符号表指针 - - ，_ ； ，_ 源程序 扫描器 scanner 1、关键字 2、标识符 5、界符 4、运算符 3、常数 由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：Pascal中的begin，end，if等。 界符：如逗号、分号、括号、/*，*/ 等。它是确定的。 运算符：如+、-、*、/ 等。它是确定的。 常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。 用来表示各种名字，如变量名、数组名、过程名等。它是不限的。 词法分析与语法分析的关系 词法分析器的设计 词法记号、模式、词法单元 记号名 词法单元例举 模式的非形式描述 if if 字符i, f for for 字符f, o, r relation , = , = , … 或 = 或 = 或 … id sum, D5 由字母开头的字母数字串 number 3.1, 2.8E12 任何数值常数 literal “seg. error” “和”之间任意不含 引号本身的字符串 id，指向符号表中position条目的指针 assign _ op id，指向符号表中initial条目的指针 add_op id，指向符号表中rate条目的指针 mul_ op number，整数值60 position = initial + rate * 60的记号和属性值 例题 position = initial + rate * 60 id, 1 = id, 2 + id, 3*60 字符流 语法分析 position = initial + rate * 60 id, 1 = id, 2 + id, 3*60 position = initial + rate * 60 id, 1 = id, 2 + id, 3*60 三地址中间代码 MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 历史上词法定义中的一些问题 忽略空格带来的困难 DO 8 I = 3. 75 等同于 DO8I = 3. 75 DO 8 I = 3, 75 关键字不保留 IF THEN THEN THEN=ELSE；ELSE … 关键字、保留字和标准标识符的区别 保留字是语言预先确定了含义的词法单元 标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义 词法错误 词法分析器对源程序采取非常局部的观点 例：难以发现下面的错误 fi (a == f (x) ) … 在实数是“数字串.数字串”格式下，可以发现下面的错误 123.x 紧急方式的错误恢复 删掉当前若干个字符，直至能读出正确的记号 错误修补 进行增、删、替换和交换字符的尝试 2.2.1 串和语言 字母表：符号的有限集合， 例： ∑ = { 0, 1} 串： 符号的有穷序列，例：0110, ε 语言： 字母表上的一个串集 {ε, 0, 00, 000, …}, {ε}, ∅ 句子： 属于语言的串 串的运算 连接（积）: xy，sε = εs = s 幂: s0为ε，si为si-1s（i 0） 语言的运算 并： L ∪ M = {s | s ∈L 或 s ∈ M } 连接： LM = {st | s ∈ L 且 t ∈ M} 幂： L0是{ε}，Li是Li-1L 闭包： L∗ = L0 ∪ L1 ∪ L2 ∪ … 正闭包： L+ = L1 ∪ L2 ∪ … 例 L: { A, B, …, Z, a, b, …, z }, D: { 0, 1, …, 9 } L ∪ D, LD, L6, L*, L(L ∪ D )*, D+ 含有偶数个0和偶数个1的01串 (00|11)* ( (01|10) (00|11)* (01|10) (00|11)*)* 作业解答2.3 叙述由下列正规式描述的语言 0(0|1)*0 ((ε|0)1*)* (0|1)*0(0|1)(0|1) 0*10*10*10* (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 2