编译原理例题与习题解答.ppt

1、1,例题与习题解答第二章,2,回顾,程序语言的定义 一个程序语言是一个记号系统,它主要由以下方面定义： 语法 语义,语法,语义,3,语法=词法规则+语法规则,词法规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。 描述工具：正规式和有限自动机理论 语法规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、子程序、过程、函数、程序等; 描述工具：上下文无关文法,回顾,4,标识符与名字,标识符：以字母开头的，由字母数字组成的字符串。 标识符与名字两者有本质区别： 标识符是语法概念 名字有确切的意义和属性,回顾,5,上下文无关文

2、法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。,回顾,6,假定G是一个文法，S是它的开始符号。如果S ，则称是一个句型。仅含终结符号的句型是一个句子。 文法G所产生的句子的全体是一个语言，将它记为L(G) L(G) = | S 中间部分可出现任意多位数字09, 每一位用非终结符D表示; 最低位只出现1,3,5,7,9, 用A表示。 由于中间部分可任意

3、位,故需另引入一 非终结符M,它包括最高位和中间部分。,14,15,解: 奇数集文法GN为: G=(0,1,9,N,A,M,B,D,N,) : NA | MA MB | MD A1 | 3 | 5 | 7 | 9 B1|2|3|4|5|6|7|8|9 D0 | B,8. 令文法为 E T|E+T|E-T T F|T*F|T/F F (E)|i,(1) 给出 i+i*i、i*(i+i)的最左推导和最右推导。,解：此处仅以 i*(i+i) 为例给出答案,最左推导 E T T*F F*F i*F i*(E) i*(E+T) i*(T+T) i*(F+T) i*(i+T) i*(i+F ) i*(i+

4、i),最右推导 E T T*F T*(E) T*(E+T) T*(E+F) T*(E+i) T*(T+i) T*(F+i) T*(i+i) F*(i+i) i*(i+i),8. 令文法为 E T|E+T|E-T T F|T*F|T/F F (E)|i,i-i-i 的语法树,(2) 给出 i+i+i、i+i*i和i-i-i的语法树。,i+i+i 的语法树,i+i*i 的语法树,注意：树枝和符号均不可随意增减！,18,9、证明文法: S iSeS | iS | i 是二义的。,二义性的含义:,如果文法存在某个句子对应两棵以上 不同的语法树，或者两种以上不同的最 左/右推导，则称这个文法是二义的。,

5、首先：找到此文法对应的一个句子 iiiei,其次：构造与之对应的两棵语法树,结论：因为该文法存在句子iiiei对应两棵 不同的语法树，因而该文法是二义的。,19,10. 把下面文法改写成无二义性的文法 S-SS | (S) | ( ) 解答： S- TS | T T-(S) | ( ),20,L2=aibncn| n1,i0,G2(S): SAB AaA| BbBc|bc,L3=anbnambm| m,n0,G3(S): SAB AaAb| BaBb|,11、给出下面语言的相应文法,21,L4=1n 0m 1m 0n| n,m0,可以看成是两部分：,剩下两边的部分就是：,S 1S0,中间部分是

6、 0m 1m ：,A 0A1 | ,所以G4S可以写为：,S 1S0 | A A 0A1 |,| A,22,例题与习题解答第三章,23,1. 假定NFA M=，我们对M的状态转换图进行以下改造： 1) 引进新的初态结点X和终态结点Y，X,YS， 从X到S0中任意状态结点连一条箭弧， 从F中任意状态结点连一条箭弧到Y。 2) 对M的状态转换图进一步施行替换，其中k是新引入的状态。,非确定有限自动机状态图的改造,24,代之为,代之为,代之为,按下面的三条规则对V进行分裂:,逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M，显然L(M)=L(M),25,确定有限自动机的确定化

