资源描述
编编 译译 原原 理理 chapter15习习题题chapter11、何谓源程序、目标程序、翻译程序、编译程序、何谓源程序、目标程序、翻译程序、编译程序 和解释程序？它们之间可能有何种关系？和解释程序？它们之间可能有何种关系？源程序：用源语言编写的程序。源程序：用源语言编写的程序。目标程序：源程序经翻译程序过加工处理后生成的程序。目标程序：源程序经翻译程序过加工处理后生成的程序。翻译程序：将源程序转换为与其逻辑上等价的目标程序。翻译程序：将源程序转换为与其逻辑上等价的目标程序。编译程序：编译程序： 源语言为高级语言，目标语言为汇编语言或机源语言为高级语言，目标语言为汇编语言或机器语言的翻译程序。器语言的翻译程序。解释程序：解释程序： 源语言程序作为输入，但不产生目标程序，而源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。是边解释边执行源程序本身。 先翻译后执行先翻译后执行 边解释边执行边解释边执行执行速度快执行速度快 有利于程序的调试有利于程序的调试多次运算多次运算 1次运算次运算编编 译译 原原 理理 chapter15习习题题2、一个典型的编译系统通常由有哪些部分组成？、一个典型的编译系统通常由有哪些部分组成？ 各部分的主要功能是什么？各部分的主要功能是什么？chapter1编译系统编译系统编译程序编译程序语法分析语法分析语义分析与中间代码生成语义分析与中间代码生成优化优化目标代码生成目标代码生成运行系统运行系统词法分析词法分析编编 译译 原原 理理 chapter15习习题题 语法分析语法分析(Syntax Analysis)： 在词法分析的基础上将单词序列分解成各类语法在词法分析的基础上将单词序列分解成各类语法短语，如短语，如“程序程序”，“语句语句”，“表达式表达式”等等。等等。 语义分析语义分析(Syntactic Analysis)： 语义分析是在语法分析程序确定出语法短语后，审语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集类型信息。查有无语义错误，并为代码生成阶段收集类型信息。 chapter1 词法分析词法分析(Lexical Analysis)： 从左到右从左到右一个字符一个字符的读入源程序，对一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而构成源程序的字符串进行扫描和分解，从而识别出识别出一个个单词一个个单词（也称单词符号或简称符号）。（也称单词符号或简称符号）。 编编 译译 原原 理理 chapter15习习题题chapter1 代码优化代码优化(Optimization of code)： 为了使生成的目标代码更为高效，可以对产生的中为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。间代码进行变换或进行改造，这就是代码的优化。 代码生成代码生成(Generation of code)： 目标代码生成是编译器的最后一个阶段。在生成目目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：标代码时要考虑以下几个问题：计算机的系统结构、指计算机的系统结构、指令系统、寄存器的分配以及内存的组织令系统、寄存器的分配以及内存的组织等。等。 中间代码生成中间代码生成(Generation of intermediate code)： 完成语法分析和语义处理工作后，编译程序将源程完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记语言或称中间代码，它是一种结构简单、含义明确的记号系统。号系统。编编 译译 原原 理理 chapter15习习题题chapter21.写出写出C语言和语言和Java语言的输入字母表。语言的输入字母表。C语言：语言：09数字，大小写英文字母，键盘上可见的字符数字，大小写英文字母，键盘上可见的字符Java语言：语言：Unicode可以包括的所有字符。可以包括的所有字符。6.文法文法G6为为: N D|ND D 0|1|2|3|4|5|6|7|8|9 （1） 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的任意数字的任意数字中间部分：空或者任意数字串中间部分：空或者任意数字串 D1|3|5|7|9 CCA| A0|B所以题目要求的文法所以题目要求的文法GNGN可以写成：可以写成：N BCD|DD 1|3|5|7|9B 2|4|6|8|DC CA |A 0 | BB2|4|6|8|D编编 译译 原原 理理 chapter15习习题题9、证明文法、证明文法: S iSeS | iS | i 是二义的。是二义的。二义性的含义二义性的含义: :如果文法存在如果文法存在某个句子某个句子对应两棵以上对应两棵以上不同的语法树，或者两种以上不同的最不同的语法树，或者两种以上不同的最左左/ /右推导，则称这个文法是二义的。右推导，则称这个文法是二义的。首先：找到此文法对应的一个首先：找到此文法对应的一个句子句子 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的不同取值来把的不同取值来把L1分成两部分：分成两部分：A aAb | ab 前半部分是前半部分是 an bn ： 后半部分是后半部分是 c i ：B Bc | 所以整个文法所以整个文法G1S可以写为：可以写为：编编 译译 原原 理理 chapter15习习题题L2=aibncn| n1,i0G2(S): SAB AaA| BbBc|bcL3=anbnambm| m,n0G3(S): SAB AaAb| BaBb|编编 译译 原原 理理 chapter15习习题题L4=1n 0m 1m 0n| n,m0可以看成是两部分：可以看成是两部分：剩下两边的部分就是：剩下两边的部分就是：S 1S0中间部分是中间部分是 0m 1m ：A 0A1 | 所以所以G4S可以写为：可以写为： S 1S0 | A A 0A1 | A编编 译译 原原 理理 chapter15习习题题chapter37.构造下列正规式相应的构造下列正规式相应的DFA。步骤步骤: :. .根据正规式根据正规式画出画出对应的对应的状态转换图状态转换图; ;. .根据状态转换图画出对应的根据状态转换图画出对应的状态转换矩阵状态转换矩阵; ;. .根据状态转换矩阵得到根据状态转换矩阵得到重命名后的状态转换矩阵重命名后的状态转换矩阵; ;. .根据重命名后的状态转换矩阵得出最后的根据重命名后的状态转换矩阵得出最后的DFA. .问题：将状态转换图与问题：将状态转换图与DFA混淆。混淆。编编 译译 原原 理理 chapter15习习题题1(0|1)*101.状态转换图状态转换图 abadb1(0|1)*101a1(0|1)*101dcef101101ggg编编 译译 原原 理理 chapter15习习题题.状态转换矩阵状态转换矩阵II0I1ab,c,db,c,dc,dc,d,ec,dc,dc,d,ec,d,ec,d,fc,d,ec,d,fc,dc,d,e,gc,d,e,gc,d,fc,d,e1abdcef10101g编编 译译 原原 理理 chapter15习习题题II0I1ab,c,db,c,dc,dc,d,ec,dc,dc,d,ec,d,ec,d,fc,d,ec,d,fc,dc,d,e,gc,d,e,gc,d,fc,d,e. .重命名后的状态转换矩阵重命名后的状态转换矩阵S01A(始态始态)BBCDCCDDEDECF(终态终态)F(终态终态)EDAB10C1D010E10101F.DFA编编 译译 原原 理理 chapter15习习题题1(1010*|1(010)*1)*0abdc10e0101fghi01110jklmn.状态转换图状态转换图 编编 译译 原原 理理 chapter15习习题题.状态转换矩阵状态转换矩阵II 0I 101,2,31,2,345,9,10,115,9,10,116,122,36,122,3,7,8,132,345,9,10,112,3,7,8,132,3,4,8,10,115,9,10,112,3,4,8,10,112,3,4,8,122,3,5,9,10,112,3,4,8,122,3,4,85,9,10,11,132,3,5,9,10,114,6,122,3,5,9,10,112,3,4,82,3,4,85,9,10,115,9,10,11,136,10,11,122,34,6,122,3,7,8,136,10,11,12122,3,7,8,1312131310,1110,11122,3编编 译译 原原 理理 chapter15习习题题. .重命名后的状态转换矩阵重命名后的状态转换矩阵II 0I 112234456576347848910911121013101111412146137141571516161717156.DFA编编 译译 原原 理理 chapter15习习题题8、给出下面正规表达式、给出下面正规表达式（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)*（3）包含奇）包含奇數個數個1或奇或奇數個數個0的二的二進進制串制串0*1(0|10*1)*|1*0(0|10*1)*编编 译译 原原 理理 chapter15习习题题（5）沒沒有重有重複複出出現現的的數數字的字的數數字符字符號號串的全串的全體體令令ri=i| ,i=0,1,2.9R0|R1|R2|.|R9記為記為Ri i (0,1,2.,9) P（0,1,2.,9)表示表示0,1,2.,9的全排列的全排列ri0ri1.ri9ri0ri1.ri9 P(0,1,2.,9)8、给出下面正规表达式、给出下面正规表达式（6）最多有一）最多有一個個重重複複出出現現的的數數字的字的數數字符字符號號串的全串的全體體i ri0ri1.ri9 i (0,1,2.,9) ri0ri1.ri9 P(0,1,2.,9)（7）不包含字串）不包含字串abb的由的由a和和b組組成的符成的符號號串的全串的全體體b*(a*|(ba)*)*编编 译译 原原 理理 chapter15习习题题9、对下面情况给出、对下面情况给出DFA及正规表达式：及正规表达式：（1）0,1上的含有子串上的含有子串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)aaa,b10.状态转换矩阵状态转换矩阵 I Ia Ib 00,1110,10,110. .重命名后的状态转换矩阵重命名后的状态转换矩阵 I Ia Ib 012211200a2baba.DFA.最小化最小化0=(0,1,2)10,1a=10,1b=2因此，不能再分因此，不能再分02baa编编 译译 原原 理理 chapter15习习题题023145aaaabbbbbbaa(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 023aabbba编编 译译 原原 理理 chapter15习习题题14、构造一个、构造一个DFA，它接受，它接受=0,1上所有满足如下上所有满足如下 条件的字符串：每个条件的字符串：每个1都有都有0直接跟在右边。直接跟在右边。思路：先写出满足条件的正规式，由正规式构造思路：先写出满足条件的正规式，由正规式构造 NFA，再把，再把NFA确定化和最小化。确定化和最小化。满足条件的正规式：满足条件的正规式：(0|10)*0110yx(0|10)*xy12100编编 译译 原原 理理 chapter15习习题题xy12100确定化：确定化：0 01 1X,1,YX,1,Y1,Y1,Y221,Y1,Y1,Y1,Y22221,Y1,Y给状态编号：给状态编号：0 01 10 01 12 21 11 12 22 21 1编编 译译 原原 理理 chapter15习习题题02101100最小化：最小化：0,1，20,10=1 0,11=220=0，21= 2或或0,1所以所以0,1不可分，用不可分，用狀態狀態0代表它代表它們們02100编编 译译 原原 理理 chapter15习习题题15、给定右线性文法、给定右线性文法G：求一个与：求一个与G等价的左线性文法。等价的左线性文法。S 0S | 1S | 1A | 0BA 1C | 1B 0C | 0C 0C | 1C | 0 | 1SABCZ001110001101GZ:Z Z0|Z1|B0|A1B A0 | 0A B1 | 1确定化、最小化后的确定化、最小化后的DFA为：为：SB0A110Z010,1编编 译译 原原 理理 chapter15习习题题补充：构造一右线性文法，使它与如下文法等价：补充：构造一右线性文法，使它与如下文法等价： SAB AUT Ua|aU Tb|bT Bc|cB 并根据所得右线性文法，构造出相应的状态转换图。并根据所得右线性文法，构造出相应的状态转换图。思路：思路： 先写出原文法所描述的语言先写出原文法所描述的语言 L(G)=ambnck|m,n,k1GS: S aS|aB B bB|bC C cC|caSaCbcBbcT编编 译译 原原 理理 chapter15习习题题chapter44.1、考虑下面文法、考虑下面文法G1：S a | | （T） T T，S | S（1）消去）消去G1的左递归；的左递归；S a | | （T）T STT ，S T |（2）经改写后的文法是否是）经改写后的文法是否是LL(1)文法，给出预测分析表。文法，给出预测分析表。经改写后的文法满足经改写后的文法满足3个条件，所以是个条件，所以是LL(1)的的编编 译译 原原 理理 chapter15习习题题预测分析表构造算法预测分析表构造算法:1.对文法中的每个产生式对文法中的每个产生式A 执行第二步和第三步执行第二步和第三步;FIRST(S)=a,( FIRST(T)=a,( FIRST(T)= , , FOLLOW(S) = ), ,# FOLLOW(T) = ) FOLLOW(T) = ) a（，）#S T T S aS S (T)T STT STT STT ,STT 编编 译译 原原 理理 chapter15习习题题预测分析表构造算法预测分析表构造算法:1.对文法中的每个产生式对文法中的每个产生式A 执行第二步和第三步执行第二步和第三步;2.对每个终结符对每个终结符a FIRST( ),把把A a加到加到MA,a中中;S a; S ; S (T); T ST; T ,ST T FTRST（a）=aFIRST（）=FIRST（T）=（ FIRST（ST）=a，（，（FIRST（，（，ST）=，FIRST（）= a（，）#S T T S aS S (T)T STT STT STT ,ST3.若若 FIRST( ),则对于任何则对于任何b FOLLOW(A)把把A 加至加至MA,b中中FOLLOW(T)=FOLLOW(T)=)T 编编 译译 原原 理理 chapter15习习题题递归子程序：递归子程序：procedure S;beginif sym=a or sym= then abvance else if sym=( then beginadvance;T;if sym=) then advance; else error; endelse errorend;编编 译译 原原 理理 chapter15习习题题procedure T;procedure T;beginbeginS;TS;TEndEndprocedure T;procedure T;beginbeginif sym=,if sym=, then bengin then bengin advance; advance; S;T S;T end endEndEndsym:是输入串指针是输入串指针IP所指的符号所指的符号 advance:是把是把IP调至下一个输入符号调至下一个输入符号error:是出错诊察程序是出错诊察程序编编 译译 原原 理理 chapter15习习题题补充题：有文法：补充题：有文法： E TE E ATE | T FT T MFT | F （E）| i A + | - M * | /（1）求）求First、Follow集，判断是否是集，判断是否是LL（1）文法？）文法？（2）若是构造）若是构造LL（1）分析表？）分析表？（3）简述）简述LL（1）分析器的工作原理。）分析器的工作原理。编编 译译 原原 理理 chapter15习习题题4.2：有文法：有文法： E TE E +E | T FT T T | F PF F *F | P (E) |a|b|（1）求）求First、Follow集，判断是否是集，判断是否是LL（1）文法？）文法？（2）若是构造）若是构造LL（1）分析表？）分析表？（3）简述）简述LL（1）分析器的工作原理。）分析器的工作原理。编编 译译 原原 理理 chapter15习习题题E TEE ATE |T FTT MFT |F （E）| iA + | -M * | /FIRST(M)=* ， /FIRST(A)=+，- FIRST(F)=(， iFIRST(T)=* ，/ ， FIRST(T)=(， i)FIRST(E)=+ ，- ， FIRST(E)=(， iFOLLOW(E)=# ，)FOLLOW(E)=# ，)FOLLOW(T)= + ，- ，# ，)FOLLOW(T)= + ，- ，# ，)FOLLOW(F)=* ，/ ， + ，- ，# ，) FOLLOW(A)= (， iFOLLOW(M)= (， iEE 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习习题题P81.2.对文法对文法G: E TE E +E| T FT T T| F PF F *F| P (E)|a|b| 1)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, , +,#,)FOLLOWF) =FOLLOW(F) =(,a,b, , +,#,)FOLLOW(P) =FIRST(F) FOLLOW(F)= *, (,a,b, , +,#,) (ab+*)#EE TEE TEETEETEEE+EE E TTFTTFTTFTTFTTTTTTTTTTT T T FFPFFPFFPFFPFFF F F F F FFF F PP(E)PaPbP编编 译译 原原 理理 chapter15习习题题 2)考虑下列产生式: FIRST(+E)FIRST()=+= FIRST(+E)FOLLOW(E)=+#,)= FIRST(T)FIRST()=(,a,b,= FIRST(T)FOLLOW(T)=(,a,b,+,),#= FIRST(*F)FIRST()=*= FIRST(*F)FOLLOW(F)=*(,a,b,+,),#= FIRST(E)FIRST(a) FIRST(b) FIRST()= 所以,该文法式LL(1)文法.编编 译译 原原 理理 chapter15习习题题(ab+*)#EETEE TEETEETEEE+EE E TTFTTFTTFTTFTTTTTTTTTTT T T FFPFFPFFPFFPFFF F F F F FFF F PP(E)PaPbP3)預測分析表：编编 译译 原原 理理 chapter15习习题题4)程序程序procedure E;beginif sym=( or sym=a or sym=b or sym= then begin T; E end else errorendprocedure E;beginif sym=+ then begin advance; E end else if sym) and sym# then errorendprocedure T;beginif sym=( or sym=a or sym=b or sym= then begin F; T end else errorend编编 译译 原原 理理 chapter15习习题题procedure T;beginif sym=( or sym=a or sym=b or sym= then T else if sym=* then errorendprocedure F;beginif sym=( or sym=a or sym=b or sym= then begin P; F end else errorendprocedure F;beginif sym=* then begin advance; F endend 编编 译译 原原 理理 chapter15习习题题procedure P;beginif sym=a or sym=b or sym= then advance else if sym=( thenbeginadvance; E;if sym=) then advance else errorendelse errorend;编编 译译 原原 理理 chapter15习习题题n4.3下面文法中，那些是下面文法中，那些是LL(1)文法的，說明理由文法的，說明理由n构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归，文法不含左递归， 2. 对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候选的各个产生式的候选首符集两两不相交。即，若首符集两两不相交。即，若A 1| 2| n 则则 FIRST( i)FIRST( j) (i j) 3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选首，若它存在某个候选首符集包含符集包含 ，则，则FIRST(A)FOLLOW(A)= 如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)LL(1)文法文法。编编 译译 原原 理理 chapter15习习题题4.3.1SAbcAa| Bb| 是，满足三个条件4.3.2SAbAa|B| Bb| 对于A不满足条件34.3.3SABBAAa| Bb| A、B都不满足条件34.3.4SaSe|BBbBe| CcCe| d满足条件3编编 译译 原原 理理 chapter15习习题题解題思路：構造文法的預測分析表，通常應當按下列步驟進行： 1.消除文法的左遞歸（包括所有直接左遞歸和間接左遞歸） 2.對消除左遞歸后的文法，提取公因子 3.對經過上述改造后的文法，計算它的每個非終結符的FIRST集合和FOLLOW集合； 4.根據FIRST集合和FOLLOW集合構造預測分析表： 第1步對文法G的每個產生式A執行第1步和第3步； 第2步對每個終結符aFIRST(),把A加至MA,a中； 第3步若 FIRST(),則對任何b FIRST(A),把A加至MA,b中； 第4步把所有無定義的MA,a標上“出錯標誌” 4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr| Varid VarTailVarTail(Expr)| (1)構造LL(1)分析表(2)給出對句子id- - id(id)分析過程编编 译译 原原 理理 chapter15习习题题 4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr| Varid VarTailVarTail(Expr)| (1)構造LL(1)分析表(2)給出對句子id- - id(id)分析過程解答：FIRST(Expr)=-,(,id FOLLOW(Expr)=),# FIRST(ExprTail)=-, FOLLOW(ExprTail)=),# FIRST(Var)=idFOLLOW(Var)=-,),# FIRST(VarTail)=(,FOLLOW(VarTail)=-,),# 编编 译译 原原 理理 chapter15习习题题 4.4對下面的文法：Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr| Varid VarTailVarTail(Expr)| (1)構造LL(1)分析表(2)給出對句子id- - id(id)分析過程-id()#ExprExpr-ExprExprVar ExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 编编 译译 原原 理理 chapter15习习题题-id()#ExprExpr-ExprExprVar ExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產生式0#Exprid- -id(id)#開始1#ExprTail varid- -id(id)#ExprVar ExprTail2#ExprTail varTail idid- -id(id)#Varid VarTail3#ExprTail varTail- -id(id)#出棧，輸入串後移4#ExprTail - -id(id)#VarTail 5#Expr - - -id(id)#ExprTail-Expr(2)給出對句子id- - id(id)分析過程编编 译译 原原 理理 chapter15习习题题-id()#ExprExpr-ExprExprVar ExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產生式5#Expr - - -id(id)#ExprTail-Expr6#Expr-id(id)#出棧，輸入串後移7#Expr - -id(id)#Expr-Expr8#Exprid(id)#出棧，輸入串後移9#ExprTail Var id(id)#ExprVar ExprTail10#ExprTail VarTail id id(id)#Varid VarTail11#ExprTail VarTail(id)#出棧，輸入串後移(2)給出對句子id- - id(id)分析過程编编 译译 原原 理理 chapter15习习题题-id()#ExprExpr-ExprExprVar ExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產生式11#ExprTail VarTail(id)#出棧，輸入串後移12#ExprTail )Expr(id)#VarTail(Expr)13#ExprTail )Expr(id)#出棧，輸入串後移14#ExprTail ) )Expr(id)#Expr(Expr)15#ExprTail ) )Exprid)#出棧，輸入串後移16#ExprTail ) ) ExprTail Varid)#ExprVar ExprTail17#ExprTail ) ) ExprTail VarTail idid)#Varid VarTail(2)給出對句子id- - id(id)分析過程编编 译译 原原 理理 chapter15习习题题-id()#ExprExpr-ExprExprVar ExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVarid VarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產生式17#ExprTail ) ) ExprTail VarTail idid)#Varid VarTail18#ExprTail ) ) ExprTail VarTail)#出棧，輸入串後移19#ExprTail ) ) ExprTail)#VarTail 20#ExprTail ) )#ExprTail 21#ExprTail )#出棧，輸入串後移22# ExprTail#出棧，輸入串後移23#ExprTail 成功(2)給出對句子id- - id(id)分析過程编编 译译 原原 理理 chapter15习习题题chapter51、令文法、令文法G1为：为： EE+T | T TT*F | F F(E) | i 证明证明E+T*F是它的一个句型，指出这个句型的所有是它的一个句型，指出这个句型的所有短语、直接短语和句柄。短语、直接短语和句柄。EE+TT*FT*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),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)编编 译译 原原 理理 chapter15习习题题(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习习题题2）指出）指出(a,a),(a),a)的规范归约及每一步的句柄。的规范归约及每一步的句柄。S(T)T,Sa(T)ST,ST,S(T)Sa(T)ST,SaSa句型句型句柄句柄归约规则归约规则(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)STS(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),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,Sa(T)ST,ST,S(T)Sa(T)ST,SaSa(aS,TaSS)T, ST(a S T)S)S T,a ST)S归约规则归约规则句柄句柄aSaSTSaSaT,STT , S(T)S(T)STSST,STT , S编编 译译 原原 理理 chapter15习习题题3、(1)计算练习计算练习2文法文法G2的的FIRSTVT和和LASTVT。 G2： Sa | | (T) T T,S | SFIRSTVT(S)= a， ，( FIRSTVT(T)=， ， a， ，(LASTVT(S)=a， ，)LASTVT(T)=， ， a， ，)S （T） （ ）.T T，S ， FIRSTVT(S). ， a , ， , ， ( .T T，S LASTVT(T) ，. a ，, ，, ） ，, ， ，.S （T） ( FIRSTVT(T). ( a, ( , ( ( , ( ，.S （T）LASTVT(T) ). a ) , ) , ) ) , ， ) .对待特殊地对待特殊地#,把它看作句型的开始和结束符把它看作句型的开始和结束符.根据根据#S#同理可得同理可得# a , # , # ( , .# #.a # , # , ） # , .#,)(a #,)(a=.=.1 1、文法是算术文法，且不含、文法是算术文法，且不含产生式。产生式。2 2、由优先关系矩阵可知，任何、由优先关系矩阵可知，任何两个终结符之间的优先关系不多两个终结符之间的优先关系不多于一种。于一种。综上，该文法是算术优先文法。综上，该文法是算术优先文法。编编 译译 原原 理理 chapter15习习题题. ，a（）#， a ( ) # .输入串输入串(a,(a,a)的算符优先过程。的算符优先过程。步骤步骤句型句型优先关系优先关系最左素最左素短语短语规约规约符号符号1#(a,(a,a)#2345678.(.a.,.(.a.,.a.).).#aS#(S,(a,a)#.,.(,(aa)#aS#(S,(S,a)#.,(,(a)#.aS#(S,(S,S)#.,(,(.)#.(,(#.)#S,ST#(S,(T)#.(T)S#(S,S)#.(,.)#.S,ST#(T)#.(.)#.(T)S#S#确认！确认！问题：没有依据最左素短语进行规约问题：没有依据最左素短语进行规约编编 译译 原原 理理 chapter15习习题题P134-5考虑文法SAS|b ASA|a1、列出这个文法的所有LR(0)项目2、构造这个文法的LR(0)项目集规范族及识别或前缀的DFA3、这个文法是SLR的吗？若是，构造出它的SLR分析表4、这个文法是LALR或LR(1)的吗解答：1、0.SS1.SS2.SAS3.SAS4.SAS5.Sb6.Sb7.ASA8.ASA9.ASA10.Sa11.Sa编编 译译 原原 理理 chapter15习习题题P134-5考虑文法SAS|b ASA|a1、列出这个文法的所有LR(0)项目2、构造这个文法的LR(0)项目集规范族及识别或前缀的DFA3、这个文法是SLR的吗？若是，构造出它的SLR分析表4、这个文法是LALR或LR(1)的吗解答：1、编编 译译 原原 理理 chapter15习习题题确定化： S SA Aa ab b0,2,5,7,100,2,5,7,101,2,5,7,8,101,2,5,7,8,102,3,5,7,102,3,5,7,101111661,2,5,7,8,101,2,5,7,8,102,5,7,8,102,5,7,8,102,3,5,7,9,102,3,5,7,9,10 1111662,3,5,7,102,3,5,7,102,4,5,7,8,102,4,5,7,8,102,3,5,7,102,3,5,7,101111662,5,7,8,102,5,7,8,102,5,7,8,102,5,7,8,102,3,5,7,9,102,3,5,7,9,10 1111662,3,5,7,9,102,3,5,7,9,102,4,5,7,8,102,4,5,7,8,102,3,5,7,102,3,5,7,101111662,4,5,7,8,102,4,5,7,8,102,5,7,8,102,5,7,8,102,3,5,7,9,102,3,5,7,9,10 111166编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题P135-6编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题P135-7证明下面文法是SLR(1)文法，但不是LR(0)文法SA AAb|bBa BaAc|a|aAb 解：文法GS： 0：SA 1：AAb 2：AbBa 3：BaAc 4：Ba 5：BaAb编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题p135-8.证明下面的文法是证明下面的文法是LL(1)的的,但不是但不是SLR(1)的。的。 SAaAb|BbBa A B解答解答: (1)首先该文法无左递归存在首先该文法无左递归存在,没有公共左因子。没有公共左因子。 其次其次:对于对于SAaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=b FIRST(AaAb)FIRST(BbBa)= 所以该文法是所以该文法是LL(1)文法。文法。 (2)证明该文法不是证明该文法不是SLR的。的。 文法的文法的LR(0)项目集规范族为项目集规范族为: I0=S.S S.AaAb S.BbBa A. B. I1= S S. I2= SA.aAb I3= SB.bBa I4= SAa.Ab A. I5= SBb.Ba B. I6= SAaA.b I7= SBbB.a I8= SAaAb. I9= SBbBa. 考察考察I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A)FOLLOW(B)= a,b产生规约产生规约-规约冲突。规约冲突。所以该文法不是所以该文法不是SLR(1)文法。文法。编编 译译 原原 理理 chapter15习习题题P135-9编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题编编 译译 原原 理理 chapter15习习题题
展开阅读全文