词法分析
# 词法分析(lexical analysis)程序设计
逐个读入源程序字符并按照构词规则切分成一系列单词(Token)。
单词是语言中具有独立意义的最小单位,包括保留关键字、标识符、常量、运算符、标点符号、分界符等。
词法分析是编译过程中的一个阶段,在语法分析前进行 。也可和语法分析结合在一起作为一遍,由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析程序和语法分析程序的关系:
词类编码原则:
界符和运算符:一字一码
常数可统归一类,也可按类型(整型、实型、布尔型等),每个类型的常数划分成一类。一类一码。
所有的标识符分为一类。一类一码。
2
3
词法分析中如何识别单词
识别单词:逐个从源程序中读取字符,根据构成单词的词法规则拼成一个有意义的单词; 词法规则描述工具: (1)状态转换图 (2)巴克斯范式BNF (3)自动机DFA (4)正则(规)表达式(5)正则文法(3型文法); 本章节3.3-3.6将介绍以上5种描述工具及它们之间的等价性,如何互相转换,如何实现(lex);
# 单词的形式化描述工具
# 1.正规文法
# 2.正规式
正规式也称正则表达式,是描述单词的构成语法的有效工具,是定义正规集的数学工具。 正规表达式(regular expression)是说明单词的模式(pattern)的一种重要的表示法(记号),用以描述单词符号。
# 4.有穷自动机
有穷自动机作为一种单词识别器,能准确地识别正规集,即识别正规式所表示的集合。应用有穷自动机理论,为词法分析程序的自动构造寻找有效的方法和工具。
有穷自动机分为两类:确定的有穷自动机(Deterministic Finite Automata, DFA)和不确定的有穷自动机(Nondeterministic Finite Automata, NFA) 。
# 4.1.确定的有穷自动机DFA
状态图:
DFA在计算机内部表示为一个矩阵数据结构:
例子:
DFA M所能接受的符号串的全体记为L(M).
# 4.2.不确定有穷自动机NFA
例子:
NFA状态集合I:
# 4.3.相互转换
# 子集法:
例子:
# 4.4.DFA的化简
例子:
# 最小状态DFA:
# 分割法:
把一个DFA的状态分成一些不相交的子集,不同子集的状态都是可区别的,同一子集中的任何两个状态都是等价的.
例子: