第6章 自底向上优先分析 (Bottom-up Parsing) 6.1 概述原理:在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。所以，任何自底向上分析方法的关键就是要找出当前 句型的句柄（或是他的变型），然后根据产生式判别将它 归约成非终极符号。两种常用的分析方法：优先分析法和LR分析法。自底向上分析的一般过程：先设置一个寄存符号的栈，称为分析栈。其作用是用 来记录分析的历史和指示分析的下一步动作。分析进行时 ，把输入符号一个一个地按扫描顺序移进栈中，当栈顶符 号形成一个句柄（即为某产生式的右部）时，就进行一次 归约，把栈顶构成句柄的那个符号串用相应的产生式左部 符号来替换。接着再检查在栈顶是否又出现了新的句柄，则再进行 归约，直至整个输入符号串处理完。最终如果栈顶为文法 的开始符号，则所分析的输入符号串为合法的符号串，报 告分析成功,否则，是不合格的符号串，报告错误。给定句型找句柄的步骤：短语 简单短语 句柄注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。句型的短语、简单短语和句柄定义 给定文法GZ, w=xuyV+，为该文法的句型,若 Z= xUy, 且U=u, 则u是句型w相对于U的短语；若 Z= xUy, 且U=u, 则u是句型w相对于U的简单短语。其中U VN，u V+，x,y V* *直观理解：短语是前面句型中的某个非终结符所能推 出的符号串。例：给定文法G：ET | E+T | ET TF | T*F | TFFi | (E) 符号串（T+i）*iF是文法G的一个句型，求其短语、简单短语和句柄。E ET TT T*FT F*FT (E) *FT (T +T) *FT (T +F) *FT (T +i) *FT (T +i) *iT (T +i) *iT解：短语有8个：1. E E，E（T+i）*iF 则有：（T+i）*iF2. E TF，T （T+i）*i 则有：（T+i）*i3. E T *iF，T （T+i） 则有：（T+i）4. E (E) *iF，ET+i 则有： T+i5. E (E +i) *iF，ET 则有： T6. E (T +F) *iF，Fi 则有： 第一个i7. E (T +i) *FF，Fi 则有： 第二个i8. E (T +i) *FT，TF 则有： F*+*+*+*+*+*+*+*+其简单短语有4个：1. E (E +i) *iF,ET 则有： T2. E (T +F) *iF,Fi 则有： 第一个i3. E (T +i) *FF,Fi 则有： 第二个i4. E (T +i) *FT,TF 则有：F句柄有1个： TEETTT*FF(E)FiE+TTFi用语法树求短语、简单短语和句柄的方法：1）每个句型都有一棵语法树；2）每棵语法树的叶（从左到右）组成一句型；3）每个子树 的叶（从左到右）组成一短语；4）每个简单子树 的叶（从左到右）组成一简单短语 ；5）最左简单子树 的叶（从左到右）组成一句柄。例：考虑文法G(E)：EE +T |TTT*F | FFi| (E) 并假定输入串为（i+i)*i，考察自底向上的分析过程。分析过程图表：为了具体实现上的方便，统一约定以“#”作为输入串的左右分界符（开始 和结束标志）。作为初始状态，先将符号串的开始标志“#”压入分析栈中，作 为栈底符号，则分析过程为：步骤 分析栈 输入串 动作 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 # 接受分析过程图表：步骤 分析栈 输入串 动作 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。判定候选式是极为简单的事 情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。从上述例子可知，自底向上方法主要包括以下四个动作： 移进：把输入流的头符读到分析栈中。归约：把分析栈顶的句柄归约为一非终极符。 接受：分析成功。报错：处理错误。6.2 简单优先方法(Simple-precedence Parsing) 6.2.1 概述简单优先方法是一种简单直观，广为使用的自底向上的分析 方法，它是经由算符优先方法变化而来的。这种方法特别有利于 分析表达式。大家知道，在做算术式的四则运算时，为了保证计算过程和 结果的唯一性，人们作了统一的四则运算规则的规定。这个法则 的主要方面就是规定运算符之间的优先顺序。即先乘除后加减， 同优先级的运算符先左后右（左结合律）。还有先括号内后括号 外的规定。而简单优先方法就是根据上述算术运算的计算过程而设计的 一种语法分析方法。这种方法的基本思想为：首先规定文法符号之间的优先关系和结合性质，然后在利用 这种关系，通过比较句型中两个相邻的符号之间的优先顺序来 确定句型的“句柄”并进行归约。6.2.2 相邻关系：设Si和Sj是文法G的任意两个符号，那么它们在句型中可相 邻出现的充要条件是必须满足下列条件之一：1、有形如 U SiSj的产生式2、有形如 USi W的产生式，且有 W Sj+3、有形如 UVSj的产生式，且有 V Si +4、有形如 UVW的产生式，且有 V Si和W Sj+(1) 有形如 U SiSj的产生式U Si Sj S USi Sj图6.1 采用USiSj的推导+SjU Si W 图6.2 采用USiW的推导(2)有形如 USi W的产生式，且有 W Sj+ S USi W Si Sj+ SiU V Sj 图6.3 采用UVSj的推导(3)有形如 UVSj的产生式，且有 V Si +S UVSj Si Sj+ SiU V W Sj 图6.4 采用UVW的推导(4)有形如 UVW的产生式，且有V Si和W Sj+S UVWj Si Sj+6.2.3 优先关系：为了把上述条件加以形式化，引进三种优先关系。其定义如下：当且仅当存在形如下面的产生式U SiSj SiSj当且仅当存在形如下面的产生式USiW的生产式， 且有 W SjSiSj +当且仅当存在形如下面的产生式UVW的生产式,且有 V Si和W SjSiSj+*在实际使用这些优先关系去识别句子时，我们希望采用一种简 洁的方法去表示这些关系，优先关系矩阵是一种常用的方式。其定义为：例：设有文法Gz：Z bMbMa( LLMa)则可根据定义求出其优先矩阵来（如下）MSi，Sj=空当 Si与Sj无关系(不相邻出现)时当 SiSj 当 SiSj 当 SiSj 优先关系矩阵：Z bMb Ma(L LMa)Zb M ba Zb M b(L Z b M b(LM a )=a( = bL= =MZZ M L b ( a ). .= .构造优先关系矩阵的一种简便方法 ：STEP 1 对每个非终极符W求下面两种集合： STEP 2 对每个符号对Si,Sj填写优先关系矩阵元素(其中W,VVN):Z M LHEAD b ( ,a M ,( ,aLAST b ) ,L ,a )如对Ga我们有：Z bMb Ma( L LMa)MSi,Sj=，如果有USiW且SjHEAD(W)MSi,Sj=，如果有UVW ,且有SiLAST(V) 和Sj HEAD(W) WMSi,Sj=，如果有U SiSj HEAD(W)= SW S,S(VNUVT) LAST(W)=SWS,S(VNUVT)+ +6.2.4 简单优先文法的分析方法：(1) 简单优先文法的定义：定义：满足下面两个条件的文法称为简单优先文法： (1)任意两个符号至多成立一种优先关系。(2)任意两个产生式具有不同右部。为了处理方便，引进特殊符号#，并定义#