编译原理_第1~5章习题课课件

1、编编 译译 原原 理理 chapter15习习 题题 chapter1 1、何谓源程序、目标程序、翻译程序、编译程序、何谓源程序、目标程序、翻译程序、编译程序 和解释程序？它们之间可能有何种关系？和解释程序？它们之间可能有何种关系？ 源程序：用源语言编写的程序。源程序：用源语言编写的程序。 目标程序：源程序经翻译程序过加工处理后生成的程序。目标程序：源程序经翻译程序过加工处理后生成的程序。 翻译程序：将源程序转换为与其逻辑上等价的目标程序。翻译程序：将源程序转换为与其逻辑上等价的目标程序。 编译程序：编译程序： 源语言为高级语言，目标语言为汇编语言或机源语言为高级语言，目标语言为汇编语言或机

2、器语言的翻译程序。器语言的翻译程序。 解释程序：解释程序： 源语言程序作为输入，但不产生目标程序，而源语言程序作为输入，但不产生目标程序，而 是边解释边执行源程序本身。是边解释边执行源程序本身。 先翻译后执行先翻译后执行 边解释边执行边解释边执行 执行速度快执行速度快 有利于程序的调试有利于程序的调试 多次运算多次运算 1次运算次运算 编编 译译 原原 理理 chapter15习习 题题 2、一个典型的编译系统通常由有哪些部分组成？、一个典型的编译系统通常由有哪些部分组成？ 各部分的主要功能是什么？各部分的主要功能是什么？ chapter1 编译系统编译系统 编译程序编译程序 语法分析语法分析

3、 语义分析与中间代码生成语义分析与中间代码生成 优化优化 目标代码生成目标代码生成 运行系统运行系统 词法分析词法分析 编编 译译 原原 理理 chapter15习习 题题 语法分析语法分析(Syntax Analysis)： 在词法分析的基础上将单词序列分解成各类语法在词法分析的基础上将单词序列分解成各类语法 短语，如短语，如“程序程序”，“语句语句”，“表达式表达式”等等。等等。 语义分析语义分析(Syntactic Analysis)： 语义分析是在语法分析程序确定出语法短语后，审语义分析是在语法分析程序确定出语法短语后，审 查有无语义错误，并为代码生成阶段收集类型信息。查有无语义错误，

4、并为代码生成阶段收集类型信息。 chapter1 词法分析词法分析(Lexical Analysis)： 从左到右从左到右一个字符一个字符的读入源程序，对一个字符一个字符的读入源程序，对 构成源程序的字符串进行扫描和分解，从而构成源程序的字符串进行扫描和分解，从而识别出识别出 一个个单词一个个单词（也称单词符号或简称符号）。（也称单词符号或简称符号）。 编编 译译 原原 理理 chapter15习习 题题 chapter1 代码优化代码优化(Optimization of code)： 为了使生成的目标代码更为高效，可以对产生的中为了使生成的目标代码更为高效，可以对产生的中 间代码进行变换或进

5、行改造，这就是代码的优化。间代码进行变换或进行改造，这就是代码的优化。 代码生成代码生成(Generation of code)： 目标代码生成是编译器的最后一个阶段。在生成目目标代码生成是编译器的最后一个阶段。在生成目 标代码时要考虑以下几个问题：标代码时要考虑以下几个问题：计算机的系统结构、指计算机的系统结构、指 令系统、寄存器的分配以及内存的组织令系统、寄存器的分配以及内存的组织等。等。 中间代码生成中间代码生成(Generation of intermediate code)： 完成语法分析和语义处理工作后，编译程序将源程完成语法分析和语义处理工作后，编译程序将源程 序变成一种内部表示

6、形式，这种内部表示形式叫做中间序变成一种内部表示形式，这种内部表示形式叫做中间 语言或称中间代码，它是一种结构简单、含义明确的记语言或称中间代码，它是一种结构简单、含义明确的记 号系统。号系统。 编编 译译 原原 理理 chapter15习习 题题 chapter2 1.写出写出C语言和语言和Java语言的输入字母表。语言的输入字母表。 C语言：语言：09数字，大小写英文字母，键盘上可见的字符数字，大小写英文字母，键盘上可见的字符 Java语言：语言：Unicode可以包括的所有字符。可以包括的所有字符。 6.文法文法G6为为: N D|ND D 0|1|2|3|4|5|6|7|8|9 （1）

