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

文档介绍：第五章语法分析 ——自下而上分析
自下而上分析:从输入串开始,逐步进行“归约”,直至归
约到文法的开始符号。
自下而上分析基本问题
归约
自下而上分析法是“移进——归约”法。
模型:
①移进
②归约
③识别成功
④其他出错
字符串:bab
A→ba
#
b
#
b
a
#
A
归约
自下而上分析基本问题
(单词+结束符#)
,初态指在最左单词上,栈内仅有#
:
①移进——读入一单词并压入栈内,读头下移一位
②归约——检查栈顶若干符号是否为语法表中产生式右部,若是,用左部替换右部
③识别成功——栈内为文法开始符号,读头指向#
④否则,语法错误
program
Id
Var
……
#
语法分析程序
分析表
#
输入串:
下推栈,
初态为#,
字符“先进后出”
如:
S→aAcBe
A→Ab|b
B→d
分析:abbcde
S
a
A
c
B
e
A
b
d
b
规范规约简述
、直接短语、句柄
短语:已知文法G[S],αβδ是文法G的一个句型,若S αAδ且Aβ,则称β是句型αβδ的相对于非终结符A的短语。
直接短语:若有SαAδ且Aβ,称β是句型αβδ的相对于规则A→β的直接短语。
句柄:一个句型的最左直接短语称为该句型的句柄。
*
+
*
例:G: E → E+T | E-T | T
T → T*F | T/F | F
F →(E) | i
给出句型E+T*F+i的短语、直接短语和句柄。
例: G: E→E+T | T 句型E+T*F+i
T→T*F | F
F→(E) | i
短语: E+T*F+i, E+T*F, T*F,i
直接短语: T*F,i
句柄: T*F
归约方法:形成句柄则进行归约。
abbcde A→b
aAbcde A→b
aAcde B→d
aAcBe S→aAcBd
S
:
假定α是文法G的一个句子,称序列αn,αn-1,…α0 是α的一个规范归约,则此序列满足:
(1)αn=α
(2)α0为文法开始符,即α0=S
(3)对任何i,0<i≤n, αi-1是从αi经把句柄替换为相应产生式的左部符号而得到的。
最左推导的逆过程——最右归约
最右推导的逆过程——最左归约
最右推导称为规范推导
最左归约称为规范归约
S
a
A
c
B
e
A
b
d
b
②
①
③
算符优先分析
直观算符优先法
对于文法,任何两个相继出现的终结符(…ab…或…aQb…),有下列三种关系:
a b a的优先性等于b
a b a的优先性高于b
a b a的优先性低于b
注意:这三个关系不同于数学中的“=”,“<”,“>”,此处a b并不一定意味着b a,a b也不一定意味着 b a。
算符优先文法及优先表的构造
(OG):文法G,如果G中每条规则不能有形如A→…BC…(A,B,C∈VN)的规则,则称G为算符文法。
-产生式的文法,对任何终结符a,b∈VT,A,B,C∈VN,
(1)a bG中含有规则A→…ab…或A→…aBb…
(2)a bG中含有规则A→…aB…,而Bb…或BCb…
(3)a bG中含有规则A→…Bb…,而B…a或B…aC
+
+
+
+