编译原理复习题

二、概念题

1、设有文法：P→P+Q|Q Q→Q*R|R R→(P)|i

（1）证明Q*R+Q+Q是它的一个句型。（3分)

（2）给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分) （3）给出句子ｉ+ｉ*ｉ的最右推导。(4分) （4）给出句子ｉ+ｉ*ｉ的最左推导。(4分) 2、

设有文法：E→E+T|T T→T*F|F F→(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) * b (1) (3) + a (2)

三、词法分析题 给出下面语言的相应文法

L1={anbnambm|n,m≥0}

- 1 -

给出下面语言的相应文法

L2={anbnci|n≥1,i≥0}

给出下面语言的相应文法

L3={anbncm| m,n≥1，n为奇数，m为偶数}。

四、词法分析题

1、构造下面正规式相应的DFA

((0|1)*|(11)*)*

（要求：先将正规式转化为NFA，再将NFA确定化，最小化） 2、构造下面正规式相应的DFA

1(0|1)*101

3、构造一个DFA，它接受?={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化） 4、构造与正规式 b(a|b)*ba 等价的DFA 五、语法分析题 1、对下面的文法G: Expr→- Expr

Expr→(Expr)|Var ExprTail ExprTail→- Expr|ε Var→id VarTail VarTail→(Expr) |ε

（1）构造LL(1)分析表。（12分）

（2）给出对句子id—id((id))的分析过程。（8分）

- 2 -

2、对下面的文法G: E→TE’ E’→+E|ε T→FT’ T’→T|ε F→PF’ F’ →*F’|ε P→(E)|a|b|∧

（1）计算这个文法的每个非终结符的FIRST和FOLLOW。（8分） （2）证明这个文法是LL(1)的。（6分） （3）构造它的预测分析表。（6分） 3、已知文法G[S] 为： S->a|(T) T->T,S|S

①消除文法G[S]中的左递归，得文法G′[S]。

② 文法G′[S]是否为LL(1)的？若是，给出它的预测分析表。 4、对下面的文法G:

S ? S ? a T | a T | ? a T T ? ? a T | ? a

(1) 消除该文法的左递归和提取左公因子； (2) 构造各非终结符的FIRST和FOLLOW集合；

(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。 5、文法G(S)及其LR分析表如下，请给出串baba#的分析过程。 (1) S → DbB (4) B → a

(2) D → d

(3) D → ε (6) B → ε

(5) B → Bba

LR分析表

0

ACTION b r3 D s3 a # S 1 - 3 -

GOTO B D 2 1 2 3 4 5 6 7 8 s4 r2 r6 r4 s7 r5 S5 S8 acc r6 r4 r1 r5 6 - 4 -

六、语法分析题 考虑文法:

S→AS|b A→SA|a

（1）列出这个文法的所有LR(0) 项目。（5分） （2）给出识别文法所有活前缀的DFA。（5分） （3）求所有非终结符的FOLLOW集。（5分）

（4）文法是SLR文法吗？若是，构造出它的SLR分析表,否则说明理由。（5分） 七、证明题

1、证明下面文法是LL(1)的但不是SLR(1)的。 S→AaAb|BbBa A→ε B→ε

2、证明下面文法是SLR(1)但不是LR(0)的。

S→A A→Ab|bBa B→aAc|a|aAb 八、语义分析题

1、将语句

if ((A<0) ? (B>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) 109

5

2、写出下面语句经语法制导翻译后所生成的四元式代码序列。 if xc do c:=c+1 else x:=x+5 答案：假设初始为100，则四元式代码序列为

100 101 102 103 104 105 106 107 108 109

if goto if goto M:=C+1 C:=M goto N:=X+5 X:=N

xc goto 104 109 102

6

本文来源：https://www.bwwdw.com/article/45kg.html