7、采用子集法,设I是M的状态集的一个子集，定义I的-闭包-closure(I)为: i) 若sI，则s-closure(I)； ii) 若sI，则从s出发经过任意条弧而能到达的任何状态s都属于-closure(I) 即： -closure(I)=Is|从某个sI出发经过任意条弧能到达s,26,设a是中的一个字符，定义 Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。,把确定化的过程: 不失一般性，设字母表只包含两个a和b，我们构造一张表:,27,对一个DFA M最少化的基本思想: 把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，

8、而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。,DFA M最少化,28,具体做法: 对M的状态集进行划分 首先，把S划分为终态和非终态两个子集，形成基本划分。 假定到某个时候，已含m个子集，记为=I(1)，I(2)，I(m)，检查中的每个子集看是否能进一步划分: 对某个I(i)，令I(i)=s1,s2, ,sk，若存在一个输入字符a使得Ia(i) 不会包含在现行的某个子集I(j)中，则至少应把I(i)分为两个部分。,29,例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行中的两个不同子集，说明有一个字， t1读出后到达终态，而t2读出后不

9、能到达终态，或者反之，那么对于字a ， s1读出a后到达终态，而s2读出a不能到达终态，或者反之，所以s1和s2不等价。,s1,t1,a,s2,t2,a,i,j,30,例题3.1,给出下面描述的正规表达式 以01结尾的二进制数串 能被5正除的十进制整数 包含奇数个1或者奇数个0的二进制数串,31,例题3.2,构造下面正规式相应的DFA 1(0|1)*101,步骤:,.根据正规式画出对应的状态转换图;,.根据状态转换图画出对应的状态转换矩阵;,.根据状态转换矩阵得到重命名后的状态转换矩阵;,.根据重命名后的状态转换矩阵得出最后的DFA.,32,1(0|1)*101,.状态转换图,a,b,a,d,

10、b,1(0|1)*101,a,1,(0|1)*,101,d,c,e,f,1,0,1,1,0,1,33,.状态转换矩阵,I,I0,I1,a,b,c,d,b,c,d,c,d,c,d,e,c,d,c,d,c,d,e,c,d,e,c,d,f,c,d,e,c,d,f,c,d,c,d,e,g,c,d,e,g,c,d,f,c,d,e,34,.重命名后的状态转换矩阵,S,0,1,A(始态),B,B,C,D,C,C,D,D,E,D,E,C,F(终态),F(终态),E,D,A,B,1,0,C,1,D,0,1,0,E,1,0,1,0,1,.DFA,35,例题3.3,设M=(x,y, a,b, f, x, y)，其中

11、f定义如下： f(x,a)=x, y f(x,b)=y f(y,a)= f(y,b)=x,y 请构造对应的确定有限自动机。,36,【解答】 对照自动机的定义，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。 先画出NFA M相应的状态图，,37,用子集法构造状态转换矩阵,38,重命名后的状态转换矩阵,39,40,1(1010*|1(010)*1)*0,a,b,d,c,1,0,0,1,0,1,f,g,h,i,0,1,1,1,0,j,k,l,m,n,.状态转换图,P64-7. 构造下列正规式相应的DFA。,41,.状态转换矩阵,42,.重命名后的状态转换矩阵,.D

12、FA,43,8、给出下面正规表达式,（4）英文字母组成的所有符号串，要求符号串中的 字母按字典序排列。,(A | a)* (B | b)* (C | c)* (Z | z)*,（5）没有重复出现的数字的数字符号串的全体。,令 ri = i | , i=0,1,2,.,9 R0|R1|R2|.|R9记为 P(0,1,2.,9)表示0,1,2.,9的全排列,44,（6）最多有一个重复出现的数字的数字符号串全体,(7) 不包含子串abb 的由a和b组成的符号串的全体,b*(a|ab)*,45,12、将图3.18的(a)和(b)分别确定化和最少化。,(a),.状态转换矩阵,0,0,1,1,1,0,1,

