《编译原理：第6章 自底向上优先分析法》由会员分享，可在线阅读，更多相关《编译原理：第6章 自底向上优先分析法（34页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 自底向上优先分析法自底向上优先分析法1本章内容本章内容 n引子：自底向上分析的一般原理引子：自底向上分析的一般原理n6.1 自底向上优先分析概述自底向上优先分析概述n6.2 简单优先分析法（了解）简单优先分析法（了解）n6.3算符优先分析法算符优先分析法2n一、自底向上分析的一、自底向上分析的基本思想基本思想q对输入串从左到右扫描，并逐个移入移入栈中。边移入边分析，一旦栈顶符号串形成某个句型的可归约串（它对应某产生式右部），就用该产生式左部的非终极符号代替它，完成进一步归约归约。q重复这一过程直到归约到栈中，只剩下开始符号和右边界符#，成功。否则，报错。引子引子:自底向上分析的一
2、般原理自底向上分析的一般原理3n例.(p94) (1) S aAcBeaAcBe (2) A (2) A b (3) A b (3) A AbAb (4) B (4) B d, d, 对对输入串输入串abbcdeabbcde# #语法分析走一遍动作。语法分析走一遍动作。 符号栈符号栈 输入串输入串 0 # 0 # abbcdeabbcde# # 1 #a 1 #a bbcdebbcde# # 2 # 2 #a ab b bcdebcde# # 用用A Ab b归约归约 3 # 3 #a aA A bcdebcde# # 4 # 4 #a aAbAb cdecde# # 用用A AAbAb归约归
3、约 5 #5 #a aA A cdecde# # 6 # 6 #aAcaAc de# de# 7 # 7 #aAcaAcd d e# e# 用用B Bd d归约归约 8 # 8 #aAcaAcB B e# e# 9 # 9 #aAcBeaAcBe # # 用用S SaAcBeaAcBe归约归约 10 #S # 10 #S #4二、自底向上分析的二、自底向上分析的关键关键n如何精确定义可归约串并识别。如何精确定义可归约串并识别。n对可归约串(p23)的不同定义形成不同的自下而上分析方法：1.在规范归约规范归约分析中，用句柄来刻画可归约串 (LR, 简单优先)2.在算符优先分析算符优先分析中，是用
4、最左素短语来刻画可归约串。n根据识别可归约串的不同方法，也形成不同的自下而上分析法。n简单优先分析法和LR分析法都是规范归约分析法（句柄可归约串），但它们识别句柄的方法不同：q1.LR分析法是根据历史、现实、展望三者信息来确定栈顶符号串是否形成句柄q2.简单优先分析法是根据文法符号之间的优先关系来确定句柄。56.1 自底向上优先分析法概述自底向上优先分析法概述n1.简单优先分析法：对一文法求出所有符号之间的优先关系，并据此确定句柄（规范归约）n2.算符优先分析法：只考虑算符之间的优先关系，不考虑VN的优先关系。只要找到可归约串就归约，并不考虑归约到哪个非终极符。66.2 简单优先分析法（了解）
5、简单优先分析法（了解）n6.2.1 优先关系优先关系qX=Y iff AXYqXY iff ABD且B X和D Yn例6.2 SbAb, A(B | a, BAa)(1)相等：b=A，A=b，(=B，A=a，a=)(2) : 由bA及A(B | a , BAa) ，可得，可得 b ( ， b a，( A， ( ， ( : 由 S bAb , A(B | a 及及 B Aa），），可得可得 B b ， B a a b ， a a ) b ， ) a +76.2.2 简单优先文法的定义简单优先文法的定义 一、一、定义定义简单优先文法满足两个条件简单优先文法满足两个条件（1）任意两个文法符号之间最多
6、只有一种优先关系成立）任意两个文法符号之间最多只有一种优先关系成立（2）在）在G中任意两个产生式没有相同的右部（归约唯一）中任意两个产生式没有相同的右部（归约唯一）分析：栈顶为分析：栈顶为aiqai ai+1 归约（已形成句柄）归约（已形成句柄）8二、二、简单优先分析法简单优先分析法n步骤：步骤：构造文法的优先关系矩阵，将构造文法的优先关系矩阵，将G规则保存，设规则保存，设置符号栈置符号栈S（1）将输入串）将输入串a1,a2,an #逐个移入符号栈逐个移入符号栈S中，直到栈顶符中，直到栈顶符号号ai ai+1为止。为止。（2）栈顶）栈顶ai为句柄尾，由此向左在栈中找句柄开头符号为句柄尾，由此向
7、左在栈中找句柄开头符号ak（找（找到到ak-1 ak为止）为止）（3）由句柄）由句柄akak+1ai在产生式中查找右部为在产生式中查找右部为akai的产生式，的产生式，若找到则用相应左部代替句柄（归约），否则出错，串不是若找到则用相应左部代替句柄（归约），否则出错，串不是合法句子。合法句子。6.2.2 简单优先文法的定义简单优先文法的定义96.3 6.3 算符优先分析法算符优先分析法n特别适合于分析程序中各类表达式且宜于手工实现简单、直观（仅适用于表达式的语法）n6.3.1 方法概述n6.3.2 算符优先文法的定义n6.3.3 算符优先关系表的构造（由定义）n6.3.4 算符优先分析算法n6.
8、3.6 算符优先分析法的局限（p115）10n一、方法一、方法n算符优先分析法就是依据四则运算过程而设计的一种语言分析方法。首先要规定运算符（广义为终结符）之间的优先关系和结合性质，然后比较相邻运算符的优先级来确定句型的可归约串并进行归约6.3.1 算符优先分析法概述算符优先分析法概述11n实例分析：GE:EE+E | E*E |(E)|id（歧义文法）句子id+id*id有两个不同的规范归约(归约中句柄不唯一)：第1个规范归约: (1)id+id*id (2)E E+id*id (3)E+E E*id (4)E+E*E E (5)E+E E (6)E E第2个规范归约过程： (1)id+id
9、*id (2)E E+id*id (3)E+E E*id (4)E E*id (5)E*E E (6)E E6.3.1 算符优先分析法概述算符优先分析法概述12n分析：句型E+E*id (1) id是它的句柄(2) E+E是它的句柄n原因：没有定义+和*的优先关系(1) 假定*优先于+，不能立即把E+E归约为E(2) 假定+优先于*，因此先把E+E归约为En决定因素：相邻两个终极符之间的优先关系6.3.1 算符优先分析法概述算符优先分析法概述13二、算符优先分析法的关键二、算符优先分析法的关键n关键关键：如何定义任意两个可能相邻出现的终极符：如何定义任意两个可能相邻出现的终极符a和和b之间的优
10、先关系。之间的优先关系。n优先关系符： a b a的优先级大于bn与出现的左右次序有关，a a14三、适用范围三、适用范围n算符优先分析法只适用于算符优先文法， 即对文法有一定要求。156.3.2 算符优先文法的定义算符优先文法的定义1. 算符文法的定义（算符文法的定义（Operater Grammar） 设有文法G，若G中没有形如ABC的产生式，其中B,CVN，则称G为算符文法，也称为OG文法。n算符文法具有两个重要性质：（1）在OG文法中，任何句型都不包含两个相邻的非终结符。（2）若Ab或bA出现在算符文法的句型中，A VN，b VT，则中任何含b的短语必含有A162. 定义任意两个终结符
11、号之间的优先关系定义任意两个终结符号之间的优先关系n设G是一个不含规则的OG文法，a、b是任意两个终结符，A、B、C是非终结符，算符优先关系=, 定义如下：(1) a =b当且仅当G中含有形如Aab或AaBb规则(2) a b当且仅当G中含有形如ABb产生式且 B a或 B aC+6.3.2 算符优先文法的定义算符优先文法的定义17AabAaB183. 算符优先文法的定义(Operater Precedence G)n设有一个不含规则的算符文法G，如果任意两个终结符对(a,b)在,=三种关系中只有一种成立，则称G是算符优先文法，也称OPG文法n判断：GE是否是OG，是否是OPG文法 E E+E
12、 | E*E | (E) | id(1)GE是OG文法(2)GE是OPG文法19(1)GE是OG文法(2)GE是OPG文法EE+EE*E(a) + *+,*之间优先关系不唯一而：GE E E+T | TT T*F | FF (E) | id是OPG文法206.3.3 算符优先关系表的构造（由定义）n根据优先关系定义，可按如下方法直接构造优先关系表。首先，对G中每个非终结符A，定义两个集合：qFIRSTVT(A)=b | A b或A Bb, bVT, BVNqLASTVT(A)=a | A a或A aB, aVT, BVNn三种优先关系：q1）对形如Aab, AaBb,有a=bq2）对形如AaB
13、, 有ab, aLASTVT(B)+21算符优先关系表的构造n1.算法基于两条规则（求FIRSTVT(A)）q(1) 若有产生式Aa或ABa, 则aFIRSTVT(A)q(2) 若aFIRSTVT(B)，且有产生式AB，则a aFIRSTVT(A)n类似的方法求得每个VN的LASTVT(A)q(1) 若有产生式A a或A aB, 则aLASTVT(A)q(2) 若aLASTVT(B)，且有产生式A B，则a aLASTVT(A)222. 算法描述p104 Procedure Insert(A,a); 功能：求FIRSTVT元素 IF NUT FA,a THEN Begin FA,a:=TRUE
14、 PUSH(A,a) ONTO STACK End / 当aFIRSTVT(A)时，置FA,a为真，并将符号对(A,a)下推到栈中 BEGIN (MAIN) For 每一个非终结符A和终结符a Do FA,a:=FALSE; For 每个形如Aa或ABa的产生式 Do Insert(A,a) WHILE STACK非空 DO Begin 把STACK的栈顶记为(B,a)弹出 For 每个形如AB的产生式 DO Insert(A, a) End End (MAIN)23n例： 0 E# E # 1 E E+T | T 3 T T*F | F 5 F P | F | P 7 P (E) 8 P I
15、对表达式求所有VN的FIRST(B) (1)第一次扫描后，STACK栈的初值为：(2)6. (p, i) (F, 1) (T, i) (E, i)(3)5. (p, () (F, 1) (T, 1) (E, 1)(4)4. (F, ) (T, ) (E, )(5)3. (T, *) (E, *) (6)2. (E, +)(7)1. (E, #)(2) 由F P，T F, E T，栈顶(6)的内容逐次改变为: (F, i), (T, i), (E, i)FIRSTVT(E)=#FIRSTVT(E)=+, *, , i, (FIRSTVT(T)=*, , i, (FIRSTVT(F)=, i, (
16、FIRSTVT(P)=i, (弹出24构造G的优先关系表算法n(1) 为每一个AVN，计算FIRSTVT(A)和LASTVT(A)n(2) 执行程序 for (每个产生式Ax1x2xn) for (i=1; i=n-1; i+) if (xiVT且xi+1VT) 置xi=xi+1 if (i=n-2且xiVT且xi+1VT且xi+2VN) 置xi=xi+2 if (xiVT, xi+1VN) for (FIRSTVT(xi+1)中的每个变量b) 置xixi+1; n(3) 对FIRSTVT(S)中的所有b，置#;置#=#。（S为G的开始符号）25n例.设有GE:EE+T | T, TT*F |
17、 F, F(E) | id,构造出算符优先关系表FIRSTVTLASTVTE+,*,(,id+,*,),idT*,(,id*,),idF(,id),id + * ( ) id #+ ( = 空 id # 空 = + (- -)* * (满足左结合) （右结合）优先级最高*, / 其次+, -最低()的优先级大于括号外的运算符266.3.4 算符优先分析算法n算符优先分析算法不是一种规范归约。因为在VT之间定义优先关系无法识别由单个非终结符组成的课归约串。即：不是用句柄，而是用最左素短语刻画可归约串。n1. 最左素短语q1）短语：设G=(VN, VT, P, S)，若有：S * A且A ，则称是
18、句型相对于A的短语。特别地，如有A ，则称是相对于A 的直接短语。一个句型的最左直接短语称为该句型的句柄。+272）句型的素短语n句型的素短语：至少包含一个VT的短语，并且除自身之外不再包含其它的素短语。n最左边的素短语称为最左素短语n例. 考虑文法GE的句型：T+T*F+id，分析句型 T+T*F+id #其短语有： 对应VNT+T*F+id (E)T+T*F ET ET*F EId F(T.E)其中素短语：T*F和id最左素短语：T*F （T是该句型的句柄，但不是最左素短语）EE+TE+TE+TT语法树282. 识别最左素短语的方法n由算符文法的性质可知，算符文法的任何句型没有相邻的VN，
19、其句型应为：#N1a1N2a2NnanNn+1#，其中Ni(1=i=n+1)为非终结符或空，aiVT(i=1n)n定理：一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串NiaiNi+1ai+1NjajNj+1：qai-1 aj+1* 出现在ai左端的Ni和出现在aj右端的Nj+1是属于素短语的29Why?nWhy? OG的任何句型中VT和VN相邻时，含VT的短语必含相邻的VNn上述句型 #T+T*F+id# 即 #N1a1N2a2N3a3a4#因有 # + + #故由定理，N2a2N3即T*F是最左素短语303. 算符优先分析算法n算符优先分析时自底向上的分析，也为自左向右归约
20、，它不是规范归约n算符优先分析的关键：如何找最左素短语NiaiNi+1ai+1NjajNj+1，即满足：qai-1 aj+1n在当前句型中存在符号串的符号个数与该素短语的符号个数相等，非终极符对应NK(k=i,j+1)，不管符号名是什么，终极符对应ai,aj,名字与实际名一样，位置也一致，才有可能形成素短语。31n在分析过程中设置一个符号栈S，存放归约或待形成最左素短语的符号串，a存放当前读入符号n归约成功的标志是：读到句子结束符#。栈中归约到只剩下#N。n在归约时要检查是否有对应规则的右部与Sj+1Sk相符，若有才可归约。326.3.6 算符优先分析法的局限(p115)n虽然，算符优先分析法比规范归约快得多，因为算符优先分析法跳过了所有非终结符之间的归约。这既是它的优点，也是缺点。n因为：忽略VN在归约工程中的作用，存在某种危险性，可能把错误的输入串误认为是句子n这种缺陷可从技术上加以弥补33n例：SS;D | D, DD(T) | H, Ha | (S), TT+S | S是一个算符优先文法。Why？FIRSTVTLASTVTS;, (, a;, ), aD(, a), aHa, (a, )T+, ;, (, a+, ;, ), a;( )a+#;(=a+#=34
