第3章词法分析与有穷自动机

第3章　词法分析本章介绍编译第一个阶段词法分析的原理和设计方法，要求明确此阶段的任务。理解通常的单词分类和构词规则。会使用单词的描述和识别机制。要求掌握正规文法、状态图、DFA、NFA、正规式和正规集的基本概念和它们之间的关系。掌握词法分析程序的手工实现方法。教学目标1词法分析程序的功能2词法分析程序的输出形式3程序设计语言单词的定义4正规式与有穷自动机5正规文法与有穷自动机6词法分析程序的编写方法教学内容（1）分析和识别单词及属性，包括识别语言的关键字、标识符、常数、运算符等；（2）跳过各种分隔符，如空格，回车，制表符等；（3）删除注释；（4）进行词法检查，报告所发现的错误；（5）建立符号表。3.1　词法分析程序的功能main()/*ADD*/{intx=10,y=20,sum;sum=x+y;}main、(、)、{、int、x、=、10、,、y、=、20、,、sum、;、sum、=、x、+、y、;、}词法分析实现：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串优点:结构清晰、各遍功能单一缺点：效率低S.P.(字符串)词法分析程序语法分析程序取单词单词单词的种类（1）关键字：if、for、while（2）标识符：（3）常数：（4）运算符：+、-、*（5）分界符：,、;、(、)3.2　词法分析程序的输出形式词法分析程序的输出形式-----二元式单词类别单词的属性值单词类别可以用整数编码表示:一类一种或一字一种单词类别关键字标识符常数运算符分界符编码12345单词符号属性的值：单词自身符号的机内编码。关键字、运算符、界符：只输出其种别码即可。标识符：自身字符串的值，长度受限制。常数：本身的值。字符型输出字符串本身，数值型，输出其自身的二进制。对于标识符和常数，若要建符号表，则输出其在符号表的入口地址。表3.1intx=10,y=20,sum;词法分析的结果单词类别单词的属性值1int2指向x的符号表入口指针4=3105,2指向y的符号表入口指针4=3205,2指向sum的符号表入口指针5;表3.1intx=10,y=20,sum;词法分析的结果3.3语言单词符号的两种定义方式文法定义:标识符的定义：标识符是以字母开头的、字母数字的组合.I→aB|a右线性文法B→aB|dB|a|dI→a|Ia|Id左线性文法正规式定义:字母(字母∣数字)*a(a∣d)*3.5字母表,定义在上的正规式和正规集递归定义如下:1.和都是上的正规式,它们所表示的正规集分别为:{}和;2.任何a,a是上的正规式,它所表示的正规集为:{a};3.假定e1和e2是上的正规式,它们所表示的正规集分别记为L(e1)和L(e2),那么e1|e2,e1•e2和e1*也都是上的正规式,它们所表示的正规集分别为L(e1)∪L(e2)、L(e1)•L(e2)和(L(e1))*4.任何上的正规式和正规集均由1、2和3产生。3.3.1　正规式与正规集正规式中的运算符：|-----或（选择）•----连接*或{}---重复（）----括号运算符的优先级：先*,后•,最后|•在正规式中可以省略.正规式相等这两个正规式表示的语言相等正规式举例例：设有字母表∑={a,b}，根据正规式与正规集的定义，有以下的正规式和正规集正规式正规集a{a}a∣b{a,b}ab{ab}(a∣b)(a∣b){aa,ab,ba,bb}a*{ε,a,aa,aaa,…,任意个a的串}（a∣b）*{ε，a,b,aa,ab,ba,bb,…所有a,b组成的串}(a︱b)*(aa︱bb)(a︱b)*∑*上所有含两个连续的a或两个连续的b组成的串【例】Σ={d,·,e,+，-}则Σ上的正规式d*(·dd*∣ε)(e(+∣-∣ε)dd*∣ε)表示的是实数。其中d为0～9中的数字。比如：2，12.59,3.6e2和471.88e-1等等都是该正规集所表示集合中的元素。【例】设Σ={a,b,c},则aa*bb*cc*是Σ上的一个正规式,它所表示的正规集L={abc,aabc,abbc,abcc,aaabc,...}={ambncl∣m,n,l≥1}【例】设Σ={a,b}正规式正规集ba*所有以b为首后跟任意多个a的符号串a(a|b)*所有以a为首的符号串(a|b)*abb所有以abb为尾的a，b符号串(a|b)*(aa|bb)(a|b)*所有含有两个连续的a或两个连续的b的符号串(aa|ab|ba|bb)*空串和任何长度为偶数的符号串(a|b)(a|b)(a|b)*任何长度大于等于2的符号串【例】使用正规式来表示程序设计语言中的相应单词符号。<标识符>→字母|<标识符>字母|<标识符>数字）<无符号整数>→数字|<无符号整数>数字<单界符>→+|*|<|,|;<双界符>→<=标识符：a(a|d)*无符号整数：dd*单界符：+|*|<|,|;双界符：<=设r，s，t均是正规式，则有以下性质：（1）交换律：r|s=s|r（2）结合律：r|(s|t)=(r|s)|t(rs)t=r(st)（3）分配律：(r|s)t=rt|st（4）同一律：εr=rε=r3.3.2正规文法与正规式正规文法正规式的转换方法：（1）将正规文法中的每一个非终结符表示成关于它的一个正规式方程，获得一个联立方程组；（2）依照求解规则:若x=ax︱β(或x=ax+β)，则解为x=a*β。若x=xa︱β(或x=xa+β),则解为x=βa*。求关于开始符号S的解.文法规则正规式方程的变换(1)若A→a,则有A=a；(2)若A→aB∣β,则有A=aB+β；举例:【例3．4】设有正规文法G：Z→0AA→0A∣0BB→1A∣ε试给出该文法生成语言的正规式。【例3．5】设有正规文法G：A→aB∣bBB→aC∣a∣bC→aB试给出该文法生成语言的正规式。【例3.6】设有正规文法G：Z→U0∣V1U→Z1∣1V→Z0∣0试给出该文法生成语言的正规式。正规表达式RE正规文法G对任何一个正规表达式e，都存在一个等价的正规文法G，使得L(e)=L(G)。字母表Σ上的正规式到正规文法G=（VN，VT，P，S）的转换方法如下：（1）令VT=Σ；（2）对任意正规式R选择一个非终结符Z生成规则Z→R，并令S=Z；（3）若a和b都是正规式，对形如A→ab的规则转换成A→aB和B→b两个规则，其中B是新增的非终结符；（4）在已转换的文法中，将形如A→a*b的规则进一步转换成A→aA∣b；（5）不断利用规则（3）和（4）进行变换，直到每条规则最多含有一个终结符为止。【例3．8】将R=（a∣b）(aa)*(a∣b)转换成相应的正规文法。设A是文法的开始符号，根据规则（2）变换为A→(a∣b)(aa)*(a∣b)根据规则（3）变换为：A→（a∣b）BB→(aa)*(a∣b)根据规则（4）变换为：A→aB∣bBB→aaB∣a∣b根据规则（3）变换为：A→aB∣bBB→aC∣a∣bC→aB【例3．9】将描述标识符的正规式R=l(l∣d)*转换成相应的正规文法。令S为文法的开始符号，根据规则（2）有S→l(l∣d)*根据规则（3）变换为：S→lAA→(l∣d)*根据规则（4）变换为：S→lAA→(l∣d)A∣ε进一步变换为：S→lAA→lA∣dA∣ε去掉ε规则：S→l∣lAA→l∣d∣lA∣dA既为标识符的文法。有穷自动机是一种数学模型，具有离散的输入与输出，系统可处于有穷状态中的任何一个状态它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具有穷自动机分为两类：确定的有穷自动机（DFA）(DeterministicFiniteAutomata)不确定的有穷自动机（NFA）(NondeterministicFiniteAutomata)3.4正规式与有穷自动机2型文法（不确定的下推自动机）1型文法（不确定的界限自动机）0型文法（图灵机）3型文法（有限自动机）1-91,3,5,7,9有穷自动机的模型104397TAS1,3,5,7,9输入带有穷控制器读头0-9有穷自动机的作用实质上是提供了一种逻辑的探测方式,去探测一些输入串是否属于某种语言,即:它可以作为一种语法检查器。3.4.1　确定的有穷自动机（DFA）M=(Σ,Q,f,S,Z)Σ：有穷字母表，它的每个元素称为一个输入符号Q：有穷状态集，它的每个元素称为一个状态S∈K，是唯一的初态ZK是一个终态集，终态也称可接受状态或结束状态f是转换函数，是Q×Σ→Q上的单值映射：f（q1，a）=q２状态转移函数f可用一矩阵来表示：输入字符状态ab012132213333例如:M:（{0,1,2,3},{a,b},f，0，{3}）f（0，a）=1f（0，b）=2f（1，a）=3f（1，b）=2f（2，a）=1f（2，b）=3f（3，a）=3f（3，b）=3所谓确定的状态机，其确定性表现在状态转移函数是单值函数！M=(Σ,Q,f,S,Z)一个DFA也可以用一状态转换图表示：输入字符状态ab012132213333DFA的状态图表示：1032aabba,bba字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串α，则称α为DFAM（接受）识别。DFAM所接受的语言为：L(M)={α|f(S,α)=Sn,Sn∈Z}DFAM所能接受的符号串的全体记为L(M)若M的初态结点同时为终态，或者存在一条从初态到某个终态结点的ε通路，则ε为M所识别。f（0，abaab）=f（1，baab）=f（2，aab）=f（1，ab）=f（3，b）=3(接受)DFA的状态图表示：1032aabba,bbaf（0，abab）=f（1，bab）=f（2，ab）=f（1，b）=2(拒绝)对于符号串abaab的识别过程对于符号串abab的识别过程f是一个多值函数，是从Q×Σ*到Q的子集的映射：f：Q×Σ→2Q其中2Q是Q的幂集，即Q中所有子集组成的集合。3.4.2不确定的有穷自动机（NFA）M=(Σ,Q,f,S,Z)有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的例：NFAN=({a,b,c},{1,2,3,4},f,{1},{4})符号状态εabc1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦ对于Σ*上的任何符号串，若存在一条从某一初态到某一终态的通路，且该通路上所有弧的标记字符依次连接成的串等于，则称可以被NFAN所识别或接受。若N的初态结点同时为终态，或者存在一条从初态到某个终态结点的通路，则为N所识别。NFAN所能识别的符号串的全体记为L(N)，称为NFAN所识别的语言上例题相应的状态图为：1234abacacεN所接受的语言（正规式）R=aa*b|ac*c|ε符号状态εabc1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦ能接受0001111010001110000001(0|1)*(000|111)(0|1)*不能接受0001100画出能够识别C语言注释/**/的DFA12453othersothers/***/6othersothersallall12453othersothers/***/　　　状态1：注释开始状态。状态2：进入注释体前的中间状态。状态3：表明目前正在注释体中的状态。状态4：离开注释前的中间状态。状态5：注释结束状态，即接受状态。用于某些重要软件的设计和构造设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件;验证所有只有有限多个不同状态的系统的软件，这类系统包括通信和信息安全交换协议。有穷自动机的其它应用几个概念1）自动机所接收字符如果对某一自动机M=（Q,∑,f,S,Z）x∈VT有f（S,x）=P,且P∈Z，则称字符x被自动机所接收。2）自动机所接收输入串自动机从开始状态读完全部输入串后，自动机恰好到达终止状态，则称输入串被自动机所接收。定义为⑴f(q,)=q⑵f(q,aα)=f(f(q,a),α)其中qQ，a,α*3）自动机接收语言自动机M所能接收的串组成一个集合，则称该集合为自动机M所能接收（识别）的语言。用L（M）表示：L（M）＝{f∣f(S,t)∈Z,t∈VT*}　４）自动机的等价性如果两个有穷自动机A1和A2满足L(A1)=L(A2)则称自动机自动机A1和A2是等价的。DFA与NFA的区别（1）DFA的转换函数f是一个单值函数；NFA的转换函数f是一个多值函数。（2）DFA拥有唯一的初始状态；NFA拥有一个初态集。（3）DFA状态图中不允许有ε边；NFA允许，并且允许多条。（表示：在没有任何输入符号的情况下也可以进行移动）这样，在NFA中从一个非终止状态经由一个或多个空移也可以到达某个终止状态。3.4.3正规式RNFAM对于字母表Σ上的每个正规式R，可以构造一个Σ上的NFAM，使得L(M)=L(R)。（1）对NFAM构造一个广义的状态图，其中只有一个初态X和终态Y，连接X和Y的有向弧标记为正规式。（2）对正规式依次进行分解，分解的过程是一个不断加入结点和弧的过程，直到转换图上的所有弧标记上都是字母表Σ上的元素或为止。若s,t为Σ上的正规式(a)对于正规式R=stxystxystt(b)对于正规式R=s|txys|txyst(c)对于正规式R=rs*txyrs*txyrttsAZS(a|b)*abb例:为R=(a|b)abb构造NFA,使得L(N)=L(R)*SZbabABbaZbbSa|bAa已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：NFAM′DFAM构造成一个使得L(M)=L(M′)DFA是NFA的特例。有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法.与某一NFA等价的DFA不唯一3.4.4NFA的确定化从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态。NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态.符号状态εabc1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦ1234abacacε(1)ε合并如果有，则把S2合并到S1S1S2ε转换需解决的问题：ijkmεaban（a）i,jmkaabn（b）(2)状态合并0123aabc（a）01,23abc（b）定义1状态集合I的-闭包，表示为-closure(I)①若q∈I，则q∈-closure(I)；②若q∈I，则从q出发经过任意条弧而能到达的任何状态q'都属于-closure(I)。为了使得NFA确定化，我们首先给出两个定义：ε_closure(I)εεεIIS2S2S1S1S3S3例：如图所示的状态图：令I={1}，求ε-closure（I）=？156432aεaaε根据定义：ε-closure（I）={1，3}课堂练习：令I={1,2}，求ε-closure（I）=？I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为go（I，a），则Ia=ε_closure(go(I,a))定义2Ia子集例：令I={1}Ia=ε-closure(go（I，a）)=ε-closure(f（1，a））=ε-closure({2，4}）={2，4，6}根据定义1，2，可以将上述的M'确定化（即可构造出状态转换矩阵）156432aεaaε课堂练习：令I={1,2,3}求Ia=？课堂练习：令I={1}，设S'=ε-closure（I），求S'＝？S'a=？将从状态S出发经过任意条弧所能到达的状态作为DFA的初态S'从S'出发，把遇到输入符号a所转移到的后继状态集作为DFA的新状态如此重复，直到不再有新的状态出现为止NFA转换为DFA的思想1234abacacεIIaIbIc{1,4}{2,3}φφ{2,3}{2}{4}{3,4}{2}{2}{4}φ{4}φφφ{3,4}φφ{3,4}（1）构造一张表，它共有｜Σ｜+1列（2）第一行第一列为-closure({S})（3）求Ia（4）重复步骤（3）（5）将状态子集重新命名1234abacacε将求得的状态转换矩阵重新编号DFAM状态转换矩阵：符号状态abc02341221________3344DFAM的状态图：注意：包含原初始状态1的状态子集为DFAM的初态包含原终止状态4的状态子集为DFAM的终态。01423{1,4}{2,3}{4}{2}acabbc{3,4}1234abacacε课堂练习4f35621iaaaabbbbstart等价的DFAaCDBAEFSbaaaaabbbbbabFstart3.4.5DFA的最小化如果不同的DFA能识别相同的语言，则称它们是等价的DFA。在等价的DFA中，如果某一个DFA的状态数是最少的，则这个DFA是最简的。对于任一个DFA，存在一个唯一的状态最少的等价的DFA最简的DFA它没有多余状态和等价状态定义1多余状态：从开始状态出发,任何输入串也不能到达的状态01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s101s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例:画状态图可以看出s4,s6,s8为不可达状态应该消除定义2等价状态状态s和t的等价条件是:①状态S和T必须同时为终态或非终态②对于所有输入符号，S和T必须转换到等价的状态里把DFA的状态划分成一些不相交的子集任何不同的两个子集的状态都是可区分的同一子集中的任何两个状态都是等价的5724361srartaaaaaaabbbbbbbDFA最小化算法的基本思想(没有多余状态)：解:(一)区分终态与非终态12345663731546737414212ab区号123123456637315467374142ab区号（1）将所有状态分成两个子集：终态集和非终态集（2）把等价的状态构成一个子集，若不等价继续划分（3）结束后，重新标号或从每个子集中选一个状态做代表123456637315467374142ab12431243123456637315467374142ab5区号区号将区号代替状态号得:12345ab5214355231155243aaaaabbbbb化简后的有穷自动机具有较少的状态，实现起来更加简洁。3.4.6.NFAM正规式R(1)在M上加两个结点X,Y，从X结点用ε弧到M的所有初态，从M的所有终态用ε到Y结成与M等价的M′，M′只有一个初态X和一个终态Y.例:M:03214starta,ba,ba,bbbaa解:(1)加XYX03412Yεεεaa,ba,ba,babb(2)逐步消去M′中的所有结点,直至剩下X和Y结点,在消结过程中,逐步用正规式来标记弧,规则如下:1.对于代之为2.对于代之为3.对于代之为R1R212331R1R21221R2R1R2R1|R1R312331R1R2﹡R3R2(2)消除M中的所有结点a|bx024yεεεaabba|ba|b解:(1)加x、yx03412yεεεaa,ba,ba,babbx0yaa(a|b)*bb(a|b)*a|bεxy(a|b)*(aa|bb)(a|b)*3.5正规文法与有穷自动机（1）对于NFAM，存在一个右线性文法（左线性文法）G，使得L(G)=L(M)；（2）对于右线性文法（左线性文法）G，可以构造一个NFAM，使得L(M)=L(G)。（1）文法的终结符号集为NFA的字母表；（2）文法的非终结符号集为NFA的状态集；（3）文法的开始符号作为NFA的初态；增加一个终态Z（4）对文法中形如A→tB的产生式，其中t为终结符或，A和B为非终结符，构造NFA的一个转换函数f(A,t)=B；（5）对文法中形如A→t的产生式，构造NFA的一个转换函数f(A,t)=Z。3.5.1正规文法(右线性)NFA例:求与文法G[S]等价的NFAG[S]:S→aA|bB|εA→aB|bAB→aS|bA|εSZABaaabbbεε求得：【例】构造下述文法G［Z］的有穷自动机。Z→0AA→0A｜0BB→1A｜ε与文法G［Z］等价的自动机M＝（｛Z，A，B，D｝，｛0，1｝，ƒ，｛Z｝，｛D｝），其中ƒ(Z,0)=｛A｝ƒ(Z,1)=φƒ(A,0)=｛A,B｝ƒ(A,1)=φƒ(B,ε)=Dƒ(B,1)=｛A｝3.5.2左线性文法有穷自动机（1）文法的终结符号集为NFA的字母表；（2）文法的非终结符号集为NFA的状态集；（3）文法的开始符号作为NFA的终态；增加一个开始状态S.（4）对G中每一形如A→Ba的产生式,构造NFA的一个转换函数ƒ(B,a)=A。（5）对G中每一形如A→a的产生式,构造NFA的一个转换函数ƒ(S,a)=A。【例】构造下述文法G[A]的自动机。A→A1∣B1B→B0∣0与文法G[A]对应的自动机M＝（｛S，A，B｝，｛0，1｝，ƒ，S，｛A｝），其中ƒ（S，0）＝Bƒ（B，0）＝Bƒ（B，1）＝Aƒ（A，1）＝A3.5.3NFA正规文法（1）NFA的字母表为文法的终结符号集；（2）NFA的状态集为文法的非终结符号集；（3）NFA的初态对应于文法的开始符号；（4）NFA的转换函数f(A,t)=B，写成一个产生式A→tB；（5）对NFA的终态Z，增加一个产生式Z→。ABt例:给出如图NFA等价的正规文法GABCDaaabbbbG=（{A，B，C，D}，{a，b}，P，A）其中P:AaBAbDBbCCaACbDCεDaBDbDDε→→→→→→→→→正规文法NFA正规式654312DFA最小化转换方法873.6词法分析程序的设计词法分析程序的主要功能包括以下几个方面：（1）组织源程序的输入；（2）按规则拼单词，并转换成二元式形式进行输出；（3）删除注释行、空格及无用符号（如回车符、字符常数的引号等）；（4）行、列计数，发现并定位语法错误，列表打印源程序和错误清单；（5）建立符号表、常数表等表格。源程序的输入及预处理预处理的主要工作主要包括:(1)删除注释;(2)删除续行符号以及后续换行符号(3)将换行符号和TAB键统一替换为空格.(4)大写换小写或相反,以便后续处理词法规则状态图词法分析程序（1）根据词法规则写出正规文法；（2）将正规文法转换成状态图；（3）将状态图转换成流程图。标识符关键字(标识符的子集）常数运算符+、*、＝、<、<=分界符,、;【例】假设某种语言的单词符号的子集有：试构造此语言子集的词法分析程序。（1）根据词法规则写出正规文法<标识符>→字母|<标识符>字母|<标识符>数字）<无符号整数>→数字|<无符号整数>数字<单界符>→+|*|<|,|;<双界符>→<=标识符出口S1非字母数字字母字母、数字无符号整数出口S2非数字数字数字单字符分界符出口S3其他字符+*=,;双字符分界符出口S4其他字符<5=非=<标识符>→字母|<标识符>字母|<标识符>数字）<无符号整数>→数字|<无符号整数>数字<单界符>→+|*|<|,|;<双界符>→<=（2）将正规文法转换成状态图合并①将初始状态合并为一个唯一的初态；②化简调整状态冲突并对冲突状态重新编号；③如有必要，增加出错状态。标识符无符号整数单界符双界符S1非字母数字字母字母、数字2非数字数字数字3其他字符+*，（）出口4其他字符<5=非=出错其他读字符查保留字表返回S合并后的状态图（3）将状态图转换成流程图写出词法分析程序扫描程序的设计下面用一个比较简单的语言作为例子来讨论扫描程序的设计。假定该语言中有分界符或运算符（如＋，－，*，/，（，）），关键字（如begin，abs，end），标识符（非保留字）以及整数。至少要有一个空白符将相邻的标识符、整数和（或）关键字隔开，但不能用空白符将符号中的相邻字符分开。此外，注解是以符号/*开始，并以符号/*的第一次出现作为结束的。有关变量和函数的说明（1）ch字符变量，存放当前读进的源程序字符。（2）token字符数组，存放构成单词符号的字符串。（3）getch（）读字符函数，每调用一次从输入缓冲区中读进源程序的下一个字符放在ch中，并把读字符指针指向下一个字符。（4）getbc（）函数，每次调用时，检查ch中的字符是否为空白字符，若是空白字符，则反复调用getch（），直至ch中读入一个非空字符为止。（5）concat（）函数，每次调用把当前ch中读进的字符与token中的字符串连接。例如，假设token字符数组中原有值为“ab”,ch中存放着“c”,调用concat（）函数后，token字符数组中的值变为“abc”。（6）letter(ch)和digit（ch）为布尔函数，它们分别判定ch中的字符是否为字母和数字，从而给出true或false布尔值。（7）reserve（）函数，对token中的字符串查关键字表，若为关键字，则返回它的种别码，否则返回输出标识符的种别码和它的值。（8）reback（）函数，读字符指针回退一个字符。（9）return（）函数，收集并携带必要的信息返回调用程序，即返回到语法分析程序。（10）dtb（）十进制转换为二进制函数。对应的C语言程序Scanner(){Token=null;Getch();Getbc();If(letter(ch)){while(letter(ch)‖digit(ch)){Concat();Getch();}reback();C=reserve();If(c!=1)return(c,token);Elsereturn(1,token);}Elseif(digit(ch)){while(digit(ch)){Concat();Getch();}reback();return(2,dbt());}ElseSwich(ch){case′＋′:return(7,_);break;case′－′:return(8,_);break;case′＊′:return(9,_);break;case′／′:return(6,_);break;case′＜′:getch();if(ch==′=′)return(*,_);elseif(ch==′＞′)return(*,_);reback;return(*,_);break;case′：′:getch();if(ch==′=′)return(*,_);reback;return(*,_);break;case′；′:return(*,_);break;defalt;error();break;}}标识符的处理在词法分析中，标识符的处理比其它单词的处理复杂得多，且涉及得面也很广，因此，在编译程序中，标识符得处理占有极为重要的位置。标识符的处理主要包括其语义表示、作用域处理、符号表构造以及内存单元分配等工作。标识符处理的难易程度依赖于语言的数据结构的复杂程度。一般，数据结构越复杂，标识符的处理也就越复杂。设计词法分析程序的直接方法在具体实现过程中，可把词法分析设计成一个子程序，即在扫描源程序时，一旦识别出标识符、保留字、常数和分界符之一，就可形成相应的单词并传递给所需部分。在具体实现时，可将各类单词设计成结构和长度均相同的形式，例如，每一单词可设计成如下形式：(type,pointer)其中type指明单词的种类，例如：k——关键字（可事先构造好）i——标识符c——常数s——分界符（可事先构造好）point指向本单词存放处的开始位置。将词法分析程序设计成子程序的框图:作业（第4次）1．请给出字母表∑={0,1}上的下列语言的正规式描述。(1)所有以11开头，以00结尾的串(2)所有包含3个连续的0的串(3)所有包含子串01011的串(4)所有包含偶数个0的串2.构造识别下列语言的FA或DFA。(1){x∣x∈{a,b}+且X是由n（≥1）个ab构成的符号串，每两个ab间间隔有任意个b}(2){x∣x∈{a,b}+且x是以a开头以ba结尾的符号串的集合}(3){x∣x∈{0,1}+且X中含有偶数个1}(4){x∣x∈{a,b}+且x的倒数第3个符号为b的字符串的集合}作业（第５次）1、有一台自动售货机，接收1分2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放>=3分的硬币，便可得到一块糖（注意：只给一块并且不找钱）。写出售货机售糖的正规表达式；构造识别上述正规式的最简DFA；2、设有L（G）={a2n+1b2ma2p+1∣n≥0,p≥0,m≥1}（1）给出描述该语言的正规表达式（2）构造识别该语言的确定的有穷自动机3、写出不以a开头但以aa结尾的字符串集合的正规式，并构造与之等价状态最少的DFA。