第02讲-词法分析-I.pptVIP

中国科大 本讲纲要 词法分析概念 词法记号的描述 词法分析器的功能： 第二章 词法分析 本章内容 词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务 介绍正规式、状态转换图和有限自动机概念 Lex与词法分析器的自动生成 词法分析：编译第一步 看一个中文的句子 词法分析：编译第一步 C语言的语句例子 词法单元、词法记号 词法单元 又称单词，是编程语言中合法的字符串 词法单元、词法记号 词法单元 又称单词，是编程语言中合法的字符串 词法记号 满足某种规则的词法单元，采用同一种记法——词法记号。 词法单元与词法记号 满足一个给定规则的词法单元，被记为一个词法记号 词法模式 C语言的标识符 ? x2, 12, _12, _abc 哪些是合法的C标识符？ 词法模式 词法记号 词法单元例举 模式的非形式描述 STRUCT struct struct FOR for for RELOP , = , = , … 或 = 或 = 或 … ID sum, _12, _x _或字母开头的 由_、字母和数字组成的串 NUM 3.1, 10, 2.8 E12 任何数值常数 LITERAL “seg. error” 引号“和”之间的任意字符 串，但引号本身除外 2.1 词法记号及属性 2.1.1 词法记号、模式、词法单元 词法记号的属性 词法记号的属性 如果简单地把词法记号流传给语法分析器，会产生什么后果？ 语义被完全摒弃，只剩下一个语法结构 词法记号的属性 每个词法记号具有一定的含义（属性） 2.1 词法记号及属性 position := initial + rate * 60的记号和属性值： ?id，指向符号表中position条目的指针? ?assign _ op， ? ?id，指向符号表中initial条目的指针? ?add_op，+? ?id，指向符号表中rate条目的指针? ?mul_ op, *? ?num，整数值60? 课后练习 prog1: 编写一个程序，用于统计文件中单词的总数，不同单词的数目。 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,…}, {?}, ? 2.2 词法记号的描述与识别 2.2.1 串和语言 串的运算 连接 xy，s? = ?s = s 积（指数） s0为?，si为si -1s（i 0） 2.2 词法记号的描述与识别 语言的运算 和：L∪M = {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 } L∪D, LD, L6, L*, L(L∪D )*, D+ *Copyright ? 2009, Software School 词法分析器 语法分析器 语义分析器 源程序 中间代码 生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表 管理器 词法分析器 记号（token）流 源代码 ? ? 词法分析器 语法分析器 符号表 记号 取下一个记号 源程序 你们 是 优秀的 大工学子 代词 动词 形容词 名词（短语） 通过分词操作，我们会把句子以单词或者词组为单位进行划分，得到一个句型。 L1 : x = ID COLON ID ASSGN y2 + 12 ; ID PLUS INT SEMI-COL 编译的词法分析做的工作类似于分词， 把原始的字符串流形式的程序