词法分析主要内容回顾.ppt

2023/11/17,第三章：词法分析,1,第2章主要内容回顾,文法的定义：=(T，N，)推导与归约：最左推导（左句型、最右归约）最右推导（右句型、规范句型、规范（最左）归约）语法树二义性（定义）文法的分类0型文法（短语结构文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）、3型文法（正则文法）,2023/11/17,第三章：词法分析,2,第三章 词法分析,单词的描述工具（正规表达式与正规集）状态转换图与基本符号的识别有限自动机词法分析器的设计与实现,本章主要内容：,2023/11/17,第三章：词法分析,3,3.1 单词的描述工具,正规表达式与正规集的定义：正规表达式也称正规式，是用以描述单词符号的方便工具，也是表示正规集的工具。正规表达式的定义：P52。设是一个字母表，是上的RE，L()=；是上的RE，L()=；对于a，a是RE，L(a)=a；如果r和s是RE，L(r)=R,L(s)=S，则：r与s的“或”(r|s)是RE，L(r|s)=RS；r与s的“连接”(rs)是RE，L(rs)=RS；r的克林闭包(r*)是RE，L(r*)=R*。只有满足、的才是RE。,2023/11/17,第三章：词法分析,4,3.1 单词的描述工具,一个由正规表达式表示的语言称为一个正规集。例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|a*b a,b,ab,aab,aaab含有符号串a和包括零个或多于零个的a后跟一个b的所有符号串形成的集合。(a|b)*,a,b,aa,ab,ba,bb,aaa所有含a和b的符号串组成的集合。,2023/11/17,第三章：词法分析,5,3.1 单词的描述工具,两个正规表达式的等价：P54。如果两个正规表达式表示同样的语言，则称这两个正规式是等价的。如(a|b)与(b|a),(a|b)*与(a*b*)*都是等价的。正规表达式的运算优先级和代数规律:P54*高于“连接”和|，“连接”高于|具有交换律、结合律“连接”具有结合律、和对|的分配律()指定优先关系.意义清楚时，括号可以省略 是“连接”运算的恒等元素。程序设计语言中的单词都能用正规表达式来定义。比如，用l来代表字母，d代表数字，=l,d,则r1=l(l|d)*表示的是标识符，r2=dd*则定义了无符号整数，r3=d*(.dd*|)(e(+|-|)dd*|)表示的是无符号数。,2023/11/17,第三章：词法分析,6,3.1 单词的描述工具,正规式与正规文法上的正规式到正规文法G转换（特指右线性正规文法）：方法：令其中的VT=；对于任何正规式r，选择S，生成Sr，然后按以下三条规则对Sr进行分解直到每个产生式最多含有一个终结符为止。并将S定为G的开始符号；若x和y都是正规式，对形如Axy的产生式重写为：A xB和B y两产生式，其中B是新选择的非终结符；对形如A x*y的产生式，重写为：A xA和A y 对形如A x|y的产生式，重写为：A x和A y,2023/11/17,第三章：词法分析,7,3.1 单词的描述工具,例3-2，将r=a(a|d)*转换成相应的正规文法：解：令S为文法的开始符号，首先形成Sa(a|d)*然后对其进行分解，得到SaA和A(a|d)*,再对后条规则重写为：A（a|d)A和A，最终形成的文法G为：SaA AaA AdA A 将正规文法G转换成上的正规式：基本上是上述过程的逆过程，最后只剩下一个开始符号定义的产生式，并且该产生式的右部不含非终结符，则此产生式的右部为所求。其转换规则如下：规则1：A xB,B y A xy 规则2：A xA|y A x*y 规则3：Ax,Ay A x|y,2023/11/17,第三章：词法分析,8,3.1 单词的描述工具,例3-3，将文法GS：S aA S a A aA A dA A a A d 转换为相应的正规表达式。解：过程如下：S aA|a A aA|dA|a|d 可写为 A(aA|dA)|(a|d)可写为 A(a|d)A|(a|d)可写为 A(a|d)*(a|d)将其代入S可得：S a(a|d)*(a|d)|a a(a|d)*(a|d)|)a(a|d)*即a(a|d)*为所求。,2023/11/17,第三章：词法分析,9,3.2 状态转换图与基本符号的识别,状态转换图的引进：P63 通常，为了识别标识符，画出识别标识符的流程图如右图所示。现在引进“状态”这个概念，在开始状态下取得一个字母便处于标识符状态，如果后面取到的仍然是字母或数字，则继续处于标识符状态，直到不是字母或数字才离开标识符状态，根据此将其变成下面的图：,2,状态转换图是为了识别正规文法的句子专门设计的有向图。它只包含有穷多个状态，即有穷多个结点。（除了终止状态结点不代表任何非终结符号外）每个状态结点都代表文法的非终结符号。状态之间用箭弧（或称有向边）连接。弧上的标记指明在射出弧的结点状态下可能出现的输入字符。,2023/11/17,第三章：词法分析,10,3.2状态转换图与基本符号的识别,状态转换图的构造：P64构造方法：对于右线形正则文法，状态转换图构造步骤如下：以每个非终结符为状态结点，开始符号对应初态 S；增设一个终态 Z；对于规则 AaB，画从状态 A 到 B 的弧，标记为 a；对于规则 Aa，画从状态 A 到终态 Z 的弧，标记为a。例3-4，为例3中所给的文法GS构造其转换图如下：,S aAS aA aAA dAA aA d,2023/11/17,第三章：词法分析,11,3.2状态转换图与基本符号的识别,利用状态图识别句子的步骤如下：（=a1a2an,aiVT)1.从初态S出发，并自左至右逐个扫描中的各个字符，显然，在状态S之下所扫视的输入字符为a1，此时在结点S所射出的箭弧中寻找标记为a1的箭弧（如不存在，则表明有词法错误），读入a1，并沿箭弧所指的方向前进到下一个状态；2.设在状态Ai的情况下，所扫视的输入字符为ai+1,在结点Ai所射出的各箭弧中寻找标记为ai+1 的箭弧，读入ai+1，并过渡到下一状态Ai+1;3.重复上面的过程，直到中全部字符读完且进入终态Z时，宣告整个识别结束，已被接受。,因为：S a1 A1，A1 a2A2，A2 a3A3,Ai ai+1Ai+1,An-1 anAn所以有：S=a1 A1=a1a2A2=a1a2a3A3=a1a2a3an,2023/11/17,第三章：词法分析,12,3.3 有限自动机,确定的有限自动机DFA M：,定义：状态图的形式化。见P73的 定义3.1。确定的有限自动机DFA M 是一个五元组，即 M=（,Q,q0,F,）其中：字母表 Q：有限状态集合 q0：初态 F Q：终态集合：Q Q 的单值映射,2023/11/17,第三章：词法分析,13,3.3 有限自动机,表示形式：状态图:假定M有n个状态，m个输入符号，那么这个状态转换图含有n个状态结，每个状态结最多由m条箭弧射出与别的状态结相连接。准确地说，若转移函数对于q,qQ及a,有(q,a)=q，则从q到q有一条标记为a的箭弧。整个图含有唯一一个初态结和若干个终态结。矩阵表示：一个DFA还可以用一个矩阵的形式来表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示在相应状态行和输入字符列下的新状态，即k行a列为(k,a)的值。用“”表示初态，否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。例3-5，设DFA M=（a，b，S，U，V，Q，S，Q，）其中定义为：(S,a)=U,(S,b)=V,(V,a)=U,(V,b)=Q,(U,a)=Q，(U,b)=V,(Q，a)=Q，(Q，b)=Q,2023/11/17,第三章：词法分析,14,3.3 有限自动机,例3-5中的DFA的状态图表示如下：,(S,a)=U,(S,b)=V(V,a)=U,(V,b)=Q(U,a)=Q，(U,b)=V(Q，a)=Q，(Q，b)=Q,矩阵表示如右：,2023/11/17,第三章：词法分析,15,3.3 有限自动机,利用DFA对字符串的识别：P74 对于 上的任何符号串*，若存在一条从初态结到终态结的通路，在这条通路上的所有箭弧标记符号连接成的符号串恰好是，则称为DFA所识别。或 若*，(q0，)=p,其中q0为DFA M的开始状态，p F,F为终态集，则称为DFA所接受（识别）。为了理解上述定义，扩充函数如P75上。即对任何a,qQ将扩张为：(q，)=q(q，a)=(q，)，a)用此定义试证：baab可为例5的DFA M所接受。过程：(S，baab)=(S，b)，aab)=(V，aab)=(V，a)，ab)=(U，ab)=(U，a)，b)=(Q，b)=Q，Q属于终态，得证。DFA M所识别的语言：所能识别的符号串的全体，记为L（M）。即L（M）=|*，若存在p F,使(q0，)=q。,(S,a)=U,(S,b)=V(V,a)=U,(V,b)=Q(U,a)=Q，(U,b)=V(Q，a)=Q，(Q，b)=Q,2023/11/17,第三章：词法分析,16,3.3 有限自动机,非确定的有限（状态）自动机NFA M：在前面的从正则文法构造NFA的例子中，恰好从一个状态射出的弧的标记是两两不同的。但是，如果有两条规则AaT1和AaT2，那么从A到T1和T2的弧的标记都是a。此时，不能用DFA的映射来表示状态为A时，输入a时的后继状态。也就是说，当状态为A，输入为a时，这个转换图的下一步动作出现了不确定性。即此时映射函数已不是单值的而是多值函数（(A，a)=T1,(A，a)=T2)。这就要扩充确定有限自动机的概念。定义：P75的定义3.2。对定义的理解：这里，并不要求具有单值性，它可以把序偶（qi,ai)映射到Q的子集qk1,qk2,qkn,即（qi,ai)=qk1,qk2,qkn。,2023/11/17,第三章：词法分析,17,3.3 有限自动机,的意义：是Q 的幂集，即Q中所有子集组成的集合。比如，Q=1，2，3则=,1,2,3,1,2,1,3,2,3,1,2,3有 个子集。Q 表示映射到 子集中的某一个，但并不是说某个子集（如1，3）就是合法的状态，而只是说1和3都有可能，还需继续去试1还是3。状态转换图的表示：一个含有n个状态，m个输入符号的NFA M，也可以形象地通过一张状态转换图来表示，这张图含有n个状态结，每个状态结可射出若干箭弧与别的状态结相连接。准确地说，如果(q，a)=q1,q2,qk,则从q出发分别向q1,q2,qk各射出一条标记为a的箭弧（q1,q2,qkQ，a，k可以是0），整个图含有一个初态结和若干个终态结。,2023/11/17,第三章：词法分析,18,3.3 有限自动机,例3-6，一个NFA M=（a,b,0,1,2,3,4,0,2,4,)其中(0，a)=0，3，(0，b)=0，1,(1，b)=2,(2，a)=2，(2，b)=2,(3，a)=4,(4，a)=4,(4，b)=4。与之对应的状态图表示如下：,b,b,b,2023/11/17,第三章：词法分析,19,3.3 有限自动机,例3-7，构造一个DFA M，它接受字母表a,b,c上，以a或b开始的字符串，或以c开始但所含的a不多于一个的字符串。满足此条件的状态转换图如下：,故：DFAM=(a,b,c,0,1,2,3,0,1,2,3，)其中：(0,a)=1(0,b)=1(0,c)=2(1,a)=1(1,b)=1(1,c)=1(2,a)=3(2,b)=2(2,c)=2(3,b)=3(3,c)=3,2023/11/17,第三章：词法分析,20,3.3 有限自动机,利用NFA对字符串的识别：P76 对于 上的任何符号串*，若存在一条从初态结到终态结的通路，且在这条通路上的所有箭弧标记符号连接成的符号串恰好是，则称为NFA所识别。若q0 F,F为终态集，这时q0状态结既是初态结也是终态结，因而存在一条从初态结到终态结的-道路，此时空符号串可为NFA所接受。具有-转移的非确定有限自动机：P78。若文法G中有形如A B（相当于A B）或A 时，在状态图中会有从A出发标有的箭弧到B或终态结，也就是说转移函数应该有(A，)=B，据此将非确定的有限自动机扩充为：Q（）的映射，而其它不变，这样所形成的非确定有限自动机为具有-转移的非确定有限自动机。此自动机与其它非确定有限自动机基本上是一样的，只是在识别时不理睬那些标记为的箭弧即可。,2023/11/17,第三章：词法分析,21,3.3 有限自动机,NFA DFA的转换：事实已经证明了不管是非确定的有限自动机M还是具有-转移的非确定的有限自动机M，都可以找到一个与之等价的确定有限自动机M，使得L（M）=L（M）。P76的定理3.1 转换思路：由M出发构造与之等价的M的办法是M的状态对应于M的状态集合，即要使转换后的DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态，也就是说，在读入符号串a1a2a3an之后，该DFA处在这样一个状态，该状态表示这个NFA的状态的一个子集T，而T是从NFA的开始状态沿着某个标记为a1a2a3an的路径可以到达的那些状态。引进两个定义：（对状态集合I）状态集合I的-closure(I):定义为一状态集，是状态集I中的任何状态经任意条弧而能到达的状态的集合。,2023/11/17,第三章：词法分析,22,3.3 有限自动机,状态集合I的a弧转换Ia:定义为一状态集，是指从状态集I出发先经过a弧后再经过若干条弧而能到达的状态的集合。可以写作：Ia=-closure(J)，J=move(I,a),其中，J是从I中任一状态出发经过一条a弧到达的状态集合，记为move(I,a)。比如，对于以下状态图中：-closure(0)=0,1,2,4,7在这里设I=0,1,2,4,7，则因为有move(I,a)=3,8=J,所以 Ia=-closure(J)=-closure(3,8)=1,2,3,4,6,7,8,2023/11/17,第三章：词法分析,23,3.3 有限自动机,具体转换步骤：(子集构造法）以下面的基于字母表=a,b上的具有-转移的非确定有限自动机M为例。步骤1：以I，Ia、Ib等为列做表，其中I列第一行的内容是初态的-闭包所得到的状态集合。并以此为I计算Ia、Ib等，而 且在所计算出的Ia、Ib等中若有新的状态集产生，就重复 以此新的集合为I再此计算Ia、Ib等，直到在所得的Ia、Ib等中不再产生新的状态集为止。,2023/11/17,第三章：词法分析,24,3.3 有限自动机,步骤1后的结果如下：,x,5,1,初态的-闭包,5,1,3,5,1,4,5,1,3,2,6,y,5,1,4,5,1,3,5,1,4,2,6,y,5,1,3,2,6,y,5,1,4,6,y,5,1,3,6,y,5,1,4,2,6,y,5,1,3,6,y,5,1,4,2,6,y,5,1,3,2,6,y,5,1,4,6,y,2023/11/17,第三章：词法分析,25,3.3 有限自动机,步骤2：在上表中将原NFA初态的-闭包作为转换后的DFA的初态，包含原NFA终态的状态作为转换后的DFA的终态，并进行重新编号得到转换后的DFA的状态转移矩阵如下：,0,0,0,1,1,1,1,包含原终态的状态作为新的终态,2023/11/17,第三章：词法分析,26,3.3 有限自动机,步骤3：画出转换后的DFA的状态图：,2023/11/17,第三章：词法分析,27,3.3 有限自动机,正规文法与有限自动机的等价性（证略）：通过前面引入有限自动机概念时我们看到正规文法G所用以识别句子的状态转换图就是某个有限自动机的状态转换图。这就是说正规文法G所产生的语言和某个有限自动机M所识别的语言是相同的，此时称G和M是等价的。等价性：对于任何一个正规文法，都存在一个FA M，使L（M）=L（G），反之亦然。见书中P8287内容。有限自动机与正规表达式的等价性：上的符号或空或经过连接、闭包所得的为正规表达式，而且可以看到，程序设计语言中的表达式（单词）大多数都可通过正规表达式比较清晰、方便地表示出来。,2023/11/17,第三章：词法分析,28,3.3 有限自动机,有限自动机与正规表达式的等价性：可以证明，对任何一个正规表达式r,都存在一个FA M，使L（M）=L（r)，反之亦然。见书中P87的定理3.5。结合正规文法与有限自动机的等价性，我们可以看到正规文法、正规表达式、有限自动机这三者之间在某种意义下是互相等价的。也就是说，字母表上的一个正规语言，既可以由某一个正规文法产生，也可以由某一正规表达式所表示，还可以由某一个有限自动机所识别，甚至还可以由某一个确定的有限自动机所识别。可根据需要在不同的情况采取不同的表达语言的方法。一般是正规表达式 NFA DFA。对于上的一个正规式r构造与之等价的NFA M：（这里要把状态图的概念拓广，令每条弧可用一个正规式作标记。）,2023/11/17,第三章：词法分析,29,3.3 有限自动机,具体转换步骤：步骤1：规定r与 等价，其中x为NFA 的初态，y为终态。步骤2：按以下三条规则将弧上的正规表达式逐渐分解直至分 解为单个的字符或空为止。规则 等价为规则 等价为规则 等价为,2023/11/17,第三章：词法分析,30,3.3 有限自动机,例3-8，构造与正规表达式(a|b)*(aa|bb)(a|b)*等价的 NFA M：首先：(a|b)*(aa|bb)(a|b)*等价为等价为等价为等价为,2023/11/17,第三章：词法分析,31,3.3 有限自动机,对于的一个NFA M构造与之等价的正规式：步骤1：在M的状态图上加两个状态结，一个为x结点，一个为 y结点。从x结点用连接到M的初态，从M的所有终 态结点用弧连接到y结点，形成只有一个初态和一个 终态的M。步骤2：使用以下三条规则逐步消去M中的所有结点，直至只 剩下x和y结点，这时在x和y之间箭弧上的标记即为所求。规则 等价为规则 等价为规则 等价为,上述两规则的逆,更具一般性,2023/11/17,第三章：词法分析,32,3.3 有限自动机,例3-9，为以下图所表示的NFA M构造与之等价的正规式r：增加结点x和y后形成新的M的状态转换图如下：,2023/11/17,第三章：词法分析,33,3.3 有限自动机,使用上述三条规则逐渐消去M中的所有结点后：,即r=(a|b)*(aa(a|b)*|bb(a|b)*)=(a|b)*(aa|bb）(a|b)*为所求。,2023/11/17,第三章：词法分析,34,3.3 有限自动机,DFA的化简（最小化）：化简条件：接受的语言必须相同。化简(最小化)算法基本思想划分法：1.将DFA M 中的状态划分为互不相交的子集，每个子集内部的状态都等价；而在不同子集间的状态均不等价。2.从每个子集中任选一个状态作为代表，消去其它等价状态。3.把那些原来射入其它等价状态的弧改为射入相应的代表状态。等价状态：设DFA M中有两个状态s,t1.s,t等价：如果从状态s出发能读出某个字串而停于终态，从t出发也能读出同样的字串而停于终态，则称s,t 等价。2.s,t可区别：如果s,t不等价，则称为s,t可区别。,2023/11/17,第三章：词法分析,35,3.3 有限自动机,化简（最小化）算法：1.把状态集Q划分为终态集和非终态集：非终态，终态。因为终态能识别，而非终态不能，所以它们是可区别的；2.对每个子集中的任何一个状态对（p,q)，若对每一个输入符号a，r=(p,a),s=(q,a)且r与s均等价，则易知p和q等价；若存在某个a使r和s可区别，则p和q可区别。以此将各子集继续分解，直至不能再分解为止。3.在最终的由各子集组成的状态集合中，在每个子集中任取一个状态做“代表”，而删去子集中其余状态，并把射向其它等价状态的箭弧都改作射向这个做“代表”的状态结中。这样得到的状态转换图所对应的DFA M就是接受L（M）的具有最少状态的DFA。,2023/11/17,第三章：词法分析,36,3.3 有限自动机,例3-10，设有一DFA 的状态转换图如下，试化简之。,解：1.1，2=0，1，2，3，4，5，6 2.考察子集1 0，1，2由(0,a)=1(1,a)=3(2,a)=1,2023/11/17,第三章：词法分析,37,3.3 有限自动机,再由(0,b)=2(2,b)=5,所以，最终 0，1，2，3，4，5，6,3.令状态3代表3,4,5,6，把原来到达状态4，5，6的弧都指向3，并删除4，5，6。得：,2023/11/17,第三章：词法分析,38,课堂练习（作业）,课上练习1：将下图中的DFA最小化。,解：1.1，2=A，B，F，C，D，E，G 2.考察子集1 A，B，F由(A,b)=C(B,b)=D(F,b)=,2023/11/17,第三章：词法分析,39,课堂练习（作业）,再由(C,b)=E(D,b)=F,接着考察子集2 C,D,E,G,由于(C,a)=(D,a)=(G,a)=(E,a)=G,所以，最终 A，B，C，D，G，E，F,3.令状态D代表D，G，把原来到达状态G的弧都射向D，并删除 G，得：,2023/11/17,第三章：词法分析,40,课堂练习（作业）,课上练习2：设计一个DFA，其输入字母表是0，1，它能接受以0开始以1结尾的所有序列。,解：（1.）根据题意，得到相应的正则式：0（0|1）*1（2.）构造其NFA如下：,（3.）NFA确定化为DFA（并换名）：,2023/11/17,第三章：词法分析,41,课堂练习（作业）,相应DFA的状态图如下为：,（4.）DFA最小化：解：1.1，2=1，2，3，4 2.考察子集1 1，2，3由(1,1)=(2,1)=4(3,1)=4,1 1，2,3,2023/11/17,第三章：词法分析,42,课堂练习（作业）,再由(2,0)=3(3,0)=3,这样，最终 1，2，3，4,所以，最小化DFA的状态图如下：,状态2与状态3等价,故最终的DFA设计为：M=（,Q,S,F,）其中=0，1Q=S，A，BF=B：(S,0)=A(A,0)=A(A,1)=B(B,0)=A(B,1)=B,课后练习：请构造与正则式r=(a*b)*ba(a|b)*等价的状态最少的DFA。,2023/11/17,第三章：词法分析,43,课后作业,P993.123.13(a),2023/11/17,第三章：词法分析,44,3.4 词法分析器的设计,词法分析程序的任务：从左至右逐个字符对源程序进行扫描，按照词法规则识别出一个个正确单词，并转换为相应的二元式（种别，属性值）形式，交给语法分析使用。另外，词法分析程序除了识别出单词及其属性外，往往还要完成那些在语法分析之前需要做的工作，如删除注解、空格、换行符等非必要信息，把标识符登录到符号表及其某些预加工处理等。,2023/11/17,第三章：词法分析,45,3.4 词法分析器的设计,词法分析程序的输出：词法分析程序的输出通常表示成二元式（种别，属性值）的形式，其中，常用单词种别有：各关键字（保留字、基本字），各种运算符，各种分界符各用一个种别码标识其它标识符用一个种别码标示常数用一个种别码标示而单词符号的属性值是指反映单词符号特性或特征的值。常用单词属性值有：常数的值，标识符的名字等保留字、运算符、分界符的属性值可以省略,2023/11/17,第三章：词法分析,46,例 3-11:单词符号序列while(*pointer!=0)pointer+;,while(WHILE，_)(SLP，_)*(FETCH，_)pointer(IDN，符号表入口指针)!=(RELOP，NE)0(CONST，0)(SRP，_)(LP，_)pointer(IDN，符号表入口指针)+(INC，_);(SEMI，_)(RP，_),3.4 词法分析器的设计,2023/11/17,第三章：词法分析,47,3.4 词法分析器的设计,词法分析程序设计为一个独立子程序的原因：词法分析器可作为一个独立的子程序，但这并不意味着必须把词法分析作为独立的一遍。词法分析程序作为一个独立子程序的好处：1.使整个编译程序的结构更简洁、清晰和条理化（简化语法分析过程）。2.编译程序的效率会改进。大部分的编译时间是花费在扫描字符以把单词符号分离出来，把词法分析独立出来，可采用专门的读字符和分离单词的技术可大大加快编译速度。另外，由于单词的结构可用有效的方法和工具进行扫描和识别，进而可建立词法分析程序的自动构造工具。3.增加编译程序的可移植性。在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，将这些置于词法分析程序中解决而不影响编译其它成分的设计。,2023/11/17,第三章：词法分析,48,3.4 词法分析器的设计,词法分析中的缓冲技术：有时词法分析程序为了得到某个单词符号的确切性质，只从该符号本身所含有的那些字符还不能作出判定，还需要超过该符号沿着程序字符流继续向前看若干个字符后才能作出确定分析，这就提出了设置输入缓冲器的必要性。特别是某些高级语言对关键字不加保护，单词间没有明确界符，要在上下文环境中识别单词，这时一定需要超前搜索。例如：FORTRAN中对“IF”的使用：IF(5.EQ.M)GOTO 50 IF=100 IF(100)=5 另外，对内存的操作比对文件系统要快。,2023/11/17,第三章：词法分析,49,3.4 词法分析器的设计,词法分析程序的手工设计：两步骤：1.画框图：正规式 NFA DFA 最小化的DFA具体的是：写出该语言的词法规则。把词法规则转换为相应的状态转换图。把各转换图的初态连在一起，构成识别该语言的自动机。2.由特殊的框图（即状态图）写出词法分析程序。将状态转换图看作通常的程序框图，按如下方法写出相应的词法分析程序。对于状态图中的每一状态（代表一个非终结符号）构造一段代码，代码的功能为：,子集法,化简,2023/11/17,第三章：词法分析,50,3.4 词法分析器的设计,从输入串中读一个字符；判断读入的字符与由此状态出发的哪条弧上的标记相匹配，然后转至相匹配的那条弧所指向的状态；重复步骤1直至无法前进（即到达那样的一个状态，它所面临的输入字符没有后继状态。可能有三种情况：一是没有前进的道路，二是超出了最长字符限制，三是文件系统单词读完了）。然后判断所在的是否为终态，是则“吃进”的字符序列为合法的单词，否则回退，直至遇到回退中的第一个终态为止，此时所形成的为合法单词。均不匹配时便失败（不能到达正常出口）。,2023/11/17,第三章：词法分析,51,3.4 词法分析器的设计,例题3-12，设计能识别以下三条规则表示的单词的词法分析程序。1.三条规则：a r1 abb r2 a*bb*r3 2.NFA:a abb a*bb*,2023/11/17,第三章：词法分析,52,3.4 词法分析器的设计,3.合并：,4.DFA:,2023/11/17,第三章：词法分析,53,3.4 词法分析器的设计,重新编号：,0,1,1,0,1,1,2023/11/17,第三章：词法分析,54,3.4 词法分析器的设计,所得状态图为：,识别r3,识别r1,识别r2,识别r3,a r1 abb r2 a*bb*r3,2023/11/17,第三章：词法分析,55,3.4 词法分析器的设计,最终所得状态图为：,对输入串aba的识别过程如下:从初态0开始工作，当它扫描到第一个字符a时，进入状态1。然后，见到b又进入了2，但2对于后面的输入字符a没有后继状态，因此不能继续前进，至此，DFA“吃进”两个字符a和b，经历了三个状态0，1，2。然后判断最后“吃进”的那个字符所处的状态2是否为终态，是则表明所识别的单词ab就认为是属于2所指的那个词形a*bb*。假如2不是终态，那么就把最后“吃进”的那个字符b退还给输入串，同时检查前一个状态1，一旦“吃进”的字符都退还完了，就宣布失败。,识别r2,识别r1,识别r3,2023/11/17,第三章：词法分析,56,3.4 词法分析器的设计,词法分析程序的自动生成：由专门的构造程序对用正规表达式组成的程序设计语言的符号说明书进行处理，生成一些表，这些表描述了不同语言中单词符号的构成规则，由一个通用的扫描算法使用这些表，就能实现某特定语言的词法分析程序的功能。如LEX实现就是词法分析程序自动构造的一例。LEX语言：用来描述词法分析程序的一组单词的正规式及其相应的语义动作，称为LEX语言。其由三部分组成：说明部分（变量说明、常量说明及类似于identifierletter(letter|digit)*的正规式的定义）、转换规则（类似于 正规式 动作描述 P1 action1 P2 action2 Pn actionn)及action所需要的辅助过程（用C语言书写的一些过程，被识别过程调用）。,2023/11/17,第三章：词法分析,57,3.4 词法分析器的设计,词法分析程序的自动生成：LEX编译程序的构造：Lex的输入称为Lex程序，主要为定义好了的一些词法规则。Lex程序的输出是一个可以识别这些单词的C语言子过程。其构造图如下：,LEX编译系统,词法分析程序L,LEX源程序,Lex.1,词法分析程序L（Lex.yy.c),输入符号串,单词符号串,2023/11/17,第三章：词法分析,58,3.5 补充：某简易语言词法分析 程序的设计与实现,词法规则 单词种别 属性(|)*IDN 符号表入口()*NUM 数值:=ASG 无 其它单词字符本身 单词名称 无,词法规则的定义：,2023/11/17,第三章：词法分析,59,3.5 补充：某简易语言词法分析 程序的设计与实现,letter|letter|digitdigit|digit:=+=(其它：实数、算术运算符、关系运算符、分号、括号等）,转换为正规文法：,2023/11/17,第三章：词法分析,60,3.5 补充：某简易语言词法分析 程序的设计与实现,转换为有限自动机：,2023/11/17,第三章：词法分析,61,3.5 补充：某简易语言词法分析 程序的设计与实现,子程序 scan()输入：字符流输出：Symbol:单词种别Attr:属性（全局变量attr）。,数据结构ch 当前输入字符token 输入缓冲区(字符数组)symbol 单词种别（子程序的返回值）attr 属性（全局变量attr）,2023/11/17,第三章：词法分析,62,3.5 补充：某简易语言词法分析 程序的设计与实现,子例程isKeyword(token):判别 token是关键字？返回关键字种别或-1Lookup(token):将 token 存入符号表，返回入口指针getchar():从输入缓冲区中读入一个字符放入ch,2023/11/17,第三章：词法分析,63,3.5 补充：某简易语言词法分析 程序的设计与实现,1.getchar()2.WHILE ch 是空格/跳过空格2.1 DO getchar();3.CASE ch of4.isdigit(ch):4.1 chtoken;getchar();4.2 WHILE isdigit(ch)DO chtoken;getchar();4.3 输入指针回退一个字符；4.4 将token中的字符串变成数值attr4.5 返回 NUM,实现算法：,2023/11/17,第三章：词法分析,64,5.isalpha(ch):5.1 chtoken;getchar();5.2 WHILE isalpha(ch)OR isdigit(ch)DO chtoken;getchar();5.3输入指针回退一个字符;5.4 key=isKeyword(token);5.5 IF key0 THEN 返回 key5.6 Lookup(token)attr;5.7 返回 IDN6:getchar();6.1 IF ch等于=THEN 返回 ASG6.2 出错处理,3.5 补充：某简易语言词法分析 程序的设计与实现,2023/11/17,第三章：词法分析,65,7+:返回 ADD8-:返回 SUB9*:返回 MUL10/:返回 DIV11=:返回 EQ12:返回 GT13:返回 LT14(:返回 LP15):返回 RP16;:返回 SEMI17 其它:出错处理18 END OF CASE,3.5 补充：某简易语言词法分析 程序的设计与实现,2023/11/17,第三章：词法分析,66,3.5 补充：某简易语言词法分析 程序的设计与实现,缓冲区预处理，超前搜索关键字的处理，符号表的实现Lookup：查找效率，算法的优化实现词法错误处理由于高级语言的词组成集合为3型语言，所以，这里讨论的词法分析技术可以用于处理所有的3型语言，也就是所有的可以用3型文法描述的语言。如：信息检索系统的查询语言、命令语言等。,需要说明的问题：,2023/11/17,第三章：词法分析,67,本章总结,词法从组成源程序的字符行中寻找出单词，并给出它们的种别和属性输出二元组序列高级语言的单词组成一个3型语言3型语言可以用正规表达式RE、正规文法RG、有限自动机FA描述有限自动机FA的状态转移图，可以被用来指导相应的词法分析器的实现3型语言相应的理论指导人们构造出了高级语言的词法分析器的自动生成器如：Lex词法分析程序的设计步骤：正规表达式 正规定义式（正规文法）状态图识别过程的实现算法 程序实现和测试,2023/11/17,第三章：词法分析,68,习题,P97 练习3.13.2；3.3,3.4选做练习3.53.13有能力者可以完成1）构造下列正规式的状态图a(a|b)*|a b*a)*b2）给出下述文法所对应的正规式S 0 A|1 BA 1 S|1B 0 S|0,2023/11/17,第三章：词法分析,69,习题,3）文法G为：|A|B|Y|Z 1|2|8|9|0将该文法改写为正规文法4）上机题合并例3-3和例3-4的状态图，设计并实现一个词法分析函数，每次返回一个单词种别和属性；编制主程序完成测试（输入和输出）。,