編譯原理復(fù)習(xí)題91265

1、精選文檔二、概念題1、設(shè)有文法：PP+Q|QQQ*R|RR(P)|i（1）證明Q*R+Q+Q是它的一個句型。（3分)（2）給出Q*R+Q+Q的全部短語，直接短語和句柄。(4分)（3）給出句子+*的最右推導(dǎo)。(4分)（4）給出句子+*的最左推導(dǎo)。(4分)2、設(shè)有文法：EE+T|TTT*F|FF(E)|i（1）證明E+T*F是它的一個句型。（3分)（2）給出E+T*F的全部短語，直接短語和句柄。(4分)（3）給出句子+*的最右推導(dǎo)。(4分)3、寫出表達(dá)式a+b*(c-d)對應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2

2、) * b (1) (3) + a (2) 三、詞法分析題給出下面語言的相應(yīng)文法L1=anbnambm|n,m0給出下面語言的相應(yīng)文法L2=anbnci|n1,i0給出下面語言的相應(yīng)文法L3=anbncm| m,n1，n為奇數(shù)，m為偶數(shù)。 四、詞法分析題1、構(gòu)造下面正規(guī)式相應(yīng)的DFA(0|1)*|(11)*)*（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）2、構(gòu)造下面正規(guī)式相應(yīng)的DFA1(0|1)*1013、構(gòu)造一個DFA，它接受S=a，b上全部包含ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）4、構(gòu)造與正規(guī)式 b(a|b)*ba 等價(jià)的DFA五、語法分析

3、題1、對下面的文法G:Expr- ExprExpr(Expr)|Var ExprTailExprTail- Expr|Varid VarTail VarTail(Expr) |（1）構(gòu)造LL(1)分析表。（12分）（2）給出對句子idid(id)的分析過程。（8分）2、對下面的文法G:ETEE+E|TFTTT|FPFF *F|P(E)|a|b|（1）計(jì)算這個文法的每個非終結(jié)符的FIRST和FOLLOW。（8分）（2）證明這個文法是LL(1)的。（6分）（3）構(gòu)造它的猜測分析表。（6分）3、已知文法GS 為： S->a|(T)T->T,S|S 消退文法GS中的左遞歸，得文法G

4、0;S。 文法G´S是否為LL(1)的？若是，給出它的猜測分析表。4、對下面的文法G:S ® S Ú a T | a T | Ú a TT ® Ù a T | Ù a(1) 消退該文法的左遞歸和提取左公因子；(2) 構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3) 構(gòu)造該文法的LL(1)分析表，并推斷該文法是否是LL(1)的。5、文法G(S)及其LR分析表如下，請給出串baba#的分析過程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObDa#SBD

5、0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5六、語法分析題考慮文法:SAS|b ASA|a（1）列出這個文法的全部LR(0) 項(xiàng)目。（5分）（2）給出識別文法全部活前綴的DFA。（5分）（3）求全部非終結(jié)符的FOLLOW集。（5分）（4）文法是SLR文法嗎？若是，構(gòu)造出它的SLR分析表,否則說明理由。（5分）七、證明題1、證明下面文法是LL(1)的但不是SLR(1)的。SAaAb|BbBaAB2、證明下面文法是SLR(1)但不是LR(0)的。SAAAb|bBaBaAc|a|aAb八、語義分析題1、將語句if (A<0) Ú (B>

6、0) then while (C>0) do C:=C-D翻譯成四元式答案：100 (j<， A， 0， 104)101 (j， -， -， 102)102 (j>， B， 0， 104)103 (j， -， -， 109)104 (j>， C， 0， 106)105 (j， -， -， 109)106 (-， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)1092、寫出下面語句經(jīng)語法制導(dǎo)翻譯后所生成的四元式代碼序列。 if x<y then while e>c do c:=c+1 else x:=x+5答案：假設(shè)初始為100，則四元式代碼序列為 100ifx