第3章词法分析 3.1词法分析程序的设计 口词法分析程序（掌握） 0 词法分析程序的手工构造（重点，OJ平台题目） 0 3.2单词的形式化描述工具（掌握) 口3.3有穷自动机（掌握重点难点) 口3.4正规式和有穷自动机的等价性（掌握重点) ▣3.5正规文法和有穷自动机的等价性（了解） 口3.6词法分析程序的自动构造工具（了解） 0 本章练习 课程目录 ①作业 25.4.2 1
25.4.2 1 第 3章 词法分析 3.1 词法分析程序的设计 词法分析程序（掌握） 词法分析程序的手工构造（重点，OJ平台题目） 3.2 单词的形式化描述工具（掌握） 3.3 有穷自动机（掌握 重点 难点） 3.4 正规式和有穷自动机的等价性（掌握 重点 ） 3.5 正规文法和有穷自动机的等价性（了解） 3.6 词法分析程序的自动构造工具（了解） 本章练习 作业 课程目录
词法分析(Lexical Analysis) 口主要功能 口从左至右逐个字符地对源程序进行扫描，产生一个个 的单词符号，把作为字符串的源程序改造成为单词符 号串的中间程序 0 或者说：逐个读入源程序字符，并按照词法规则分割 成一系列单词，再转换成单词串，同时进行词法检查 25.4.2 2
25.4.2 2 词法分析（Lexical Analysis） 主要功能 从左至右逐个字符地对源程序进行扫描，产生一个个 的单词符号，把作为字符串的源程序改造成为单词符 号串的中间程序 或者说：逐个读入源程序字符，并按照词法规则分割 成一系列单词，再转换成单词串，同时进行词法检查
词法分析(Lexical Analysis) 0主要任务 口读源程序，产生单词符号。 口其他任务 口滤掉空格，跳过注释、换行符； 口追踪换行标志，复制出错源程序； 口宏展开，. 0关键 口找出单词分隔符。 25.4.2 D3
25.4.2 3 词法分析（Lexical Analysis） 主要任务 读源程序，产生单词符号。 其他任务 滤掉空格，跳过注释、换行符； 追踪换行标志，复制出错源程序； 宏展开，. 关键 找出单词分隔符
词法分析技术应用 0 可应用于其它领域 ▣比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模 式的匹配来引发动作。 0 又如LEX,说明词法分析程序的语言，可以看成是一个模式动作语言。 口词法分析程序的自动构造工具也广泛应用于许多方面 ▣如用以生成一个程序，可识别印刷电路板中的缺陷。 口又如开关线路设计和文本编辑的自动生成等。 25.4.2 4
25.4.2 4 词法分析技术应用 可应用于其它领域 比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模 式的匹配来引发动作。 又如LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。 词法分析程序的自动构造工具也广泛应用于许多方面 如用以生成一个程序，可识别印刷电路板中的缺陷。 又如开关线路设计和文本编辑的自动生成等
3.1词法分析器程序的设计p37 口功能：输入源程序，输出单词符号。 口单词符号一般可分为下列五种： ▣关键字 C语言main int void ▣标识符 变量名数组名函数名 口常数 1003.14159‘a' 0 运算符 +-米/ 口界符 25.4.2 KD5
25.4.2 5 3.1 词法分析器程序的设计 p37 功能：输入源程序，输出单词符号。 单词符号一般可分为下列五种： 关键字 C语言main int void 标识符 变量名 数组名 函数名 常数 100 3.14159 ‘a’ 运算符 + - * / 界符 ，；（ ） /* */
单词符号的输出形式p37 G 二元式（单词种别，属性值） ▣单词种别单词符号的特性。 口通常用整数编码，怎样分种，怎样编码，主要取决于处 理上的方便。 0 例：标识符一一1 常 数 一一2 关键字 -3 0 运算符 4 界 符 5 25.4.2 6
25.4.2 6 单词符号的输出形式 p37 二元式（单词种别，属性值） 单词种别 单词符号的特性。 通常用整数编码，怎样分种，怎样编码，主要取决于处 理上的方便。 例：标识符——1 常 数——2 关键字——3 运算符——4 界 符——5
单词符号的输出形式p38 二元式（单词种别，属性值) 口属性值单词符号特性的值。 一个种别只含一个单词符号，不需属性值。 关键字if（“if”,-) 关键字then (“then”,_) 一个种别含有多个单词符号，为区别各个单词符号需要 属性值。 0 表示方法 常用常数的值，标识符的名字表示。 变量i（1,指向i的符号表项的指针) 关键字if（3,“if”) 25.4 关键字then (3,“then”)
25.4.2 7 属性值 单词符号特性的值。 一个种别只含一个单词符号，不需属性值。 关键字 if （“if” ，_ ） 关键字 then （“then” ，_ ） 一个种别含有多个单词符号，为区别各个单词符号需要 属性值。 表示方法 常用常数的值，标识符的名字表示。 变量 i （1，指向i的符号表项的指针） 关键字 if （3，“if”） 关键字 then （3，“then”） 单词符号的输出形式 p38 二元式（单词种别，属性值）
例C++代码段及对应的单词符号序列 whi1e(i>=10)i-; 单词 输出表示 1 while (3,“while”) 2( (5, “(”) 3 i (1, 指向1的符号表项的指针) 4 >= (4, ) 5 10 (2, “10”) 6 ) (5, “)”) 7 i (1, 指向i的符号表项的指针) 8 (4, -) 4 9 254.2 (5, :） 8
25.4.2 8 例 C++代码段及对应的单词符号序列 while (i>=10) i- -; 单词 输出表示 1 while (3， “while”) 2 ( (5， “(”) 3 i (1，指向i的符号表项的指针) 4 >= (4，>=) 5 10 (2， “10”) 6 ) (5， “)”) 7 i (1，指向i的符号表项的指针) 8 - - (4，- -) 9 ; (5，;)
词法分析器的组织方法p37 口作为单独的一遍，在语法分析前进行。 0 与语法分析结合在一起作为一遍。 口作为语法分析程序的一个子程序，每次调用识别 一个单词，交给语法分析器使用。 取单词 源程序 词法分析 语法分析 语法树， 送单词 表格管理 符号表 常数表 章节目录 25.4.2 >a9
25.4.2 9 词法分析器的组织方法 p37 作为单独的一遍，在语法分析前进行。 与语法分析结合在一起作为一遍。 作为语法分析程序的一个子程序，每次调用识别 一个单词，交给语法分析器使用。 词法分析 表格管理 源 程 语法分析 序 送单词 符号表 常数表 取单词 语法树 章节目录
单词的识别一状态转换图P41 0 状态转换图 有限方向图 口结点一状态，用O表示；终态，用©表示 有向弧 一箭头 口弧上标记一 输入字符 多读进了一个不 0 标识符的状态转换图 属于标识符部分 的字符 初态 字母 其它 *终态 已识别出 字母或数字 二个标迟符 25.4.2 10
25.4.2 10 单词的识别──状态转换图P41 状态转换图 有限方向图 结点 —— 状态，用○表示；终态，用◎表示 有向弧 ── 箭头 弧上标记 ── 输入字符 标识符的状态转换图 字母 字母或数字 其它 初态 * 终态 多读进了一个不 属于标识符部分 的字符 已识别出 一个标识符 0 1 2