淮南网络运营公司,西安网站建设优化,推荐营销型网站建设,做招牌的广告公司文章目录 对于词法分析器的要求概念词法分析器的功能和输出形式 词法分析器的设计词法分析器的结构单词符号的识别#xff1a;超前搜索状态转换图 正规表达式和有限自动机正规式和正规集确定有限自动机#xff08;DFA#xff09;非确定有限自动机#xff08;NFA#xff09… 文章目录 对于词法分析器的要求概念词法分析器的功能和输出形式 词法分析器的设计词法分析器的结构单词符号的识别超前搜索状态转换图 正规表达式和有限自动机正规式和正规集确定有限自动机DFA非确定有限自动机NFA 对于词法分析器的要求
概念
词法分析的任务从左到右逐个字符地对源程序进行扫描产生一个个单词符号词法分析器又称扫描器执行词法分析的程序
词法分析器的功能和输出形式
功能输入源程序输出单词符号关键字程序语言定义的具有固定意义的标识符例如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的转换子集法
将初态唯一化将弧上面的多个字符集|正规式变成单个字符 将弧上的ε去掉、且做唯一化
这一步是将弧上的ε去掉这样我们把这些识别字相同的状态放在一起了这样直接放在一起还会有一个问题就是他们还有自己的识别状态 经过a弧严格意义上经过一个a弧,强调个数,再对J做ε闭包 I 和 Ia的关系I和Ia都是一个状态I经过若干个弧第一个弧是a后面的弧都是ε可以到达Ia实际意义就是I识别一个a字符到达Ia 这一步进行的意义是将状态之间的转换变为状态集之间的转换这样就有可能消除映射不是单值部分映射的问题
