第6章_自下而上分析和优先分析方法.pdf

第6章自下而上分析和优先分析方法  自上而下的分析方法从文法的识别符号 出发，试图推导出输入符号串，而自下 而上的分析方法从输入符号串出发而上的分析方法从输入符号串出发，，试试 图归约到文法的识别符号。  简单优先分析方法简单优先分析方法  算符优算符优先分析方分析方法 自下而上分析过程 自下而上的分析方法是自下而上的分析方法是一种种“移进移进-归约归约” 法。它用到一个符号栈S，待检查符号串的 符号逐个被符号逐个被 ““移进移进””符号栈符号栈，当栈顶符号串当栈顶符号串 与某个产生式右部相匹配时，这个符号串被 替换成替换成 （“归约归约”）该产生式左部非终结符该产生式左部非终结符。 例例6.16.1 文法文法GG3030[A]:[A]: AaBb BBb|b 符号栈S 输入字符串= “abbb” b Bb B b Bb BB BB a a a a b AaBb b AaBb BB AA BB AA a a bb 不能归不能归 A 约到A 短语和句柄 定义定义66.11 设设SS是文法是文法GG的识别符号的识别符号，如果如果SS**xUyxUy ， U+ ，则称子串是句型xy相对于非终结符U的 * 短语短语，其中其中UUVV , xx,yy (V(V VV )) ，如果如果是是UU的的一 N N T 个直接推导，即U，则称子串是句型xy相对 于非终结符于非终结符UU的的直接短语直接短语或或简单短语简单短语，一个句型的个句型的 最左直接短语，称为该句型的句柄。 例例6.26.2 文法文法GG3131[S]:[S]: SS(T)|a|(T)|a| TS|T, S  ∵S + (T, S), T + (a), ∴(a)是句型((a), S)相对于T 的短语。  ∵∵SS ++ ((T)((T), S)S), TT TT, SS, ∴∴TT, SS是句型是句型((((TT, S)S), S)S)相对于相对于TT 的的 直接短语。 给定符号串=(a, (T), (T,S))，是该文法的一个句型，求其句柄 先找出的所有直接短语。 ∵S +(S, (T), (T, S)), S a, ∴a是句型相对于S的直接短语 ∵∵SS +(a+(a, SS, (T(T, S))S)), SS (T)(T), ∴∴(T)(T)是句型是句型相对于相对于SS的直接短的直接短 语 ∵∵SS +(a,+(a, T,T, ((TT)),)), TT T,T, S,S, ∴∴T,T, SS是句型是句型相对于相对于TT 的直接短语的直接短语 因此共有三个短语，其中子串a是句型的最左直接短语，即句型 的句柄。 句型语法树  一个句型的短语、直接短语和句柄实际上也可以用 其语法树的子树来进行描述其语法树的子树来进行描述。  一个句型有一棵相应的语