第二章词法分析LexicalAnalysis对于编译器而言，其前端(frontend)执行分析，后端(backend)执行合成。词法分析：以字符流作为输入，生成一系列的名字、关键字和标点符号(punctuationmark)，同时去掉单词之间的空白符(whitespace)和注释(comment)。词法分析作为一个独立子程序的原因：描述单词的结构比描述源程序的其它语法结构要简单得多，这样就能采用比语法分析更为有效的方法或工具（如状态转换图、有限自动机）来识别单词和描述扫描器的结构。词法分析器的结构(1)输入缓冲区：为了提高读盘效率和便于扫描器进行工作，让操作系统直接将磁盘上的源程序字符串分批送入此缓冲区中，供扫描器进行处理。(2)预处理子程序：当词法分析器调用它时，它就处理一串确定长度的输入字符。(3)扫描缓冲区：存放经预处理子程序处理的字符，供扫描器使用。2.1词法单词符号2.1词法单词符号2.2正则表达式为了用有限的描述表示这类语言（可能是infinite的），我们使用regularexpressions表示法，每个regularexpression代表一个字符串集合。符号：对于字母表∑中的每个符号a，正则表达式a表示仅包含字符串a的语言可选(alternation)：对于给定的两个正则表达式M和N，则M|N表示一个字符串属于语言M或语言N联结(concatenation)：对于给定的两个正则表达式M和N，M·N表示一个字符串是任意两个字符串α和β的联结，且α属于语言M，β属于语言Nε(epsilon)：表示仅含一个空字符串的语言重复(repetition)：对于给定的正则表达式M，它的克林(Kleene)闭包M*表示一个字符串是由M中的字符串经零至多次联结运算的结果书写正则式时，一般会省略(omit)联结操作符“·”或符号ε。运算优先级：Kleenclosure高于concatenation；concatenation高于alternation。Regularexpressions举例Someabbreviations(缩写形式):[abcd]means(a|b|c|d)[b-g]means[bcdefg][b-gM-Qkr]means[bcdefgMNOPQkr]M?means(M|ε)M+means(M·M*)——正闭包Figure2.1概括了所有这些操作符.(period):除换行符之外的任意单个字符“a.+*”(quotation):引号中的字符串表示字符串本身Figure2.2表示某些单词记号的正则表达式词法规范(lexicalspecification)应当是完整的(complete)，即应当总是能与输入中的某些初始子串(substring)相匹配。二义性(ambiguous)问题：消除二义性规则最长匹配：取可与正则表达式匹配的那个最长输入子串为下一个单词。规则优先：对于一个特定的最长初始子串，第一个与之匹配的正则表达式决定其单词类型。2.3有限自动机(FiniteAutomata)Figure2.3表示部分构词规则的有限自动机，每个状态有一个编号，初态都是编号为1的状态，标有多个字符(severalcharacters)的边是多条平行边(manyparalleledges)的缩写形式FiniteAutomata确定的有限自动机(DFA)确定的有限自动机(DFA)Figure2.4为Figure2.3中六个独立的自动机合并后得到的一个可作为词法分析器的自动机：注意！！DFA的映射关系可以由一个矩阵表示，矩阵的行表示状态，列表示输入字符，这个矩阵称为转换矩阵(transitionmatrix)，存储形式为二维数组(two-dimensionalarray)。2.4非确定的有限自动机(NFA)设有限自动机M的状态转换图如下：2.4.1RE→NFARulesfortranslatingREtoNFA:例：将正规式a(b|aa)*b转换成等价的有限自动机例：将四个RE转换为NFA2.4.2NFA→DFAε-closure的形式化定义：证明：算法是正确的DFAedge(d,c)：当位于由NFA状态si，sk，sl组成的集合d={si,sk,sl}时，从d中的状态出发，并输入符号c，所到达的NFA的一个新的状态集合。利用DFAedge(d,c)能够更形式化地写出NFA模拟算法(simulationalgorithm)。设NFA的初态是s1，输入字符串的字符是c1,…,ck，则算法为：NFA→DFA的可行性：在实际的应用中，需要预先计算出所有的状态集合，即由NFA构造一个DFA，使得NFA的每一个状态集合都对应于DFA的一个状态。由