自下而上语法分析

(3)规范归约的实质:在移进过程中，当发现栈顶呈现句柄时， 就用相应产生式的左部符号进行替换。
规范归约的中心ห้องสมุดไป่ตู้题：如何寻找或确定一个句型的句柄。
给出了寻找句柄的不同算法就给出了不同的规范归约方法。
12
5.1 自下而上分析基本问题
三、符号栈的使用
1.与LL(1)方法区别：
开始 分析成功
符号栈 # #S
作无法正常进行,此时需调用出错处理程序.
14
例2：有文法：
(1) E->E+T|T (2) T->T*F|F (3) F->(E)|i 对输入串 i1+i2*i3 的规范规约过程：
15
动作
栈
输入缓冲区 (1) E->E+T|T
1) 准备 2) 移进 3) 归约 F→i 4) 归约 T→F 5) 归约 E→T 6) 移进 7) 移进 8) 归约 F→i 9) 归约 T→F 10) 移进 11) 移进 12) 归约 F→i
例: S ⇒(1)aAcBe ⇒(2a) Acde ⇒(3a) Abcde ⇒(4)abbcde
11
5.1 自下而上分析基本问题
2.规范归约
(2)规范推导:即最右推导. 规范句型:由规范推导所得到的句型,称为规范句型. 若文法G是无二义的,则规范推导(最右推导)的逆过程必是 规范归约(最左归约)。
2
5.1 自下而上分析基本问题
举例：已知文法G为(1)SaAcBe (2)Ab (3)AAb (4)Bd 及输入串abbcde
归约过程如下:
e
dBB
b
cc c c
b AA AA A A A
a a aa aa a a a S
动作: 进 进 归 进 归 进 进 归 进 归 步骤: 1 2 3 4 5 6 7 8 9 10
句型 abbcd e aAbcde aAcde aAcBe
归约规则 (2)Ab (3)AAb (4)Bd (1)SaAcBe
S
10
5.1 自下而上分析基本问题
2.规范归约
(1)定义:设α是文法G的一个句子,我们称序列αn, αn-1,…,α0 是α的一个规范归约,若此序列满足: ① αn=α; ② α0=S，S为文法开始符号; ③ 对任何i,0＜i≤n, αi-1是经把αi的句 柄替换为相应产生式的左部符号而得到的. 规范归约是关于α的一个最右推导的逆过程.
S
直接短语： A =>β
句柄：最左直接短语
...............
.......
A
.......
α
γ
................
β
7
例1： E→E+T | T T→T*F | F F→(E) | i i1*i2+i3
E
E+ T
T
F
T*F
i3
F
i2
i1
短语： i1，i2，i3，i1*i2，i1*i2+i3 直接短语： i1，i2，i3 句柄： i1
#
i1+i2*i3# (2) T->T*F|F
#i1
+i2*i3#
(3) F->(E)|i
E
#F
+i2*i3#
#T
+i2*i3#
#E
+i2*i3#
T
#E+ #E+i2
i2*i3# *i3# E
#E+F #E+T
*i3#
*i3# T
T
#E+T*
i3#
#E+T*i3
#F
F
F
#E+T*F
#
13) 归约 T→T*F #E+T
３.自下而上分析的中心问题： 怎样判断栈顶的符号串的可归约性以及如何归约。
各种自下而上分析法的共同特点： 边输入单词符号（移进符号栈），边归约。
即：在从左到右移进输入串的过程中，一旦发现栈顶呈 现可归约串就立即进行归约。
5
5.1 自下而上分析基本问题
二.规范归约简述
１.定义：令Ｇ是一个文法，Ｓ是Ｇ的开始符号， 假定αβδ是文法Ｇ的一个句型，
即Ｓ αβδ*⇒ (1)短语:若Ｓ⇒*αＡδ且Ａ⇒β+,则称β是句型αβδ相对于
非终结符Ａ的短语。 (2)直接短语:若Ａ⇒β，则称β是句型αβδ相对于规则Ａβ
的直接短语。 (3)句柄：一个句型的最左直接短语成为该句型的句柄。
6
5.1 自下而上分析基本问题
规范规约中的概念
短语：β是句型αβγ的短语仅当 S αAγ 且A β
# i1 + i2 * i3
14) 归约 E→所E+得T 的结#E果是：用产生式序列# 表示语法分析树
15) 接受
16
5.2 算符优先分析
算符优先分析： 不是一种规范归约法，是一种自下而上的语法
分析法，关键在于规定算符（即终结符）之间的优 先顺序和结合性质，借助这种优先关系寻找“可归 约串”进行归约。 特点：有利于表达式分析，宜于手工实现。
3
5.1 自下而上分析基本问题
2.自下而上分析的关键: “可归约串”——如何精确定义？
从上例的步骤（５）可发现
“可归约串”的不同定义，形成了不同的自下而上的分析方法。
例： “算符优先分析”中：“最左素短语”——“可归 约串” “规范归约分析”中：“句柄”——“可归约串”
4
5.1 自下而上分析基本问题
输入串 W# #
LL(1)分析:
开始 分析成功
符号栈 #S #
输入串 W# #
13
5.1 自下而上分析基本问题
2.举例：——规范归约（课本88页例5.3） 语法分析对符号栈的使用有四类操作：
“移进”——指把输入串的一个符号移进栈. “归约”——指发现栈顶呈可规约串,并用适当的相应符号 去 “接受替”换—这—个指串宣.布最终分析成功. “出错处理” ——指发现栈顶的内容与输入串相悖,分析工
8
练习： E→E+T | T T→T*F | F F→(E) | i
E+T*F+i
E E+ T
E+T
F
T* F i
短语： E+T*F+i, E+T*F, T*F, i 直接短语： T*F, i 句柄：T*F
9
5.1 自下而上分析基本问题
例2：利用句柄对句子进行归约 对文法(1)SaAcBe; (2)Ab; (3)AAb; (4)Bd 的句子abbcde进行归约。
第五章 语法分析—自下而上分析
5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析法 5.4 语法分析器的自动产生工具YACC（略）
1
5.1 自下而上分析基本问题
一、归约 1.“移进—规约”的思想：
用一个寄存符号的先进后出栈，把输入符号一个 一个地移进栈里，当栈顶形成某个产生式的一个候选 式时，即把栈顶的这一部分替换成（归约为）该产生 式的左部符号。
17
5.2 算符优先分析
一、算符优先文法及优先表构造 1.算符优先文法