![](https://csdnimg.cn/release/download_crawler_static/87313166/bg6.jpg)
拓广文法:假定文法 G 是一个以 S 为开始符号的文法,我们构造一个文法 G’,它包含整
个 G,但它引进了一个不出现在 G 中的非终结符 S’,并加进一个新产生式 S’→S,而这个
S’是 G’的开始符号。那么我们称 G’是 G 的拓广文法。
函数 GO(I,X):函数 GO(I,X)是一个状态转换函数。第一个变元 I 是一个项目集,第二
个变元 X 是一个文法符号。函数值 GO(I,X)定义为 GO(I,X)=CLOSURE(J),其中 J={任何形
如 A→αX•β 的项目 | A→α•Xβ 属于 I}。
2.2 基本原理
项目集构造算法:枚举每个规范句型,然后枚举·的位置,获得所有的项目。
项目集规范族构造算法:假定 I 是文法 G’的任一项目集,定义和构造 I 的闭包
CLOSURE(I) 的 办 法 是 : I 的 任 何 项 目 都 属 于 CLOSURE(I) ; 若 A→α•Bβ 属 于
CLOSURE(I),那么,对任何关于 B 的产生式 B→γ,项目 B→•γ 也属于 CLOSURE(I);重
复执行上述两步骤直至 CLOSURE(I)不再增大为止。
Go(I,a)函数构造算法:遍历所有的项目,如果任意两个项目之间存在边(有向),那
么这两个项目所在的项目规范族之间连上对应的有向边。
LR(0)分析表构造算法:假定项目集规范族 C={I0,I1,…,In}。令每一个项目集 Ik 的下标
k 作为分析器的状态。分析表的 ACTION 子表和 GOTO 子表可按如下方法构造:
令那个包含项目 S’→•S 的集合 Ik 的下标 k 为分析器的初态。若项目 A→α•aβ 属于 Ik 且
GO(Ik , a)= Ij,a 为终结符,置 ACTION[k,a]为“把(j,a)移进栈”,简记为“sj”。若项目 A→α•属
于 Ik,对任何终结符 a(或结束符#),置 ACTION[k,a]为“用产生式 A→α 进行归约”,简记为
“rj”(假 定产生 式 A→α 是文 法 G’ 的第 j 个产生式)。若 项目 S’→S• 属于 Ik ,则置
ACTION[k,#] 为 “ 接 受 ” , 简 记 为 “acc” 。 若 GO(Ik , A)= Ij , A 为 非 终 结 符 , 则 置
GOTO[k,A]=j。分析表中凡不能用规则 1 至 4 填入信息的空白格均填上“报错标志”。
LR(0)分析法的分析过程:遍历输入字符串,对于每一个字符,获取当前状态栈的顶部
的状态值,通过查询 action 表获取的当前的操作是移进、规约还是接受。如果当前操作是
移进,将新的状态放入状态栈当中,当移入的字符放入符号栈中。如果当前操作是规约,
那么将需要规约的部分的状态从状态栈中弹出,将规约后的状态放入状态栈,将规约后的
左部放入符号栈,当前的字符不向下推进。如果接收,则结束。
LR 分析器的基本原理:在逻辑上,一个 LR 分析器有一个输入符号串,一个下推分析
栈,以及一个总控程序和分析表。LR 分析器在总控程序的控制下自左至右扫视输入串的各
个符号,并根据当前分析栈中所存放之文法符号的状况及正注视的输入符号,按分析表的
指示完成相应的分析动作。在分析的每一时刻,分析栈中记录了迄今为止所移进或归约出