7、 G6的语言是什么的语言是什么? G6的语言是：的语言是： 09的数字组成的任意的数字组成的任意非空非空串串 L(G6)=x|x0,1,2,3,4,5,6,7,8,9+ （2）给出句子）给出句子0127、34和和568的最左和最右推导。的最左和最右推导。 编编 译译 原原 理理 chapter15习习 题题 7、 写一文法，使其语言是写一文法，使其语言是奇数集奇数集。 要求：不以要求：不以0打头。打头。 复杂的情况复杂的情况: :分三部分分三部分 末尾：以末尾：以1|3|5|7|9结尾结尾 ( (一位一位):):D 1|3|5|7|9 开头：除了开头：除了0的任意数字的任意数字 中间部分：空或

8、者任意数字串中间部分：空或者任意数字串 D1|3|5|7|9 CCA| A0|B 所以题目要求的文法所以题目要求的文法GNGN可以写成：可以写成： N BCD|D D 1|3|5|7|9 B 2|4|6|8|D C CA | A 0 | B B2|4|6|8|D 编编 译译 原原 理理 chapter15习习 题题 9、证明文法、证明文法: S iSeS | iS | i 是二义的。是二义的。 二义性的含义二义性的含义: :如果文法存在如果文法存在某个句子某个句子对应两棵以上对应两棵以上 不同的语法树，或者两种以上不同的最不同的语法树，或者两种以上不同的最 左左/ /右推导，则称这个文法是二义

9、的。右推导，则称这个文法是二义的。 首先：找到此文法对应的一个首先：找到此文法对应的一个句子句子 iiiei 其次：构造与之对应的其次：构造与之对应的两棵两棵语法树语法树 S i S e S i S i i S i S i S e S i i 结论：因为该文法存在句子结论：因为该文法存在句子iiieiiiiei对应两棵对应两棵 不同的语法树，因而该文法是二义的。不同的语法树，因而该文法是二义的。 编编 译译 原原 理理 chapter15习习 题题 11、给出下面语言的相应文法、给出下面语言的相应文法 L1=anbnci| n1,i0 G1(S): SAB AaAb|ab BcB| 从从n，i

10、的不同取值来把的不同取值来把L1分成两部分：分成两部分： A aAb | ab 前半部分是前半部分是 an bn ： 后半部分是后半部分是 c i ：B Bc | 所以整个文法所以整个文法G1S可以写为：可以写为： 编编 译译 原原 理理 chapter15习习 题题 L2=aibncn| n1,i0 G2(S): SAB AaA| BbBc|bc L3=anbnambm| m,n0 G3(S): SAB AaAb| BaBb| 编编 译译 原原 理理 chapter15习习 题题 L4=1n 0m 1m 0n| n,m0 可以看成是两部分：可以看成是两部分： 剩下两边的部分就是：剩下两边的部

11、分就是： S 1S0 中间部分是中间部分是 0m 1m ： A 0A1 | 所以所以G4S可以写为：可以写为： S 1S0 | A A 0A1 | | A 编编 译译 原原 理理 chapter15习习 题题 chapter3 7.构造下列正规式相应的构造下列正规式相应的DFA。 步骤步骤: : . .根据正规式根据正规式画出画出对应的对应的状态转换图状态转换图; ; . .根据状态转换图画出对应的根据状态转换图画出对应的状态转换矩阵状态转换矩阵; ; . .根据状态转换矩阵得到根据状态转换矩阵得到重命名后的状态转换矩阵重命名后的状态转换矩阵; ; . .根据重命名后的状态转换矩阵得出最后的根

12、据重命名后的状态转换矩阵得出最后的DFA. . 问题：将状态转换图与问题：将状态转换图与DFA混淆。混淆。 编编 译译 原原 理理 chapter15习习 题题 1(0|1)*101 .状态转换图状态转换图 a b a d b 1(0|1)*101 a 1 (0|1)* 101 d c ef 1 0 1 1 01 g g g 编编 译译 原原 理理 chapter15习习 题题 .状态转换矩阵状态转换矩阵 II0 I1 ab,c,d b,c,dc,dc,d,e c,dc,dc,d,e c,d,ec,d,fc,d,e c,d,fc,dc,d,e,g c,d,e,gc,d,fc,d,e 1 ab

