编译原理陈意云_课后答案2[1].ppt

1、编译原理练习课(2)，栾军7/22/2020，2020/7/22，2，3.1，考虑语法S-(L)| A1-L，S|S(a)建立句子(A，(A，A)和(A，(A)。a)的分析树(b)为a)的两个句子构造最左边的演绎(c)为a)的两个句子构造最右边的演绎(d)由该语法产生的语言是什么，2020/7/22，3，3.1(续)-(a，(a，a) (s)，S()=(a，(a，s)=(a，(a，a)，s=(l)=(l，s)=(l，(L，s) (a，a)(S，(L)，L，S，S，S，S，S，S S)=(A，(A，A)，S)=(A，(A，A)，(L)=(A，(A，A)，(L，S)=(a，(A，A)，(S，S)=

2、(a，(A，A)，(A，S)=(a，(A，A，(A)，A)，(L)，L，S，S，S=(L)=(L，S)=(L，(L)=(L)=(L，(L)，S)=(L)=(L，(L)，S)=(L，(L)，S)=(L，(L) (1)S=AsBs=AbS=AbAbS=AbAbAbS=AbAbAbS(2)S=AsBs=AbAsBs=AbAbAbS=AbAbAbS=AsB=AbAbAbS=AbAbAbS=AbAbAbAb(2)，S，A，S，B，S，B，S，S，B，S，S，(1)，(2)，所描述的语言是一个具有相等数量的A和B的字符串，语法为R-R | R | R * |(R)| A | B(c)根据上述两个语法，构造

3、ab|b*a，2020/7/22，9，3.4(续)的分析树，并证明该语法产生了字母a和b上的所有范式：1)该语法产生的字符串是字母a和b上的范式R-a和R-b，它们产生a、b和a、b，如果R1和R2产生范式， 然后R-R-RR产生正规形式R-R1|R2产生正规形式| R-R1*产生正规形式* R-(R1)产生正规形式()2)字母表A和B上的所有正规形式可以产生字母表A和B上的任何正规形式从这个语法(这里它是正规形式)必须是下列形式之一：语法可以从R-R*产生()从R-(R)，从R-a产生B，从R-B产生B 语法不包含运算符|、*、(。r=r | r=a | r *=a | b * r=r *=

4、r | r *=a | r *=a | b * e-e | t | TT-TF | ff-f * |(e)| a | b e=e |。不含糊，r，r | r，r，a，b，r，a，r *，b，r，r，a，r *，r | r，b，r，b，r，b，a，e，e | t以下条件语句语法stmt-if expr然后stmt | matched _ stmt matched _ stmt-if expr然后matched _ stmt else stmt |其他尝试消除浮动else的歧义。请证明这个语法仍然是不明确的。，2020/7/22，13，3.5(续)，由于匹配(_stmt)不能保证然后和其他的配对，

5、因而存在二义性句型如果表达式然后如果表达式然后匹配_stmt else如果表达式然后匹配_stmt else stmt存在两个不同的最左推导期望的是：如果expr，则如果expr，则匹配_stmt else如果expr，则匹配_stmt else stmt，2020/7/22，14，3.5(续)，一种推导，和期望的不一样stmt=匹配_stmt=if expr然后matched_stmt else stmt=if expr然后if expr然后matched_stmt else stmt=if expr然后if expr然后匹配_stmt else if expr然后stmt else stm

6、t=if表达式然后if expr然后匹配的_ stmt else如果expr然后匹配_stmt else stmt if expr然后if expr然后匹配的_stmt else如果expr然后matched_stmt else stmt，2020/7/22，15，3.5(续)，另一种推导stmt=if expr然后stmt=if expr然后matched_stmt=if expr然后if expr然后matched_stmt else stmt=if expr然后if expr然后matched _ stmt else matched _ stmt=if expr然后if expr然后匹配

7、的_stmt else如果expr然后匹配_stmt else stmt if expr然后if expr然后匹配的_ stmt else如果expr然后matched_stmt else stmt，2020/7/22，16，3.8(a)，消除3.1的左递归，2020/7/22，17，3.8(a) （续)，S - (L)|aL - L，S|S只有直接左递归S - (L)|aL - SLL-，SL|，2020/7/22，18，3.10，构造下面文法的LL(1)分析表TLT国际| RealIdrR-，idR|，2020/7/22，19，3.10(续)，先计算第一和FOLLOWFIRST(D)=FI

8、RST(T)=int，realFIRST(L)=id FIRST(R)=，FOLLOW(D)=FOLLOW(L)=$ FOLLOW(T)=IDFOLLOW(R)=$，2020/7/22，20，3.10(续)，2020/7/22，21，3.11，下面文法是否LL(1)文法？ 说明理由S - AB|PQxA - xyB - bcP - dP| Q - aQ|，2020/7/22，22，3.11(续)，不是LL(1)文法LL(1)文法：对于产生式A-|，本题中，FIRST(AB)=x，FIRST(PQx)=d，a，x不满足条件(1)，2020/7/22，23，3.15，(a)用3.1的文法构造(a，

9、(a，a)的最右推导，说出每个右句型的句柄(b)给出对应(a)的最右推导的移进-归约分析器的步骤(c)对照(b)的移进-归约，给出自下而上构造分析树的步骤，2020/7/22，24，3.15(续)(a) (b)，S=(L)=(L，S)=(L，(L)=(L，(L，S)=(L，(L，a)=(L，(S，a)=(L，(a，a)=(S，(a，a)=(a，(a，(a)，a)，2020/7/22，25，3.15(续)(a) (b)续上表，S=(L)=(L，S)=(L，(L)=(L，(L，S)=(L，(L，a)=(L，(S，a)=(L，(a，a)=(S，(a，a)=(a，(a，(a)，a)，2020/7/22，26，3.15(续)(a) (b)续上表，S=(L)=(L，S)=(L，(L)=(L，(L，S)=(L，(L，a)=(L，(S，a)=(L，(a，a)=(S，(a，a)=(a，(a，