编译原理考试重点题

1、设正规式r=a(a|b)*,将r转换为相应的正规文法。令S为文法开始符，首先形成Sfa(a|b)*,然后形成SfaA和Af(a|b)*,再变换成：SfaAAfAf(a|b)A，进而变换成正规文法形式：SfaAAfAfaAAfbA2、令文法GSSfcC,Sfc,CfcC,CfdC,Cfc,Cfd，将该文法转换为相应的正规式。首先有S=cC|c，C=(cC|dC)|(c|d)=(c|d)C|(c|d)=(c|d)*|(c|d)=(c|d)+进一步有S=c(c|d)+|c=c(c|d)*c(c|d)*即为该文法所对应的正规式令文法GS为：S-S+A|AA-A*B|BB-(S)|a|b分析说明a*a+b是该文法的一个句型；指出该句型的所有短语、直接短语和句柄(1)该字符串对应的语法树为：所以a*a+b为该文法的句型。(2)短语为：a,a,a*a,b,a*a+b直接短语为：a,a,b；句柄为：最左边的a令文法GS为：S-aCcDeC-b|CbD-d(1)分析说明aCbcde是它的一个句型;(2)指出该句型的所有短语、直接短语和句柄(1)此句型对应语法树如下，故aCbcde为此文法的一个句型(2)短语为:aCbcde,Cb,d；直接短语：Cb,d；句柄：Cb。构造正规式(a|b)*相应的最小化DFA1、首先构造对应的NFA2、将NFA确定化:&S,A,Z-AaJA,J扎LAZA,Z.a-bpA”母3、对其最小化:设有非确定的有自限动机NFAM=(A,B,C,0,1A,C),其中：(A,0)=C,(A,1)=A,B,(B,1)=C,(C,1)=Co请画出状态转换距阵和状态转换图。状态转换距阵为：0*1*AtB-0*Cp0c*状态转换图为：对表达式文法G:EfE+T|TTfT*F|FFf(E)|I(1) 构造各非终结符的FIRSTVT和LASTVT集合;(2) 构造文法的算符优先关系表。各非终结符的FIRSTVT和LASTV集合：4kFIRSTVT.LASTVT-E.*,+f(f*,+J，耳*,(,*J,UF*(,i),i*算符优先关系表:LJ)A+*.A*A*41A#J*jaJ)，AaAA-aBb|bB-Cc|eC-aB|d证明：G是LL(1)文法。构造的LL(1)预测分析表为:53faAmfb-Cof&f&Cofd*由预测分析表中无多重入口判定该文法是LL(1)文法设有文法G(S):SaBc|bABAaAb|bBb|e(1) 求各产生式的FIRST集，FOLLOW(A和FOLLOW(B)以及各产生式的SELECT!。(2) 构造LL(1)分析表。解：(1)FIRST(aBc)二aFIRST(bAB)二bFIRST(aAb)=aFIRST(Ab)=bFIRST(b)=bFIRST(e)=eFOLLOW(A)=b,#FOLLOW(B)=c,#SELECT(&aBc)=aSELECT(SbAB)=bSELECT(AaAb)=aSELECT件b)=bSELECT(Bb)=bSELECT(B)=c,#(2)所得的LL(1)分析表如下所示:LL分析表卫aCpS”SaBaSbABvA.AaAbAhBeB-bBEBl谢谢观看!欢迎您的下载，资料仅供参考，如有雷同纯属意外