第五章语法分析自下而上分析.ppt

内容
自下而上分析基本问题
算符优先分析
自下而上分析基本问题
自下而上分析:
从输入开始,逐步进行“归约”,直至归约到文法的开始符号。
归约
自下而上分析法是一种“移进-归约”法。
基本思想:
用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部符号。
归约
例:设文法G[S]:
(1) S  aAcBe
(2) A  b
(3) A  Ab
(4) B  d
试对abbcde进行“移进-归约”分析。
a
bbcde
b
a
bcde
A
a
bcde
b
A
a
cde
A
a
cde
c
A
a
de
d
c
A
a
e
abbcde
e
B
c
A
a
S
归约
例:设文法G[S]:
(1) S  aAcBe
(2) A  b
(3) A  Ab
(4) B  d
试对abbcde进行“移进-归约”分析。
归约
分析树和语法树不一定一致。
自下而上分析过程:边输入单词符号,边归约。
核心问题:识别可归约串
b
d
b
a
c
e
S
A
B
A
规范归约简述
定义:令G是一个文法,S是文法的开始符号,假定是文法G的一个句型,如果有
且
则称是句型相对于非终结符A的短语。
特别是,如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。
规范归约简述
例:文法G[E]:
E→E+T|T T→T*F|F F→(E)|–F|id
考虑文法G[E]上的句子id1+id2*id3。(a)、(b)所示。
分析树中的叶子与短语、直接短语和句柄有下述关系。
①短语:以非终结符为根的子树中所有从左到右排列的叶子;
②直接短语:只有父子关系的树中所有从左到右排列的叶子(树高为2);
③句柄:最左边父子关系树中所有从左到右排列的叶子(句柄是唯一的)。
id1+id2*id3的最右推导、分析树与短语
(a) 最右推导;(b) 分析树;(c) 短语
根据定义,从文法开始符号经过0步推导得到E1,从E1经过若干步推导得到id1+id2*id3,所以id1+id2*id3是句型id1+id2*id3相对于E1的短语(其中α和δ均为ε,β是句子的全体)。
考虑推导E1 => E2+id2*id3 => T2+id2*id3 => F1+id2*id3 => id1+id2*id3,id1是相对于非终结符E2、T2和F1的短语(其中α为ε,δ为+id2*id3),特别是相对于F1的直接短语,也是句柄。
id1+id2不是句型id1+id2*id3中相对于任何非终结符的短语,因为找不到任何一个非终结符,它的子树中的所有叶子构成id1+id2。
E
F
F
T
T
T
i1
+
*
E
F
i3
i2
规范归约简述
例:考虑文法G[E]:ET|E+T TF|T*F F(E)|i和句型i1*i2+i3:
在一个句型对应的语法树中,以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语,如果子树只有两代,则该短语就是直接短语。
E  E+T  E+F  E+i3  T+i3
 T*F+i3  T*i2+i3  F*i2+i3
 i1*i2+i3
短语: i1,i2,i3, i1*i2, i1*i2+i3
直接短语: i1,i2,i3
句柄: i1