第五章语法分析-自下而上分析 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) 是否是算符文法？