编译原理习题课答案市公开课一等奖百校联赛获奖课件.pptx

编编译译原原理理chapter15习题习题chapter11、何谓源程序、目标程序、翻译程序、编译程序、何谓源程序、目标程序、翻译程序、编译程序和解释程序？它们之间可能有何种关系？和解释程序？它们之间可能有何种关系？源程序：用源语言编写程序。源程序：用源语言编写程序。目标程序：源程序经翻译程序过加工处理后生成程序。目标程序：源程序经翻译程序过加工处理后生成程序。翻译程序：将源程序转换为与其逻辑上等价目标程序。翻译程序：将源程序转换为与其逻辑上等价目标程序。编译程序：编译程序：源语言为高级语言，目口号言为汇编语言或机源语言为高级语言，目口号言为汇编语言或机器语言翻译程序。器语言翻译程序。解释程序：解释程序：源语言程序作为输入，但不产生目标程序，而源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。是边解释边执行源程序本身。先翻译后执行先翻译后执行 边解释边执行边解释边执行执行速度快执行速度快 有利于程序调试有利于程序调试屡次运算屡次运算 1次运算次运算第第1页页编编译译原原理理chapter15习题习题2、一个经典编译系统通常由有哪些部分组成？、一个经典编译系统通常由有哪些部分组成？各部分主要功效是什么？各部分主要功效是什么？chapter1编译系统编译系统编译程序编译程序语法分析语法分析语义分析与中间代码生成语义分析与中间代码生成优化优化目标代码生成目标代码生成运行系统运行系统词法分析词法分析第第2页页编编译译原原理理chapter15习题习题语法分析语法分析(SyntaxAnalysis)：在词法分析基础上将单词序列分解成各类语法短在词法分析基础上将单词序列分解成各类语法短语，如语，如“程序程序”，“语句语句”，“表示式表示式”等等。等等。语义分析语义分析(SyntacticAnalysis)：语义分析是在语法分析程序确定出语法短语后，审语义分析是在语法分析程序确定出语法短语后，审查有没有语义错误，并为代码生成阶段搜集类型信息。查有没有语义错误，并为代码生成阶段搜集类型信息。chapter1词法分析词法分析(LexicalAnalysis)：从左到右从左到右一个字符一个字符读入源程序，对组一个字符一个字符读入源程序，对组成源程序字符串进行扫描和分解，从而成源程序字符串进行扫描和分解，从而识别出一个识别出一个个单词个单词（也称单词符号或简称符号）。（也称单词符号或简称符号）。第第3页页编编译译原原理理chapter15习题习题chapter1代码优化代码优化(Optimizationofcode)：为了使生成目标代码更为高效，能够对产生中间代为了使生成目标代码更为高效，能够对产生中间代码进行变换或进行改造，这就是代码优化。码进行变换或进行改造，这就是代码优化。代码生成代码生成(Generationofcode)：目标代码生成是编译器最终一个阶段。在生成目标目标代码生成是编译器最终一个阶段。在生成目标代码时要考虑以下几个问题：代码时要考虑以下几个问题：计算机系统结构、指令系计算机系统结构、指令系统、存放器分配以及内存组织统、存放器分配以及内存组织等。等。中间代码生成中间代码生成(Generationofintermediatecode)：完成语法分析和语义处理工作后，编译程序将源程完成语法分析和语义处理工作后，编译程序将源程序变成一个内部表示形式，这种内部表示形式叫做中间序变成一个内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一个结构简单、含义明确记号语言或称中间代码，它是一个结构简单、含义明确记号系统。系统。第第4页页编编译译原原理理chapter15习题习题chapter21.写出写出C语言和语言和Java语言输入字母表。语言输入字母表。C语言：语言：09数字，大小写英文字母，键盘上可见字符数字，大小写英文字母，键盘上可见字符Java语言：语言：Unicode能够包含全部字符。能够包含全部字符。6.文法文法G6为为:ND|NDD0|1|2|3|4|5|6|7|8|9（1）G6语言是什么语言是什么?G6语言是：语言是：09数字组成任意数字组成任意非空非空串串L(G6)=x|x 0,1,2,3,4,5,6,7,8,9+（2）给出句子）给出句子0127、34和和568最左和最右推导。最左和最右推导。第第5页页编编译译原原理理chapter15习题习题7、写一文法，使其语言是写一文法，使其语言是奇数集奇数集。要求：不以要求：不以0打头。打头。复杂情况复杂情况:分三部分分三部分末尾：以末尾：以1|3|5|7|9结尾结尾(一位一位):):D1|3|5|7|9开头：除了开头：除了0任意数字任意数字中间部分：空或者任意数字串中间部分：空或者任意数字串D1|3|5|7|9CCA|A0|B所以题目要求文法所以题目要求文法GNGN能够写成：能够写成：NBCD|DD1|3|5|7|9B2|4|6|8|DCCA|A0|BB2|4|6|8|D第第6页页编编译译原原理理chapter15习题习题9、证实文法、证实文法:SiSeS|iS|i是二义。是二义。二义性含义二义性含义:假如文法存在假如文法存在某个句子某个句子对应两棵以上对应两棵以上不一样语法树，或者两种以上不一样最不一样语法树，或者两种以上不一样最左左/右推导，则称这个文法是二义。右推导，则称这个文法是二义。首先：找到此文法对应一个首先：找到此文法对应一个句子句子 iiiei其次：结构与之对应其次：结构与之对应两棵两棵语法树语法树S i S e S i S i i S i S i S e S i i结论：因为该文法存在句子结论：因为该文法存在句子iiieiiiiei对应两棵对应两棵 不一样语法树，因而该文法是二义。不一样语法树，因而该文法是二义。第第7页页编编译译原原理理chapter15习题习题11、给出下面语言对应文法、给出下面语言对应文法L1=anbnci|n1,i0G1(S):SABAaAb|abBcB|从从n，i不一样取值来把不一样取值来把L1分成两部分：分成两部分：AaAb|ab前半部分是前半部分是anbn：后半部分是后半部分是ci：BBc|所以整个文法所以整个文法G1S能够写为：能够写为：第第8页页编编译译原原理理chapter15习题习题L2=aibncn|n1,i0G2(S):SABAaA|BbBc|bcL3=anbnambm|m,n0G3(S):SABAaAb|BaBb|第第9页页编编译译原原理理chapter15习题习题L4=1n0m1m0n|n,m0能够看成是两部分：能够看成是两部分：剩下两边部分就是：剩下两边部分就是：S1S0中间部分是中间部分是0m1m：A0A1|所以所以G4S能够写为：能够写为：S1S0|AA0A1|A第第10页页编编译译原原理理chapter15习题习题chapter37.结构以下正规式对应结构以下正规式对应DFA。步骤步骤:.依据正规式依据正规式画出画出对应对应状态转换图状态转换图;.依据状态转换图画出对应依据状态转换图画出对应状态转换矩阵状态转换矩阵;.依据状态转换矩阵得到依据状态转换矩阵得到重命名后状态转换矩阵重命名后状态转换矩阵;.依据重命名后状态转换矩阵得出最终依据重命名后状态转换矩阵得出最终DFA.问题：将状态转换图与问题：将状态转换图与DFA混同。混同。第第11页页编编译译原原理理chapter15习题习题1(0|1)*101.状态转换图状态转换图abadb1(0|1)*101a1(0|1)*101dcef101101ggg第第12页页编编译译原原理理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第第13页页编编译译原原理理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第第14页页编编译译原原理理chapter15习题习题1(1010*|1(010)*1)*0abdc10e0101fghi01110jklmn.状态转换图状态转换图第第15页页编编译译原原理理chapter15习题习题.状态转换矩阵状态转换矩阵II0I101,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第第16页页编编译译原原理理chapter15习题习题.重命名后状态转换矩阵重命名后状态转换矩阵II0I112234456576347848910911121013101111412146137141571516161717156.DFA第第17页页编编译译原原理理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)*第第18页页编编译译原原理理chapter15习题习题（5）沒有重複出現數字數字符號串全體）沒有重複出現數字數字符號串全體令令ri=i|,i=0,1,2.9R0|R1|R2|.|R9記為記為Rii(0,1,2.,9)P（0,1,2.,9)表示表示0,1,2.,9全排列全排列ri0ri1.ri9ri0ri1.ri9 P(0,1,2.,9)8、给出下面正规表示式、给出下面正规表示式（6）最多有一個重複出現數字數字符號串全體）最多有一個重複出現數字數字符號串全體iri0ri1.ri9i(0,1,2.,9)ri0ri1.ri9 P(0,1,2.,9)（7）不包含字串）不包含字串abb由由a和和b組成符號串全體組成符號串全體b*(a*|(ba)*)*第第19页页编编译译原原理理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*第第20页页编编译译原原理理chapter15习题习题12、将图、将图3.18(a)和和(b)分别确定化和最少化。分别确定化和最少化。(a)aaa,b10.状态转换矩阵状态转换矩阵IIaIb00,1110,10,110.重命名后状态转换矩阵重命名后状态转换矩阵IIaIb012211200a2baba.DFA.最小化最小化0=(0,1,2)10,1a=10,1b=2所以，不能再分所以，不能再分02baa第第21页页编编译译原原理理chapter15习题习题023145aaaabbbbbbaa(b)这道题实质上已经是确定化了，所以我们只需最小化这道题实质上已经是确定化了，所以我们只需最小化：2，3，4，50，12，3，4，5a=0，1，3，5分属两区，所以分为分属两区，所以分为2，43，50，1a=10，1b=2，4所以所以0，1等价等价2，4a=0，12，4b=3，5所以所以2，4等价等价3，5a=3，53，5b=2，4所以所以3，5等价等价所以分为所以分为0，12，43，5023aabbba第第22页页编编译译原原理理chapter15习题习题14、结构一个、结构一个DFA，它接收，它接收=0,1上全部满足以下上全部满足以下条件字符串：每个条件字符串：每个1都有都有0直接跟在右边。直接跟在右边。思绪：先写出满足条件正规式，由正规式结构思绪：先写出满足条件正规式，由正规式结构NFA，再把，再把NFA确定化和最小化。确定化和最小化。满足条件正规式：满足条件正规式：(0|10)*0110yx(0|10)*xy12100第第23页页编编译译原原理理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第第24页页编编译译原原理理chapter15习题习题02101100最小化：最小化：0,1，20,10=10,11=220=0，21=2或或0,1所以所以0,1不可分，用狀態不可分，用狀態0代表它們代表它們02100第第25页页编编译译原原理理chapter15习题习题15、给定右线性文法、给定右线性文法G：求一个与：求一个与G等价左线性文法。等价左线性文法。S0S|1S|1A|0BA1C|1B0C|0C0C|1C|0|1SABCZ001110001101GZ:ZZ0|Z1|B0|A1BA0|0AB1|1确定化、最小化后确定化、最小化后DFA为：为：SB0A110Z010,1第第26页页编编译译原原理理chapter15习题习题补充：结构一右线性文法，使它与以下文法等价：补充：结构一右线性文法，使它与以下文法等价：SABAUTUa|aUTb|bTBc|cB并依据所得右线性文法，结构出对应状态转换图。并依据所得右线性文法，结构出对应状态转换图。思绪：思绪：先写出原文法所描述语言先写出原文法所描述语言L(G)=ambnck|m,n,k1GS:SaS|aBBbB|bCCcC|caSaCbcBbcT第第27页页编编译译原原理理chapter15习题习题chapter44.1、考虑下面文法、考虑下面文法G1：Sa|（T）TT，S|S（1）消去）消去G1左递归；左递归；Sa|（T）TSTT，ST|（2）经改写后文法是否是）经改写后文法是否是LL(1)文法，给出预测分析表。文法，给出预测分析表。经改写后文法满足经改写后文法满足3个条件，所以是个条件，所以是LL(1)第第28页页编编译译原原理理chapter15习题习题预测分析表结构算法预测分析表结构算法:1.对文法中每个产生式对文法中每个产生式A执行第二步和第三步执行第二步和第三步;FIRST(S)=a,(FIRST(T)=a,(FIRST(T)=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW(T)=)a（，）#STTSaS S(T)TSTTSTTSTT,STT第第29页页编编译译原原理理chapter15习题习题预测分析表结构算法预测分析表结构算法:1.对文法中每个产生式对文法中每个产生式A执行第二步和第三步执行第二步和第三步;2.对每个终止符对每个终止符a FIRST(),把把Aa加到加到MA,a中中;Sa;S;S(T);TST;T,STTFTRST（a）=aFIRST（）=FIRST（T）=（FIRST（ST）=a，（，（FIRST（，（，ST）=，FIRST（）=a（，）#STTSaS S(T)TSTTSTTSTT,ST3.若若 FIRST(),则对于任何则对于任何b FOLLOW(A)把把A加至加至MA,b中中FOLLOW(T)=FOLLOW(T)=)T第第30页页编编译译原原理理chapter15习题习题递归子程序：递归子程序：procedureS;beginifsym=aorsym=thenabvanceelseifsym=(thenbeginadvance;T;ifsym=)thenadvance;elseerror;endelseerrorend;第第31页页编编译译原原理理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:是犯错诊察程序是犯错诊察程序第第32页页编编译译原原理理chapter15习题习题补充题：有文法：补充题：有文法：ETEEATE|TFTTMFT|F（E）|iA+|-M*|/（1）求）求First、Follow集，判断是否是集，判断是否是LL（1）文法？）文法？（2）若是结构）若是结构LL（1）分析表？）分析表？（3）简述）简述LL（1）分析器工作原理。）分析器工作原理。第第33页页编编译译原原理理chapter15习题习题4.2：有文法：有文法：ETEE+E|TFTTT|FPFF*F|P(E)|a|b|（1）求）求First、Follow集，判断是否是集，判断是否是LL（1）文法？）文法？（2）若是结构）若是结构LL（1）分析表？）分析表？（3）简述）简述LL（1）分析器工作原理。）分析器工作原理。第第34页页编编译译原原理理chapter15习题习题ETEEATE|TFTTMFT|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)=(，iEETEETEEEATEEATEEETTFTTFTTT-TTMFTTMFTTTFFiF（E）AA+A-MM*M/i+-*/（）#第第35页页编编译译原原理理chapter15习题习题P81.2.对文法对文法G:ETEE+E|TFTTT|FPFF*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+*)#EETEETEETEETEEE+EEETTFTTFTTFTTFTTTTTTTTTTTTTFFPFFPFFPFFPFFFFFFFFFFFPP(E)PaPbP第第36页页编编译译原原理理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)文法.第第37页页编编译译原原理理chapter15习题习题(ab+*)#EETEETEETEETEEE+EEETTFTTFTTFTTFTTTTTTTTTTTTTFFPFFPFFPFFPFFFFFFFFFFFPP(E)PaPbP3)預測分析表：第第38页页编编译译原原理理chapter15习题习题4)程序程序procedureE;beginifsym=(orsym=aorsym=borsym=thenbeginT;EendelseerrorendprocedureE;beginifsym=+thenbeginadvance;Eendelseifsym)andsym#thenerrorendprocedureT;beginifsym=(orsym=aorsym=borsym=thenbeginF;Tendelseerrorend第第39页页编编译译原原理理chapter15习题习题procedureT;beginifsym=(orsym=aorsym=borsym=thenTelseifsym=*thenerrorendprocedureF;beginifsym=(orsym=aorsym=borsym=thenbeginP;FendelseerrorendprocedureF;beginifsym=*thenbeginadvance;Fendend第第40页页编编译译原原理理chapter15习题习题procedureP;beginifsym=aorsym=borsym=thenadvanceelseifsym=(thenbeginadvance;E;ifsym=)thenadvanceelseerrorendelseerrorend;第第41页页编编译译原原理理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)文法文法。第第42页页编编译译原原理理chapter15习题习题4.3.1SAbcAa|Bb|是，满足三个条件4.3.2SAbAa|B|Bb|对于A不满足条件34.3.3SABBAAa|Bb|A、B都不满足条件34.3.4SaSe|BBbBe|CcCe|d满足条件3第第43页页编编译译原原理理chapter15习题习题解題思绪：構造文法預測分析表，通常應當按以下步驟進行：1.消除文法左遞歸（包含全部直接左遞歸和間接左遞歸）2.對消除左遞歸后文法，提取公因子3.對經過上述改造后文法，計算它每個非終結符FIRST集合和FOLLOW集合；4.根據FIRST集合和FOLLOW集合構造預測分析表：第1步對文法G每個產生式A執行第1步和第3步；第2步對每個終結符aFIRST(),把A加至MA,a中；第3步若FIRST(),則對任何bFIRST(A),把A加至MA,b中；第4步把全部無定義MA,a標上“出錯標誌”4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id-id(id)分析過程第第44页页编编译译原原理理chapter15习题习题4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id-id(id)分析過程解答：FIRST(Expr)=-,(,idFOLLOW(Expr)=),#FIRST(ExprTail)=-,FOLLOW(ExprTail)=),#FIRST(Var)=idFOLLOW(Var)=-,),#FIRST(VarTail)=(,FOLLOW(VarTail)=-,),#第第45页页编编译译原原理理chapter15习题习题4.4對下面文法：Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVarTail(Expr)|(1)構造LL(1)分析表(2)給出對句子id-id(id)分析過程-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVaridVarTailVarTailVarTail VarTail(Expr)VarTail VarTail 第第46页页编编译译原原理理chapter15习题习题-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVaridVarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產生式0#Exprid-id(id)#開始1#ExprTailvarid-id(id)#ExprVarExprTail2#ExprTailvarTailidid-id(id)#VaridVarTail3#ExprTailvarTail-id(id)#出棧，輸入串後移4#ExprTail-id(id)#VarTail 5#Expr-id(id)#ExprTail-Expr(2)給出對句子id-id(id)分析過程第第47页页编编译译原原理理chapter15习题习题-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVaridVarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產生式5#Expr-id(id)#ExprTail-Expr6#Expr-id(id)#出棧，輸入串後移7#Expr-id(id)#Expr-Expr8#Exprid(id)#出棧，輸入串後移9#ExprTailVarid(id)#ExprVarExprTail10#ExprTailVarTailidid(id)#VaridVarTail11#ExprTailVarTail(id)#出棧，輸入串後移(2)給出對句子id-id(id)分析過程第第48页页编编译译原原理理chapter15习题习题-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVaridVarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產生式11#ExprTailVarTail(id)#出棧，輸入串後移12#ExprTail)Expr(id)#VarTail(Expr)13#ExprTail)Expr(id)#出棧，輸入串後移14#ExprTail)Expr(id)#Expr(Expr)15#ExprTail)Exprid)#出棧，輸入串後移16#ExprTail)ExprTailVarid)#ExprVarExprTail17#ExprTail)ExprTailVarTailidid)#VaridVarTail(2)給出對句子id-id(id)分析過程第第49页页编编译译原原理理chapter15习题习题-id()#ExprExpr-ExprExprVarExprTailExpr(Expr)ExprTaiExprTail-ExprExprTail ExprTail VarVaridVarTailVarTailVarTail VarTail(Expr)VarTail VarTail 步驟符號棧輸入串所用產生式17#ExprTail)ExprTailVarTailidid)#VaridVarTail18#ExprTail)ExprTailVarTail)#出棧，輸入串後移19#ExprTail)ExprTail)#VarTail 20#ExprTail)#ExprTail 21#ExprTail)#出棧，輸入串後移22#ExprTail#出棧，輸入串後移23#ExprTail 成功(2)給出對句子id-id(id)分析過程第第50页页编编译译原原理理chapter15习题习题chapter51、令文法、令文法G1为：为：EE+T|TTT*F|FF(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是句柄是句柄第第51页页编编译译原原理理chapter15习题习题2、考虑下面表格结构文法、考虑下面表格结构文法G2：Sa|(T)TT,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)第第52页页编编译译原原理理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)第第53页页编编译译原原理理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第第54页页编编译译原原理理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第第55页页编编译译原原理理chapter15习题习题3、(1)计算练习计算练习2文法文法G2FIRSTVT和和LASTVT。G2：Sa|(T)TT,S|SFIRSTVT(S)=a，(FIRSTVT(T)=，a，(LASTVT(S)=a，)LASTVT(T)=，a，)S（T）（）.TT，S，FIRSTVT(S).，a,，,，(.TT，SLASTVT(T)，.a，,，,），,，.S（T）(FIRSTVT(T).(a,(,(,(，.S（T）LASTVT(T).a),),),，).对待特殊地对待特殊地#,把它看作句型开始和结束符把它看作句型开始和结束符.依据依据#S#同理可得同理可得#a,#,#(,.#.a#,#,）#,.#,)(a#,)(a=.=.1 1、文法是算术文法，且不含、文法是算术文法，且不含产生式。产生式。2 2、由优先关系矩阵可知，任何、由优先关系矩阵可知，任何两个终止符之间优先关系不多于两个终止符之间优先关系不多于一个。一个。综上，该文法是算术优先文法。综上，该文法是算术优先文法。第第56页页编编译译原原理理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#确认！确认！问题：没有依据最左素短语进行规约问题：没有依据最左素短语进行规约第第57页页编编译译原原理理chapter15习题习题P134-5考虑文法SAS|bASA|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第第58页页编编译译原原理理chapter15习题习题P134-5考虑文法SAS|bASA|a1、列出这个文法全部LR(0)项目2、结构这个文法LR(0)项目集规范族及识别或前缀DFA3、这个文法是SLR吗？若是，结构出它SLR分析表4、这个文法是LALR或LR(1)吗解答：1、第第59页页编编译译原原理理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