《指导教师：杨建国》由会员分享，可在线阅读，更多相关《指导教师：杨建国（93页珍藏版）》请在金锄头文库上搜索。
1、指导教师:杨建国,编 译 原 理,二零一零年三月,第四章 词法分析,第一节 词法分析程序的设计,第二节 单词的描述工具,第三节 有穷自动机,第四节 正规式和有穷自动机的等价性,第五节 正规文法和有穷自动机的等价性,第六节 词法分析程序的自动构造工具,第七节 典型例题及解答,知识结构,词法分析,自动构造工具LEX,正规集,正规式,有穷自动机（NFA DFA),正规文法,知识结构,描述,识别,寻找特殊方法和工具,第四章 词法分析,4.1 词法分析程序的设计,主要任务：读源程序，产生单词符号 其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，,一.词法分析程序与语法分析
2、程序的接口方式,词法分析工作可以是独立的一遍，把字符流的源程序 变为单词序列，输出在一个中间文件上，这个文件作 为语法分析程序的输入而继续编译过程,更通常情况，常将词法分析程序设计成一个子程序， 每当语法分析程序需要一个单词时，则调用该子程序。 词法分析程序每得到一次调用，便从源程序文件中读 入一些字符，直到识别出一个单词，或说直到下一单 词的第一个字符为止,二.词法分析程序的输出,1.单词符号一般可分为下列五种： 基本字（关键字）：begin、end、if、while、var 标识符：常量名、变量名、过程名 常数（量）：25、3.1415、true、“ABC” 运算符：、*、= 界符：逗点、
3、分号、括号,2.输出表示： （单词种别，单词自身的值） 单词种别：语法分析需要的信息 单词自身的值：编译其他阶段需要的信息 例如：const i=25,yes=1;,（标识符，指向该标识符所在符号表中位置的指针） const i=25,yes=1;对单词i和yes的表示为： （标识符，指向i的表项的指针） （标识符，指向yes的表项的指针） 单词的种别可以用整数编码表示，假如标识符编码为1 ，常数为2，关键字为3，运算符为4，界符为5,if i=5 then x:=y 关键字 if (3, if) 标识符 i （1，指向i的符号表入口） 等号 （4, = ） 常数 5 （ 2, 5 ） 关键字
4、 then （ 3, then ） 标识符 x （ 1,指向x的符号表入口） 赋值号:= （ 4, ：= ） 标识符y （ 1, 指向y的符号表入口 ） 分号; （ 5, ; ）,三.将词法分析工作分离的考虑,1.使整个编译程序的结构更简洁、清晰和条理化： 2.编译程序的效率会改进： 3.增强编译程序的可移植性：,4.2 单词的描述工具,一.正规文法 什么是正规文法？ 正规文法所描述的是VT上的正规集,程序设计语言中的几类单词可用下述规则描述： l|l l|d|l|d d|d +|-|*|/|=| = ,|;|(|)| 其中l表示az中的任何一个英文字母，d表示09中 的任何一个数字,关键字也
5、是一种单词，一般关键字都是由字母构成，它 的描述也极容易，实际上，关键字集合是标识符集合的 子集 最复杂的一类单词要属无符号实数，如25.55e+5和2.1， 它们可以由例4.1的规则描述,例4.1： d|.e d|.e| d e| d | d |s d d | 其中，s表示正或负号(+,-),二.正规式（正则表达式） 表示正规集的工具 描述单词符号的工具,正规式和它所表示的正规集的递归定义： 设字母表为，辅助字母表=， （1）和都是上的正规式，它们所表示的正规集分别为 和 （2）任何a ，a是上的一个正规式，它所表示的正规集 为a,（3）假定e1和e2都是上的正规式，它们所表示的正规集分别
6、为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规 式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1) 仅由有限次使用上述三步骤而定义的表达式才是上的正规 式，仅由这些正规式所表示的字集才是上的正规集,其中的“”读为“或”（也有使用“+”代替 “” 的 ）；“ ”读为“连接”；“”读为“闭包”（即，任 意有限次的自重复连接）。在不致混淆时，括号可省去， 但规定算符的优先顺序为“”、“”、“”、“ ”、 “” 。连接符“ ”一般可省略不写。“”、“ ”和 “” 都是左结合的,例4.2 令=a，b, 上的正规式和相
7、应的正规集的例子有： 正规式 正规集 a a ab a,b ab ab (ab)(ab) aa,ab,ba,bb a ,a,a, 任意个a的串 (ab) ,a,b,aa,ab 所有由a和b组成的串 (ab)(aabb)(ab) 上所有含有两个相继的a或两个 相继的b组成的串,例4.3 =d，e，+，-,则上的正规式 d(dd )(e(+- )dd ) 其中d为09的数字 表示的是： 无符号数的集合,例题：词法分析器的输入是什么？（10分） 例题：令=a,b,则上所有以a开头，后跟0个或许多个的 ab的字的全体对应的正规式是什么？（5分） 例题：请写出表示标识符的正规式e1=(l|_)(l|d|
8、_)*所对应的 正规集。（5分） 例题：有一台饮料自动售货机，接收1元或2元硬币，出售3 元钱一瓶的饮料。顾客每次向机器中投放等于或大于3元的 硬币，便可得到一瓶饮料（注意：多投不找钱）。写出对 应饮料自动售货机售货过程的正规式。画出与该正规式的 最小DFA。（10分）,答案：源程序（的字符流） 答案：a(ab)* 答案：l,_,ll,ld,l_,_l,_ _,-d,或者以1或_打头l,_,d组成 的字符串 答案：设a=1,b=2,则a (b | a( a| b) ) | b (a |b) 或者：21|22|12|111|112,若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写
9、 作e1=e2 例如： e1= (ab)， e2 = ba 又如： e1= b(ab) , e2 =(ba)b e1= (ab) , e2 =(ab),设r,s,t为正规式，正规式服从的代数规律有： rs=sr “或”服从交换律 r(st)=(rs)t “或”的可结合律 (rs)t=r(st) “连接”的可结合律 r(st)=rsrt (st)r=srtr 分配律 r=r r=r 是“连接”的恒等元素（零一律） rr=r r=rrr “或”的抽取律,三.正规文法和正规式的等价性,1.将上的一个正规式r转换成文法G=(VN,VT,P,S)： 令VT，确定产生式和VN的元素用如下办法：,选择一个非
10、终结符S生成产生式S r，并将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做变换，直到每个产生式右端只含一个VN,AxB,A y A xA,B y,A xA,A y,例4.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
11、B R3 S aA A A aB A dB B aB B dB B ,2.将正规文法转换成正规式： 基本上是上述过程的逆过程，最后只剩下一个开始符 号定义的正规式，其转换规则如表4.1所示：,例4.5 Gs: S aA S a A aA A 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)*,4.3 有穷自动机,一.确定的有穷自动机（DFA）（有限自动机） DFA：能准确地识别正规集 一个确定的DFA：M=（K，f，S，Z） K是一个
12、有穷集，它的每个元素称为一个状态 是一个有穷字母表，它的每个元素称为一个输入符 号，所以也称为输入符号字母表,f是转换函数，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着，当前状 态为ki，输入符为a时，将转换为下一个状态kj，我们 把kj称作ki的一个后继状态 SK是唯一的一个初态 Z K是一个终态集，终态也称可接受状态或结束状态,例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）=V f（v，b）=Q f（U，a）=Q f（Q，a）=Q f（U，b）=V f（Q，b）=Q,一个DFA可以
13、表示成一个状态图（状态转换图） 假定DFA M含有m个状态，n个输入符号，那么这个 状态图含有m个结点，每个结点最多有n个弧射出，整 个图含有唯一一个初态结点( 、)和若干个终态结 点(双圈、+)，若f(ki,a)=kj，则从状态结点ki到状态结点 kj画标记为a的弧,图4.1 状态图表示,例4.6中的DFA的状态图表示如图4.1所示：,一个DFA可以表示成一个矩阵表示，该矩阵的行表示状 态，列表示输入符号，矩阵元素表示相应状态和输入符 号将转换成的新状态，即k行a列为f(k,a)的值。用 标明初态；否则第一行即是初态，相应终态行在表的右 端标以1，非终态标以0,图4.2 矩阵表示,例4.5中
14、的DFA的矩阵表示如图4.2所示：,若t *，f(S，t)=P，其中S为 M的开始状态，P Z， Z为终态集，则称t为DFA M所接受（识别） 设QK，函数f(Q,)=Q，一个输入符号串t（t1tx，t1 ,tx *），在DFA M上运行的定义为： f(Q,t1tx)=f(f(Q,t1),tx),例如，证明t=baab被例4.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属于终态 得证,DFA M所能接受的符号串的全体记为L(M) 结论：上一个符号串集V是正规的，当且
15、仅当存 在一个上的确定有穷自动机M，使得V=L(M) DFA的确定性表现在转换函数f:KK是一个单值 函数，也就是说,对任何状态kK和输入符号a ， f(k,a)唯一地确定了下一个状态,二.不确定的有穷自动机NFA 一个NFA：M=（K，f，S，Z） K是一个有穷集，它的每个元素称为一个状态 是一个有穷字母表，它的每个元素称为一个输入符号 f是一个从K * 到K的子集的映像，即：K* * 2 K （多值映射） SK是一个非空初态集 ZK是一个终态集,提示：NFA与DFA的第三个区别是，前者可以空移：t(q, )=某些状态的集合,例4.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
