君，已阅读到文档的结尾了呢~~
第7章自下而上的LR(K)分析方法
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
第7章自下而上的LR(K)分析方法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口下次自动登录
现在的位置:
& 综合 & 正文
编译原理:LL(1),LR(0),SLR(1),LALR(1),LR(1)对比
LL(1)定义：一个文法G是LL（1）的，当且仅当对于G的每一个非终结符A的任何两个不同产生式 A→α|β，下面的条件成立：SELECT( A→α)∩SELECT( A→β)=,其中，
α|β不能同时ε。
解释：LL(1)的意思是，第一个L,指的是从左往右处理输入，第二个L,指的是它为输入生成一个最左推导。1指的是向前展望1个符号。LL(1)文法是上下文无关文法的一个子集。它用的方法是自顶向下的(递归式的处理)。它要求生成的预测分析表的每一个项目至多只能有一个生成式。上面的定义说的是，任何两个不同的产生式 A→α和 A→β,选择A→α或者 A→β是不能有冲突的，即SELECT( A→α)∩SELECT( A→β)=，具体来说，就是，第一:First( A→α) ∩
First( A→β)=,首符集不能有交集，否则当交集中的元素出现时，选择哪个产生式进行推导是不确定的，（这其中也包含了α|β不能同时ε，否则交集就是{ε}不为空），第二：若任何一个产生式β，有ε属于First(β),应有First(A)∩Follow(
A)为空（当ε属于First(β)，则A有可能被空串代替，那么就要看A的下一个字符，即Follow集，即要求Follow集和First集不能相交，否则可能发生冲突）。
LR文法：定义：如果某一文法能够构造一张分析表，使得表中每一个元素至多只有一种明确动作，则该文法称为LR文法。
拓展：由上面的定义可以看到，LL(1)和LR文法都是无二义性的：LL(1)要求生成的预测分析表的每一个项目至多只能有一个生成式，即对于读头下的每一个字符，都可以明确地选择哪个产生式来推导，LR文法要求每一步都有明确的动作，移进和归约都是可确定的，没有二义性。
比较两大类型（自顶向下　vs 自底向上）的文法的特点：
1.首先LL(1)分析法是自上而下的分析法。LR(0),LR(1),SLR(1),LALR(1)是自下而上的分析法。
2.自上而下:从开始符号出发，根据产生式规则推导给定的句子。用的是推导
3.自下而上:从给定的句子规约到文法的开始符号。用的是归约
4.自上而下就是一种试探过程，怎么试探？需要你写出它的FIRST()集与FOLLOW()集。写出这两个集合后根据LL(1)分析表构造规则画出LL(1)分析表。现在基本完成了大半，当计算机输入句子时，分析程序便会根据输入去和分析表进行匹配，如果每步都能够匹配成功则说明符合该语法规则，分析成功。
FIRST()集：其实是终结符的集合，看该非终结符A能不能产生以它里面的某个符号开头的句子。（这也是自上而下分析法的思想）
5.自下而上就是把句子变成非终结符，在把非终结符变成非终结符，这样不断的进行如果能到根节点则成功。
LL(1)就是向前只搜索1个符号，即与FIRST()匹配，如果FIRST为空则还要考虑Follow。
　 LR需要构造一张LR分析表，此表用于当面临输入字符时，将它移进，规约（即自下而上分析思想），接受还是出错。
LR(0)找出句柄前缀，构造分析表，然后根据输入符号进行规约。不考虑先行，只要出现终结符就移进，只要出现归约状态，就无条件归约,这样子可能出现归约－移进，归约－归约冲突。
SLR(1)使用LR(0)时若有归约－归约冲突，归约－移进冲突，所以需要看先行，则只把有问题的地方向前搜索一次。
SLR(1)定义：满足下面两个条件的文法是SLR(1)文法
a.对于在s中的任何项目 A→α.Xβ,当X是一个终结符，且X在Follow(B)中时，s中没有完整的项目B→r.
b.对于在s中的任何两个完整项目A→α.和 B→β.,Follow(A)∩Follow(B)为空。
解释：a.当X是一个终结符且X出现在读头上，对于项目 A→α.Xβ应该采用移进，若有完整的项目B→r.且Follow(B)中有X，当X出现在读头上时，此时应该归约，于是，就产生了移进和归约冲突
b.假设Follow(A)∩Follow(B)为{ X },对于A→α.，若Follow(A)[A后面的元素]出现时，应该归约，同理B也一样，于是，会产生归约－归约冲突，SLR(1)是为了消除LR(0)的两个冲突。
LR(1)1.在每个项目中增加搜索符。2.举个列子如有A-&α.Bβ，则还需将B的规则也加入。
LALR(1)就是假如两个产生式集相同则将它们合并为一个，几合并同心集
见到First集就移进，见到Follow集就归约。
LR(0):见到First集就移进，见到终态就归约
SLR(1)见到First集就移进，见到终态先看Follow集，与Follow集对应的项目归约，其它报错。
SLR分析法包含的展望信息是体现在利用了Follow(A)信息，可以解决“归约－归约”冲突
SLR分析法没有包含足够的展望信息，不能完成解决“移进－归约”冲突，需要改进。
下面是LR(0),SLR(1),LALR(1),LR(1)文法处理能力的比较，圆圈越大说明能力越强。
&&&&推荐文章:
【上篇】【下篇】