第三章 词法分析
这一章主要包含了三小节内容{对于词法分析器的要求 词法分析器的设计 正规表达式与有限自动机}
一. 词法分析器
词法分析器:执行词法分析的程序
输入:源程序
输出:单词符号
源程序-词法分析器-单词符号
单词的表示形式:<单词种别 , 单词符号的属性值>
二. 词法分析器的设计
1,结构
超前搜索:
在单词识别的过程中,通过向前多读几个符号的形式,准确的进行单词的识别
一旦确定识别到的单词之后,需要进行扫描指针的回退,保证单词识别工作的顺利进行例如: ++,&&,10e2, int a
直接分析法:
根据读来的第一个字符的种类分别转到各种子程序处理。这些子程序功能就是识别以相应字符开头的各种单词。
状态转换图法
状态转换图:一张有限方向图
2、正规式与正规集
我们可以把具有相同特征的字放在一起组成一个集合,即所谓的正规集
然后使用一种形式化的方法来表示正规集,即所谓的正规式
3、确定的有限自动机(DFA)
一个确定有限自动机(DFA)M是一个五元式:
M = (S, ∑, f, s0, F),其中
S是一个有限的状态集合,它的每个元素我们称为一个状态
∑是一个有穷的输入符号的字母表,它的每个元素我们称为一个输入字符
f是从 S×∑ →S的单值部分映射
s0是S的一个元素,为初始状态,它是唯一的
状态集合F是终止状态的集合,它是S的子集(可空)
注意:
所谓的自动机不是指一台实际的机器,而是一种数学模型(集合,函数,序列…), 利用它模拟计算机识别的功能
所谓确定性是指,f(s, a) = s’ 是单值函数。 对任何状态s∈S,和输入符号 a∈∑ , f(s, a) 唯一的确定下一个状态所谓有限性是指,S是一个有限的状态集合,并且∑是一个有限的输入符号的字母表
用上述5条,来定义一个DFA,来完成识别一个序列是否被机器所接受
课后题:
课后题只会比着葫芦画瓢,有时候在课上跟着老师思路走看着课件还是感觉不难的,但是当没有老师在一边引导,不看答案,自己直接做题的时候还是很吃力,知识点掌握的不够透彻。