编译原理考试重点题.docxVIP

精选 精选 欢迎下载 欢迎下载 1、设正规式 r= a(a|b)*, 将 r 转换为相应的正规文法。 令S为文法开始符，首先形成S f a(a|b)*,然后形成S f aA和A f (a|b)*, 再变换成： Sf aA Afz Af(a|b)A ， 进而变换成正规文法形式： Sf aA Afz Af aA AfbA 2、令文法 G[S] SfcC,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)*即为该文法所对应的正规式 令文法 G[S]为：S-S+A|A A-A*B|B B-(S)|a|b 分析说明a*a+b是该文法的一个句型； 指出该句型的所有短语、直接短语和句柄 (1)该字符串对应的语法树为： 所以a*a+b为该文法的句型。 (2)短语为：a,a,a*a,b,a*a+b 直接短语为：a,a,b ； 句柄为：最左边的a 令文法 G[S]为：S-aCcDe C-b|Cb D-d (1)分析说明aCbcde是它的一个句型; (2)指出该句型的所有短语、直接短语和句柄 (1)此句型对应语法树如下，故 (1)此句型对应语法树如下，故 aCbcde为此文法的一个句型 (2)短语为:aCbcde, Cb, d； 直接短语：Cb, d； 句柄：Cb。 构造正规式(a|b)*相应的最小化DFA 1、首先构造对应的NFA 2、将NFA确定化: ■ S, A, Z- Aa J A, J 扎L AZ A, Z. a- bp A” 母 3、对其最小化: 设有非确定的有自限动机 NFA M=({A, B, C}, {0,1}…{A} , {C}), 其中： (A, 0)={C}, (A, 1)={A , B}, (B, 1)={C}, (C, 1)={C} o 请画出状态转换距阵和状态转换图。 状态转换距阵为： 0* 1* At B- 0* Cp 0 c* 状态转换图为： 对表达式文法 G: E f E+T | T T f T*F | F F f (E) | I 构造各非终结符的FIRSTVT和LASTVT集合; 构造文法的算符优先关系表。 各非终结符的FIRSTVT和LASTV■集合： ■4k FIRSTVT. LASTVT- E. *, +f (f *, + J， 耳 *, (, * J, U F* (,i』 ),i* 算符优先关系表: L J )A +■* . A* * A* 4 A* L 事 41 A# J * *j a —?J )， A ? J 设文法 G[S]: S-aA A-aBb|b B-Cc| e C-aB|d 证明：G是LL(1)文法。 构造的LL(1)预测分析表为: ￡ 5 3 f aAm f b- —Co f f —Co f d* 由预测分析表中无多重入口判定该文法是 LL(1)文法 设有文法 G(S): S— aBc|bAB A — aAb|b B — b| e 求各产生式的 FIRST集，FOLLOW(A和 FOLLOW(B)以及各产生 式的 SELECT!。 构造LL(1)分析表。 解：(1) FIRST(aBc)二{a} FIRST(bAB)二{b} FIRST(aAb)={a} FIRST(A— b)={b} FIRST(b) = {b} FIRST( e )={ e } FOLLOW(A)={b, #} FOLLOW(B)={c, #} SELECT( aBc)={a} SELECT(S bAB) ={b} SELECT(A aAb)={a} SELECT件 b)={b} SELECT(B b)={b} SELECT(B )={c, #} (2)所得的LL(1)分析表如下所示: LL⑴分析表卫 a Cp S” S^aBa S^bABv A. A—aAb A h Be B-b B■ E B l 谢谢观看! 欢迎您的下载，资料仅供参考，如有雷同纯属意外