第四章 自底向上分析方法 主要内容 自底向上分析的基本思想 简单优先分析方法 LR类分析方法 LR(0)分析方法 SLR(1)分析方法 LALR(1)分析方法

逆过程:(符号栈，输入流) 1.1例：SaAcBe [1] A  b [2] A  Ab [3] B  d [4] (-, abbcde) (a,bbcde) (ab,bcde) (aA,bcde) (aAb,cde) (aA,cde) (aAc,de) (aAcd,e) (aAcB,e) (aAcBe,-) (S,-) 1.1例：SaAcBe [1] A  b [2] A  Ab [3] B  d [4] 输入流：abbcde。 规范推导过程为： S a A c B e A b d S  aAcBe[1]  aAcd[4]e[1]  aAb[3]cd[4]e[1]  ab[2]b[3]cd[4]e[1] b

1 自底向上语法分析方法介绍 自下而上 S a A c B e A b d b 思想：从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归约为文法的开始符。(移入-归约分析)

1.自底向上的语法分析 语法分析的动作： a.移入：把输入流的头符压入分析栈 b.归约：把分析栈栈顶的句柄，用某一非终极符进行替换 c.成功 d.失败 核心问题 如何确定句柄，不同的找句柄的方法构成不同的自底向上语法分析程序 语法分析的动作，实际上从我们刚才的过程来看大概也就这么几项 确定句柄是很重要的，不能简单的按照某个规则的右部一样了就去替换，最直观的来想，就是出现了规则右部是可以用规则左部直接替换么？（分情形讨论实例） 所以核心的方法就是确定句柄，如果给出一个新的找句柄的方法，就相当于给了个新的方法。 下面就要介绍一个最一般的，也是以前用的比较多的方法，简单优先方法，以后的课还会给大家介绍一些比较标准的现在应用更多的LR语法分析方法，这两类的方法实际上都是告诉大家如何来确定句柄。

2 简单优先分析方法概述 一种“移入-归约”分析方法，根据文法符号的优先关系来确定句柄 优先分析法的主要思想是，为每个符号对(X,Y)定义其在句型中的相邻关系，并通过相邻关系判定进行何种分析动作。 符号相邻：如存在形如"…XY…"的句型，则称X和Y是可相邻的。

简单优先分析中的三种关系 —— 表示相邻两个文法符号归约的先后顺序 X  Y ： 当且仅当存在一个产生式A→…XY… X ⊲ Y ： 当且仅当存在一个产生式A→…XB… 并有B+Y… X ⊳ Y ： 当且仅当存在一个产生式A→…BC… 并有B+…X，C*Y… A X Y … X  Y A X B … . Y X ⊲Y A B C … . X Y X ⊳ Y

3 简单优先文法 文法G为简单优先文法如果满足：  对于任意两个语法符号X和Y，至多成立一种 优先关系；  任意两个产生式都具有不同的右部.

FIRST(W) ={S | W + S…，S(VNVT)} 4 优先关系的确定 A B C … . X Y FIRST(W) ={S | W + S…，S(VNVT)} LAST(W) ={S | W + …S，S(VN VT)} 若有U…SiSj…: 则有Si  Sj ; 若有U…SiW…:任SjFIRST(W),有Si ⊲ Sj 若有U…VW…:任SiLAST(V), Sj(FIRST(W) {W}) 则有: Si ⊳ Sj 输入流的开始和结束标志 ‘＃’，文法的开始符为Z， Si FIRST(Z),有# ⊲ Si ; 且＃ ⊲ Z Si LAST(Z)，有Si ⊳ #; 且Z ⊳ ＃

5 优先关系矩阵 优先关系可以用一个矩阵来表示，称之为优先关系矩阵。其中: R[X,Y]= ，当X  Y时 给出了3中优先关系，和定理，实际上我们就可以根据这个来进行语法分析了，在构造这个分析器之前呢，我们要先来看看，给定了文法，实际上优先关系就已经确定了，如果不事先存好的话，会导致进行语法分析的时候效率比较低，如果是现算肯定慢，所以我们首先一个任务就是把所有的优先关系先求出来。既然文法是给定的，那终极符和非终极符都是固定的，那我就可以构造一个所谓的优先关系矩阵，把优先关系用矩阵的时候存起来，以后到矩阵里去查表就可以了。 矩阵里存的就是这些内容 不满足也可以存错误的编号， 把两个语法符号作为下标就行。 这个矩阵其实也挺好构造的

