编译原理 - 陈火旺版 - 第三章

1编译方法中国人民大学信息学院陈文萍2第三章词法分析•3.1词法分析器的要求•3.2词法分析器的设计•3.3正规表达式与有限自动机•3.4词法分析器的自动产生3回顾——词法分析•词法分析的任务：逐个读入源程序字符并按照构词规则切分成一系列单词。•词法分析器：实现词法分析（lexicalanalysis）的程序43.1词法分析器的要求•输入：源程序•输出：单词符号–单词是语言中具有独立意义的最小单位–分类•基本字：具有固定意义的标识符，–如Pascal中,begin,end•标识符：变量名、数组名、过程名等•常数：分为整型、实型、布尔型等–如100,0.8,TRUE•运算符：＋、－、*、/等•界符：逗号，分号，括号等–表示形式：二元式（单词种别，单词符号的属性值）5词法分析器的要求–表示形式：二元式（单词种别，单词符号的属性值）•单词种别编码–1）基本字：可归成一种，也可以一字一种。–2）标识符：可以是一种，也可以按类型分种。–3）常数：按类型分种，整、实、布尔等。–4）运算符：一符一种，或一类符号一种。–5）界符：一符一种6词法分析器的要求•例：C代码段：While(i=j)i--;词法分析处理后的单词符号序列：while,-(,-id,指向i的符号表项的指针＝,-id,指向j的符号表项的指针),-id,指向i的符号表项的指针--,-;,-7与语法分析程序的关系•可作为独立的一遍，在语法分析前进行•也可和语法分析结合在一起作为一遍。源程序词法分析程序语法分析程序Tokengettoken….词法分析程序语法分析程序源程序词法分析程序语法分析程序源程序83.2词法分析器的设计•词法分析器结构图输入预处理输入缓冲区扫描器扫描缓冲区单词符号列表9几个问题•输入、预处理•单词符号的识别•状态转换图10输入、预处理•预处理的任务–滤掉空格，跳过注释、换行符–宏展开，……•预处理子程序–扫描缓冲区：定长，两个半区（why?）–限定单词符合长度11单词符号的识别•关键字–超前搜索：在某些语言中（如FORTRAN）关键字未加特殊保护，与标识符或标号之间没有界符间隔–例：IF(5.EQ.M)I=10IF(5)=10•标识符–多以字母开头，识别困难不大•常数–超前搜索：某些语言中，如5.EQ.M与5.E08•算符和界符–超前搜索：如++，=12状态转换图•设计词法分析程序的一种途径。•转换图：有限方向图–结点：表示状态，有初态和终态–箭弧的标记：触发状态转换的输入•例：识别标识符的转换图012字母其它字母或数字*133.3正规表达式和有限自动机•正规式与正规集•确定有限自动机（DFA）•非确定有限自动机（NFA）•正规文法与有限自动机的等价性•正规式与有限自动机的等价性•确定有限自动机的化简14正规式与正规集•正规式：也称正则表达式,是定义正规集的数学工具，是描述说明单词符号的一种重要的表示法•递归定义–设字母表为，1.和都是上的正规式，它们所表示的正规集分别为{}和；2.任何a，a是上的一个正规式，它所表示的正规集为{a}；3.假定U和V都是上的正规式，它们所表示的正规集分别为L(U)和L(V)，那么，(UV)、(UV)、U也都是正规式,它们所表示的正规集分别为L(U)L(V),L(U)L(V)和(L(U))。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。–算符的优先顺序为“”、“”、“”–连接符“”一般可省略不写。“”、“”和“”都是左结合的。15正规式与正规集•例={a，b}，上的正规式和相应的正规集的例子正规式正规集aabab(ab)(ab)a(ab)(ab)(aabb)(ab){a}{a,b}{ab}{aa,ab,ba,bb}{,a,aa,……任意个a的串}{,a,b,aa,ab,bb……所有由a和b组成的串}{上所有含有两个相继的a或两个相继的b组成的串}16正规式与正规集•例令={l，d}，其中l代表字母,d代表数字则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……}正规式即是字母(字母|数字),它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则.•例={d，，e，+，-},其中d为0~9的数字则上的正规式d(dd)(e(+-)dd)表示的是无符号数的集合。程序设计语言的单词都能用正规式来定义.17正规式与正规集•若两个正规式U和V所表示的正规集相同,则说U和V等价,写作U=V–如：e1=b(ab),e2=(ba)be1=(ab),e2=(ab)•设U,V,W为正规式，正规式服从的代数规律有：–UV=VU，“或”服从交换律–U(VW)=(UV)W，“或”的可结合律–(UV)W=U(VW)，“连接”的可结合律–U(VW)=UVUW，(VW)U=VUWU，分配律–U=U=U，零一律，是“连接”的恒等元素–UU=U，“或”的抽取律18确定有限自动机（DFA）•DFA:DeterministicFiniteAutomata•定义：一个确定有限自动机(DFA)M是一个五元式：M=(S,Σ,δ,s0,F)，其中1.S是一个有限集，它的每个元素称为一个状态；2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；3.δ是在S×Σ→S上的单值映射，δ(s,a)=s’意味着：当前状态为s，输入符为a时，将转换为下一个状态s‘，我们把s‘称为s的一个后继状态；4.s0∈S，是唯一的一个初态；5.FS，是一个终态集，终态也称可接受状态或结束状态。19确定有限自动机（DFA）•例：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q20确定有限自动机（DFA）•状态转换矩阵–行：表示状态–列：表示输入字符–矩阵元素：表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值21确定有限自动机（DFA）abSUVUQVVUQQQQ字符状态f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q22确定有限自动机（DFA）•状态转换图bSUVQaaaba，bbf（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q23确定有限自动机（DFA）•∑*上的符号串t被DFAM接受–M=(S,Σ,δ,s0,F)，若t∑*，f(S，t)=P，其中S为M的开始状态，PF，F为终态集。则称t为DFAM所接受（识别）.•例：证明t=baab被下图的DFA所接受。f(S,baab)=f(f(S,b),aab)=f(V,aab)=f(f(V,a),ab)=f(U,ab)=f(f(U,a),b)=f(Q,b)=QQ属于终态。得证。bSUVQabaaa或bb24确定有限自动机（DFA）•DFAM所能接受的符号串的全体记为L(M).上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。•对于任何两个有穷自动机M和M’L(M)=L(M’)，则称M与M’是等价的.•DFA的确定性表现在映射δ:S×Σ→F是一个单值函数，也就是说，对任何状态s∈S，和输入符号a∈Σ，δ(s,a)唯一地确定了下一个状态。25非确定有限自动机（NFA）•NFA:NondeterministicFiniteAutomata•定义：NFAM=S,,δ,S0,F，其中S为状态的有限集，为有穷字母表，δ为S*到S的子集（2S）的映射，S0S是初始状态集，FS为终止状态集。26NFAvs.DFA一个确定有限状态自动机DFA是一个五元组M=(S,,δ,S0,F).δ:SSS0SFS有限状态集有限输入符号集转移函数一个开始状态一个终态集合27NFAvs.DFA一个非确定有限状态自动机NFA是一个五元组M=(S,,δ,S0,F).S0SFS有限状态集有限输入符号集转移函数开始状态集合终态集合与DFA的不同处之一δ:S*2S28非确定有限自动机•类似DFA,对NFAM=S,,δ,S0,F也有如下定义：–∑*上的符号串t被NFAM接受，若t∑*，δ(S0，t)=P，其中S0∈S，PF，则称t为NFAM所接受（识别）–对于Σ﹡中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFAM所识别(读出或接受)。29非确定有限自动机–若M的某些结点既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的道路,其上所有弧的标记均为ε，那么空字可为M所接受。30非确定有限自动机（NFA）•例：NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}），其中f（S，0）={P}f（S，1）={S，Z}f（P，1）={Z}f（Z，0）={P}f（Z，1）={P}SPZ00,111131DFA&NFA•确定有限自动机和不确定有限自动机–DFA是NFA的特例.对每个NFAN一定存在一个DFAＭ，使得L(M)=L(N)。–有一种算法，将NFA确定化为DFA的方法称为子集法.32DFA&NFA–NFA的矩阵表示中，表项通常是一状态的集合；而在DFA的矩阵表示中，表项是一个状态。–NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。•DFA用它的一个状态对应NFA读入一个输入符号后可能达到的所有状态。33NFA确定化算法•状态集合I的ε-闭包，–表示为ε-closure(I)，定义为一状态集–状态集合I的任何状态S都属于ε-closure(I)。–状态集I中的任何状态S经任意条ε弧能到达的状态的集合都属于ε-closure(I)。•状态集合I的a弧转换闭包，–Ia＝ε-closure(J)，J为所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。34非确定有限自动机（NFA）•例：I={1},-closure(I)={1,2}；I={5},-closure(I)={5,6,2}；I={1,2},Ia={5,3,4,6,7,8,2}12534687aaa35NFA确定化算法•假设NFAN=(K,,f,K0,Kt)，按如下办法构造一个DFAM=(S,,d,S0,St)，使得L(M)=L(N)：1.M的状态集S由K的一些子集组成。用[S1S2...Sj]表示S的元素，其中S1,S2,,...Sj是K的状态。并且约定，状态S1,S2,,...Sj是按某种规则排列的，即对于子集{S1,S2}={S2,S1,}来说，S的状态就是[S1S2]；2.M和N的输入字母表是相同的，即是；3.转换函数是这样定义的：d({S1S2,...Sj},a)={R1R2...Rt}{R1,R2,...,Rt}=-closure(f({S1,S2,,...Sj},a))4.S0=-closure(K0)为M的开始状态；5.St={[SiSk...Se]，其中[SiSk...Se]S且{Si,Sk,,...Se}Kt}36非确定有限自动机（NFA）•构造NFAN的状态K的子集的算法：–假定所构造的子集族为C，即C=(T1,T2,,...Ti),其中T1,T2,,...Ti为状态K的子集。1,开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。2,while（C中存在尚未被标记的子集T）do{标记T；for每个输入字母a