13、d c ef 1 0 101 g 编编 译译 原原 理理 chapter15习习 题题 I I0I1 a b,c,d b,c,d c,d c,d,e c,dc,dc,d,e c,d,ec,d,fc,d,e c,d,fc,dc,d,e,g c,d,e,gc,d,fc,d,e . .重命名后的状态转换矩阵重命名后的状态转换矩阵 S01 A(始态始态)B BCD C C D D E D E C F(终态终态) F(终态终态)ED AB 1 0C 1D 0 1 0 E 1 0 1 01 F .DFA 编编 译译 原原 理理 chapter15习习 题题 1(1010*|1(010)*1)*0 ab d

14、 c 1 0 e 0 1 0 1 f gh i 0 1 11 0 j k lm n .状态转换图状态转换图 编编 译译 原原 理理 chapter15习习 题题 .状态转换矩阵状态转换矩阵 II 0I 1 01,2,3 1,2,345,9,10,11 5,9,10,116,122,3 6,122,3,7,8,13 2,345,9,10,11 2,3,7,8,132,3,4,8,10,115,9,10,11 2,3,4,8,10,112,3,4,8,122,3,5,9,10,11 2,3,4,8,122,3,4,85,9,10,11,13 2,3,5,9,10,114,6,122,3,5,9,1

15、0,11 2,3,4,82,3,4,85,9,10,11 5,9,10,11,136,10,11,122,3 4,6,122,3,7,8,13 6,10,11,12122,3,7,8,13 1213 1310,11 10,11122,3 编编 译译 原原 理理 chapter15习习 题题 . .重命名后的状态转换矩阵重命名后的状态转换矩阵 II 0I 1 12 234 456 57 634 784 8910 91112 101310 11114 12146 137 14157 1516 1617 17156 .DFA 编编 译译 原原 理理 chapter15习习 题题 8、给出下面正规表达

