编译原理第五讲

1、Compiler Construction Principlesl面临当前输入符号都能唯一确定选择哪个产生式进行推导。Compiler Construction Principlesl若有文法G1S:S pA |qBA cAd|aB d B |c识别输入串w= pccadd是否是G1S的句子Compiler Construction Principlesl若有文法G2S:S Ap |BqA a|cA B b|dB识别输入串w=ccap是否是G2S的句子，那么试探推出输入串的推导过程为 ：Compiler Construction Principlesl若有文法G3S:S aA|dA bAS|识

2、别输入串w=abd是否是G3S的句子Compiler Construction Principles4.1.1 词法分析程序的功能词法分析程序的功能 WhileWhile ij dodo if if ij then then i:i-j elseelse j:=ji whilewhile，i， ，j， dodo， ifif，i，j,thenthen, i, := , i, - , j,elseelse, j, :=, j, -, iCompiler Construction Principlesl词法分析程序的功能：逐个读入源程序字符并按照构词规则切分成一系列单词。l输入：源程序l输出：单词

3、（种类编码，单词自身的属性值）Compiler Construction Principles种类和属性程序语言单词的分类： 1关键字(保留字或基本字)：begin,end 2标识符：用来表示各种名字 3常数：256，3 .14，true,abc 4 运算符：如，、*、/ 等等 5分界符：如逗号，分号，冒号等Compiler Construction Principles词法分析器的输出： （种类编码，单词自身的属性值）关键字可分成一类，也可以一字分成一类。常数可统归一类，也可按类型。运算符可采用一符一类的分法，但也可以把具有一定共性的算符视为一类。分界符一般用一符一类的分法。标识符一般统归为

4、一种。Compiler Construction Principles例如：图31的源程序经词法分析器while， id，指向i的符号表入口的指针 ， id，指向j的符号表入口的指针do， if， id，指向i的符号表入口的指针 id，指向i的符号表入口的指针WhileWhile ij dodo if if ij then then i:i-j elseelse j:=jiCompiler Construction Principles4.1.3 把词法分析设计成一个独立程序把词法分析设计成一个独立程序 （1）组织成一遍扫描；（2）作为语法分析和语义分析的子程序原因：简化设计改进编译效率增加编

5、译系统的可移植性 Compiler Construction Principles4.2单词的描述工具单词的描述工具4.2.1正规文法正规文法例例 文法文法G=（VN，VT，P，S）VN =标识符，字母，数字标识符，字母，数字VT =a,b,c,x,y,z,0,1,9P=| a, zz 0, 0, 99 S=Compiler Construction Principles4.2.2正规式正规式1)定义（正规式和它所表示的正规集）：设字母表为，辅助字母表=，。1. 和都是上的正规式，它们所表示的正规集分别为和 ；Compiler Construction Principles2.任何a ，a是上

6、的一个正规式，它所表示的正规集为a；3.假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。Compiler Construction Principles其中的“”读为“或”（也有使用“+”代替 “” 的）；“ ”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符

7、的优先顺序为“”、“ ”、“” 。连接符“ ”一般可省略不写。“”、“ ”和“” 都是左结合的。Compiler Construction Principles例子例子令=a，b， 上的正规式和相应的正规集的例子有：正规式 正规集a aab a,bab ab(ab)(ab) aa,ab,ba,bba ,a,a, 任意个a的 串Compiler Construction Principles 正规式 正规集(ab) ,a,b,aa,ab 所有由a 和b组成的串(ab)(aabb)(ab) 上所有含有两个相继 的a或两个相继的b组成 的串Compiler Construction Principl

8、es 讨论下面两个例子例3.1 令=l，d，则上的正规式 r=l(l d) 定义的正规集为: l,ll,ld,ldd,其中l代表字母,d代表数字,正规式 即是 字母(字母|数字) ,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和 多数程序设计语言允许的的标识符的词法规则.例3.2=d，e，+，-,则上的正规式 d(dd )(e(+- )dd )表示的是无符号数的集合。其中d为09的数字。 程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义. .Compiler Construction Principlesl若两个正规式e1和e2所表示的

