北京交通大学计算机与信息技术学院：《编译原理》课程教学资源（PPT课件讲稿）第四章 语法分析和语法分析程序（4.2）自底向上的语法分析

符号串计的语法分析过程 步柴分析栈优先关系」「r余留输入串句柄所用产生式 0123 i #F >>> +++ i*i# F T i*i# T 4#T i*i# E1→T #E i*i# #E1+ 7|#E1+i 8#E1+F >>= i★☆i i# i# F T→F #E1+T i# 10#E1+T兴 11#E+T * 12#E1+T*F ## #T*F|T→T*F 13#E1+T T T1→T 「14「#E1+T1 E1+T1|E1→E1+T 15#E >>>>> ### ### E1E→E1 16|#E #成功

11 步骤 分析栈 优先关系 r 余留输入串 句柄 所用产生式 0 # < i + i * i # 1 # i > + i * i # i F→i 2 # F > + i * i # F T→F 3 # T > + i * i # T T1→T 4 # T1 > + i * i # T1 E1→T1 5 # E1 = + i * i # 6 # E1 + < i * i # 7 # E1 + i > * i # i F→i 8 # E1 + F > * i # F T→F 9 # E1 + T = * i # 10 # E1 + T * < i # 11 # E1 + T * i > # # i F→i 12 # E1 + T * F > # # T * F T→T*F 13 # E1 + T > # # T T1→T 14 # E1 + T1 > # # E1 + T1 E1→E1 + T1 15 # E1 > # # E1 E→E1 16 # E > # # 成功 符号串i+i*i的语法分析过程

简单优先分析矩阵的构造 通过考察若干个句型来发现优先关系的方法比较繁琐, 可以一次计算出全部优先关系,得到优先关系矩阵, 为此,引入V上定义的若干二元关系: 定义42LEAD∈V2: ALEADB,A→B,,∈P; A LEAD B, iff A=>B 定义4.3LAST∈V2: ALATE,A→B∈P; A LASTB, iffA→>+…B 定义4.4逆关系( TRANSPOSE(R或~R) a-Rb,if bra 定义4.5s=S,切丑U→…Ss…∈P;

12 三、简单优先分析矩阵的构造 通过考察若干个句型来发现优先关系的方法比较繁琐， 可以一次计算出全部优先关系，得到优先关系矩阵， 为此，引入V上定义的若干二元关系： 定义4.2 LEADV2 : A LEAD B, iff A→B…P; A LEAD+ B, iff A=>+ B…; 定义4.3 LASTV2 : A LAST B, iff A→…BP; A LAST+B, iff A=>+ …B 定义4.4逆关系(TRANSPOSE(R)或~R): a ~R b, iff b R a 定义4.5 si= sj , iff U→…si sj ... P;

若干二元关系的定义(续) 定义4.68Sy3U→… W EPA W=+s… 定义4.7$>s卯U→…WW2∈PAW1→+…,A So,SEVi 由定义46,sS分W∈VNs= WAWLEAD+ 分s1(=)(LEAD)s复合关系 由定义47,有s>s分W=W2AW1LAST+SAW2 LEAD 其中W1 LAST+ S分s1 TRANSPOSE(L4ST)W (或:(L4ST);LEAD*=I+LEAD+,为恒等关系 综上所述,S>S分s~LAST)(=)( +LEAD)S

13 若干二元关系的定义(续) 定义4.6 si<sj , iff U→... siW... P W=>+ sj…。 定义4.7 si>sj , iff U→…W1W2 ...P W1=>+…si  W2=>*sj…， sjVT 由定义4.6, si<sj  WVN: si=W  W LEAD+ sj  si (=)(LEAD+ ) sj ; 复合关系 由定义4.7, 有si > sj  W1= W2 W1 LAST+ si  W2 LEAD* Sj ; 其中 W1 LAST+ si  si TRANSPOSE(LAST+ ) W1 (或:~(LAST+ ); LEAD* = I+LEAD+ ,I为恒等关系 综上所述, si > sj  si ~(LAST+ ) (=) (I+LEAD+ ) sj

优先关系矩阵构造举例 上述定义的二元关系R可以用布尔矩阵BR来表示,关系 R的布尔矩阵B定义为:当S1RS时,Bij=1;否则 BR[Jj]=0。 对于文法G:S→Ac;A→AS;A→>Aa;,A→>b,计算相应的 优先关系矩阵如下: (1)构造B s Aa b c S「00000 A10 01 B 00000 b00000

14 优先关系矩阵构造举例 上述定义的二元关系R可以用布尔矩阵BR来表示，关系 R的布尔矩阵BR定义为：当 Si R Sj时，BR[i,j]=1; 否则 BR[i,j]=0。 对于文法G: S→Ac; A→AS; A→Aa; A→b，计算相应的 优先关系矩阵如下： （1）构造B=                 = = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 c b a A S S A a b c B