16、式、给出下面正规表达式 （1）以）以01结尾的二进制数串。结尾的二进制数串。 (0 | 1)*01 （2）能被）能被5整除的十进制数。整除的十进制数。 0 | 5(0 |5)| (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* （4）英文字母组成的所有符号串，要求符号串中的）英文字母组成的所有符号串，要求符号串中的 字母按字典序排列。字母按字典序排列。 (A | a)* (B | b)* (C | c)* (Z | z)* 编编 译译 原原 理理 chapter15习习 题题 9、对下面情况给出、对下面情况给出DFA及正规表达式：及正规表达式： （1）0,1上

17、的含有子串上的含有子串010的所有串。的所有串。 正规式：正规式：(0 | 1)* 010 (0 | 1)* DFA做法同第做法同第7题。题。 （2） 0,1上不含子串上不含子串010的所有串。的所有串。 正规式：正规式：1*(0|11*1)* 1*0*1*(0 | 11)*(0 | 1)1*( 0 | 11)*1* 编编 译译 原原 理理 chapter15习习 题题 12、将图、将图3.18的的(a)和和(b)分别确定化和最少化。分别确定化和最少化。 (a) a a a,b 1 0 .状态转换矩阵状态转换矩阵 I Ia Ib 0 0,11 1 0,10,11 0 . .重命名后的状态转换矩

18、阵重命名后的状态转换矩阵 I Ia Ib 0 12 2 112 0 0 a 2b a b a .DFA .最小化最小化 0=(0,1,2) 1 0,1a=1 0,1b=2 因此，不能再分因此，不能再分 0 2 b a a 编编 译译 原原 理理 chapter15习习 题题 023 145 a a a a b b b b b b a a (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 所以所以

19、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 023 a a bb b a 编编 译译 原原 理理 chapter15习习 题题 14、构造一个、构造一个DFA，它接受，它接受=0,1上所有满足如下上所有满足如下 条件的字符串：每个条件的字符串：每个1都有都有0直接跟在右边。直接跟在右边。 思路：先写出满足条件的正规式，由正规式构造思路：先写出满足条件的正规式，由正规式构造 NFA，再把，再把NFA确定化和最小化。确定化和最小化。 满足条件的正规式：满足条件的正规

20、式：(0|10)* 正规式不同，则构造的正规式不同，则构造的NFA及确定化的及确定化的DFA可能可能 不同，但最小化的不同，但最小化的DFA是唯一的。是唯一的。 0 2 1 0 0 最小化后的最小化后的DFA: 编编 译译 原原 理理 chapter15习习 题题 15、给定右线性文法、给定右线性文法G：求一个与：求一个与G等价的左线性文法。等价的左线性文法。 S 0S | 1S | 1A | 0B A 1C | 1 B 0C | 0 C 0C | 1C | 0 | 1 S A B CZ 0 0 11 1 0 0 0 1 1 0 1 GZ: Z Z0|Z1|B0|A1 B A0 | 0 A B

21、1 | 1 确定化、最小化后的确定化、最小化后的DFA为：为： S B 0 A 1 10Z 0 1 0,1 编编 译译 原原 理理 chapter15习习 题题 补充：构造一右线性文法，使它与如下文法等价：补充：构造一右线性文法，使它与如下文法等价： SAB AUT Ua|aU Tb|bT Bc|cB 并根据所得右线性文法，构造出相应的状态转换图。并根据所得右线性文法，构造出相应的状态转换图。 思路：思路： 先写出原文法所描述的语言先写出原文法所描述的语言 L(G)=ambnck|m,n,k1 GS: S aS|aB B bB|bC C cC|c a S a C b c B b c T 编编

22、译译 原原 理理 chapter15习习 题题 chapter4 1、考虑下面文法、考虑下面文法G1：S a | | （T） T T，S | S （1）消去）消去G1的左递归；的左递归； S a | | （T） T ST T ，S T | （2）经改写后的文法是否是）经改写后的文法是否是LL(1)文法，给出预测分析表。文法，给出预测分析表。 经改写后的文法满足经改写后的文法满足3个条件，所以是个条件，所以是LL(1)的的 编编 译译 原原 理理 chapter15习习 题题 预测分析表构造算法预测分析表构造算法: 1.对文法中的每个产生式对文法中的每个产生式A 执行第二步和第三步执行第二步和第

23、三步; 2.对每个终结符对每个终结符a FIRST( ),把把A a加到加到MA,a中中; S a; S ; S (T); T ST; T ,ST T FTRST（a）=a FIRST（）= FIRST（T）=（ FIRST（ST）=a，（，（ FIRST（，（，ST）=，FIRST（）= a（，）# S T T S aS S (T) T STT STT ST T ,ST 3.若若 FIRST( ),则对于任何则对于任何b FOLLOW(A)把把A 加至加至MA,b中中 FOLLOW(T)=FOLLOW(T)=) T 编编 译译 原原 理理 chapter15习习 题题P81.2.对文法对文法

24、G: E TE E +E| T FT T T| F PF F *F| P (E)|a|b| FIRST(E)=FIRST(T) =FIRST(F) =FIRST(P) =(,a,b, FIRST(E) =+, FIRST(T) =FIRST(T) = (,a,b, , FIRST(F) =*, FOLLOW(E) =#,)FOLLOW(E) =FOLLOW(E)= #,) FOLLOW(T) =FIRST(E) FOLLOW(E)= +,#,) FOLLOW(T) =FOLLOW(T)= +,#,) FOLLOW(F) =FIRST(T) FOLLOW(T)=(,a,b, , +,#,) FO

25、LLOWF) =FOLLOW(F) =(,a,b, , +,#,) FOLLOW(P) =FIRST(F) FOLLOW(F)= *, (,a,b, , +,#,) (ab+*)# E E T T F F P E TE E TE E TE E TE E +EE E T FT T FT T FT T FT T T T T T T T T T T T F PF F PF F PF F PF F F F F F F * FF F P(E) Pa Pb P 编编 译译 原原 理理 chapter15习习 题题 补充题：有文法：补充题：有文法： E TE E ATE | T FT T MFT | F （

26、E）| i A + | - M * | / （1）求）求First、Follow集，判断是否是集，判断是否是LL（1）文法？）文法？ （2）若是构造）若是构造LL（1）分析表？）分析表？ （3）简述）简述LL（1）分析器的工作原理。）分析器的工作原理。 编编 译译 原原 理理 chapter15习习 题题 E TE E ATE | T FT T MFT | F （E）| i A + | - M * | / FIRST(M)=* ， / FIRST(A)=+，- FIRST(F)=(， i FIRST(T)=* ，/ ， FIRST(T)=(， i) FIRST(E)=+ ，- ， FIRST(

27、E)=(， iFOLLOW(E)=# ，) FOLLOW(E)=# ，) FOLLOW(T)= + ，- ，# ，) FOLLOW(T)= + ，- ，# ，) FOLLOW(F)=* ，/ ， + ，- ，# ，) FOLLOW(A)= (， i FOLLOW(M)= (， i E E TE E TE E E ATEE ATE E E TT FT T FT T T-T T MFTT MFT T T FF i F （E） A A +A - M M *M / i+-*/（）# 编编 译译 原原 理理 chapter15习习 题题 chapter5 1、令文法、令文法G1为：为： EE+T | T

28、 TT*F | F F(E) | i 证明证明E+T*F是它的一个句型，指出这个句型的所有是它的一个句型，指出这个句型的所有 短语、直接短语和句柄。短语、直接短语和句柄。 E E +T T*F T*F是句型是句型E+T*F相对于相对于T的短语的短语 E+T*F句型句型E+T*F相对于相对于E的短语的短语 T*F是句型是句型E+T*F相对于相对于T的直接短语的直接短语 T*F是句柄是句柄 编编 译译 原原 理理 chapter15习习 题题 2、考虑下面的表格结构文法、考虑下面的表格结构文法G2： Sa | | (T) T T,S | S （1）给出）给出(a,(a,a)和和(a,a),(a),

29、a)的最左和最右推导。的最左和最右推导。 (a,(a,a)的最的最左左推导：推导： S (T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a) (a,a),(a),a)的最的最左左推导：推导： S (T) (T,S) (S,S) (T),S) (T,S),S) (T,S,S),S) (S,S,S),S) (T,S),S,S),S) (S,S),S,S),S) (a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),a),S) (a,a),a),a) 编编 译译 原原 理理 chapte

