编译技术编译原理 (25).pdf

《编译技术编译原理 (25).pdf》由会员分享，可在线阅读，更多相关《编译技术编译原理 (25).pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译技术语 法 分 析本讲纲要LALRL A L R从前面的例子看到，LR(1)分析表的状态数目比较大LALR是在SLR(1)和LR(1)之间进行了文法描述能力与分析表紧凑程度之间做的折衷 SLR(1)文法描述能力稍弱，而由于状态数目较小能够得到高效实现（不必消耗太多内存）LR(1)文法描述能力较强，但是由于状态数目多，分析表较大 LALR的描述能力与分析表大小介乎SLR(1)与LR(1)之间L A L RLALR的做法：合并识别 LR(1)文法的活前缀的DFA中的同心项目集 略去搜索符后它们是相同的集合 例：B bB,$与B bB,b/a 同心的LR(1)项目集构 造 规 范 的 L R 分

2、 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1SS B B,$B bB,$B a,$I2BB b B,b/aB bB,b/aB a,b/aI3Ba,b/aI4aabbS BB,$I5B b B,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/aI8BbbBaaB构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1SS B B,$B bB,$B a,$I2BB b B,b/aB bB,b/aB a,b/aI3Ba,b/aI4aabbS BB,$I5B b B,$B bB,$B a,$I

3、6B bB,$I9B a,$I7B bB,b/aI8BbbBaaB构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S B B,$B bB,$B a,$I2SBB b B,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5BbB,b/a/$I89BbBa构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S B B,$B bB,$B a,$I2SBB b B,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$

4、I47aabbS BB,$I5BbB,b/a/$I89BbBa栈输入0bba$构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S B B,$B bB,$B a,$I2SBB b B,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5BbB,b/a/$I89BbBa栈输入0b36ba$构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S B B,$B bB,$B a,$I2SBB b B,b/a/$B bB,b/a/$B a,b

5、/a/$I36B a,b/a/$I47aabbS BB,$I5BbB,b/a/$I89BbBa栈输入0b36b36a$构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S B B,$B bB,$B a,$I2SBB b B,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5BbB,b/a/$I89BbBa栈输入0b36b36a47$构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S B B,$B bB,$B a,$I2SBB

6、b B,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5BbB,b/a/$I89BbBa栈输入0b36b36B89$构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S B B,$B bB,$B a,$I2SBB b B,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5BbB,b/a/$I89BbBa栈输入0b36B89$构 造 规 范 的 L R 分 析 表S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S

7、 B B,$B bB,$B a,$I2SBB b B,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5BbB,b/a/$I89BbBa栈输入0B2$L A L R合并同心项目集可能会引起冲突 同心集的合并不会引起新的移进-归约冲突如果存在，那么在合并前也存在这样的冲突于是对应的LR(1)文法中存在冲突，矛盾。A,a/bB a,c/dA,xB a,y同心集中有：合并前的LR(1)项目集中有：L A L R合并同心项目集可能会引起冲突 同心集的合并不会引起新的移进-归约冲突 同心集的合并有可能产生新的归约-归约冲突S SS aAd|bBd|aBe|bAeA cB c对对ac有效的项目集有效的项目集A c ,dB c ,e对对bc有效的项目集有效的项目集A c ,eB c ,d合并同心合并同心集后集后A c ,d/eB c ,d/e该文法是该文法是LR(1)的，的，但不是但不是LALR(1)的。的。构 造 L A L R(1)分 析 表构造LR(1)项目集规范族C=I0,I1,In。寻找LR(1)项目集规范族中同心的项目集，用它们的并集代替它们。按构造规范的LR(1)分析表的方式进行构造。编译技术语 法 分 析