唐诗五百首
编译原理LR分析（主要是LR（0）分析）
⼀、LR分析的基本原理
1、LR分析的基本思想
LR⽅法的基本思想就是，在规范归约的过程中，⼀⽅⾯要记住已移进和归约出的整个字符串，也就是说要记住历史；⼀⽅⾯能够根据所⽤的产⽣式的推测未来可能碰到的输⼊符号，也就是说能够对未来进⾏展望。这样，当⼀串貌似句柄的字符串出现在分析栈的顶部时，我们希望能够根据历史和展望以及现实的输⼊符号这三部分的材料，决定出现在栈顶的这⼀串符号是否就是我们要找的句柄。
2、LR分析器的构成
采⽤下推⾃动机这种数据模型。包括以下⼏个部分：
1.输⼊带
2.分析栈：包括状态栈和⽂法符号栈两部分。(s0,#)为分析开始前预先放在栈⾥的初始状态和句⼦括号。
3.LR 分析表：包括动作表和状态转移表两张表。
3、LR分析表是LR分析器的核⼼部分
⼀张LR分析表包括两部分：动作表(ACTION)和状态转换表(GOTO)。它们都是⼆维数组。ACTION[s,a]规定了当状态s⾯临输⼊符号a时应采取什么动作(移进、归约、接受和报错)，⽽GOTO[s,X]规定了当状态s⾯对⽂法符号X(终结符或⾮终结符)时的下⼀状态是什么。
显然， GOTO[s,X]定义了⼀个以⽂法符号为字母表的DFA。
不同的 LR 分析法构造LR分析表的⽅法都不同，由此产⽣了不同的LR分析法。
4、LR分析算法
置ip指向输⼊串w的第⼀个符号
令Si为栈顶状态
a是ip指向的符号（当前输⼊符号）
BEGIN(重复开始)
IF ACTION[Si,a]=Sj THEN
民办学校BEGIN
PUSH j,a (进栈)
ip前进(指向下⼀输⼊符号)
END
ELSEIF ACTION[Si,a]=rj(若第j条产⽣式为A→β) THEN
BEGIN
pop|β| 项
若当前栈顶状态为Sk
pushGOTO[Sk,A] 和A(进栈)
杏花天影 END
ELSEIF ACTION[Si,a]=acc THEN
return (成功）
ELSE error
END. (重复结束)
⼆、LR（0）分析器
1、可归前缀与规范句型的活前缀
⽂法G[S]：
(1) S → aAcBe[1]
(2) A → b[2]
(3) A → Ab[3]
(4) B → d[4]
S ÞaAcBe[1]
ÞaAcd[4]e[1]
ÞaAb[3]cd[4]e[1]
Þab[2]b[3]cd[4]e[1]
每次归约句型的前部分依次为：
ab[2]
aAb[3]
aAcd[4]
aAcBe[1]
规范句型的这种前部分符号串称为可归前缀
我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀（活前缀就是可归前缀的前缀）如下：
e,a,ab
小葱e ,a,aA,aAb
e ,a,aA,aAc,aAcd
e ,a,aA,aAc,aAcB,aAcBe
三、LR分析
（⼀）LR分析构造识别活前缀的有穷⾃动机
项⽬（item）：在每个产⽣式的右部适当位置添加⼀个圆点构成项⽬。
根据圆点所在的位置和圆点后是终结符还是⾮终结符把项⽬分为以下⼏种：
移进项⽬，形如 A→a·ab
待约项⽬，形如 A→a·Bb
归约项⽬，形如 A→a·
接受项⽬，形如S’ →S·
根据圆点所在的位置和圆点后是终结符还是⾮终结符把项⽬分为以下⼏种：
移进项⽬，形如 A →a . ab
待约项⽬，形如 A→a . Bb
归约项⽬，形如 A→a .
接受项⽬，形如 S’→S.
把⽂法的所有产⽣式的项⽬都引出，每个项⽬都为NFA的⼀个状态。其中
⽂法的第⼀个产⽣式的第⼀个项⽬为⽂法的初态
放风筝的日记
⽂法的接受项⽬为⽂法的句⼦识别态
⽂法的每⼀个产⽣式的归约项⽬为⽂法的句柄识别态
构造步骤：
项⽬圆点的左部表⽰分析过程的某个时刻⽤该产⽣式归约时句柄已识别的部分，圆点右部表⽰待识别的部分。构造识别活前缀的NFA：
形容努力的词语1、把⽂法的所有产⽣式的项⽬都引出，每个项⽬都为NFA的⼀个状态
方兴未艾是什么意思
2、确定 初态、 句柄识别态、 句⼦识别态
3、确定状态之间的转换关系
*若项⽬i为 X → X i-1·X n
项⽬j为 X → X i-1X i ·X X n
则从状态i到状态j连⼀条标记为X i的箭弧
*若i为X→g ·Ad，k为A→ ·b，则从状态i画标 记为 e的箭弧到状态k
（⼆）将⾮确定的有限⾃动机转换成确定的有穷⾃动机
⽅法⼀：（采⽤⼦集构造法）
⽅法⼆：通过构造⽂法G的LR（0）的项⽬集规范族来直接构造识别活前缀的DFA
LR(0)项⽬集规范族的构造
构成识别⼀个⽂法活前缀的DFA项⽬集（状态）的全体称为这个⽂法的LR(0)项⽬集规范族
（1）通过闭包函数(CLOSURE)来求DFA⼀个状态的项⽬集，找出所有的等价的项⽬。
如果I是⽂法G’的⼀个项⽬集，定义和构造I的闭包CLOSURE(I)如下：
a)I的项⽬都在CLOSURE(I)中
b)若A→a· Bb属于CLOSURE(I)，则每⼀形如B→· g的项⽬也属于CLOSURE(I)
薯片简笔画c)重复b)直到CLOSURE(I)不再扩⼤
（2）定义转换函数如下：
GOTO（I，X）=CLOSURE（J）
其中：I为包含某⼀项⽬集的状态，X为⼀⽂法符号
J={任何形如A→aX ·b的项⽬|A→a·X b属于I}
圆点不在产⽣式右部最左边的项⽬称为核，唯⼀的例外是S’ → · S。因此⽤GOTO（I，X）转换函数得到的J为转向后状态所含项⽬集的核
使⽤闭包函数（CLOSURE）和转向函数(GOTO(I,X))构造⽂法G’的LR(0)的项⽬集规范族，步骤如下：
a)置项⽬S’→ ·S为初态集的核，然后对核求闭包CLOSURE（{S’→ ·S}）得到初态的项⽬集
b)对初态集或其它所构造的项⽬集应⽤转换函数GOTO(I，X)=CLOSURE(J)求出新状态J的项⽬集
c)重复b)直到不出现新的项⽬集为⽌