30、r15习习 题题 (a,a),(a),a)的最右推导：的最右推导： S (T) (T,S) (S,S) (S,a) (T),a) (T,S,S),S) (S,S,S),S) (T,S),S,S),S) (S,S),S,S),S) (a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),a),S) (a,a),a),a) (a,(a,a)的最右推导：的最右推导： S (T) (T,S) (T,(T) (T,(T,S) (T,(T,a) (T,(S,a) (T,(a,a) (S,(a,a) (a,(a,a) 编编 译译 原原 理理 chapter15习习 题题

31、2）指出）指出(a,a),(a),a)的规范归约及每一步的句柄。的规范归约及每一步的句柄。 S (T) T,S a (T) S T,S T,S(T) S a (T) S T,S a S a 句型句型句柄句柄归约规则归约规则 (a,a),(a),a)aSa (S,a),(a),a) STS (T,a),(a),a)aSa (T,S),(a),a) T,STT , S (T),(a),a)(T)S(T) (S,(a),a)S TS (T,(a),a) S (T,S,(a),a) T,STT , S (T,(a),a)aSa (T,(S),a)STS (T,(T),a)(T)S(T) (T, S),

32、a)T,STT , S (T),a)TS(T ) (S,a)STS (T,a)aSa (T,S) T,STT , S (T)(T)S(T) S 编编 译译 原原 理理 chapter15习习 题题 根据这个规范规约，给出根据这个规范规约，给出“移进移进归约归约”的过程，的过程， 并给出它的语法树的自下而上的构造过程。并给出它的语法树的自下而上的构造过程。 # 符号栈符号栈 输入串：输入串： ( ( ( a , a ) , , ( a ) ) , a ) # S (T) T,S a (T) S T,S T,S(T) S a (T) S T,S a S a ( ( ( a S , T a S S ) T , S T ( a S T ) S ) S T , a S T ) S 归约规则归约规则句柄句柄 aSa STS aSa T,STT , S (T)S(T) S TS S T,STT , S 编编 译译 原原 理理 chapter15习习 题题 3、(1)计算练习计算练习2文法文法G2的的FIRST