《第三章词法分析终》由会员分享，可在线阅读，更多相关《第三章词法分析终（75页珍藏版）》请在金锄头文库上搜索。
1、1第三章 词法分析3.1 词法分析程序的设计3.2 单词的描述工具3.3 有穷自动机3.4 正规式和有穷自动机的等价性3.5 正规文法和有穷自动机的等价性3.6 词法分析程序的自动构造工具3.7 典型例题及解答2知识结构3词法分析自动构造工具正规集正规式有穷自动机（NFA DFA)正规文法知识结构43.1 词法分析程序的设计源程序词法分析程序语法分析程序Tokenget token.v主要任务：读源程序，产生单词符号v其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，5一.词法分析程序与语法分析程序的接口方式v词法分析工作可以是独立的一遍，把字符流的源程序变为单词
2、序列，输出在一个中间文件上，这个文件作为语法分析程序的输入而继续编译过程v更通常情况，常将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词，或说直到下一单词的第一个字符为止6二.词法分析程序的输出1.单词符号一般可分为下列五种：v基本字（关键字）：begin、end、if、while、varv标识符：常量名、变量名、过程名v常数（量）：25、3.1415、true、“ABC”v运算符：、*、=v界符：逗点、分号、括号2.输出表示：v（单词种别，单词自身的值） 单词种别：语法分析需要的信息
3、单词自身的值：编译其他阶段需要的信息7v（标识符，指向该标识符所在符号表中位置的指针） 单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，关键字为3，运算符为4，界符为5， if i=5 then x:=y 关键字 if (3, if) 标识符 i （1，指向i的符号表入口） 等号 （4, = ） 常数 5 （ 2, 5 ） 关键字 then （ 3, then ） 标识符 x （ 4,指向x的符号表入口） 赋值号:= （ 4, ：= ）8 标识符y （ 1, 指向y的符号表入口 ） 分号; （ 5, ; ）三.将词法分析工作分离的考虑1.使整个编译程序的结构更简洁、清晰和条理化：2
4、.编译程序的效率会改进：3.增强编译程序的可移植性：93.2 单词的描述工具一.正规文法v程序设计语言中的几类单词可用下述规则描述： l|l l|d|l|d d|d +|-|*|/|=| = ,|;|(|)| 其中l表示az中的任何一个英文字母，d表示09中的任何一个数字10v例3.1： d|.e d|.e| d e| d | d |s d d |其中，s表示正或负号(+,-)11二.正规式v正规表达式（regular expression）是说明单词的pattern的一种重要的表示法（记号），是定义正规集的工具v定义（正规式和它所表示的正规集）： 设字母表为，辅助字母表=， 和都是上的正规式
5、，它们所表示的正规集分别为和 任何a ，a是上的一个正规式，它所表示的正规集为a12 假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1) 仅由有限词使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集13 其中的“”读为“或”（也有使用“+”代替 “” 的）；“ ”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、
6、“”、“”、“ ”、“” 。连接符“ ”一般可省略不写。“”、“ ”和“” 都是左结合的14v例3.2 令=a，b, 上的正规式和相应的正规集的例子有：正规式 正规集a aab a,bab ab(ab)(ab) aa,ab,ba,bba ,a,a, 任意个a的串 (ab) ,a,b,aa,ab 所有由a和b组成 的串 (ab)(aabb)(ab) 上所有含有两个相继的a或两个相继的b组成的串15v例3.3 =d，e，+，-,则上的正规式d(dd )(e(+- )dd ) 其中d为09的数字表示的是：无符号数的集合。v若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2
7、例如： e1= (ab)， e2 = ba 又如： e1= b(ab) , e2 =(ba)b e1= (ab) , e2 =(ab)16v设r,s,t为正规式，正规式服从的代数规律有： rs=sr“或”服从交换律 r(st)=(rs)t“或”的可结合律 (rs)t=r(st)“连接”的可结合律 r(st)=rsrt (st)r=srtr分配律 r=rr=r是“连接”的恒等元素（零一律） rr=rr=rrr“或”的抽取律17三.正规文法和正规式的等价性1.将上的一个正规式r转换成文法G=(VN,VT,P,S)：令VT，确定产生式和VN的元素用如下办法： 选择一个非终结符S生成产生式S r，并将
8、S定为G的识别符号。若x和y都是正规式 ， BVN ，则：(R1) 对形如 A xy的正规产生式，重写为：A xB，B y (R2)对形如A x*y的正规产生式，重写为：A xB，A y，B xB，B y (R3)对形如A xy的正规产生式，重写为:A x，A y不断应用R做变换，直到每个产生式右端只含一个VN18例3.4 将 r=a(a|d)*转换成相应的正规文法令S是文法的开始符号，形成S a(a|d)*：R1 S aA A (a|d)*R2 S aA A (a|d)B A B (a|d)B B R3 S aA A A aB A dBB aB B dBB 192.将正规文法转换成正规式：基
9、本上是上述过程的逆过程，最后只剩下一个开始符号定义的正规式，其转换规则如表4.1所示：20例3.5 Gs:S aA S a A aAA dA A a A d S aA|a A aA|a|dA|d (a|d)A|(a|d) (a|d)*(a|d)s=a(a|d)*(a|d)|a=a(a|d)*(a|d)|)=a(a|d)*|)r=a(a|d)*213.3 有穷自动机一.确定的有穷自动机（DFA）（有限自动机）vDFA：能准确地识别正规集v一个确定的DFA：M=（K，f，S，Z） K是一个有穷集，它的每个元素称为一个状态 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表 f
10、是转换函数，是在KK上的映射，即，如f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态22 SK是唯一的一个初态 Z K是一个终态集，终态也称可接受状态或结束状态v例4.6：DFA M=（S，U,V，Q，a，b，f，S，Q）其中f定义为： f（S，a）=U f（V，a）=U f（S，b）=Vf（v，b）=Q f（U，a）=Qf（Q，a）=Q f（U，b）=Vf（Q，b）=Q23v一个DFA可以表示成一个状态图（状态转换图）v假定DFA M含有m个状态，n个输入符号，那么这个状态图含有m个结点，每个结点最多有n
11、个弧射出，整个图含有唯一一个初态结点( )和若干个终态结点(双圈)，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧v例4.6中的DFA的状态图表示如图4.1所示：24图3.1 状态图表示25v一个DFA可以表示成一个矩阵表示，该矩阵的行表示状态，列表示输入符号，矩阵元素表示相应状态和输入符号将转换成的新状态，即k行a列为f(k,a)的值。用 标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0v例4.5中的DFA的矩阵表示如图4.2所示：26图3.2 矩阵表示字符状态27v若t *，f(S，t)=P，其中S为 M的开始状态，P Z，Z为终态集，则称t为D
12、FA M所接受（识别）v设QK，函数f(Q,)=Q，一个输输入符号串t（t1tx，t1 ,tx *），在DFA M上运行的定义为：f(Q,t1tx)=f(f(Q,t1),tx)28v例如，证明t=baab被例3.6的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）=Q Q属于终态 得证29vDFA M所能接受的符号串的全体记为L(M)v结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)vDFA的确定性表现在转换函数f:KK是一个单值函数，也就是说,对
13、任何状态kK和输入符号a ，f(k,a)唯一地确定了下一个状态30二.不确定的有穷自动机NFAv一个NFA：M=（K，f，S，Z） K是一个有穷集，它的每个元素称为一个状态 是一个有穷字母表，它的每个元素称为一个输入符号 f是一个从K * 到K的子集的映像，即：K* * 2 K SK是一个非空初态集 ZK是一个终态集31v例3.7：一个NFA M=（0，1，2，3，4，a，b，f，0，2,4）其中 f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4 它的状态图表示如图4.3所示：3233v一个N
14、FA也可以用一个矩阵表示.v*上的符号串t在NFA N上运行.v*上的符号串t被NFA N识别（读出、接受）.vDFA是NFA的特例v对每个NFA N存在一个DFA ,使得L(M)=L(N)v对于任何两个有穷自动机M和N，如果L(M)=L(N)，则称M与N是等价的34三.NFA转换为等价的DFAv定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机v将NFA转换成接受同样语言的DFA，这种算法称为子集法35v状态集合I的几个有关运算：vv定义定义1 1：集合：集合I I的的 - -闭包：闭包：令令I I是一个状态集的子集，定义是一个状态集的子集，定义-closure-closure（I I）为：为： 1 1）若）若s sI I，则，则s s-closure-closure（I I）；）； 2 2）若）若s sI I，则从则从s s出发经过任意条出发经过任意条 弧能够到达的弧能够到达的 任何状态都属于任何状态都属于-closure
