资源描述
编译原理,第一章-第六章补充,例1,文法GP及相应翻译方案为：PbQbprint:”1”QcRprint:”2”Qaprint:”3”RQad(print:”4”（1)该文法是不是算符优先文法，请构造算符优先关系表证实之。(2)输入串为bcccaadadadb时，该翻译方案的输出是什么。,(1）文法GP的每个非终结符的FIRSTVT集和LASTVT集如下：FIRSTVT(P)=b；FIRSTVT(Q)=a,c；FIRSTVT(R)=a,c；LASTVT(P)=b；LASTVT(Q)=a,c；LASTVT(R)=d)。构造优先关系表：,由表3.19可看出：终结符对（c,a)存在着两种优先关系和，故文法G不是一个算符优先文法。,PbQbprint:”1”QcRprint:”2”Qaprint:”3”RQad(print:”4”,PbQbprint:”1”QcRprint:”2”Qaprint:”3”RQad(print:”4”,(2)对输入串bcccaadadadb,画出其语法树，。采用修剪语法树的办法，按句柄方式自下而上归约语法树，每当一个产生式得到匹配（归约）时执行相应的语义动作。因此，第一个句柄匹配的产生式为Qa,执行相应的语义动作：打印3;第二个句柄匹配的产生式为RQad,执行相应的语义动作：打印4；。由此得到最终的翻译结果为：34242421。,1.语法分析之所以采用上下文无关文法是因为它的描述能力最强。（）2.欲构造行之有效的自上而下分析器，则必须消除左递归。（）3.文法(SaS|bcS|)描述的语言是（a|bc）*()4.在自下而上的语法分析中，语法树与分析树一定相同。（）5.二义文法不是上下文无关文法.（）6.每一个算符优先文法，必定能找到一组优先函数与之对应。7.语法分析时必须先消除文法中的左递归。（）8.规范归约和规范推导是互逆的两个过程。（）9.一个文法所有句型的集合形成该文法所能接受的语言。（）10.LL(1)文法一定不含左递归和二义性。（）,已知文法GS：SdABAaA|aBBb|（1）试问GS是否为正规文法，为什么？（2）GS所产生的语言是什么？（3）GS能否改写为等价的正规文法?,答：(1)因为SdAB不符合正规文法产生式AaB或Aa,aVT*,A,BVN的格式，故GS不是正规文法。(2)GS产生的语言为：L=danbm|n1,m0(3)可以得到GS对应的正规文法GS:SdAAaA|aB|aBbB|,给出文法G1：SaSb|PPbPc|bQcQQa|a（1)它是Chomsky哪一型文法？（2）它生成的语言是什么？,根据Chomsky的定义，对任何形如A的产生式，有AVN，(VTVN)*时为2型文法。而文法G1恰好满足这一要求，故为Chomsky2型文法。(2)由文法Gl可以看出：S推出串的形式是aiPbi(i0),P推出串的形式是bjQcj(j1),Q推出串的形式是ak(k1).因此，文法G1生成的语言是L=aibjakcjbi|i0,jl,k1。,已知文法GS:SS*aP|aP|*aPP+aP|+a（1）将文法GS改写为LL(1）文法GS。（2）写出文法GS的预测分析表。,文法GM是否LL(1)的，说明理由。GM：MTBTBa|BDb|eT|Dd|,设有文法GS：SSAS|bAbSb|b试构造一个与其等价的算符文法。,经分析可知GS产生的句子为奇数个b,其正规式为b(bb)*,由此得到NFA,令S对应状态X,A对应状态Y,B对应状态1，我们得到改写的文法GS为：GS：SbA|bAbBBbA|b对文法GS求FIRSTOP集与LASTOP集如下：FIRSTOP(S)=b；FIRSTOP(A)=b；FIRSTOP(B)=b；LASTOP(S)=b；LASTOP(A)=b；LASTOP(B)=b。,由于文法GS只存在形如P.aR.的产生式，则：由SbA得bFIRSTOP(A），即bb；由AbB得bFIRSTOP(B），即bb；由于终结符对（b,b)仅满足一种优先关系，故为算符优先文法。,1.LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。（）2.构造LR分析器的任务就是产生LR分析表。（）3.LR文法肯定是无二义的，一个无二义文法决不会是LR文法。（）4.在任何时候，分析栈的活前缀X1X2.Xm的有效项目集就是栈顶状态Sm所在的那个项目集。（）5同心集的合并有可能产生新的“移进”“归约”冲突。（）6.由于LR(0)分析表构造简单，所以它的描述能力强、适用面宽；LR(1)分析表因构造复杂而描述能力弱、适用面窄。（）7所有LR分析器的总控程序都是一样的，只是分析表各有不同。（）8.LR分析技术无法适用二义文法。（）9.项目A12对活前缀1是有效的，其条件是存在规范推导S*=aAW=a12。（）10.SLR(1)文法的特点是：当符号栈中的符号串为，而面临的输入符号为则存在把归约为A的规范句型的前缀A时，方可把a归约为A。（）,文法G的产生式如下：SBBBaB|b请分别构造该文法的（1)LR(0）分析表；(2）SLR分析表；(3）规范LR分析表（即LR（1）分析表）；（4）LALR分析表。,答：（1）将文法G拓广为文法G：0）SSI）SBB2）BaB3）Bb,构造SLR分析表必须先求出形如Aa.的FOLLOW(A)，即对文法G的BbSBBBaB求FOLLOW集，由FOLLOW的构造文法得：FOLLOW（S）；FIRST（B）cFOLLOW（B），即FOLLOW（B）a,b；由SS得：FOLLOW（S）FOLLOW（S），即FOLLOW（S）；由SBB得：FOLLOW（S）FOLLOW（B），即FOLLOW（B）a,b，。根据SLR(1)分析表的构造方法得文法G的SLR(1)分析表，见表4.2。,（4）构造LALR分析表根据LR(1)项目集族，将同心集合并在一起，即将图4.4中的I3与I6、I勺与I7以及I8与I9分别合并成：I36:BaB,a/b/#I47:Bba/b/#BaB,a/b/#I89：BaB,a/b/#Bb,a/b/#由合并后的集族按照LALR分析表的构造算法得到LALR分析表，见表4.4.,由此表看出，它与SLR表是相同的。注意，这是因为文法G既可以用SLR构造又可以用LALR构造。但有些文法却只能用LALR构造而不能用SLR构造。,LR(0),SLR(1),LR(1)及LALR的共同特征就是用规范归约的方法寻找句柄，即LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。它们的本质区别是寻找句柄的方法不同。如果当前的栈顶状态为归约状态（即有形如Aa的项目属于栈顶状态），则：对LR(0)来说，无论现行输入符号是什么，都认为栈顶的符号串为句柄而进行归约；对SLR(1)来说，则对现行输入符号加了一点限制，即该输入符号必须属于允许跟在句柄之后的字符范围内，才认为栈顶的符号串为句柄而进行归约；对LR(1)来说，对现行输入符号的限制则更加严格，它在该输入符号跟在栈顶符号串后形成一个规范句型的前缀时，才认为栈顶的这个符号串为句柄，从而进行归约。由于要对不同的输入符号进行判断，因此LR(1)的状态数要比LR(0)、SLR(1)多。,LR(0),SLR(1),LR(1)及LALR比较,LALR从本质上讲与LR（1)相同，只不过它把那些栈顶符号串相同但现行输入符号不同（即认为这个相同的栈顶符号串为同心）的判断合一（使状态数又减少到与LR（0）、SLR(1)一样），只有输入符号跟在栈顶符号串后面形成一规范句型前缀时，才认为栈顶的这个符号串为句柄而进行归约。对于同心的栈顶符号串而言，由于面对不同的输入符号将形成不同规范句型的前缀，这就给归约带来一些困难；也即，当输入串有误时，LR（1)能够及时地发现错误，而LALR则可能还继续执行一些多余的归约动作，但决不会执行新的移进，即LALR能够像LR（1)一样准确地指出出错的地点。此外，LALR这种同心集的合并有可能带来新的“归约”“归约”冲突。,
展开阅读全文