LALR分析法的提出

0) S′ →S
1) S→L=R
2) S→R
3) L→*R
4) L→id
5) R→L

LALR (lookahead-LR)分析的基本思想

  • 寻找具有相同核心的LR (1) 项集,并将这些项集合并为一个项集。 所谓项集的核心就是其第一分量的集合

  • 然后根据合并后得到的项集族构造语法分析表

  • 如果分析表中没有语法分析动作冲突,给定的文法就称为LALR (1) 文法,就可以根据该分析表进行语法分析

例:合并同心项集

合并同心项集时产生归约-归约冲突的例子

文法
0) S′→S
1) S→aAd|bBd|aBe|bAe
2) A→c
3) B→c

合并同心项集 不会产生移进- 归约冲突

合并同心项集后,虽然不产生冲突,但可能会推迟错误的发现

LALR(1)的特点

  • 形式上与LR(1)相同

  • 大小上与LR(0)/SLR相当

  • 分析能力介于SLR和LR(1)二者之间:SLR<LALR(1)<LR(1)

  • 合并后的展望符集合仍为FOLLOW集的子集

最后修改日期:2020年6月2日

留言

撰写回覆或留言