5.1 引言
5.2 简单优先分析技术
5.3 算符优先分析技术
5.4 LR(k)分析技术
本章小结
第五章 语法分析 ----自底向上分析技术
5.1 引言
5.1.1 自底向上分析技术及识别算法
5.1.2 讨论的前提
5.1.3 基本实现方法
第五章 语法分析 ----自底向上分析技术
5.1 引言
5.1.1 自底向上分析技术及识别算法
基本思想是，从输入符号串出发，在每一分析步对相
应句型中的某个简单短语进行归约。如果最终能归约到识
别符号，则该输入符号串是相应文法的句子，否则就不是。
当句型分析过程中每个分析步都对最左的简单短语进
行直接归约时，自底向上分析技术的两个基本问题可以更
确切地叙述为：如何找出句柄及把此句柄直接归约为哪个
非终结符号。
第五章 语法分析 ----自底向上分析技术
5.1 引言
5.1.1 自底向上分析技术及识别算法
5.1.2 讨论的前提
识别过程是从左到右, 自底向上地进行的, 一般都将采
用规范归约；除了特别指明的以外, 每一步总是对句柄 ——
最左的简单短语进行直接归约 。
第五章 语法分析 ----自底向上分析技术
5.1 引言
5.1.1 自底向上分析技术及识别算法
5.1.2 讨论的前提
5.1.3 基本实现方法
采用自底向上分析技术时, 通常以移入 -归约法为基础 。
一般地, 动作共有 4类, 即移入, 归约, 接受与报错 。
? 移入：读入下一个输入符号并把它下推进栈；
? 归约：当栈顶的 (部分 )符号串形成一个句柄时, 对此句柄进行直接归约；
? 接受：当识别程序发现栈中除了栈底标志符号 #外仅有识别符号, 而输
入也已到达右端 #,则接受；
? 报错：当识别程序察觉一个错误, 因此输入符号串不是句子而无法继续
识别工作时, 调用一个出错处理子程序进行处理或停止 。
第五章 语法分析 ----自底向上分析技术
? 移入：读入下一个输入符号并把它下推进栈；
? 归约：当栈顶的 (部分 )符号串形成一个句柄时, 对此句柄进行直接归约；
? 接受：当识别程序发现栈中除了栈底标志符号 #外仅有识别符号, 而输
入也已到达右端 #,则接受；
? 报错：当识别程序察觉一个错误, 因此输入符号串不是句子而无法继续
识别工作时, 调用一个出错处理子程序进行处理或停止 。
步骤 栈 输入 动作 规则
（ 1 ）
（ 2 ）
（ 3 ）
（ 4 ）
（ 5 ）
（ 6 ）
（ 7 ）
（ 8 ）
（ 9 ）
（ 10 ）
（ 11 ）
#
# i
#E
#E*
#E*i
#E*E
#E
#E+
#E+i
#E+E
#E
i*i+i#
*i+i#
*i+i#
i+i#
+i#
+i#
+i#
i#
#
#
#
移入
归约
移入
移入
归约
归约
移入
移入
归约
归约
接受
E ∷ =i
E ∷ =i
E ∷ =E*E
E ∷ =i
E ∷ =E+E
例 5.1 设有文法 G[E],E∷=E+E|E*E|(E)|i
5.2 简单优先分析技术
5.2.1优先关系与优先文法
5.2.2简单优先分析技术的实现
5.2.3简单优先分析技术的局限性及克服
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
? 寻找句柄的基本思想
? 优先关系及其应用
? 简单优先文法
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
? 寻找句柄的基本思想
? 优先关系及其应用
? 简单优先文法
第五章 语法分析 ----自底向上分析技术
Sk± Sl表示 Sk与 Sl优先级相同,
它们同时成为句柄的一部分；
Sk Sl表示 Sk优先级大于 Sl,也
可称 Sk优先于 Sl,Sk先于 Sl成为
句柄的一部分；
Sk Sl表示 Sk优先级小于 Sl,Sk
后于 Sl成为句柄的一部分 。
5.2 简单优先分析技术
5.2.1优先关系与优先文法
? 寻找句柄的基本思想 Z M L a b ( )
? 优先关系及其应用 Z
? 简单优先文法 M ± ±
L
a ±
b ±
( ±
)
例 设有文法 G[Z],Z∷=bMb M∷=(L|a L∷=Ma)
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
? 寻找句柄的基本思想
? 优先关系及其应用
? 简单优先文法
定义 5.2 如果某个文法 G满足下列条件,
条件 1 其字汇表中的任意两个符号之间至多有一种
优先关系成立；
条件 2 任何两个重写规则都没有相同的右部, 则称文
法 G是简单优先文法, 简称优先文法或 (1,1)优先文法 。
一个简单优先文法是无二义性的
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
5.2.2简单优先分析技术的实现
简单优先分析技术的实现思想,
第一步,每次把栈顶符号 Si与当前正扫描 (读入 )的符号 Sl比
较优先级别, 如果不是 Si Sl,便把 Sl下推入栈, 继续扫描
输入符号, 直到 Si Sl,这时找到栈顶符号 Si是句柄尾符号,
整个句柄已在栈中, 因而回头, 在栈中自顶向底寻找优先关
系 成立的相邻两个符号 Sj－ 1与 Sj,Sj－ 1 Sj。 这时找到了句
柄的头符号 Sj。
第二步,把栈中构成句柄的子串 Sj…Si替换为相应的非终结符号 。
重复上述过程, 直到再无输入符号而仅为右端标志符号 #，
且栈中仅包含识别符号连同左端标志符号 #。
简单优先分析技术的实现思想,
例 设有文法 G[Z],
Z∷=bMb M∷=(L|a L∷=Ma)
识别输入符号串 b(aa)b是否是文法的句子。
优先矩阵,
Z M L a b ( )
Z
M ± ±
L
a ±
b ±
( ±
)
5.2 简单优先分析技术
5.2.1优先关系与优先文法
5.2.2简单优先分析技术的实现
? 优先关系与文法规则的表示法
优先矩阵的表示法,
优先矩阵 P的每个元素 Pij,
Pij=0 如果 Si与 Sj之间无优先关系
Pij=1 如果 Si Sj
Pij=2 如果 Si ± Sj
Pij=3 如果 Si Sj
? 文法规则的表示法
例 设有文法 G[E],E∷=E+E|E*E|(E)|i
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
5.2.2简单优先分析技术的实现
5.2.3简单优先分析技术的局限性及克服
? 只能应用于简单优先文法
? 构造优先关系困难，尤其是优先矩阵体积的激增
第五章 语法分析 ----自底向上分析技术
5.3 算符优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
5.3.4算符优先文法句型的识别
5.3.5算符优先技术与简单优先技术的比较
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
1) 找出句柄 u;
2) 找出规则 U∷=u ；
3) 把 u直接归约成 U。
算术表达式求值规则,
（ 1） 先乘除后加减,2+3× 5
（ 2） 左结合性,9－ 7+5
因此, 将文法中的终结符号 运算符；
非终结符号 运算对象 。
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
? 定义
? 性质
? 对 C语言的简单讨论
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
? 定义
? 性质
? 对 C语言的简单讨论
第五章 语法分析 ----自底向上分析技术
定义 5.7 如果文法 G 中没有形如
U∷= …VW…
的规则, 其中 U,V,W∈V N,则该文法 G称
为算符文法, 缩写为 OG。
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
? 定义
? 性质
? 对 C语言的简单讨论
第五章 语法分析 ----自底向上分析技术
定理 5.9 对于算符文法, 不存在包含有两个
相邻非终结符号的句型 。
定理 5.10 如果 TU出现在句型 w中, 其中 T∈V T，
U∈V N,则 w中任何包含其中之 T的短语也必包
含其中之 U。
定理 5.11 如果 UT出现在句型 w中, 其中 T∈V T,
U∈V N,则 w中任何包含其中之 T的短语也必包
含其中之 U。
定理 5.12 在算符文法的任何句型中, 不存在
其紧前与紧后是非终结符号的短语 。
句型的一般形式, [N1]T1[N2]T2… [Nn]Tn[Nn+1]
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
? 定义
? 性质
? 对 C语言的简单讨论
第五章 语法分析 ----自底向上分析技术
<条件语句 >∷=if(< 布尔表达式 >)<语句 >|
if(<布尔表达式 >)<语句 ><否则部分 >
<否则部分 >∷=else< 语句 >
<项 >∷=< 项 ><乘法运算符 ><因式 >|<因式 >
<乘法运算符 >= * | / | % | && | ||
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
? 算符优先关系
? 算符优先文法
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
? 算符优先关系
? 算符优先文法
第五章 语法分析 ----自底向上分析技术
定义 5.8 设文法 G是一个算符文法, Tj与 Ti是两个任意的终结符号, 而
U,V,W∈V N,定义算符优先关系如下,
Tj=Ti 当且仅当文法 G中存在形如 U∷= …TjTi…或 U∷= …TjVTi…的规则；
Tj＜ Ti 当且仅当文法 G中存在形如 U∷= …TjV…的规则, 其中 V=>Ti…或 V=>WTi…；
Tj＞ Ti 当且仅当文法 G中存在形如 U∷= …VTi…的规则, 其中 V=>…Tj或 V=>…TjW。
例 设有文法 G[Z],Z∷=E E∷=T|E+T T∷=F|T*F F∷=(E)|i +
+
+
+
i + * ( )
i > > >
+ < > < < >
* < > > < >
( < < < < =
) > > >
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
? 算符优先关系
? 算符优先文法
第五章 语法分析 ----自底向上分析技术
定义 5.11 设有算符文法 G,如果在它的任意
两个终结符号之间, 算符优先关系 =,＜与
＞至多只有一种关系成立, 则称该文法 G为算
符优先文法, 缩写为 OPG。
例 1 文法 G[Z],Z∷=E E∷=T|E+T
T∷=F|T*F F∷=(E)|i
例 2 文法 G[E],
E∷=E+E|E*E|(E)|i
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
5.3.4算符优先文法句型的识别
? 质短语
? 算符优先识别算法
第五章 语法分析 ----自底向上分析技术
定义 5.12 设有算符文法 G[Z],(句型的 )质短语定义为这样一个
短语：它至少包含一个终结符号, 且除它自身外不再包含其他质
短语 。
例 1 文法 G[Z],Z∷=E E∷=T|E+T T∷=F|T*F F∷=(E)|i
定理 5.14 一个算符优先文法句型 [N1]T1[N2]…[Nn]Tn[Nn+1]的最
左质短语是满足条件,Tj－ 1 < Tj = Tj+1 = … = Ti－ 1 = Ti > Ti+1
的最左子符号串 [ Ｎ j]Tj[Nj+1]… [Ni]Ti[Ni+1], 其中的
Nk(k=1,2,…, n+1)可能有也可能无 。
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
5.3.4算符优先文法句型的识别
? 质短语
? 算符优先识别算法
例 文法 G[Z],Z∷=E E∷=T|E+T
T∷=F|T*F F∷=(E)|i
设有输入符号串 i+(i+i)*i,
试识别它是否是文法的句子。
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
5.3.4算符优先文法句型的识别
5.3.5算符优先技术与简单优先技术的比较
第五章 语法分析 ----自底向上分析技术
项目 简单优先技术 算符优先技术
优先关系 简单优先关系 算符优先关系
关系定义集 字汇表 终结符号集
归约方式 规范归约 规范归约
被归约者 最左简单短语 S
j
…S
i
,它满足 最左质短语 T
j
… T
i
,它满足
归约条件 S
j-1
<S
j
± S
j + 1
± … ± S
i-1
± S
I
>S
i + 1
T
j-1
< T
j
= T
j + 1
= … = T
i - 1
= T
i
> T
i + 1
识别算法之控制手段 优先矩阵或优先函数 优先矩阵或优先函数
实现工具 栈 （符号栈） 栈 （运算符栈与运算分量 栈）
存储容量 优先矩阵较大 优先矩阵小
功效 低 更高
对语义子程序的要求 少 做更多的检查工作
适用范围 简单优先文法 算符优先文法
5.2 简单优先分析技术
5.3 算符优先分析技术
5.4 LR(k)分析技术
本章小结
第五章 语法分析 ----自底向上分析技术
5.1 引言
5.1.1 自底向上分析技术及识别算法
5.1.2 讨论的前提
5.1.3 基本实现方法
第五章 语法分析 ----自底向上分析技术
5.1 引言
5.1.1 自底向上分析技术及识别算法
基本思想是，从输入符号串出发，在每一分析步对相
应句型中的某个简单短语进行归约。如果最终能归约到识
别符号，则该输入符号串是相应文法的句子，否则就不是。
当句型分析过程中每个分析步都对最左的简单短语进
行直接归约时，自底向上分析技术的两个基本问题可以更
确切地叙述为：如何找出句柄及把此句柄直接归约为哪个
非终结符号。
第五章 语法分析 ----自底向上分析技术
5.1 引言
5.1.1 自底向上分析技术及识别算法
5.1.2 讨论的前提
识别过程是从左到右, 自底向上地进行的, 一般都将采
用规范归约；除了特别指明的以外, 每一步总是对句柄 ——
最左的简单短语进行直接归约 。
第五章 语法分析 ----自底向上分析技术
5.1 引言
5.1.1 自底向上分析技术及识别算法
5.1.2 讨论的前提
5.1.3 基本实现方法
采用自底向上分析技术时, 通常以移入 -归约法为基础 。
一般地, 动作共有 4类, 即移入, 归约, 接受与报错 。
? 移入：读入下一个输入符号并把它下推进栈；
? 归约：当栈顶的 (部分 )符号串形成一个句柄时, 对此句柄进行直接归约；
? 接受：当识别程序发现栈中除了栈底标志符号 #外仅有识别符号, 而输
入也已到达右端 #,则接受；
? 报错：当识别程序察觉一个错误, 因此输入符号串不是句子而无法继续
识别工作时, 调用一个出错处理子程序进行处理或停止 。
第五章 语法分析 ----自底向上分析技术
? 移入：读入下一个输入符号并把它下推进栈；
? 归约：当栈顶的 (部分 )符号串形成一个句柄时, 对此句柄进行直接归约；
? 接受：当识别程序发现栈中除了栈底标志符号 #外仅有识别符号, 而输
入也已到达右端 #,则接受；
? 报错：当识别程序察觉一个错误, 因此输入符号串不是句子而无法继续
识别工作时, 调用一个出错处理子程序进行处理或停止 。
步骤 栈 输入 动作 规则
（ 1 ）
（ 2 ）
（ 3 ）
（ 4 ）
（ 5 ）
（ 6 ）
（ 7 ）
（ 8 ）
（ 9 ）
（ 10 ）
（ 11 ）
#
# i
#E
#E*
#E*i
#E*E
#E
#E+
#E+i
#E+E
#E
i*i+i#
*i+i#
*i+i#
i+i#
+i#
+i#
+i#
i#
#
#
#
移入
归约
移入
移入
归约
归约
移入
移入
归约
归约
接受
E ∷ =i
E ∷ =i
E ∷ =E*E
E ∷ =i
E ∷ =E+E
例 5.1 设有文法 G[E],E∷=E+E|E*E|(E)|i
5.2 简单优先分析技术
5.2.1优先关系与优先文法
5.2.2简单优先分析技术的实现
5.2.3简单优先分析技术的局限性及克服
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
? 寻找句柄的基本思想
? 优先关系及其应用
? 简单优先文法
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
? 寻找句柄的基本思想
? 优先关系及其应用
? 简单优先文法
第五章 语法分析 ----自底向上分析技术
Sk± Sl表示 Sk与 Sl优先级相同,
它们同时成为句柄的一部分；
Sk Sl表示 Sk优先级大于 Sl,也
可称 Sk优先于 Sl,Sk先于 Sl成为
句柄的一部分；
Sk Sl表示 Sk优先级小于 Sl,Sk
后于 Sl成为句柄的一部分 。
5.2 简单优先分析技术
5.2.1优先关系与优先文法
? 寻找句柄的基本思想 Z M L a b ( )
? 优先关系及其应用 Z
? 简单优先文法 M ± ±
L
a ±
b ±
( ±
)
例 设有文法 G[Z],Z∷=bMb M∷=(L|a L∷=Ma)
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
? 寻找句柄的基本思想
? 优先关系及其应用
? 简单优先文法
定义 5.2 如果某个文法 G满足下列条件,
条件 1 其字汇表中的任意两个符号之间至多有一种
优先关系成立；
条件 2 任何两个重写规则都没有相同的右部, 则称文
法 G是简单优先文法, 简称优先文法或 (1,1)优先文法 。
一个简单优先文法是无二义性的
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
5.2.2简单优先分析技术的实现
简单优先分析技术的实现思想,
第一步,每次把栈顶符号 Si与当前正扫描 (读入 )的符号 Sl比
较优先级别, 如果不是 Si Sl,便把 Sl下推入栈, 继续扫描
输入符号, 直到 Si Sl,这时找到栈顶符号 Si是句柄尾符号,
整个句柄已在栈中, 因而回头, 在栈中自顶向底寻找优先关
系 成立的相邻两个符号 Sj－ 1与 Sj,Sj－ 1 Sj。 这时找到了句
柄的头符号 Sj。
第二步,把栈中构成句柄的子串 Sj…Si替换为相应的非终结符号 。
重复上述过程, 直到再无输入符号而仅为右端标志符号 #，
且栈中仅包含识别符号连同左端标志符号 #。
简单优先分析技术的实现思想,
例 设有文法 G[Z],
Z∷=bMb M∷=(L|a L∷=Ma)
识别输入符号串 b(aa)b是否是文法的句子。
优先矩阵,
Z M L a b ( )
Z
M ± ±
L
a ±
b ±
( ±
)
5.2 简单优先分析技术
5.2.1优先关系与优先文法
5.2.2简单优先分析技术的实现
? 优先关系与文法规则的表示法
优先矩阵的表示法,
优先矩阵 P的每个元素 Pij,
Pij=0 如果 Si与 Sj之间无优先关系
Pij=1 如果 Si Sj
Pij=2 如果 Si ± Sj
Pij=3 如果 Si Sj
? 文法规则的表示法
例 设有文法 G[E],E∷=E+E|E*E|(E)|i
第五章 语法分析 ----自底向上分析技术
5.2 简单优先分析技术
5.2.1优先关系与优先文法
5.2.2简单优先分析技术的实现
5.2.3简单优先分析技术的局限性及克服
? 只能应用于简单优先文法
? 构造优先关系困难，尤其是优先矩阵体积的激增
第五章 语法分析 ----自底向上分析技术
5.3 算符优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
5.3.4算符优先文法句型的识别
5.3.5算符优先技术与简单优先技术的比较
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
1) 找出句柄 u;
2) 找出规则 U∷=u ；
3) 把 u直接归约成 U。
算术表达式求值规则,
（ 1） 先乘除后加减,2+3× 5
（ 2） 左结合性,9－ 7+5
因此, 将文法中的终结符号 运算符；
非终结符号 运算对象 。
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
? 定义
? 性质
? 对 C语言的简单讨论
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
? 定义
? 性质
? 对 C语言的简单讨论
第五章 语法分析 ----自底向上分析技术
定义 5.7 如果文法 G 中没有形如
U∷= …VW…
的规则, 其中 U,V,W∈V N,则该文法 G称
为算符文法, 缩写为 OG。
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
? 定义
? 性质
? 对 C语言的简单讨论
第五章 语法分析 ----自底向上分析技术
定理 5.9 对于算符文法, 不存在包含有两个
相邻非终结符号的句型 。
定理 5.10 如果 TU出现在句型 w中, 其中 T∈V T，
U∈V N,则 w中任何包含其中之 T的短语也必包
含其中之 U。
定理 5.11 如果 UT出现在句型 w中, 其中 T∈V T,
U∈V N,则 w中任何包含其中之 T的短语也必包
含其中之 U。
定理 5.12 在算符文法的任何句型中, 不存在
其紧前与紧后是非终结符号的短语 。
句型的一般形式, [N1]T1[N2]T2… [Nn]Tn[Nn+1]
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
? 定义
? 性质
? 对 C语言的简单讨论
第五章 语法分析 ----自底向上分析技术
<条件语句 >∷=if(< 布尔表达式 >)<语句 >|
if(<布尔表达式 >)<语句 ><否则部分 >
<否则部分 >∷=else< 语句 >
<项 >∷=< 项 ><乘法运算符 ><因式 >|<因式 >
<乘法运算符 >= * | / | % | && | ||
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
? 算符优先关系
? 算符优先文法
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
? 算符优先关系
? 算符优先文法
第五章 语法分析 ----自底向上分析技术
定义 5.8 设文法 G是一个算符文法, Tj与 Ti是两个任意的终结符号, 而
U,V,W∈V N,定义算符优先关系如下,
Tj=Ti 当且仅当文法 G中存在形如 U∷= …TjTi…或 U∷= …TjVTi…的规则；
Tj＜ Ti 当且仅当文法 G中存在形如 U∷= …TjV…的规则, 其中 V=>Ti…或 V=>WTi…；
Tj＞ Ti 当且仅当文法 G中存在形如 U∷= …VTi…的规则, 其中 V=>…Tj或 V=>…TjW。
例 设有文法 G[Z],Z∷=E E∷=T|E+T T∷=F|T*F F∷=(E)|i +
+
+
+
i + * ( )
i > > >
+ < > < < >
* < > > < >
( < < < < =
) > > >
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
? 算符优先关系
? 算符优先文法
第五章 语法分析 ----自底向上分析技术
定义 5.11 设有算符文法 G,如果在它的任意
两个终结符号之间, 算符优先关系 =,＜与
＞至多只有一种关系成立, 则称该文法 G为算
符优先文法, 缩写为 OPG。
例 1 文法 G[Z],Z∷=E E∷=T|E+T
T∷=F|T*F F∷=(E)|i
例 2 文法 G[E],
E∷=E+E|E*E|(E)|i
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
5.3.4算符优先文法句型的识别
? 质短语
? 算符优先识别算法
第五章 语法分析 ----自底向上分析技术
定义 5.12 设有算符文法 G[Z],(句型的 )质短语定义为这样一个
短语：它至少包含一个终结符号, 且除它自身外不再包含其他质
短语 。
例 1 文法 G[Z],Z∷=E E∷=T|E+T T∷=F|T*F F∷=(E)|i
定理 5.14 一个算符优先文法句型 [N1]T1[N2]…[Nn]Tn[Nn+1]的最
左质短语是满足条件,Tj－ 1 < Tj = Tj+1 = … = Ti－ 1 = Ti > Ti+1
的最左子符号串 [ Ｎ j]Tj[Nj+1]… [Ni]Ti[Ni+1], 其中的
Nk(k=1,2,…, n+1)可能有也可能无 。
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
5.3.4算符优先文法句型的识别
? 质短语
? 算符优先识别算法
例 文法 G[Z],Z∷=E E∷=T|E+T
T∷=F|T*F F∷=(E)|i
设有输入符号串 i+(i+i)*i,
试识别它是否是文法的句子。
第五章 语法分析 ----自底向上分析技术
5.3 简单优先分析技术
5.3.1算符优先分析技术的引进
5.3.2算符文法
5.3.3算符优先关系与算符优先文法
5.3.4算符优先文法句型的识别
5.3.5算符优先技术与简单优先技术的比较
第五章 语法分析 ----自底向上分析技术
项目 简单优先技术 算符优先技术
优先关系 简单优先关系 算符优先关系
关系定义集 字汇表 终结符号集
归约方式 规范归约 规范归约
被归约者 最左简单短语 S
j
…S
i
,它满足 最左质短语 T
j
… T
i
,它满足
归约条件 S
j-1
<S
j
± S
j + 1
± … ± S
i-1
± S
I
>S
i + 1
T
j-1
< T
j
= T
j + 1
= … = T
i - 1
= T
i
> T
i + 1
识别算法之控制手段 优先矩阵或优先函数 优先矩阵或优先函数
实现工具 栈 （符号栈） 栈 （运算符栈与运算分量 栈）
存储容量 优先矩阵较大 优先矩阵小
功效 低 更高
对语义子程序的要求 少 做更多的检查工作
适用范围 简单优先文法 算符优先文法
