编译原理(清华)第四章词法分析

第四章词法分析(LexicalAnalysis)主要内容：单词的描述工具：正规文法和正规式单词识别系统：有穷自动机词法分析程序的设计词法分析程序的自动构造原理学习目标:掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简理解：正规文法、正规式、DFA的概念、NFA的概念了解：词法分析程序的自动构造工具4.1单词的描述工具4.2有穷自动机4.3正规式和有穷自动机的等价性4.4正则文法和有穷自动机间的转换4.5词法分析程序的设计4.6词法分析程序的自动构造工具4.1单词的描述工具作用:描述单词的构成规则,基于这类描述工具建立词法分析技术,进而实现词法分析程序的自动构造.工具有:正规文法正规式(RegularExpression)4.2.1正规文法多数程序设计语言单词的语法都能用正规文法(3型文法)描述正规文法回顾文法的任一产生式α→β的形式都为A→aB或A→a，其中A，B∈VN，a∈VT。正规文法描述的是VT*上的正规集例如:用l表示a~z中的任一英文字母，d表示0~9中任一数字描述标识符的正规文法为标识符→l｜l字母数字字母数字→l｜d｜l字母数字｜d字母数字描述无符号整数的正规文法无符号整数→d｜d无符号整数4.2.2正规式(正则表达式)RegularExpression对于字母表∑，我们感兴趣的是它的一些特殊字集－正规集。正规式是描述正规集的方便工具正规式与正规集的递归定义1.ε和φ都是∑上的正规式，它所表示的正规集分别为｛ε｝和Ф；2.任何ａ∈∑，ａ是∑上的正规式，它所表示的正规集为｛ａ｝；3.假定ｅ1和ｅ2都是∑上的正规式，他们所表示的正规集分别为Ｌ(ｅ1)和Ｌ(ｅ2)，那么，以下也都是正规式和他们所表示的正规集；正规式正规集(ｅ1)Ｌ(ｅ1)ｅ1｜ｅ2Ｌ(ｅ1)∪Ｌ(ｅ2)ｅ1.ｅ2Ｌ(ｅ1)Ｌ(ｅ2)ｅ1＊(Ｌ(ｅ1))＊说明:算符的优先顺序:‘＊’‘.’‘｜’‘.’和‘｜’都是左结合4.仅由有限次使用上述三步定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集。例子令={a，b}，上的正规式和相应的正规集有正规式正规集a{a}ab{a,b}ab{ab}(ab)(ab){aa,ab,ba,bb}a{,a,aa,…任意个a串}(ab){,a,b,aa,ab……所有由a和b组成的串}正规式的代数性质设r，s，t是正规式，正规式服从的代数规律是：1.r｜s=s｜r“或”满足交换律2.r｜(s｜t)=(r｜s)｜t“或”的结合律3.(rs)t=r(st)“连接”的结合律4.r(s｜t)=rs｜rt(r｜s)t=rt｜st分配律5.εr=rε=rε是“连接”的恒等元素6.rr=r“或”的抽取律r=rrr…程序中的单词都能用正规式来定义令l为a~z的字母，d为0~9的数字e1=l(l|d)*e1表示标识符集合e2=dd*e2表示无符号整数注：标识符→l｜l字母数字字母数字→l｜d｜l字母数字｜d字母数字正规式比正规文法更容易让人理解单词是按怎样的规律构成的，且可以从某个正规式自动地构造识别程序。4.2.3正规文法和正规式间的转换等价性：对任意一个正规文法，存在一个定义同一语言的正规式对任意一个正规式，存在一个定义同一语言的正规文法1.将∑上的一个正规式r转换成文法G=(VN,VT,S,P)VT=∑,首先形成产生式S→r,S为G的开始符不断利用下面的规则做变换,直到每个产生式最多含有一个终结符为止原产生式变换后产生式规则1A→xyA→xBB→y规则2A→x*yA→xAA→y规则3A→x|yA→xA→y其中B为一新非终结符例:将R=a(a|d)*转换成相应的正则文法令转换成文法G=(VN,VT,P,S)其中VT={a,d}，文法开始符为S首先形成S→a(a|d)*,然后变换S→aAA→(a|d)*A→(a|d)AA→εA→aAA→dA最终有产生式：S→aA，A→ε，A→aA，A→dA2.将正规文法转换成正规式将每条产生式改写为正规式用代入法解正规式方程组最后只剩下一个开始符号定义的正规式,其中不含非终结符正规文法到正规式的转换规则:文法产生式正规式规则1A→xBB→yA=xy规则2A→xA|yA=x*y规则3A→xA→yA=x|y例：将文法G[S]转换成正规式G：S→aA|aA→dA|d先由产生式得:S=aA|aA=d*d将A代入S中得:S=ad*d|a利用正规式变换得S=a(d*d|ε)=ad*说明:d*d|ε=(ε|d|dd|…)d|ε=d|dd|…|ε=d*所求正规式为ad*4.2有穷自动机(也称有限自动机)是一种识别装置作用:能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合意义:为词法分析程序的自动构造寻找特殊的方法和工具。分类:确定的有穷自动机(DeterministicFiniteAutomata)不确定的有穷自动机(NondeterministicFiniteAutomata)4.3.1确定的有穷自动机（DFA）定义:一个DFAM是一个五元组:M=（K，Σ，f，S，Z）1.K是一个有穷集，它的每个元素称为一个状态2.Σ是一个有穷字母表，它的每个元素称为一个输入字符3.f是一个从K×∑→K的单值部分映射。f(ki,a)=kj意味着当前状态为ki、输入字符为a时，将转换到下一状态kj4.S∈K，是唯一的初态5.ZK,是一个终态集，终态也称为可接受状态或结束状态。例DFAM=（{S，U，V，Q},{a，b},f,S,{Q}）其中f定义为：f（S，a）=Uf（S，b）=Vf（V，a）=Uf（V，b）=Qf（U，a）=Qf（U，b）=Vf（Q，a）=Qf（Q，b）=QDFA表示成状态转换图(TransitionDiagram)每个状态对应图中的一个结点：初态为唯一初态结点，用=〉标记；终态对应终态结点，用双圈表示。若有f(ki,a)=kj，则从结点ki到结点kj画标记为a的弧。例DFAM=（{S，U，V，Q},{a，b},f,S,{Q}）f（S，a）=Uf（S，b）=Vf（V，a）=Uf（V，b）=Qf（U，a）=Qf（U，b）=Vf（Q，a）=Qf（Q，b）=Q状态转换图表示为:bSUVQaaaba，bbDFA表示成状态转换矩阵例DFAM=（{S，U，V，Q},{a，b},f,S,{Q}）f（S，a）=Uf（S，b）=Vf（V，a）=Uf（V，b）=Qf（U，a）=Qf（U，b）=Vf（Q，a）=Qf（Q，b）=QabSUVUQVVUQQQQ字符状态0001行表示状态，用双箭头“=”标明初态；否则第一行即是初态列表示输入字符相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值相应终态行在表的右端标以1，非终态标以0DFA识别(接受)的字符串对于Σ*中的任何字符串t，若存在一条从初态结到某一终态结的通路，且该通路上所有弧的标记符连接成的字符串等于t，则称t可以为DFAM所识别若DFAM的初态结同时又是终态结，则ε可为M所识别。bSUVQaaaba，bbbaab为DFA所接受DFAM所能接受的符号串的全体记为L(M).结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)确定性表现在:转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。4.3.2不确定的有穷自动机（NFA）NFA的定义一个不确定的有穷自动机M是一个五元组：M=（K，Σ，f，S，Z），其中1.K是一个有穷集，它的每个元素称为一个状态；2.∑是一个有穷字母表，它的每个元素称为一个输入字符；3.f是一个从K×∑*至K的子集的映射；4.SK，是一个非空初态集5.ZK，是一个终态集。例NFAM=（{S，P，Z},{0，1},f,{S，P},{Z}）其中f（S，0）={P}f（S，1）={S，Z}f（Z，0）={P}f（Z，1）={P}f（P，1）={Z}矩阵表示:01S{P}{S,Z}P{}{Z}Z{P}{P}001SPZ00,1111状态图表示:说明：因为NFA的转换函数f为K*到K的子集的一种映射，所以NFA中可以有转移例：12ε3εabcNFA识别的字符串对于Σ*中的任何字符串t，若存在一条从某一初态结到某一终态结的通路，且该通路上所有弧的标记字依次连接成的串（不理睬那些标记为ε的弧）等于t，则称t可以被NFAM所识别。若M的某个初态结又是终态结，或者存在一条从某个初态结到某个终态结的ε通路，那么ε为M所识别。12ε3εabcNFAM所能识别的符号串的全体记为L(M)NFA与DFA的等价性DFA是NFA的特例对于任何两个有穷自动机M和M’，如果L(M)=L(M’)，则称M与M’是等价的对于每个NFAM，存在一个与其等价的DFAM’4.3.3NFA到DFA的转换从NFA构造DFA的算法—子集法abSUVUQVVUQQQQ字符状态000101S{P}{S,Z}P{}{Z}Z{P}{P}DFA的状态转换矩阵NFA的状态转换矩阵1.基本思想:让DFA的每个状态对应NFA的一个状态集合。即DFA用它的一个状态记录在NFA读入一个输入符号后可能达到的所有状态。001ε合并如果有，则把S2状态合并到S1状态。S1S2εijkmεaban（a）i,jmkaabn（b）2.转换需解决的问题：状态合并0123aabc（a）01,23abc（b）3.对状态集合I的有关运算：①状态集合I的ε闭包ε_closure(I)是状态集I中的任何状态S以及经任意条ε弧而能到达的状态的集合。εεεIIS2S2S1S1S3S3ε_Closure(I)以下将ε_closure(I)简写为Closure(I)Closure(I)=I{Sk|存在SjSk，SjClosure(I)，SkClosure(I)}ε注意：这是一个递归定义，通过多条ε边才能到达的状态也将被合并到closure中ifI={0},theε_closure(I)={Example:NFAε100124536789ababbεεεεεεε}74,2,1,0,②Ia子集。I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为Move（I，a），则Ia=ε_closure(Move(I,a))Ib=ε_closure({Example:NFAεε100124536789ababbεεεεεεifI={0,1,2,4,7}thenIa=ε_closure({})3,8={3,8,6,7,1,2,4}56,})={}5,7,2,1,44.NFA确定化算法假设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的状态。2)M和N的输入字母表是相同的，即是；3)转换函数d([S1S2,...Sj],a)=[R1R2...Rt]其中{R1,R2,...,Rt}=-closure(move({S1,S2,,...Sj},a))4)S0=-closure(K0)为M的开始状态；5)St={[SiSk...Se]，其中[SiSk...Se]S且{Si,Sk,,...Se}Kt}5.构造DFA的状态集的算法假设NFAN=(K,Σ,F,K0,Kt)构造的DFA为M=(C,Σ,D,C0,Ct)，状态集C=(T1,T2,…Ti),其中T1,T2,…Ti都是状态集K的子集。1.开始，令ε_closure(K0)为C中唯一成员，并且它是未被标记的。2.while（C中存在尚未被标记的子集T）do{标记T；for（每个输入字符a∈Σ）do{U:=Ta;（即ε_closure(Move(T,a))）if（