第三章 词法分祈及词法分析程序
1 第三章 词法分析及词法分析程序
主要内容 3.1设计扫描景肘应考虑的问题 符号的内部表示、识别约定和篥略、憑程序的輪入和预处理 32正规文油和状态转换图 正规文渎——状态转换图,状态转换图的尖现 33有限旬动机(FA) DFA、NFA以及三者的等价性;具有E动作的NFA的确定化 DFA状态数的录小化 34正蚬表达式与正规集 正觌文油——正规式FA 3.5词法分析程序的实现(自学 编写、自动生成
2 主要内容 3.1 设计扫描器时应考虑的问题 符号的内部表示、识别约定和策略、源程序的输入和预处理 3.2 正规文法和状态转换图 正规文法——状态转换图，状态转换图的实现 3.3 有限自动机（FA） DFA、NFA以及二者的等价性；具有动作的NFA的确定化； DFA状态数的最小化 3.4 正规表达式与正规集 正规文法——正规式——FA 3.5 词法分析程序的实现（自学） 编写、自动生成
词法分析的任务 词法分析的任务 扫描输入串中的字符,从中识别出具有独立意义的基本 语法单位:单词,生成单词序列。 √剥去源程序中的注释(块、行)和“空白”符 √预处理—宏处理与文件包含 词法分析程序亦称为扫描器 设计和实现扫描器的相关问题 √描述语言中各种单词的结构:3型文法及其正规式 √识别源程序中的各个单词:状态转换图或有限自动机
3 词法分析的任务 ▪ 词法分析的任务 ✓ 扫描输入串中的字符，从中识别出具有独立意义的基本 语法单位：单词，生成单词序列。 ✓ 剥去源程序中的注释（块、行）和“空白”符 ✓ 预处理——宏处理与文件包含 ▪ 词法分析程序亦称为扫描器 ▪ 设计和实现扫描器的相关问题： ✓ 描述语言中各种单词的结构：3型文法及其正规式 ✓ 识别源程序中的各个单词：状态转换图或有限自动机
扫描器的功能 单词 流 token 高级语言 编译器其 源程序 词法分 语法分它阶段 析器| get next token析器 字符流 符号表
4 扫描器的功能 词法分 析器 语法分 get_next_token 析器 编译器其 它阶段 符号表 高级语言 源程序 字符流 token 单词 （流）
程序语言的单词(1) 单词:同类词文的总称 词文:源程序中能匹配某一记号的字符串 模式:描述用字符串构成单词的规则 单词 文 模式 WHILE While While 关键字 FOR for for 标识符D temp, I 字母开头的字母数字串 max 3.14 常数|NUM 100 数字串数字串} 5
5 程序语言的单词（1） 单词 词文 模式 关键字 WHILE while while FOR for for 标识符 ID temp, i, max 字母开头的字母数字串 常数 NUM 3.14 100 数字串{.数字串} 单词：同类词文的总称 词文：源程序中能匹配某一记号的字符串 模式：描述用字符串构成单词的规则