编译原理复习题2

1、(10分)下面的文法G[S]是否是LL(1)文法,说明理由,构造LL(1)

分析表

S→aBc|bAB A→aAb|Bb B→cB|

2、(5分)消除下列文法的左递归,消除左递归后判断是否是LL(1)文

法。

S→SaB|bB A→S|a B→Ac

3、(5分)构造下面算符文法的优先矩阵,判断是否是算符优先文法

S→A[] A→[ A→aA A→B] B→a

4、(10分)将表达式A+B*(C-D)-E/F↑G分别表示为三元式、四元式、逆

波兰式序列

5、(10分)现有文法如下:

S→aS|bS|a 判断该文法是哪一类LR文法,说明理由,并构造相应的分析表。

1、已知文法G A::=aABe|a B::=Bb|d

(1)给出与上述文法等价的LL(1)文法G’。

(2)构造预测分析表并给出输入串aade#分析过程。(10分)

2、设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=P↑F F::=P P::=(E)

P::=i

构造此文法的算符优先矩阵。(10分)

3、有正规式b*abb*(abb*)*

(1)构造该正规式所对应的NFA(画出状态转换图)。

(2)将所求的NFA确定化。(画出确定化的状态转换图)。

(3)将所求的NFA最小化。(画出最小化后的状态转换图)。(10分)

4、若有文法G(S)的产生式如下:S::=L=R S::=R L::=*R L::=i R::=L,构造

识别所有项目集规范族的DFA。(15分)

(1)判断该文法是否是LR(0)文法,说明理由。

(2)判断该文法是否是SLR(1)文法,说明理由。

(3)判断该文法是否是LR(1)文法,说明理由。

(4)判断该文法是否是LALR(1)文法,说明理由

1、(10分)将表达式((B*D+A)/E+D)*F+G分别表示为三元式、四元式、逆波兰式序列

2、(10分)对基本块P画出DAG图

B:=3

D:=A+C

E::=A*C

F:=E+D

G:=B*F

H:=A+C

I:=A*C

J:=H+I

K:=B*5

L:=K+J

M:=L

假定只有L在基本块出口之后活跃,写出优化后的四元式序列。

相关推荐
相关主题
热门推荐