编译原理复习题91265

1、精选文档二、概念题1、设有文法：PP+Q|QQQ*R|RR(P)|i（1）证明Q*R+Q+Q是它的一个句型。（3分)（2）给出Q*R+Q+Q的全部短语，直接短语和句柄。(4分)（3）给出句子+*的最右推导。(4分)（4）给出句子+*的最左推导。(4分)2、设有文法：EE+T|TTT*F|FF(E)|i（1）证明E+T*F是它的一个句型。（3分)（2）给出E+T*F的全部短语，直接短语和句柄。(4分)（3）给出句子+*的最右推导。(4分)3、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2

2、) * b (1) (3) + a (2) 三、词法分析题给出下面语言的相应文法L1=anbnambm|n,m0给出下面语言的相应文法L2=anbnci|n1,i0给出下面语言的相应文法L3=anbncm| m,n1，n为奇数，m为偶数。 四、词法分析题1、构造下面正规式相应的DFA(0|1)*|(11)*)*（要求：先将正规式转化为NFA，再将NFA确定化，最小化）2、构造下面正规式相应的DFA1(0|1)*1013、构造一个DFA，它接受S=a，b上全部包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）4、构造与正规式 b(a|b)*ba 等价的DFA五、语法分析

3、题1、对下面的文法G:Expr- ExprExpr(Expr)|Var ExprTailExprTail- Expr|Varid VarTail VarTail(Expr) |（1）构造LL(1)分析表。（12分）（2）给出对句子idid(id)的分析过程。（8分）2、对下面的文法G:ETEE+E|TFTTT|FPFF *F|P(E)|a|b|（1）计算这个文法的每个非终结符的FIRST和FOLLOW。（8分）（2）证明这个文法是LL(1)的。（6分）（3）构造它的猜测分析表。（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) 构造各非终结符的FIRST和FOLLOW集合；(3) 构造该文法的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) 项目。（5分）（2）给出识别文法全部活前缀的DFA。（5分）（3）求全部非终结符的FOLLOW集。（5分）（4）文法是SLR文法吗？若是，构造出它的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、写出下面语句经语法制导翻译后所生成的四元式代码序列。 if x<y then while e>c do c:=c+1 else x:=x+5答案：假设初始为100，则四元式代码序列为 100ifx