9、正规集相同,则说e1和e2等价,写作e1=e2。例如： e1= (ab)， e2 = baCompiler Construction Principlesl正规式服从的如下的代数规律 设r,s,t为正规式，则有：1。rs=sr“或”服从交换律2。r(st)=(rs)t“或”的可结合律3。(rs)t=r(st)“连接”的可结合律4。r(st)=rsrt (st)r=srtr分配律 Compiler Construction Principles5。 r=r, r=r是“连接”的恒等元素6。 rr=r零一律 r=rrr“或”的抽取律 练习1 设=a，b指出下列正规式的正规集a(a|b)b ab*

10、a(a|b)*练习2 设=a，b，c则aa*bb*cc*是上的正规式，求它所表示正规集Compiler Construction Principles4.2.3正规文法和正规式的等价性正规文法和正规式的等价性对上的正规式r ,存在一个RG=(VN,VT,P,S)：L(G)=L(r)初始， VT= ,S VN ，生成正规产生式 Sr (R.1) 对形如 Ar1r2的正规产生式：Ar1B Br2 BVN (R 2)对形如Arr1的正规产生式： ArA|r1 AVN (R 3)对形如Ar1r2的正规产生式: Ar1 A r2 不断应用R做变换，直到每个产生式右端至多有一个VNCompiler Con

11、struction Principles例例 r=a(a d) Compiler Construction Principles正规文法和正规式正规文法和正规式 对对G=(VN,VT,P,S),存在一个存在一个 =VT上的正规式上的正规式r : L(r)=L(G)AxB, By A=xy AxAy A=xy Axy A=xyCompiler Construction Principles正规文法和正规式正规文法和正规式Gs:SaA|a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a=a(ad)(ad)=a(ad) R=a(ad)Compiler Constr

12、uction Principles一设计一个奇偶校验器 DFA是由集合，序列和函数定义的数学模型，它对于上的w，判定是可接受的还是不可接受的。例如，设计一个DFA m ，奇偶校验器，首先，w是由0，1组成的字符串，因此，1. =0 ,1且w在一条输入带上。 0 1 0 1 1$读头Compiler Construction Principles 2. 状态集：它记忆已读入w子串的状态,m是奇偶校验器，它应该记住，初始序列是奇数个1还是偶数个1。因此，m有even和odd两个状态. 3 .even为开始状态。 4 . 转换函数，（qold , ,a)=qnew m有: (even ,0)=eve

13、n （even ,1)=odd (odd ,0)=odd （odd ,1)=even 5. 接受状态（或终止状态）集odd 若w使m从初始状态出发，最后到达一个接受状态，则w被m接受；否则w被m拒绝。Compiler Construction Principles二 定义31 一个确定的有限自动机 M（记 作DFA M）是一个五无组 （，0，），其中（）是一个有限状态集合。（）是一个字母表，它的每个元素称 为一个输入符号。（）0，0 称为初始状态。（），称为终结状态集合。（）是一个从 到的单值映射 (，)（,，） 表示当前状态为q,输入符号为a时，自动机将转换到下一个状态，称为的一个后继。Co

