编译原理5、6、7章解题小结_编译原理心得体会
编译原理5、6、7章解题小结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“编译原理心得体会”。
第5、6、7章小结
几种语法分析方法
• 自上而下
– 递归下降分析法
– 预测（LL(1)）分析法
• 自下而上
– 算符优先分析法
– LR分析法：LR(0)、SLR(1)、LR(1)、LALR(1)
一、自上而下的语法分析方法
1.不带回溯确定的自上而下分析法
2.对文法的要求：
1)文法非左递归
2)LL（1）文法
i.LL（1）文法的定义：
LL分析表不含多重元素
对AVT，A->｜
• FIRST() FIRST()=
• 与至多只有一个为
• 若* ,则FIRST() FOLLOW(A)=
ii.LL（1）文法的两个性质
LL（1）文法不含左递归
LL（1）文法无二义
i.将方法G改写成LL（1）文法的方法：
消去直接左递归
提公共左因子
3.根据文法规则构造
1)递归下降分析程序的方法
2)预测分析表的方法
EX1:已知文法G：
S->aAbDe | d
A->BSD | e
B->Sac | cD |
D->Se |
求：1）每个非终结符的FIRST，FOLLOW集
2）判定是否为LL（1）文法。
解：FIRST（S）={a,e};
FIRST（B）={a,d,c,};
FIRST（D）={a,d,};
FIRST（A）={a,d,c,,e};
FOLLOW（S）={a,e,d,b,#};
FOLLOW（B）={a,e};
FOLLOW（D）={a,e,b};
FOLLOW(A）={b};
FIRST()
EX2:已知 =｛a,b｝,用高级语言编写一个能够识别集合L＝｛ anbn | n0｝的程序。
提示：
1、求文法G：S->aSb |
2、判定文法G能用何种方法做。
二、自下而上的语法分析方法
(一)、算符优先分析法
1.算符优先分析法的定义
2.最左素左语
3.确定优先关系，构造优先关系表
EX3:已知文法G：
S->S;D | D
D->D(T)| H
T->T+S | S
H->a |(S)
求：1）求优先关系表
2）判定是否为OG、OPG文法。
3）根据文法和表分析句子(a+a)# 是否为该文法的句子。（答案：不是）
解: FIRSTVT（H）={a,(}
FIRSTVT（T）={+,a,(}
FIRSTVT（D）={a.(}
FIRSTVT（B）={;,a,(}
LASTVT（H）={a,}
LASTVT（T）={+,a,(}
LASTVT（D）={a.(}
LASTVT（B）={;,}
(二)、LR分析技术
1.所有无二义的上下文无关文法都可以用LR分析法
2.过程：
上下文无关文法->识别文法活前缀的DFA->LR
LR(0)
SLR(1)
LR(1)
LALR(1)
1.四类文法的判别方法
1.任何二义性文法都不是LR文法
2.根据项目集中是否含有冲突的项目：
1.LR(0)文法：所有LR(0)项目集中不含任何冲突
2.SLR(1)文法：LR(0)项目集中的冲突能用SLR规则解决。
3.LR(1)文法：若不能解决，则继续求搜索符，求LR（1）项
目集；若搜索符a只对归约冲突起作用，对移进不起作用，则可用以下LALR方法：
4.LALR(1)文法：合并同心集后，不存在归约与归约的冲突。
2.结论：
LR(0)SLR(1) LR(1)LALR(1),反之不成立
EX4:
已知文法G：
S->bASB | bA
A->dSa | 1
B->cAd | c
判定是否为LR(0), SLR(1), LR(1), LALR(1)文法。
分析：B->cAd | c 有移归冲突，不是LR(0)文法。
求{d,1}FOLLOW(B)
={d,1} FOLLOW(S)
= {d,1} (FIRST(B){#,a})
= {d,1} {#,a,c}
=
所以文法为SLR(1), LR(1), LALR(1)文法。
EX5:已知文法G：
S->AS | b
A->SA | a
判定是否为LR(0), SLR(1), LR(1), LALR(1)文法。
分析：对句子abab对应两棵语法树，故为二义文法，所以文法不是LR(0),SLR(1), LR(1), LALR(1)文法。
EX6:已知文法G：
S->SbSe
S->
问：LL(1)与 SLR(1)哪些方法可用？
分析：左递归
S-> ＝＝＝＞S->.不是S->.和S->.EX7:已知文法G：
A->BA |
B->aB | b
（1）证明它是LR(1)文法
（2）求它的LR(1)分析表
（3）列出句子abab的分析过程
第八章
中间代码的几种形式(逆波兰式 四元式 三元式 间接三元式 树)
EX2：A＋B＊（C－D）＋E /(C－D）^N
逆波兰式
ABCD-*+ECD-N^/+
四元式
（1）（－，C，D，T1）
（2）（＊，B，T1，T2）
（3）（＋，A，T2，T3）
（4）（－，C，D，T4）
（5）（＾，T4，N，T5）
（6）（/，E，T5，T6）
（7）（+，T3，T6，T7）
三元式
（1）（－，C，D）
（2）（＊，B，（1））
（3）（＋，A，（2））
（4）（－，C，D）
（5）（＾，（4），N）
（6）（/，E，（5））
（7）（+，（3），（6））
EX2：A＋B＊（C－D）＋E /(C－D）^N
间接三元式
间接三元式系列间接码表
（1）（－，C，D）（1）
（2）（＊，B，（1））（2）
（3）（＋，A，（2））（3）
（4）（＾，（4），N）（1）
（5）（/，E，（5））（4）
（6）（+，（3），（6））（5）
（6）
每生成一条指令，先检查间接三元式系列，若已有，不再生成，只将序号列入间接码表中； 间接码表表明了执行间接三元式序列的顺序
