.词法分析
第三章 词法分析
3.1 对于词法分析器的要求
3.1.1词法分析器的功能和输出形式
(1)关键字 如Pascal中的begin,end,if,while等
(2)标识符 如变量名,数组名,过程名等
(3)常数
(4)运算符 +、-、*、/等
(5)界符
词法分析器输出的单词符号常常用二元式来表示:<单词种别,单词符号的属性值>,对于资格含有多个单词符号的种别,还要给出单词符号的属性信息。
3.2 词法分析器的设计
结构:
3.2.1 输入、预处理
3.2.2单词符号的识别:超前搜索
关键字的识别、标识符、常数、算符、界符的识别
直接分析法:根据读来的第一个字符的种类分别转到各种子程序处理。这些子程序功能就是识别以相应字符开头的各种单词。
3.2.3 状态转换图:是一张有限方向图,节点代表状态,用圆圈表示。
一个完整的状态转换图有n个状态,其中有一个初态,至少要有一个终态(用双圆圈表示)。
3.3 正确表达式和有限自动机
3.3.1 我们可以把具有相同特征的字放在一起组成一个集合,即所谓的正规集, 然后使用一种形式化的方法来表示正规集,即所谓的正规式。
正规式的性质:
3.3.2 确定有限自动机
一个确定有限自动机(DFA)M是一个五元式:M =(S, ∑, f, s0, F),其中:
有限自动机的化简:
(1)状态转换矩阵表示法
(2)用状态转换图来表示
DFA M所能识别的字的全体记为L(M)
正规式与有限自动机的等价性
定理:对于任何∑上NFA M都可构造一个∑上的正规式V,使得 L(V)= L(M) 。
如何由一个NFA M,构造一个正规式V:
(1)在M转换图上加进X结点和Y结点,从X结点用弧ε连接M的所有初态结点,M的所有终态结点用弧ε连接到Y,得到一个NFA M’,且L(M) = L(M’)
(2)使用替换规则逐步消去M’的所有结点,直到只剩下X结点和Y结点,在消去过程中,逐步使用正规式来标记箭弧。
确定有限自动机的化简(最少化)即寻找一个状态比DFA M少的DFA M’,使得 L(M’) = L(M)。
(1)检查状态转换函数是否为全函数。所谓全函数,是指每个状态对每个输入符号都有转换。 若不是全函数,可以引入一个“死状态”d,d对所有输入符号都转换到d,如果状态s对输入符号a没有转换,那么加上从s到d的a转换。
(2)用化简算法进行化简
(3) 去掉死状态。
课后习题:
个人总结:
这一章的内容对于我来说还是挺难的,在词法分析器部分还可以,能搞明白,正规表达式和有限自动机只能听懂一点点,感觉迷迷糊糊的,定义都懂,一用就不会,做题也得不停地番薯,问别人,清明假期准备把课件好好看看。