编译原理与技术 - 习题集（含答案）(2)

2、构造算符优先表。

五、计算题4

21. 已知文法G(S)为：

S → A A → Ab | bBa B → aAc | a | aAb

给出文法的项目集规范族。

22. 已知文法G（E）：

1.

2. 3. 4. 5. 6.

的LR分析表为：

E→ E+T E→ T T→ T*F T→ F F→ (E) F→ i

Acction Goto ） r2 r4 r6 $ Acc r2 r4 r6 r1 r3 r5 E 1 T 2 F 3 3 3 S 0 1 2 3 4 5 6 7 8 9 10 11 i S5 + * s7 r4 （ S4 S6 r2 r4 S5 8 2 S4 r6 r6 S5 S5 9 S4 S4 S7 r3 r5 10 S5 r1 r3 r5 S11 r1 r3 r5 第 6 页 共 26 页

请按以下格式给出“i+i*i$”的LR分析过程。

步骤 栈 输入

动作 说明 23. 已知文法G(S)：

S→(L) | a L→L,S | S

给出文法的项目集规范族。

24. 已知文法G（S ）：

S→(L) | a L→L,S | S

的项目集规范族如下：

I0： S’→?S ( S I1： S’→ S? I2： ( a a L S ( ) I4： S→ (L?) , I6： S→ (L)? I7： I5： L→ S? S→?(L) a I3： S→ a? S→(?L) L→?L,S L→?S S →L,?S S→?(L) S I8： S →L,S? 构造其的SLR分析表。 25. 已知文法G[S]：

S?SA|A A?a

1、求其识别活前缀的项目集规范族

2、构造其SLR(1)分析表。

第 7 页 共 26 页

六、计算题5

26. 已知文法G(L)为：

L→En E → E+T|T T → T*F| F F →digit

根据S属性定义，求表达式为3*5+4的带注释分析树。 27. 已知表达式S=A?B?┐C； 1、求其后缀表示

2、求其用布尔表达式的控制流翻译方法翻译的四元式。 28. 将下列程序段翻译成四元式序列并划分基本块：

A=M＋N；

B= M－N； IF A≦B C=N； ELSE C=M；

29. 翻译下列语句为逆波兰式。

if X

else C=C+X;

30. 翻译下列语句为四元式。

if X

else C=C+X;

七、简答题 （略）……

第 8 页 共 26 页

答案

一、计算题1 1. 确定化:

i0{0} i1{0,1} i2{1,2} i3{1} DFA M：

a {0,1} {0,1} {1} / b / {1,2} {1,2} {1,2}

(内容一行1.5分，图１分，共7分)

正规式:a+b(b|ab)*(有拓广1分，消0、１态2分，消２、3态3分，共6分) 2. NFA Ｍ:

(有初态2分，有末态2分，有中间态2分，共6分)

确定化:

i0{0} i1{0,1} i2{1,2} i3{1} a {0,1} {0,1} {1} / 第 9 页 共 26 页

b / {1,2} {1,2} {1,2}

DFA M：

(内容一行1.5分，图１分，共7分)

3. 1、NFA M

(有初态1分，终态1分，1态、2态各1分，共4分)

2、确定化：

I0{0} I1{0,1,2} NFA M：

a {0,1,2 } {0,1,2} b / {0,1,2}

（有框架１分，内容一行1.5分， DFA效果图2分，共6分） 3、最小化：∵

0 1 ∴原图已最小化

（原因2分，结果１分，共3分） 4. 语言L的正规式是：

(正规式5分)

第 10 页 共 26 页

a 1 1 b / 1 (a b*a | b)* 或 b*(a b*a b*)*

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理与技术 - 习题集（含答案）(2)在线全文阅读。