第四章第5节 LR(1)分析

LR(1)分析法的提出

SLR分析存在的问题
SLR只是简单的考察下一个输入符号b是否是属于与归约项目A->α 相关的 FOLLOW(A)，但 b∈ FOLLOW(A) ,但 b∈FOLLOW(A) 只是归约a的一个必要条件，而非充分条件

LR(1)分析法的提出

对于产生式A->α的归约，在不同的使用位置，A会要求不同的后继符号

image.png

在特定位置，A 的后继符集合是 FOLLOW(A)的子集

规范LR(1)项目

将一般形式为[A->α·β,a]的项称为 LR(1)项 ，其中A->αβ是一个产生式，a 是一个终结符（这里将$视为一个特殊的终结符）它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符
LR(1)中的1 是指的项的第二个分量的长度
在形如[A->α·β，a] 且 β≠ ε 的项中，展望符 a 没有任何作用
但是一个形如[A->α·，a] 的项在只有在下一个输入符号等于a时 才可以按照A->α进行归约
这样的a集合总是FOLLOW(A)的子集，而且它通常是一个真子集

等价LR(1)项目

image.png image.png image.png image.png image.png image.png

LR(1)项目集闭包

image.png

GOTO 函数

image.png image.png

LR(1)自动机的形式化定义

image.png

LR分析表构造算法

image.png