编译原理－何炎祥-第六章.pptVIP

第六章自下而上分析和优先分析方法 自下而上分析是最右推导的逆过程，从构造语法树的观点来讲,是指从树的末端结点开始，逐步向上归约，直至树的根结点，也就是说，从输入串本身开始，朝着开始符号进行归约。直至到达开始符号为止。 确定的自下而上分析器通常分为两大类：优先分析器(Precedence Parser)和 LR(k)分析器。 本章将主要讨论优先分析器方面的内容。在具体讨论优先分析方法之前，我们先介绍句柄和归约的概念。因为它们在自下而上分析过程中占有重要地位。 6.1 短语和句柄 定义6.1 设S是文法G的识别符号，w= xUy是其中的句型，若 则称子串?是句型x?y相对于非终结符U的短语。其中，U?VN；x，y? (VN∪VT)*。此外，如果有 则称子串?是句型x?y相对于非终结符U的直接短语或简单短语。一个句型的最左直接短语，称为该句型的句柄(Handle),句柄的最右符号称为该句柄之尾。一个规范句型的句柄的右边只包含终结符号。 注意，U ?不一定意味着?就是句型w= xUy的短语，还必须考虑S xUy这一条件。为说明这一点，请看下面的例子。 例6.1 设文法G37[数]: 数→数字串 数字串→数字串数字|数字 数字→0|1|2|3|4|5|6|7|8|9 w=数字串1是它的一个句型。我们不能因为有数?数字串就断定数字串就是w的简单短语。因为“数1”不是一个句型。事实上 ，w含有两个短语：“数字串1”和“1”，“1”是简单短语而且是句柄，因为有 a) 数 数字串 且数字串 数字串1 b) 数 数字串数字 且数字?1 语法树与短语的关系密切。语法树的子树是由该树的某个结点(称为子树的根)及其所有分枝构成的部分树称为原树的一颗子树。 语法树的简单子树是只有单层分枝的子树——这颗子树只有且必须有父子两代，没有第三代，由此，引出下述结论： 每个句型(句子)都对应一颗语法树； 每颗语法树的端末结点自左至右排列构成一个句型(句子)； 每颗子树的端末结自左至右排列构成一短语； 每颗子树的端末结自左至右排列构成一简单短语； 最左简单子树的端末结自左至右排列构成一句柄。 例6.3 句型? = (a，(T)，(T，S))的语法树如图6.1所示。它有7个分枝结点，分别以这7个分枝结点为根结点，得7棵子树。再分别由这7棵子树的叶子结点（从左到右）组成7个符号串，它们是句型?的7个短语。这7个短语是： ① (a，(T)，(T，S)) ② a，(T)，(T，S) ③ a，(T) ④ (T，S) ⑤ a ⑥ (T) ⑦ T，S 句型?的语法树有3棵简单子树。由这3棵简单子树的叶子结点组成的符号串，则是句型?的3个简单短语： ① a ② (T) ③ T，S 句型?的语法树的最左简单子树的叶子结点a便是句型?的句柄。 6.2 移进–归约方法 最一般的自下而上分析方法称为移进－归约(Shift-Reduce)方法。 这种方法的基本思想是设置一个暂存符号的栈，用来保存分析的历史信息和指示分析的下一步动作。 分析进行时，把输入符号一个个地按扫描顺序移进栈，当栈顶部的符号串形成一个句柄(也就是某个产生式的右部)时，就进行一次归约，即把栈顶部构成句柄的那个符号串用相应产生式的左部替代；接着再检查栈顶部是否又形成了新的句柄，若是，则再进行归约，若未形成新的句柄，则再从输入串中移进新的符号，如此继续，直至输入串分析完毕. 此时，若栈中仅为文法的开始符号，则表明所分析的输入串是合法的，报告分析成功；否则输入串是不合法。 移进-规约过程 下面我们来看一个具体的移进–归约分析器，它将按照上面的流程完成一个符号串的移进－归约分析。这个分析器设置了一个符号栈和一个输入缓冲区。当输入符号串为?，分析开始时，栈和输入缓冲区的格局为 在符号栈里先放置一个“#”号，输入符号串?之后跟着一个“#”号，作为输入符号串的结束符。 对?进行分析时，将?的符号从左到右逐个移进符号栈，一旦栈顶符号串与某一个产生式右部相匹配成为一个可归约符号串时，则将此符号串归约为一个非终结符，这个非终结符是该产生式左部符号。?的符号继续逐个移进符号栈，当栈顶又形成一个可归约的符号串时，则又可将此符号串归约为某一个产生式左部非终结符。 重复这个过程，如果最终出现如下格局： 符号栈里仅有“#”号与识别符号Z，输入符号串?全部被符号栈吸收，只剩下“#”号，则分析成功，说明符号串?是文法的一个句子。如果得不到以上格局，则表明符号串?不是文法的句子，存在语法错误。 自下而上分析法的主要问题