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在基本块出口之后活跃,写出优化后的四元式序列。
3、(10分)对于文法G[S]:S→aBb | aAa |bAb|bBa A→x B→x
(1)判断该文法是否是LR(1)文法,构造LR(1)分析表
(2)判断该文法是否是LALR(1)文法,说明理由
三、问答题:(共50分)
1、已知文法G S::=bBc|aAB A::=bAa|a B::=a|
写出所有非终结符号的First集和Follow集,构造预测分析表并给出输入串abbaaa分析过程。(10分)
2、正规式0(0|1)*1
构造该正规式所对应的NFA(画出状态转换图)。
将所求的NFA确定化和最小化。(分别画出确定化和最小化的状态转换图)。(10分)
3、若有文法G(S)的产生式如下:S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范族的DFA。(20分)
判断该文法是否是LR(0)文法,说明理由。
判断该文法是否是SLR(1)文法,说明理由。
判断该文法是否是LR(1)文法,说明理由。
判断该文法是否是LALR(1)文法,说明理由。
4、简述编译的整个过程(10分)。
1、已知文法G[S] S→eT|RT T→DR| R→dR| D→a|bd
写出所有非终结符号的First集和Follow集,构造LL(1)分析表,判断此文法是否是LL(1)文法。(10分)
2、给出正规式 (a|b)*bb(a|b)*
构造该正规式所对应的NFA(画出状态转换图)。
将所求的NFA确定化和最小化。(分别画出确定化和最小化的状态转换图)。(10分)
3、若有文法G(S)的产生式如下:S→aAD|aBe|bBS|bAe A→g B→g D→d|,构造识别所有LR(1)项目集规范族的DFA。(20分)
判断该文法是否是LR(1)文法,说明理由,构造LR(1)表。
判断该文法是否是LALR(1)文法,说明理由。
4、简述编译的整个过程(10分)。
1、 把下图确定化和最小化:(15分)
2、 已知文法G S::=bBc|aAB A::=bAa|a B::=a|
写出所有非终结符号的First集和Follow集,构造预测分析表并给出输入串abbaaa分析过程。(15分)
3、 若有文法G(S)的产生式如下:S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范族的DFA。(20分)
判断该文法是否是LR(0)文法,说明理由。
判断该文法是否是SLR(1)文法,说明理由。
判断该文法是否是LR(1)文法,说明理由。
判断该文法是否是LALR(1)文法,说明理由。
三、问答题:(共计50分)
5、 已知文法G A::=aABe|a B::=Bb|d
(1) 给出与上述文法等价的LL(1)文法G’。
(2) 构造预测分析表并给出输入串aade#分析过程。(10分)
6、 设={0,1}上的正规集S由倒数第二个字符为1的所有字符串组成,请给出该字集对应的正规式,并构造一个识别该正规集的DFA。(15分)
3、设文法G(S):(10分)
构造算符优先关系表和优先函数。
4、构造文法G(S):
(1) S BB
(2) B aB
(3) B b
的LR分析表。假定输入串为abab,请给出LR分析过程(即按照步骤给出状态,符号,输入串的变化过程)(15分)。
四、综合题(共45分)
1、(10分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合,并判断该文法是否是LL(1)的,请说明理由。
G(M):
a) M → TB
b) T → Ba |
c) B → Db | eT |
d) D → d |
2、(15分)对文法G(S):
S → a | ^ | (T)
T → T,S | S
(1) 构造算符优先表;
(2) 判断是算符优先文法吗?
(3) 构造优先函数。
3、(10分)将表达式A-B*(C+D)+E/F↑G分别表示为三元式、四元式、逆波兰式序列
4、(10分)设有文法G[S]
S→Ba|Bb|c B→Bd|Se|f
判断该文法是哪一类LR文法,说明理由,并构造相应的分析表
1、已知文法G S::=aBc|bAB A::=aAb|b B::=b|
构造预测分析表并给出输入串baabbb分析过程。(10分)
2、构造正规式 (0|1)*00 相应的DFA并进行化简。(15分)
7、 若有文法G(S)的产生式如下:S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范族的DFA。(15分)
(1) 判断该文法是否是LR(0)文法,说明理由。
(2) 判断该文法是否是SLR(1)文法,说明理由。
(3) 判断该文法是否是LR(1)文法,说明理由。
(4) 判断该文法是否是LALR(1)文法,说明理由。
8、 (10分)对文法G(S):
S S a T | a T | a T
T a T | a
(1) 消除该文法的左递归和提取左公因子;
(2) 构造各非终结符的FIRST和FOLLOW集合;
(3) 构造该文法的LL(1)分析表,并判断该文法是否是LL(1)的。
三、已知文法G S::=aBc|bAB A::=aAb|b B::=b|
构造预测分析表并给出输入串baabbb分析过程。(10分)
四、正规式((0*|1)(1*0))*(10分)
(1) 构造该正规式所对应的NFA(画出状态转换图)。
(2) 将所求的NFA确定化。(画出确定化的状态转换图)。
五、若有文法G(S)的产生式如下:S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范族的DFA。(15分)
i. 判断该文法是否是LR(0)文法,说明理由。
ii. 判断该文法是否是SLR(1)文法,说明理由。
iii. 判断该文法是否是LR(1)文法,说明理由。
iv. 判断该文法是否是LALR(1)文法,说明理由。
六、设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=(E) F::=i
构造此文法的算符优先矩阵。(15分)
本文来源:https://www.2haoxitong.net/k/doc/4150c93950e2524de4187e34.html
文档为doc格式