第五章语法分析-自下而上分析 51自下而上分析的基本问题 Figure5.5LR演示自下而上分析i+(i+i)*i 原理:自左向右扫描,自下而上分析 从输入符号串入手,通过反复查找当前句型的可归约串, 并使用文法的产生式把它归约成相应的非终结符来一步步地 进行分析的。 最终把输入串归约成文法的开始符号,表明分析成功。 任何自下而上分析方法的关键就是要找出当前句型的 可归约串,然后根据产生式判别将它归约成什么样的非终 结符
第五章 语法分析-自下而上分析 5.1 自下而上分析的基本问题 Figure5.5LR演示自下而上分析 i+(i+i)*i 原理:自左向右扫描，自下而上分析 从输入符号串入手，通过反复查找当前句型的可归约串， 并使用文法的产生式把它归约成相应的非终结符来一步步地 进行分析的。 最终把输入串归约成文法的开始符号，表明分析成功。 任何自下而上分析方法的关键就是要找出当前句型的 可归约串，然后根据产生式判别将它归约成什么样的非终 结符
规范归约基本概念 G为文法,S为开始符号,假定αβδ是G的一个句型,如果 SaA'且AB 则称β是句型aβ8相对于非终结符A的短语。 如果A=>β,则称β是句型aβ8相对于非终结符A的直接短语 最左直接短语称为句柄。 表达式文法的例子i+i*i,找出所有短语,直接短语和句柄 从句子到开始符号的归约序列,如果每一步都是把句柄替换为 相应产生式的左部符号而得到的,则称为规范归约。规范归约 是最右推导(规范推导)的逆过程
规范归约基本概念 如果A=> β，则称β是句型 αβδ相对于非终结符A的直接短语。 G为文法，S为开始符号，假定αβδ是G的一个句型，如果 则称β是句型 αβδ相对于非终结符A的短语。 + S A 且A * 表达式文法的例子 i+i*i,找出所有短语，直接短语和句柄 最左直接短语称为句柄。 从句子到开始符号的归约序列，如果每一步都是把句柄替换为 相应产生式的左部符号而得到的，则称为规范归约。规范归约 是最右推导（规范推导）的逆过程
例:考虑文法G(E):E→E+TT T→T*F|F F→i(E) 并假定输入串为(i+i)*,考察自下而上的分析过程
例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 并假定输入串为（i+i)*i，考察自下而上的分析过程
分析过程图表: 步骤分析栈输入串动作 步骤分析栈输入串动作 (i+i)*i#移进 10#(E+T)*i#归约 #(i+i)*i#移进 11#(E)*i#移进 123456789 #(i i)*i#归约 12#(E) i#归约 #(F+i)*#归约 #F i#归约 #(T+i)*i#归约 45 #T i#移进 #(E+i)*i#移进 #Tk i#移进 #(E+i)*i#移进 16 #1*i #归约 #(E+i)*i#归约 17#T*F #归约 #(E+F)*#归约 18 #T #归约 #E #接受 栈上的候选式不一定是句柄。例如,在第14步对栈顶为T,它是E的一候选式,但 它不是句柄,不能归约成E。判定候选式是极为简单的事情,但判定句柄就不那么 容易。而不同的自底向上方法给出不同的判定方法。 自下而上方法包括四个动作: 移进:把输入流的头符读到分析栈中。 归约:把分析栈顶的句柄归约为一非终极符。 接受:分析成功。 报错:处理错误
分析过程图表： 步骤 分析栈 输入串 动作 1 # (i+i)*i# 移进 2 #( i+i)*i# 移进 3 #(i +i)*i# 归约 4 #(F +i)*i# 归约 5 #(T +i)*i# 归约 6 #(E +i)*i# 移进 7 #(E+ i)*i# 移进 8 #(E+i )*i# 归约 9 #(E+F )*i# 归约 步骤 分析栈 输入串 动作 10 #(E+T )*i# 归约 11 #(E )*i# 移进 12 #(E) *i# 归约 13 #F *i# 归约 14 #T *i# 移进 15 #T* i# 移进 16 #T*i # 归约 17 #T*F # 归约 18 #T # 归约 19 #E # 接受 栈上的候选式不一定是句柄。例如，在第14步对栈顶为T，它是E的一候选式，但 它不是句柄，不能归约成E。判定候选式是极为简单的事情，但判定句柄就不那么 容易。而不同的自底向上方法给出不同的判定方法。 自下而上方法包括四个动作： 移进：把输入流的头符读到分析栈中。 归约：把分析栈顶的句柄归约为一非终极符。 接受：分析成功。 报错：处理错误
5.2算符优先分析 首先规定文法符号之间的优先关系和结合性质,然后再利用 这种关系,通过比较两个相邻的符号之间的优先顺序来确定可 归约串。 算符文法:任何产生式的右部都不含两个相继的非终结符 例:考虑文法G(E):E→E+TT T→T*FF F→i(E) 是否是算符文法?
首先规定文法符号之间的优先关系和结合性质，然后再利用 这种关系，通过比较两个相邻的符号之间的优先顺序来确定可 归约串。 算符文法：任何产生式的右部都不含两个相继的非终结符 5.2 算符优先分析 例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 是否是算符文法？
优先关系: 终结符ab的三种优先关系: a=b当且仅当存在形如下面的产生式U→..ab.或 U→….aQb a≤b当且仅当存在形如下面的产生式U→.laW..的生产式, 且有W鸷b a>b当且仅当存在形如U->.Vb.的产生式 且有V乡.a或V参.aQ
优先关系： 终结符ab的三种优先关系： 当且仅当存在形如下面的产生式U→ … ab…或 U→ … aQb… 当且仅当存在形如下面的产生式U→…aW…的生产式， 且有 W b… 当且仅当存在形如U→…V b…的产生式 且有 V …a 或V … aQ a b a b a b
如果一个算符文法的任何终结符对至多只满足三种关系之一, 称为算符优先文法。 例:考虑文法G(E):E→E+TT T→T*FF F→i(E) 是否是算符优先文法? 验证终结符对之间的优先关系(p90优先表)
如果一个算符文法的任何终结符对至多只满足三种关系之一， 称为算符优先文法。 验证终结符对之间的优先关系(p90优先表) 例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 是否是算符优先文法？
如何从文法构造优先关系表? 检查文法产生式的每个候选,可找出所有满足=的终结符对。 如何找出满足终结符对? 对每个非终结符P构造两个集合 FIRSTⅥT(P和 LASTVT (P) 十 FIRSTⅥTP)=4Pa.或PQn…,a∈VQ∈VN LASTVT(P)=alp 戈P +/a∈n,Q∈N 检查每个产生式候选,若形为.aP..,则对任何b∈ FIRSTVT(P), 我们有ab。 对表达式文法的非终结符构造 FIRSTVT和LASTⅥ并建立优先关系毒
如何从文法构造优先关系表？ 检查文法产生式的每个候选，可找出所有满足 的终结符对。 如何找出满足 和 终结符对？ 对每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P) FIRSTVT(P)= + + a P a P Qa a VT Q VN | ...或 ..., , LASTVT(P) = + + a P a P aQ a VT Q VN | ... 或 ... , , 检查每个产生式候选，若形为...aP...,则对任何b∈FIRSTVT(P)， 我们有a b。 若形为...Pb...,则对任何a∈LASTVT(P)， 我们有a b。 对表达式文法的非终结符构造FIRSTVT和LASTVT并建立优先关系表
算符优先分析算法 素短语:这样的一个短语,它至少含一个终结符,不含比自身 更小的素短语。 最左素短语:句型最左边的素短语。 定理:算符优先文法的句型N1a1N2a2,, N-an+1#的最左素短语 是满足如下条件的最左子串Na1NaN a;=a;+1 a
算符优先分析算法 素短语：这样的一个短语，它至少含一个终结符，不含比自身 更小的素短语。 最左素短语：句型最左边的素短语。 定理：算符优先文法的句型#N1a1N2a2...NnanNn+1#的最左素短语 是满足如下条件的最左子串Njaj...NiaiNi+1 aj-1 aj aj aj+1 ... ai ai ai+1
优先函数 利用两个函数f和g,对每个终结符θ,映射为两个数f(0)和 g(0),使得: 若0102则f(1)>g(62) 有的关系表不存在优先函数! 对于存在优先函数的关系表,如何构造优先函数? 请自学p9495优先函数的构造方法
优先函数 利用两个函数f和g，对每个终结符θ，映射为两个数f(θ)和 g(θ)，使得： 若θ1 θ2则f(θ1) g(θ2) 有的关系表不存在优先函数！ 对于存在优先函数的关系表，如何构造优先函数？ 请自学p94~95优先函数的构造方法