主要内容 自LR(0)分析
主要内容 LR(0)分析
S→·E# E→T● T→(eE E→●E+T E→·E+T E→●T E→·T T→●id 5 T→●id id T→●(E) id T→●(E) ( s→→E· E→E+●T EE●+T T→●id 7TE E·) T→●(E E●+T # T 2 S→E# E→E+T● T→(E G的LRSM
0 S→ • E ＃ E→ • E+T E→ • T T→ • id T→ • ( E ) 1 S→E • ＃ E→E • +T 5 T→id • 3 E→E+ • T T→ • id T→ • (E) 4 E→E+T • 9 E→T • 6 T→( • E) E→ • E+T E→ • T T→ • id T→ • ( E ) 7 T→(E • ) E→E • +T 8 T→(E) • T T ( id E T id )E + id( ( G E 的LRSM + 2 S→E ＃ •＃
LRSM给出了所有的可归活前缀 G LRSM中的每个状态将对应一个饱和项目集: (1)其中一部分是由先驱状态分出来 称为基本项目); (2)一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“”出现在 产 生式右部的最左侧
LRSM给出了所有的可归活前缀 LRSM中的每个状态将对应一个饱和项目集： （1）其中一部分是由先驱状态分出来 (称为基本项目)； （2）一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“ • ”出现在 产 生式右部的最左侧
拿形如A→[P]的项目称为归约型项目 形如A→α[P的项目称为移入型项目 享移入一归约冲突 享归约一归约冲突 享LRSM不能直接用于LR分析 享LRSM提供的信息 (1)合法性检查信息[A→aaB] (2)移入/归约信息[A→aa]; [A→兀° (3)移入/归约后的转向状态信息
形如A→•[P]的项目称为归约型项目 形如A→•[P]的项目称为移入型项目 移入－归约冲突 归约－归约冲突 LRSM不能直接用于LR分析 LRSM提供的信息： （1）合法性检查信息 [A→•a] （2）移入/归约信息 [A→•a]； [A→•] （3）移入/归约后的转向状态信息
#X1x2…xk t S:: s aa;+1…an# 2 移入动作:设S1的a输入边所指向的状态为S* #X1X2 S:oS: 1S i2 ik S it 归约动作:设按A→X+1+…,X进行归约,则首先归约为A #X1X2 XuA S: oS i 1 i2 S的A输出边所指向的状态设为S*,则格局变为: #X1X2 A SS:1s Sik S
# X1 X2 … Xk … Xt Si0 Si1 Si2 … Sik … Sit aiai+1…an # 移入动作：设Sit的ai输入边所指向的状态为S* # X1 X2 … Xk … Xt Si0 Si1 Si2 … Sik … Sit ai S * 归约动作：设按A→Xk+1Xk+2…Xt进行归约，则首先归约为A Sik的A输出边所指向的状态设为S*，则格局变为： # X1 X2 … Xk Si0 Si1 Si2 … Sik A S * 设当前格局是： # X1 X2 … Xk Si0 Si1 Si2 … Sik A
LR分析模型 nput a a a.# . X LR分析驱动器 Output action goto Stack
LR分析模型 Output Stack a1 … ai … an # LR分析驱动器 action goto Input St Xt … …
LR分析表 Action矩阵:行代表状态,列代表输入 符,而矩阵元素则表示相应的分析动作: Shift Reduce?/Accept / Error GoTo矩阵:行代表状态,而列则代表语 法符号(非终极符,终极符),而矩阵 元素则表示归约后的转向状态
LR分析表 ◼ Action矩阵：行代表状态，列代表输入 符，而矩阵元素则表示相应的分析动作： Shift / Reduce? / Accept / Error ◼ GoTo矩阵：行代表状态，而列则代表语 法符号（非终极符，终极符），而矩阵 元素则表示归约后的转向状态
LR(0投影函数r0 动作集Ω:[ Shift, Reduce1, Reduce2, ■投影函数ro: State Set→22 r°(S)={ Reduce jB→πeS,且B→是产生式j U(if(存在X→0aβ∈S且aeV) then Shift)
LR(0)投影函数 0 ◼ 动作集: {Shift,Reduce1,Reduce2, ... } ◼ 投影函数 0：StateSet→2 0(S)={Reduce j|B→•S,且B→是产生式j} ∪(if (存在X→•aS 且aVT ) then {Shift} )
LR(0)文法 如果其LRSM的每个状态S都有|r(S)|=1, 即r0S)只包含一个元素,我们称文法G 是LR(0)文法。 若r0()={ Shift},则表示S只含移入 项目 若r°(S)=[ Reduce j},则表示S只含 个[门归约项目。 每个状态的移入/归约动作的确定没有冲 突,而且不依赖于输入符号
LR(0)文法 ◼ 如果其LRSM0的每个状态S都有| 0(S)|=1， 即 0(S)只包含一个元素，我们称文法G 是LR(0)文法。 ◼ 若 0(S)={ Shift }，则表示S只含移入 项目 ◼ 若 0(S)={ Reduce j }，则表示S只含一 个[j]归约项目。 每个状态的移入/归约动作的确定没有冲 突，而且不依赖于输入符号
Action表的构造 Action(S= Shift 当I0(S)= Shi ft Action( S)=Reduce j ..To(S)=Reduce j (j不是拓广产生式号 Action( S)=Accept .当I0(S)= Reduce j (是拓广产生式号) ■ Action(S)= Error.. ●●●●●。●● 当I0(S)= Action(⊙)= Error 是特别引进的 错误状态标记
Action表的构造 ◼ Action( S)= Shift .......当0 (S)=Shift ◼ Action( S)= Reduce j ...当0 (S)=Reduce j （j不是拓广产生式号） ◼ Action( S)= Accept ....当0 (S)=Reduce j （j是拓广产生式号） ◼ Action( S)= Error ...………当0 (S)= ◼ Action()= Error .……… 是特别引进的 错误状态标记