编译原理复习题-给学生(简)

《编译原理》复习题

35.文法

S ? A a | b A c | d c | b d a A ? d

造识别活前缀的DFA。请根据这个DFA来判断该文法是不是SLR(1)文法并说明理由。 【解】 S’ S S’

? ? .

S A S a S S ? ? ? .

A a c S A S b S S ? ? ? b . d S A c a S d ? S ? S b ? c S d .d .?

c Follow(S)={#} Follow(A)={a,c}

I4存在冲突且Follow(A)∩{c}={ c} I7存在冲突且Follow(A)∩{a}={ a} 所以不是SLR(1)文法

36.将下图所示的确定有限自动机(DFA)最小化。其中,X为初态,Y为终态。

【解】 1-9 0-9 ?(其它) 2 3 1 0 38.设有文法G[S]:

S→S*S|S+S|(S)|i

该文法是否为二义文法,并说明理由?

【解】该文法是二义文法,因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图所示。

S S i (1) S S S i + S i S i S * + S i (2) *

aaXb21ba3abYb 【解】 先划分为终态集{Y}和非终态集I={X,1,2,3}

X面对输入符号b时下一状态属于I,而1,2,3面对输入符号b时下一状态属于{Y},故划分为{X}、{1,2,3}

非终态2和非终态3面对输入符号a的下一状态相同,而1不同,即最简状态{X}、{1}、{2,3}、{Y}。按顺序重新命名为0、1、2、3,则得到最简DFA,

a0ab21abb339.程序的文法如下:

P → D

D → D;D | id : T | proc id; D; S

写一语法制导定义,打印该程序一共声明了多少个id

【解】 属性num表示id个数 P → D print(D.num) D → D(1);D(2) D.num = D(1).num + D(2).num D → id : T D.num = 1 D → proc id; D(1); S D.num = D(1).num + 1

例:proc id; proc id; id : T; S; S(从语法树分析入手)

(注意:本例只是帮助学生理解题意,不是答案部分)

P D procid ; D ; S procid ; D ; S

37.请画出识别无符号十进制整数的状态转换图

21

id : T 《编译原理》复习题

40.把下列语句翻译为四元式序列(四元式序号 int real id , # D D ? D ? 从1开始):

while (A > B) if (C > D)

X = Y * Z

else

X = Y + Z 【解】(1) (j>, A, B, 3) (2) (j, _, _, 11) (3) (j>, C, D, 5) (4) (j, _, _, 8) (5) (*, Y, Z, T1) (6) (=, T1, _, X) (7) (j, _, _, 1) (8) (+, Y, Z, T2) (9) (=, T2, _, X) (10) (j, _, _, 1) (11)

41.构造下面文法的LL(1)分析表。 G[D]: D ? TL

T ? int | real L ? i

>>閻忕偞娲栫槐鎴﹀礂閵婏附鐎�<<
12@gma联系客服:779662525#qq.com(#替换为@)