第五章
第五章
归约:是指根据文法的产生式规则,把产生式的右部替换成左部符号。
规范规约:
1)短语:
定义:令G是一个文法,S是文法的开始符号,假定abd是文法G的一个句型其中α,β,d∈(VN∪VT)*,A∈VN ,如果有
则b称是句型abd相对于非终结符A的短语。
2)直接短语
特别是,如果有AÞb,则称b是句型abd相对于规则A® b的直接短语。
3)句柄
一个句型的最左直接短语称为该句型的句柄。
定义:假定a是文法G的一个句子,我们称序列
an, an-1,¼ ,a0
是a的一个规范归约,如果此序列满足:
(1) an= a
(2) a0为文法的开始符号,即a0=S
(3) 对任何i,0 < i £ n, ai-1是从ai经把句柄替换成为相应产生式左部符号而得到的。
掌握 用符号栈进行自下而上的语法分析
算符优先分析法
首先定义两个终结符‘a’与‘b’的优先关系
a =.b 表示a的优先性等于b
a >.b 表示a的优先性大于b
a <.b 表示a的优先性小于b
1)算符文法
一个文法,如果它的任一产生式的右部都不含两个相继(并列)的非终结符,即不含如下形式的产生式右部:
…QR…
则我们称该文法为算符文法,也称OG文法
2)定义终结符之间的优先关系
假定G是一个不含e产生式的算符文法。对于任何一对终结符a、b,我们说:
· 1. a =. b 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式
2. a <. b 当且仅当G中含有形如P→…aR…的产生式, 而R b…或R Qb…;
3. a>.b 当且仅当G中含有形如P→…Rb…的产生式,而 R …a或R …aQ。
3)如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一:
a=.b
a>.b
a<.b
则称G是一个算符优先文法(OPG文法)。
构造算符优先关系表
(1)通过检查产生式的每一个候选式可以找出满足a=.b
(即P→…ab…或P→…aQb…的产生式)
(2)为了满足<.和>.,需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):
(3)构造集合FIRSTVT(P)的算法
按其定义,可用下面两条规则来构造集合FIRSTVT(P):
① 若有产生式P→a…或P→Qa…,
则aÎFIRSTVT(P);
② 若aÎFIRSTVT(Q),且有产生式P→Q…,
则aÎFIRSTVT(P)。
(4)同理构造构造集合LASTVT(P)的算法
按其定义,可用下面两条规则来构造集合LASTVT(P):
① 若有产生式P→… a或P→… aQ ,
则aÎ LASTVT(P);
② 若aÎ LASTVT(Q),且有产生式P→… Q ,
则aÎ LASTVT(P)。
(5)有了这两个集合之后,就可以通过检查每个产生式的候选式确定满足关系<.和>.的所有终结符对。
(1)假定有个产生式的一个候选形为
…aP…
那么,对任何bÎFIRSTVT(P),有a <. b。
(2)假定有个产生式的一个候选形为
…Pb…
那么,对任何aÎLASTVT(P),有a >. b。
LR分析法
1. LR分析方法——分析器结构
(1)把历史和展望材料抽象成某些状态。分析栈用来存放这些状态。栈顶的状态都代表了整个历史和已经推测出的展望。
(2)为了有助于明确归约手续,将已归约出的文法符号串也同时放到栈里。
动作表:
ACTION[s,a]:
当状态s面临输入符号a时,应采取什么动作
状态转换表:
GOTO[s,X]:
状态s面对文法符号X时,下一状态是什么
四种动作:
<1>.移进
把(s,a)的下一状态s’=GOTO[s,a] 和输入符号a推进栈,下一输入符号变成现行输入符号.
<2>.归约
指用某产生式A®b进行归约. 假若b的长度为r, 归约动作是A, 去除栈顶r个项,使状态sm-r变成栈顶状态,然后把(sm-r, A)的下一状态s’=GOTO[sm-r,A]和文法符号A推进栈.
<3>.接受
宣布分析成功,停止分析器工作。
<4>.报错
发现源程序含有错误,调用出错处理程序
LR文法
一个文法,如果能构造出一个所有条目都唯一的分析表。
LR(k)文法
最多向前看K个的符号就可以决定动作的LR分析器所分析的文法成为LR(k)文法。
我们最感兴趣的是k=0,1
活前缀:
文法G的活前缀是他的规范句型的前缀,该前缀不超过句柄的右端。
活前缀特点:
该前缀加上被分析串中未被分析的终结符,就可以构成一个规范句型
只要输入串的已扫描部分可归约成一个活前缀,意味着扫描过的部分没有错误
活前缀与句柄间的关系:
(1)活前缀中已含有句柄的全部符号(句柄的符号即为其最右符号)。
(2)活前缀中含句柄的一部分符号(句柄开头的 若干符号与活前缀最右的若干个符号一致)。
(3)活前缀中全然不包含句柄的任何符号
LR(0)项目
在每个产生式的右部适当位置添加一个圆点构成项目。
构造识别活前缀的NFA
1、构造文法的所有产生式的项目,每个项目都为NFA的一个状态。
2、确定初态、句柄识别态、句子识别态。
① 由于S′(起始符)仅在第一产生式的左部出现,因此规定起始符相关的项目1为初态
② 其余每个状态都为活前缀的识别态(终态)
③ 圆点在最后的项目为句柄识别态
④ 第一个产生式的句柄识别态为句子识别态
状态之间的转换关系确定方法如下:
• 若项目i为X→X1X2...Xi-1• Xi…Xn。
项目j为X→X1X2...Xi-1Xi• Xi+1…Xn。
则从状态i到状态j连一条标记为Xi的箭弧。
• 若i为X→g•Ad,k为A→•b,
则从状态i画标记为e的箭弧到状态k。
项目集规范族:
构成识别一个文法活前缀的DFA项目集(状态)的全体称为这个文法的LR(0)项目集规范族。
项目集的闭包:
1.构造G的拓广文法G’
设S为文法G的开始符号,构造一个文法G’,它包含整个文法G,并且引进了一个不出现在G中的非终结符S¢,并加进一个新产生式S¢→S,这个S¢是G¢的开始符号。把G’成为G的拓广文法。(有一个仅含项目S¢→S. 的状态,这就是唯一的“接受”状态)
2.I的闭包CLOSURE(I)
(1) I的任何项目都属于CLOSURE(I);
(2) 若A→a·Bb属于CLOSURE(I),那么,对任何关于B的产生式B→g的项目B→·g也属于CLOSURE(I);
(3) 重复执行上述两步骤直至CLOSURE(I) 不再增大为止
例如:设I={S¢→·E}
则CLOSURE(I)={S¢→·E ,E→·aA, E→·bB}
3.转换函数
定义转换函数如下:
GOTO(I,X)=CLOSURE(J)其中:
I为包含某一项目集的状态,
X为一文法符号,
J={任何形如A→aX•b的项目|A→a•Xb属于I}。
例题: