词法分析14-3.

1、第三章第三章 词法分析词法分析 1) 1) 单词符号的表示单词符号的表示 例例3-1: 3-1: 单词符号序列单词符号序列 while( while( * *p != 0 ) p+; p != 0 ) p+; 2) 2) 词法分析程序（扫描器）的词法分析程序（扫描器）的 工作方式工作方式 词法分析词法分析 表格管理表格管理 语法分析语法分析 源程序源程序 单词单词 符号表符号表 常数表常数表 设计与实现设计与实现 3.2 3.2 正规式和正规文法正规式和正规文法 例：标识符（名字）的描述例：标识符（名字）的描述 正则式的运算符正则式的运算符 例：标识符的文法表示例：标识符的文法表示 表示方法不

2、是唯一的表示方法不是唯一的 2) 2) 正规文法与正规式正规文法与正规式 正规式转换到正规文法正规式转换到正规文法 3.3 3.3 单词的识别单词的识别 单词种类单词种类词法描述词法描述 标识符标识符 L ( L | D ) * 整数整数 D ( D ) * 赋值符赋值符 : = 其他运算符其他运算符 单词的设计单词的设计 状态图状态图 123 L L 或或 D 其他其他 初态初态终态终态 2 2）右线性文法）右线性文法 状态图状态图 例例3-3 3-3 的状态图的状态图( (合并后合并后) ) L | D L （IDN，入口），入口） D D （NUM，值），值） （ASG，_） = ： +

3、 （ADD，_） 基于状态图的单词识别基于状态图的单词识别 例例3-4 3-4 语言无符号整数的描述语言无符号整数的描述 整数的状态图（整数的状态图（1/21/2） 3421 0 0-7 0-7 561 0 1-9 0-9 十进制整数十进制整数 八进制整数八进制整数 有限自动机：有限自动机：状态图的形式化状态图的形式化 识别无符号整数的自动机识别无符号整数的自动机 M = （0,9, 1,6, 1, 4,6, ） FA的确定性：映射函数不同的确定性：映射函数不同 将将NFA构造构造 DFA的方法的方法 1、从开始状态出发；、从开始状态出发； 2、选择每个输入字符，构成目标状态集、选择每个输入字

4、符，构成目标状态集 3、从每个新状态集出发，重复、从每个新状态集出发，重复1、2 4、直到不出现新状态集为主、直到不出现新状态集为主 1 0 8-9 2,6 5,6 2,6 3,41-7 5,6 3,4 3,4 5,6 5,6 5,6 3,43,4 5,6 输入字符输入字符 状态集状态集 将每个状态集都作为将每个状态集都作为1个新状态，得到个新状态，得到 DFA M = （0,9, 1,26,34,56, 1, 34,56, ） （OCT，值），值） 得到的得到的DFADFA 1 0 26 34 0-7 0-7 其他其他 56 1-9 0-9 其他其他（DEC，值），值） 其他 3.4 词法分析器的设计与实现词法分析器的设计与实现 2) 2) 状态图的实现：状态图的实现：词法分析程序词法分析程序 扫描器的设计扫描器的设计 例例3-5 scan( )3-5 scan( )的实现算法的实现算法 符号表与标识符符号表与标识符 其他实现问题其他实现问题: : 3) 3) 小结小结正规式正规式 正规文法正规文法 状态图状态图 / NFA DFA 识别过程的实现算法识别过程的实现算法 程