《第5章语法分析2自下而上分析编译原理陈火旺.ppt

Ch5.语法分析---自下而上分析 自上而下 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导（最左推导），若能推导出与输入字串相同的句子,则表示输入字符串是合法的； 特点 从文法开始符开始； 推导中始终使用产生式的右部替换左边的非终结符； 自下而上 根据文法,对输入符号串进行归约,若能正确地归约为文法的初始符号,则表示输入字串是合法的。 归约：在输入串中，寻找一条产生式的右部，如果找到用产生式的左边的非终结符替换右部。 特点 从输入串开始； 归约中始终使用产生式的左部替换右边的候选式； 自下而上语法分析：教学内容 5.1 自下而上分析的基本问题--- 重点 自下而上分析的基本思想、归约、规范归约、短语、直接短语、句柄等概念， 规范归约———自下而上分析法 5.2 算符优先分析--- 重点难点 算符优先文法、算符优先分析算法、优先表的构造、最左素短语、优先函数 * 5.3 LR分析法 5.4 语法分析器的自动产生工具 YACC---了解 5.1 自下而上分析的基本问题 自下而上分析法的基本思想： 从输入串出发，反复利用产生式逐步进行“归约”，如果最后能归约到文法的开始符号，则输入串是句子，否则输入串有语法错误。 各种不同自下而上分析法一个共同特点是： 边输入单词符号（移进栈），边归约； 5.1 自下而上分析的基本问题 自下而上分析的基本技术是采用归约栈,如下图所示: 把输入符号依次移入栈内,当栈顶符号串形成某产生式的右部时，就归约为产生式左部非终结符; 继续移入输入字串，直到栈中归约为文法初始符号S. 这种方法也称为“移进－归约法”. 5.1 自下而上分析的基本问题 定义：栈顶形成的某产生式的候选称为归约串。 自底向上分析方法，也称移进－归约分析法，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个归约串时，（某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为归约。重复这一过程直到归约到栈顶中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。 5.1.1 归约 归约串分为：可归约串、非可归约串 在上例中,当栈中为aAb时,存在两个归约串:b及Ab,都可以归约为A； 若使用b进行归约，栈中得到aAA,导致最终不能归约为S,因此，判定输入字符串非法； 这是一种错误归约, 原因在于栈中同时存在多个归约串,而只有一个归约串的选择是正确的,如Ab； 把Ab称为可归约串，而b为非可归约串 5.1.1 归约 自下而上分析的核心问题：就是寻找句型中的“可归约串”进行归约。 对“可归约串”概念的不同定义，就形成了不同的自下而上的分析方法。 在“规范归约”中，则用“句柄”来刻画“可归约串” 在“算符优先分析法”用“最左素短语”来刻画”可归约串” 5.1.1 归约 语法分析树: 一棵倒立的树,可用于描述语法分析的过程； 自上而下分析采用的方法是推导，从根到叶子构造分析树。 或者说从文法的开始符号产生句子。 自下而上分析采用的方法是归约，从叶子到根构造分析树。 或者说从句子开始归约出文法的开始符号。 语法树的一个子树：由该树的某个结连同它的所有子孙组成。 在自下而上分析过程中，每一步归约都可画出一棵子树。 例如,上例中的归约过程可描述为如下分析树: 一个简单的归约过程 a b b c d e 5.1.1 归约 归约与推导关系： 推导与归约互逆关系 最右推导称为 最右推导得到的句型称为规范句型 最左归约称为 5.1.2 规范归约简述 令G是一个文法，S是文法的开始符号 短语 假定???是文法G的一个句型，如果有： S?*?A? 且 A ?+ ? 则称?是句型 ??? 相对于非终结符A的短语。 直接短语 如果有 S?*?A? 且 A ? ? 则称?是句型 ??? 相对于规则 A?? 的直接短语。 句柄：一个句型的最左直接短语。 注意：短语的两个条件缺一不可, αAδ是句型，β符号串可由A出发推导出来。 5.1.2 规范归约简述 例5.4 求P85.(5.2)文法的另一个句型 E+T*F+i 的短语。 解：E?E+T?E+T+T?E+T*F+T?E+T*F+F? E+T*F+i 短语有4个：E+T*F+i (相对于E)； E+T*F(相对