例: Z  bMb M  a M  (L L  Ma) ⊳ ⊳ ⊳ ⊳ ⊲ ⊲ ⊲ ⊲ ⊲ ⊳ ⊳ ⊳ ⊳ ⊲ ⊲ ) a L ) FIRST LAST 例: Z  bMb M  a M  (L L  Ma) # ) a ( b L M Z ⊳   ⊳ ⊳ ⊳  ⊲ ⊲ ⊲  ⊲ ⊲ ⊳  ⊳ ⊳ ⊳ ⊲ ⊲

6 简单优先分析算法 定理： 设X1…XiXi+1…Xj…Xn是一个句型，若有 Xi ⊲ Xi+1 Xi+2 … Xj-1 Xj ⊳Xj+1 则Xi+1Xi+2…Xj-1Xj一定是该句型的简单短语. 结论： ⊲用来确定句柄的头； 用来确定句柄的内部； ⊳用来确定句柄的结束.

简单优先分析算法要点 找第一个使Sj⊳Sj+1的Sj 从Sj开始往前(左)找第一个使Si-1⊲Si的Si 用SiSi+1…Sj去查产生式的右部，并用相应的左部符号代替句柄SiSi+1…Sj (归约) . 重复上述过程，直至输入符结束.如果归约出文法的开始符号则成功.否则失败. A C D … B … X1X2…Xn SiSi+1…Sj

2.7 程序结构 a b c # Input X1 驱动程序 X2 ... Xn # Stack 优先矩阵 产生式集 栈顶X1与当前输入符a到优先矩阵查R[X1,a]， ⊲或则a入栈； ⊳则从栈顶X1向栈底找Xi-1⊲Xi, XiXi+1…X1为句柄进行规约。 2.7 程序结构 a b c # Input X1 驱动程序 优先矩阵 X2 ... 语法分析栈 ，分析的对象（输入流，词法分析后得到的，怎么确定单词是什么属性？实际上我们token的第一位就已经确定了类型），中间是驱动程序，规则集就是查是哪个右部，矩阵当然不用说了 驱动程序要做的工作就是刚才我们所说的，比较优先关系 产生式集 Xn # Stack

⊲ ⊲ ⊲ ⊳ ⊳ ⊳ ⊳ ⊳ 简单优先分析实例1 符号栈 关系 输入流 动作 # b ( a a ) b # 例 G(Z): Z  bMb M  a M  (L L  Ma) 分析字符串：b(aa)b 符号栈 关系 输入流 动作 # b ( a a ) b # # b ( a a ) b # # b ( a a ) b # # b ( a a ) b # # b ( M a ) b # # b ( M a ) b # # b ( M a ) b # # b ( L b # # b M b # # b M b # # Z # ⊲ 移入 ⊲ 移入 ⊲ 移入 ⊳ 规约2  移入  移入 ⊳ 规约4 ⊳ 规约3  移入 ⊳ 规约1 ⊳ 成功

例 已知文法G[E]，判断该文法是否为简单优先文法. EE1 E1E1+ T1 | T1 T1T TT * F | F F(E) | i E E1 T1 T F FIRST LAST E1 ,T1 ,T ,F ,( ,i E1 ,T1 ,T ,F ,( ,i T ,F ,( ,i ( ,i T ,F ,( ,i E1 ,T1 ,T ,F ,),i T1 ,T ,F ,),i T ,F ,),i F ,),i ),i

因为优先矩阵元素至多有一种优先关系，所以是简单优先文法。 E E1 T T1 F + * ( ) i # EE1 E1E1+ T1 | T1 T1T TT * F | F F(E) | i 因为优先矩阵元素至多有一种优先关系，所以是简单优先文法。 E E1 T1 T F FIRST LAST E1 T ,F ( ,i ,( ,i ,T1 T1 ),i F ,),i ,T

符号栈 关系 输入流 动作 # i*i # # i *i # #F *i # #T *i # #T * i # #T *i # 符号栈 关系 输入流 动作 # i*i # # i *i # #F *i # #T *i # #T * i # #T *i # #T *F # #T # #T1 # # E1 # # E # 移入 规约[8] EE1 E1E1+ T1 | T1 T1T TT * F | F F(E) | i 规约[6] 移入 移入 规约[8] 规约[5] 规约[4] 规约[2] 规约[1] 成功

练习：已知文法G[S]： S→a | b | (A) A→SdA | S 完成下列表1的简单优先关系矩阵，并判断G[S]是否为简单优先文法。