编译原理复习题

更新时间:2024-04-30 01:09:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

二、概念题

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)给出句子i+i*i的最右推导。(4分) (4)给出句子i+i*i的最左推导。(4分) 2、

设有文法:E→E+T|T T→T*F|F F→(E)|i

(1)证明E+T*F是它的一个句型。(3分)

(2)给出E+T*F的所有短语,直接短语和句柄。(4分) (3)给出句子i+i*i的最右推导。(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

Top