14、mpiler Construction Principles例33 设（， ，）其中（，），（，）3（，），（，）（，），（，）（，），（，）三 一个有三种表示：（1）象上面，用转换函数；（2）转移矩阵；（3）状态转换图。Compiler Construction Principlesab012132213333转移矩阵0132aaaabbbb3状态转换图易存储Compiler Construction Principles四 DFA M 接受的语言 如果对所有*，以下述方式递归地扩张的定义 （，），(，）(，w），）， 对任何 ,，则有（）*，若存在， 使（，） 对于例3.3的DFA M和w

15、=baa， (0，ba）=(2,a）= (1,）=3Compiler Construction Principles 从状态转换图看，从初态出发，沿任一条路径到达接受状态，这条路径上的弧上的标记符号连接起来构成的符号串被接受。0123aaaabbbbCompiler Construction Principles 五. DFA M 判定 ?(）的算法： 输入：$ q:=q0; a:=nextchar; WHILE a$ DO BEGIN q:=move(q,a); a:=nextchar; END; IF q IN F THEN return (”yes) ELSE return (”no);

16、Compiler Construction Principles3.2.2 手工构造识别单词的DFA m 根椐DFA识别单词的定义，在研究给定程序语言单词结构的基础上，能直接构造出识别它的DFA m。例如：对于Pascal, 标识符：字母开始的字母数字串。 整数：非空数字串。 无符号实数（用表示数字）： （a) dd.d dE(+- ) dd (b) ddE(+- ) dd (c) dd.d dCompiler Construction Principles1342字母字母数字数字数字Pascal 标识符Pascal整数和实数0134652700dddddddEE+7*Compiler Con

17、struction Principles3.2.3 编写词法分析程序 根据画出的状态转换图（识别单词的）构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。 在识别标识符的过程中，要拼写出来，并和保留字区别开来；在识别常数的过程中，要把它转换成机器表示以作为属性值。Compiler Construction Principles 使用下面的全局变量和过程：1. Character 2. Token3. Getchar 4. getbc5. Concatenation6. letter,digit7. Reserve 8. Retract

18、9. buildlist10. returnCompiler Construction Principles作业： 3.2 3.3解释下面每个有限自动机识别的语言是什磨？(a)12345678900000001111111(b)12345aaaaaCompiler Construction Principles( c )0120001113.4 给出接受下列在字母表0，1上的语言的DFA: ( a ) 所有以00结束的串的集合； （b) 所有具有三个0的串的集合。0Compiler Construction Principles3. 3 有限自动机 FA m 3. 3. 1 非确定的 有限自动

19、机NFA m 一. NFA m 二. FA 的等价定理 三. 例3.3，用DFA模拟NFA的动作 四. 从一个NFA构造DFA的算法3. 3. 2 确定的 有限自动机的化简 一.何谓确定的 有限自动机的化简 二.等价状态的定义 三.确定的 有限自动机的化简方法Compiler Construction Principles一. 非确定的有限自动机NFA m定义32 非确定有限自动机是一个五元组 （，q，）其中，q，的意义和的定义一样，而是一个从到的子集的映射，即： 类似FA，NFA m可用状态转换图表示，可定义NFA m接受的语言。Compiler Construction Principle

20、s二. FA的等价性定理3 . 1 对任何一个NFA m，都存在一个 DFA m，使L(m)=L(m)证明思想：用m的一个状态对应m的一个状 态集合，用这种方法，能从一个NFA m 构造一个DFA m，称作子集构造法。例3 . 2 NFAm=(0,1 , q0,q1,q0, ),其中 (q0,0)= q0,q1, (q0,1)= q1 (q1,0)= (q1,0)= q0,q1Compiler Construction Principlesq0q0q100111q0q0q0q1q0,q10110,1L(m)=L(m)=0,1+100,1*Compiler Construction Princi

21、ples014236578910aabbb012470,1,2，4,7a3a8612473,8,6,1,2,4,7b5b961247a5,9,6,1,2,4,7bb56124b105,10,6,1,2,4,77b例3.3从具体例子的讨论,提炼出从NFA构造DFA的算法。Compiler Construction Principles四. 从NFA构造DFA的算法 1.closure(S) 的定义和算法 从S中任一状态出发，仅沿弧到达的状态集合，T=S ( edge(t, ), 其中，edge(t, a)是NFA中从状态t出发，仅沿a弧到达的状态集合。如下计算T： T:=S; REPEAT T:

22、=T ; T:=T ( edge(t, ) (tT) UNTIL T=TtTCompiler Construction Principles2. DFA的转移函数 DFAedge(d, a)= closure( edge(t, a)其中， d是NFA的状态集， a 。 从NFA构造DFA，是对于NFA的所有输入,，用DFA模拟NFA的动作，令t1是NFA的初态，DFA的初态d1= closure(t1) ，若， dj= DFAedge(di, a),那磨，从di到dj存在一条用a标识的弧。算法3,2 从一个NFA构造一个DFAtdCompiler Construction Principles

23、States1 :=-closure(t1); p:=1; j:=1;WHILE j=p DO for each a e:=DFAedge(statesj,a); IF e=statesi for some i=p THENtransj,a=i ELSE p: =p+1; statesp:=e; transj,a:=p; ; ; j:=j+1; Compiler Construction Principles01436578910abbb2astatesab3,8,6,1,2,4,70,1,2,4,725,6,1,2,4,7325,9,6,1,2,4,742325,10,6,1,2,4,752

24、3Compiler Construction Principles3.3.2 确定的有限自动机的化简一. 何谓确定的有限自动机的化简 所谓一个DFA m=(, Q, q0, F, )的化简是指寻找一个状态数比较少的DFA m,使L(m)=L(m)。而且可以证明， 存在一个最 少状态的DFA m, 使L(m)=L(m)。二.等价状态的定义 设p,q Q ，若对任何w * , (p,w) F 当且仅当 (q,w) F ，则称p和q是等价状态。否则，称p和q是可区别的。Compiler Construction Principlesq1q2q3q4q1q2q3q6q4q5q7baaaaaaaaaaa

25、bbb,bbbbbbbCompiler Construction Principles1.等价状态定义了状态集合上的等价关系。因此，状态集合能被划分成等价类；2 .两个状态p和q等价应满足如下条件：（a）一致性条件， p和q必须同时或为接受 状态或为非接受状态；（b）蔓延性条件，对于a ， （p,a)=r, （q,a)=s, r和s必须等价; 相反, r和s不等价, p和q不等价。 判定两个状态p和q不等价，只要o找到一个w*， 使（p,w)F 且（q,w) F，或者相反。 W称为判别序列。Compiler Construction Principles三. 方法： 构造一张表，对每一个状态对

26、（qi,qj）（ij）有一表项，每当发现一对状态不等价时，就放一个x到相应表项中。1 . 根据一致性条件，在每一个对应于终结状态和非终结状态的表项中放上一个x。2 .根据蔓延性性条件，对每一个状态对（p,q），若a，（p,a）=r， （q,a）=s，r和s不等价，则（p,q）不等价。重复2，直到没有新的不等价状态对出现。Compiler Construction Principlesq8q7q6q5q1q2q311110111000000 xxxxxxq2q3q5q6q7q8q1 q2 q3 q5 q6 q7xxxxxxxxxxxxxCompiler Construction Principl

27、es3.4 正规表达式 用正规表达式描述单词，把它转换成识别装置-有限自动机。3.4 .1正规表达式与单词 一.正规表达式的定义 二.正规表达式的代数性质 三.正规定义式 四.例示，用正规定义式描述单词3.4 .2 正规表达式与有限自动机的等价性 L( r )=L(m)Compiler Construction Principles一. 正规表达式的定义 是字母表 正规表达式 正规表达式表达的语言 1. ， ， 2. a , a a 3. 若 r, s L( r ) , L(s) 则 ( a ) (r)(s) L( r ) L(s) ( b ) (r)(s) L( r ) L(s) ( c )

28、 ( r )* ( L( r )* ( d ) ( r ) L( r )Compiler Construction Principles注：（1）正规表达式描述的集合称作正规集（正规表达式的计算描述如何构造正规集）。（2）“*”，连接，“”运算左结合，优先级由高到低。例：=A,B,Z,a,b,z,0,1,9 A B. Z a b. z L( A)L( B)L( Z) L( a) L( b). L(z) = A,B,Z,a,b,z 0 1 . . 9 L(0) L(1) . L(9)= 0,1,9Compiler Construction Principles ( A B. Z a b. z)

29、( A B. Z a b. z) (0 1 . . 9)* A,B,Z,a,b,z(A,B,Z,a,b,z 0,1,9)* 标识符例3.3 =a,b (a) a b a,b (b) (a b )(a b ) aa,ab,ba,bb ( c) a* ,a,aa,aaa,aaaa, (d) (a b)* (,a,b,aa,ab,ba,bb,aaa,. (e) a ab*Compiler Construction Principles 恒等式 说明 rs=sr“”是可交换的 r(st)=(rs)t “”是可结合的 r(st)=(rs)t连接是可结合的 r(st)=rs rt(st)r=srtr 分配

30、律r=r r=r对连接，是单位元素 r*=(r)*“*”和之间的关系 r*=r*“*”是幂等的二.正规表达式的代数性质Compiler Construction Principles正闭包r+, 表达的语言 (L( r )+(L( r )+=(L( r )1 (L( r )2 (L( r )3 r*=r+ r+= r r*三.正规定义式 给正规表达式命名，引用。 ，序列： d1r1 d2 r2 . dnr n其中di表示不同的名子，每一个ri是 d1,d2,di-1上的正规表达式。 正规定义式和产生式的区别。Compiler Construction Principles四.例示， 用正规定义

31、式描述单词例3.4 Pascal标识符和无符号实数 letter(letterdigit)* letterA B . Z a b . z digit 0 1 . 9 id letter(letterdigit)*(digit)+(.(digit)+ )(E(+ - )(digit)+) ) digits digit(digit)* fraction digits exponent ( E(+ - )digits) num digits fraction exponent Compiler Construction Principles3.4.2 正规表达式与有限自动机的等价性 单词结构用正规表

32、达式描述，用机械的方法（程序），把正规表达式变换成等价的有限自动机。定理3.2 设r是上一个正规表达式，则存在一个FA m接受L( r )。反之亦然。证 对正规表达式r的运算数目作归纳。设r具有零个运算，则或r=或r= 或r=a q0q0q1q0q1ar=r= r=aCompiler Construction Principles设结论对少于i(i1)个运算的正规表达式r成立。当r有i个运算时，有三种情况： 情况1 r=r1r2 情况2 r=r1r2 情况3 r=r1* 有 m1=(1,Q1,q1,F!,1), m2=(2,Q2,q2,F2,2) 且L(m1)=L( r 1), L(m2)=L

33、(r2) ，由m1和m2构造m,使得 L(m)=L( r ).构造方法图示如下：q0q1f1f2q2f0m2m1r=r1r2Compiler Construction Principlesq0q1f1q2f0m2m1f2q1f1r=r1r2r=r1* 上述证明方法，是对于一个正规表达式r,构造一个FA m,且L(m)=L( r )的算法,但假定知道r的计算顺序。 正规表达式r的语法是上下文无关文法。Compiler Construction Principles例3.5构造与下列正规式 ( c) r=01*1 等价的有限自动机。语法树如左下图。*011q0q10q2q31q2q3q5q41Co

34、mpiler Construction Principles01q0q1q6q71q2q5q4q0q1q4q2q3q3q6q7110q8q5q9Compiler Construction Principles 对于上任一NFA m，能构造上一个正规表达式r，使得L( r )=L(m)。 把转换图的概念拓广，每条弧上可以用一个正规式标记。首先，在m的转换图上加进x,y两个结。从x用弧连接到m的所有初态结点，从m的所有接受态结点用弧连接到y，从而构成一个新的NFA m，L(m)=L(m)。下面，逐步消去NFA m中的状态结点，直至剩下x,y为止。在消结的过程中，逐步用正规式标记弧。消结的过程是直观

35、的，只需反复使用下面的替换规则。Compiler Construction Principlesabcacacacabcacr1r2r2r2r1r1r3r1r2r1r2r1r2*r3替换规则代之以代之以代之以Compiler Construction Principles3.5 正规文法与有限自动机(FA)的等价性 L(G)=L(m)定理3.3 对于每一个右线性正规文法或左 线性正规文法G，都存在一个FA m，使 L(m)=L(G)证 给定右线性正规文法G=(VT,VN,S,P),设f VN ，令m=(VT ,Q, S, F, ), 其中，F= fQ= VNf, 转移函数 定义如下： (a)

36、Aa, (A,a)=f (b) A aA1aA2 . aAn (A,a)= A1,A2 ,. ,An Compiler Construction Principles 给定左线性正规文法G=(VT, VN, S, P), 设q0VN ，令m=(VT ,Q, q0 ,S , ), 其中，Q= VN q0 , 转移函数 定义如下： (a) Aa, (q0,a)=A (b) A1 A,a, A2Aa , An Aa (A,a)= A1, A2 ,. , A n定理3.4 对于每一个DFA m，都存在一个右 线性正规文法G和一个左线性正规文法G， 使L(m)=L(G)=L(G)。证 设m=(, VN

37、, S,F, ),右线性正规文法G的构造方法如下：Compiler Construction Principles若sF, G=(,V N ,S,P), P的定义如下：对任何a 及A,B VN, 若有(A,a)=B, 则 (a) B F, A aB (b) B F A aaB若s F, S0 V N , S0 S 构造左线性正规文法， P的定义如下：对任何a 及A1,A2 VN, 有(A1,a)=A2, 则 (a) A1是初态， A2 a (b) A1不是初态, A2 A1aCompiler Construction Principles例3.6 DFA m 右线性正规文法G NFA m左线性

38、正规文法G ADCB0,1111000A00B 1DB 0D 1CC 0 0B 1DD 0D 1DCompiler Construction PrinciplesADCB0,1111000S0C0B 0C0C B 1D 1B0 C1 D0 D1f00NFA m左线性正规文法Compiler Construction Principles3.6词法分析程序的自动构造工具LEX简介一.原理 单词的结构用正规式描述 正规式 NFA DFA min DFA二.用LEX建立词法分析程序的过程LEX编译器LEX源程序lex.1Lex.yy.cCompiler Construction Principles

39、C编译器Lex.yy.ca.outa.out输入流单词序列三.lex源程序 lex源程序由三部分组成Compiler Construction Principles声明%翻译规则%辅助过程声明包括变量，显明常量和正规定义式。 翻译规则的形式为： p1 动作1 p2 动作2 p n 动作nCompiler Construction Principles 每个pi是正规定义式的名子，每个动作i是正规定义式pi识别某类单词时，词法分析器应执行动作的程序段。用C书写。 辅助过程是动作需要的，这些过程用C书写，可以分别编译。 词法分析器返回给语法分析器一个单词, ,把单词的属性值存放于全程变量yylva

40、l中。Compiler Construction Principles3.5 对于下列各语言，分别写出它们的正规 表达式： (a) 字母表a,b,c上的串，其中第一个a先于 第一个b。 (b) 具有偶数个a的字母表a,b,c上的串。 ( c ) 0，1上的串，该串看成二进制是4的 倍 数。 (d) 0，1上不含子串011的串。 (e) 0，1 上的串，有偶数个0和奇数个1。 (f) 英文字母组成的所有符号串，且顺序 包 含五个元音字母。Compiler Construction Principles3.7 构造等价于下列正规表达式的NFA (a) ab|(a|bb)a*b (b) (a|b)*

41、|(bb)*Compiler Construction Principles识别识别Pl0单词的单词的FACompiler Construction PrinciplesNFA的确定化的确定化 More exampleCompiler Construction PrinciplesCompiler Construction PrinciplesCompiler Construction PrinciplesCompiler Construction PrinciplesCompiler Construction Principles DFA的最小化算法的最小化算法英文描述英文描述1. Construct an