目录
对于词法分析器的要求
概念
- 词法分析的
任务：从左到右逐个字符地对源程序进行扫描，产生一个个单词符号 - 词法分析器：又称扫描器，执行词法分析的程序
词法分析器的功能和输出形式
- 功能：输入源程序，输出单词符号
- 关键字：程序语言定义的具有固定意义的标识符，例如Pascal中的
begin、end、if、while - 标识符：表示各种名字：如变量名、数组名和过程名
- 常数：整型、实型、布尔型、文字型。
- 运算符：+、-、*、/
- 界符：逗号、分号、括号
- 输出的单词符号：
（单词种别， 单词符号的属性值）单词种别：单词种别通常用符号编码表示
- 词法分析器在编译器中的地位
词法分析器的设计
词法分析器的结构
输入缓冲区:输入源程序文本，输入串放在一个缓冲区中,扫描缓冲区：
预处理子程序主要的工作:剔除无用的空白、空格、换行、回车等字符扫描器：处理经过预处理子程序处理过的相对规整的字符串
单词符号的识别：超前搜索
关键字的识别：
标识符的识别：字母开头的字母数字串，后跟界符或算符常数识别：识别出算术常数并将其转变为二进制内码表示，有些也要超前搜索算符和界符的识别：把多个字符结合而成的算符和界符拼合成一个单一单词符合几点限制-不必使用超前搜索：
1.所有关键字都是保留字
2.关键字作为特殊的标识符处理，都是用保留字表
3.如果基本字、标识符、常量之间没有确定的运算符或界符做间隔，则必须使用一个空白符做间隔
状态转换图
节点：代表状态，用圆圈表示
箭弧：状态之间用箭弧连接，箭弧上的标记代表射出结状态下可能出现的输入字符或字符类
有限个状态必须有初态和终态状态转换图可用于识别一定的字符串：若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于alfa，则称alfa为改状态转换图所识别。
正规表达式和有限自动机
正规式和正规集
正规式：正规集的名字，当我们一看到正规式的时候就能想起来正规式对应的正规集正规集：真正的字集，可以理解为我们要研究的程序语言单词的集合就是正规集正规式等价：若两个正规式所表示的正规集相同，则认为二者等价
确定有限自动机（DFA）
确定有限自动机是状态转换图的一种形式化表示
eg：
答案：B
我们考虑转换到状态1的条件：我们只有在接收到字符a的时候才会转换成状态1，而想要从状态1转换的状态3则必须要再接收一个字符a，考虑状态2，只有在接收到字符b的情况下才会转换到状态2，然后终态一定是以aa或bb结尾吗？我们看到终态还可以接收a|b转圈，所以一定不是以aa|bb结尾，但是要想从初态到终态，一定会经过1、2两个状态中的一个，所以一定会出现连续的aa|bb
ans:A
A:识别的是空串，从初态到终态可以一个字都不接收
B:识别的是空集
非确定有限自动机（NFA）
NFA和DFA统称为有限自动机
-
定义：
下图是DFA和NFA的状态转换图
-
DFA是NFA的区别
DFA和NFA的转换：
- 将初态唯一化
- 将弧上面的多个字符集|正规式变成单个字符
- 将弧上的ε去掉、别且做唯一化