13、0,1,1,0,.重命名后的状态转换矩阵,0,1,2,2,1,1,2,0,a,2,b,a,b,a,.DFA,.最小化,0=(0,1,2),0,1a=1,0,1b=2,因此，不能再分,2,b,a,a,46,(b),这道题实质上已经是确定化了的，所以我们只需最小化,：2，3，4，5 0，1,2，3，4，5a=0，1，3，5,分属两区，所以分为2，4 3，5,0，1a=1 0，1b=2，4,所以 0，1等价,2，4a=0，1 2，4b=3，5,所以2，4等价,3，5a=3，5 3，5b=2，4,所以3，5等价,所以分为 0，1 2，4 3，5,47,P64-14. 构造一个DFA，它接受0,1上所有

14、满足如下条件的字符串：每个1都有0直接跟在右边。,思路：先写出满足条件的正规式，由正规式构造NFA，再把NFA确定化和最小化。,48,(1)先写出满足条件的正规式正规式: (10|0)* (2) NFA: 确定化:,DFA:,49,DFA:,DFA:(最简化),50,例题与习题解答第四章,51,.,语法分析器在编译程序中的地位,52,自上而下分析法(Top-down),基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析

15、程序 优点：直观、简单和宜于手工实现。,53,困难和难点: 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。 出错时，不得不“回溯”。 文法左递归问题。一个文法是含有左递归的，如果存在非终结符P 含有左递归的文法将使自上而下的分析陷入无限循环。,54,左递归的消除,直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为 PP | 其中不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式： PP PP|,左递归变右递归,55,间接左递归 例如文法G(S): SQc|c QRb|b RSa|a 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSab

16、c 潜在左递归 即形如：N-N 而 ,56,消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 将Pj代入Pi的产生式（若可代入的话） 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,57,消除回溯、提左因子,为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。,58,令G

17、是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：,特别是，若 ，则规定FIRST()。,如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 j FIRST(i)FIRST( j) 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。,59,如何把一个文法改造成任何非终结符的所有侯选式的首符集两两不相交？ 提取公共左因子: 假定关于A的规则是 A 1 | 2 | | n | 1 | 2 | | m (其中，每个 不以开头) 那么，可以把这些规则改写成 AA |

18、1 | 2 | | m A 1 | 2 | | n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。,60,构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A 1| 2| n 则 FIRST( i)FIRST( j) (ij) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含，则 FIRST(i)FOLLOW(A)= i=1,2,.,n 如果一个文法G满足以上条件，则称该文法G为LL(1)文法。,LL(1)文法,61,假定S是文法G的开始符号，对于G的任

19、何非终结符A，我们定义,特别是，若 ，则规定 FOLLOW(A),FOLLOW,提醒：要掌握构造First和Follow集合的方法,62,递归下降分析程序构造,在不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交条件下，构造一个不带回溯的自上而下分析程序，该分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。 这样的一个分析程序称为递归下降分析器。,63,预测分析程序,使用一张分析表和一个栈同样可实现递归下降分析，用这种方法实现的语法分析程序叫预测分析程序, a ,总控程序,预测分析表M,X #,输 出,栈,输入串,64,分析表MA，a的构造,构造FIRST()和FOLLOW

20、(A) 构造分析表MA，a,65,在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。 1. 对文法G的每个产生式A执行第2步和第3步； 2. 对每个终结符a FIRST()，把A加至MA，a中； 3. 若FIRST()，则对任何bFOLLOW(A)把A加至MA，b中。 4. 把所有无定义的MA，a标上“出错标志”。,66,总控程序根据现行栈顶符号X和当前输入符号a，执行下列三种动作之一: 1. 若Xa，则宣布分析成功，停止分析。 2. 若Xa ，则把X从STACK栈顶逐出，让a指向下一个输入符号。,67,3. 若X是一

21、个非终结符，则查看分析表M。 若MX，a中存放着关于X的一个产生式，把X逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为，则意味不推什么东西进栈)。 若MX，a中存放着“出错标志”，则调用出错诊察程序ERROR。,如：MX，a=XUVW,就用WVU（U在顶）替换栈顶的X作为输出； 如：MX，a=error，则调用error程序。,68,1.考虑下面文法G1: Sa|(T) TT，S|S (1) 消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。,解(1) 消左后的文法G1: Sa|(T) TST T ,ST|,练习解答,解(1) 不带回溯的递归子程

22、序: Sa|(T) Procedure S; Begin if sym=a or sym= then advance else if sym=( then begin advance; T; if sym=) then advance else error end else error End;,解(1) 不带回溯的递归子程序: TST Procedure T; Begin S; T; end;,解(1) 不带回溯的递归子程序: T,ST| procedure T; begin if sym=, then begin advance; S; T; end End;,(2) 经改写后的文法是否是

23、LL(1)的? 给出它的预测分析表。 消左后的文法G1 : Sa|(T) TST T ,ST|,因为G1 : 文法不含左递归; 对 Sa|(T) FIRST(a)=a, FIRST()=, FIRST( (T) )= ( , 集合互不相交且不含; 对 T,ST| FIRST( ,ST )= , , FIRST()=, 其交集为空。 但FIRST(T)=FIRST( ,ST ) FIRST()=，, 然而，FOLLOW(T)= ) FIRST(T)=，, ，两者 不相交。 所以，G1是LL(1)文法。,72,构造G1的预测分析表: 对Sa|(T) 对TST FIRST(a)=a FIRST(ST

24、)=a,( FIRST()= 对 T,ST| FIRST(T)=( FIRST(,ST)=, FOLLOW(T)=),73,2、对下面的文法G： ETE EE TFT TT FPF F*F P(E)ab （1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。 （2）证明这个文法是LL（1）的。 （3）构造它的预测分析表。 （4）构造它的递归下降分析程序。,74,解：（1）计算FIRST与FOLLOW集 FIRST(P)= ( , a , b , FIRST(F)= * , FIRST(F)=FIRST(P) = ( , a , b , FIRST(T)=FIRST(T)= ( , a

25、 , b , , FIRST(T)=FIRST(F) = ( , a , b , FIRST(E)= + , FIRST(E)=FIRST(T)= ( , a , b , FOLLOW(E)= ) , # FOLLOW(E)=FOLLOW(E)= ) , # FOLLOW(T)=FIRST(E) FOLLOW(E)=+, ) , # FOLLOW(T)=FOLLOW(T)=+, ) , # FOLLOW(F)=FIRST(T) FOLLOW(T)= (,a,b, , +, ) , # FOLLOW(F)=FOLLOW(F)=(, a , b , , +, ) , # FOLLOW(P)=FIR

26、ST(F) FOLLOW(F)=*,( ,a, b ,+ , ) ,# ,ETE EE TFT TT FPF F*F P(E)ab,75,76,（2）证明这个文法是LL（1）的。 对产生式P(E)ab，有 FIRST(E)FISRT(a) FIRST(b) FIRST()= 对产生式EE FIRST(+E) FOLLOW(E)= + ) , # = 对产生式TT FIRST(T) FOLLOW(T)= ( , a , b , +, ) , # = 对产生式F*F FIRST（*F) FOLLOW(F)= * (, a , b , , +, ) , # = 文法不含左递归。 综上 i,ii,ii

27、i 可知，文法G是LL（1）的。,ETE EE TFT TT FPF F*F P(E)ab,77,（3）构造预测分析表。,78,（1）设置过程advance为读下一个单词送全程变量 （2）设置过程error为错误处理程序,1. 主程序 Begin advance; E; End 2. E过程 Procedure E Begin T;E; end,（4）构造递归下降分析程序。,ETE EE TFT TT FPF F*F P(E)ab,79,3. E过程 Procedure E Begin if sym=+ then begin advance; E; end else if sym in #,) return else error,ETE EE TFT TT FPF F*F P(E)ab,80,4. T过程 Procedure T Begin F;T;