编译原理第五章-参考答案

文法G3:S→A[B]A→[B]|AaB→a1.求出各非终结符N的Firstvt(N)和Lastvt(N),构造包括符号'#'在内的算符优先表;2.给出语句#[a][a]#的算符优先分析过程。a[]#a[=]#=给定以下拓广了的文法G[S’]：(0)S’-A(1)A-Ab(2)A-bBa(3)B-aAc(4)B-a(5)B-aAb1.构造LR(0)项目集规范族，证明它是SLR(1)的，而不是LR(0)的。2.构造SLR(1)分析表。（按题中的产生式编号填写）3.用你构造的SLR(1)分析表分析串baab是否为该文法的句子。S[a]A[aa]BaaS[a]A[aa]BaaS[a]因为FOLLOW(B)={a},和{b}不相交，所以可以解决I5中的移进和归约冲突；FOLLOW(A)={#,b,c}和FOLLOW(B)={a}也不相交，所以可以解决I9中的归约和归约冲突；因此该文法是SLR(1)文法。2．SLR(1)分析表如下：ACTIONGOTOabc#AB0s211s3acc2s543r1r1r14s65r4s276r2r2r27s9s88r39r5r1r1r13.符号串baab的分析过程为：步骤状态栈符号栈输入串动作转向00#baab#S2102#baab#S52025#baab#r443024#bBab#S640246#bBab#r21501#Ab#s31.LR(0)项目集规范族:从LR(0)项目集规范族中可以看出：由于在状态I5中有移进和归约冲突，在状态I9中有归约和归约冲突，所以它而不是LR(0)文法。6013#Ab#r11701#A#acc所以，符号串baab是该文法的一个句子。文法G[S]为（VT,VN,S,P），其中VT={a,b,c},VN={S,L,R}，P为如下产生式：S-LaR|RL-bR|cR-L该文法是否SLR(1)文法？该文法是否LR(1)文法？如果是LR(1)文法，请给出用LR(1)分析表对句子bcac#的分析过程；如果不是LR(1)文法，请给出句子bcac的规范推导。答：（过程略）该文法的lr(0)项目集中出现了移进和归约冲突，所以不是SLR文法，该文法的lr(1)项目集中没有冲突，所以是LR(1)文法状态actiongotoabc#SLR0s4s51231acc2s6r53r24s4s5875r46s11s121097r38r59r110r511s11s12101312r413r3用LR(1)分析表对句子bcac#的分析过程：步骤状态栈符号栈输入串动作转向00#bcac#S4104#bcac#S52045#bcac#r483048#bLac#R574047#bRac#R32502#Lac#S66026#Lac#S13702612#Lac#R410802610#LaL#R5990269#LaR#R111001#S#acc