编译原理试题及答案二市公开课一等奖省赛课微课金奖PPT课件.pptx

程序设计语言编译原理参考答案Chapter4.自上而下语法分析第1页CH.4.练习题1(P81.)1.考虑下面文法G1:S→a|^|(T)T→T，S|S(1)消去G1左递归。然后对每个非终止符,写出不带回溯递归子程序。解(1)消左后文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε第2页CH.4.练习题1(P81.)解(1)不带回溯递归子程序:S→a|^|(T)ProcedureS;Beginifsym=‘a’orsym=‘^’thenadvanceelseifsym=‘(‘thenbeginadvance;T;ifsym=‘)’thenadvanceelseerrorendelseerrorEnd;第3页CH.4.练习题1(P81.)解(1)不带回溯递归子程序:T→ST’ProcedureT;BeginS;T’end;解(1)不带回溯递归子程序:T’→,ST’|εprocedureT’;beginifsym=‘,’thenbeginadvance;S;T’endEnd;第4页CH.4.练习题1(P81.)(2)经改写后文法是否是LL(1)?给出它预测分析表。消左后文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε(2)因为G1’:①文法不含左递归;②对S→a|^|(T)FIRST(a)={a},FIRST(^)={^},FIRST((T))={(},集合互不相交且不含ε;③对T’→,ST’|εFIRST(,ST’)={,},FIRST(ε)={ε},其交集为空。但ε∈FIRST(T’)=FIRST(,ST’)∩FIRST(ε)={，,ε},然而，FOLLOW(T’)={)}FIRST(T’)={，,ε}，二者不相交。所以，G1’是LL(1)文法。第5页CH.4.练习题1(P81.)(2)结构G1’