《编译原理第六章—自顶向下优先分析》由会员分享，可在线阅读，更多相关《编译原理第六章—自顶向下优先分析（141页珍藏版）》请在金锄头文库上搜索。
1、第六章 自底向上优先分析,数计学院 宋彩芳,第6章 自底向上优先分析,自底向上优先分析概述 简单优先分析 算符优先分析,文法和语言,自上而下分析的方法是产生语言的过程。 自下而上分析的方法是分析语言的过程。 语法分析处理的对象一开始都是终结符组成的串，而不是文法的开始符号。所以，自下而上分析的方法更自然。,语法分析常用方法,自上而下分析,自下而上分析,确定 不确定,优先分析 LR分析,语法分析的常用方法,递归下降分析程序 LL方法,Ch 5,Ch 6,Ch 7,简单优先 算符优先,例3.27 用移进-归约方法分析abbcde： abbcde=aAbcde=aAcde=aAcBe Y 表示X的优
2、先性比Y的优先性大X Y 文法中有产生式ABY，且B +X或文法中有产生式ABD，且B + X， D * Y,简单优先分析法,优先关系的含义X = Y 文法中有产生式AXY表示X和Y是句柄中的相邻符号，可以一起被归约。X Y 文法中有产生式ABD，且B + X， D * Y表示X必须先和其他符号一起归约为B， Y必须先和其他符号一起归约为D， B和D作为句柄中的相邻符号才可以一起归约。,简单优先分析法,优先关系的计算优先关系矩阵的构造 例：若有文法GSS bAb A ( B|aB Aa) 构造优先关系矩阵。,简单优先分析法,（1）求=关系 由S bAb；A (B；B Aa)可得： b = AA
3、 = b( = BA = a a = ),S bAb A ( B|a B Aa),简单优先分析法,简单优先关系矩阵,简单优先分析法,（2）求关系由S bAb；A +(B；A +(Aa)；A +a可得： B . b ；) . b；a . b由B Aa) ；A +(B；A +a；A+(Aa) 可得： B . a ；a . a ；) . a,S bAb A ( B|a B Aa),简单优先分析法,简单优先关系矩阵,简单优先分析法,（4）#的优先级所有符号 . # # .所有符号# = #,简单优先分析法,简单优先关系矩阵,简单优先分析法,例：若有文法GS构造优先关系矩阵。 (1)求=关系 由S(R)
4、; TS,T可得： (=R；R=)； S=,; ,=T,S(R)|a| RT TS,T|S,简单优先分析法,（2）求.关系(A bB) 由S(R); R+T+S|S,T +(R)|(R),T+ a|a,T+ |,T 可得：(.T; (.S; ( .(; ( . a; ( .; 由TS,T; T+S|S,T +(R)|(R),T+ a|a,T+ |,T 可得：,.S; ,.(; ,. a; ,关系(A Bb) 由S(R); R+T+S|S,T +(R)|(R),T+ a|a,T+ |,T 可得：T.); S.); ).); a.); .); 由TS,T; S +(R)|a| 可得：).,; a.
5、,; .,;,S(R)|A| RT TS,T|S,简单优先分析法,（4）#的优先级所有符号 . # # ai+1（下一个输入符号）时为止；此时，栈顶当前符号ai为句柄尾，由此向左在栈中找句柄头符号ak，若( ak-1 * / + - ； （2）i 和，右结合； （3）+和- ，*和/，左结合； （4）有括号时，先括号内后括号外，内括号的优先性大于外括号； （5）#的优先性低于与其相邻的算符。,算符优先分析法,直观算符优先关系表,算符优先分析法,这个归约过程是唯一的。 上述归约过程中起决定作用的是相邻两个终结符号之间的优先关系。 一旦确定了这种优先关系，就可以借助这种关系去寻找可归约串并进行归约
6、。,文法的句子id+id-id*(id+id)的归约过程为： (1) id+id-id*(id+id) (2) E+id-id*(id+id) (3) E+E-id*(id+id)(4) E-id*(id+id) (5) E-E*(id+id)(6) E-E*(E+id) (7) E-E*(E+E) (8) E-E*(E) (9) E-E* E (10) E-E(11) E,算符优先分析,直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性,算符优先分析法,1. 算符文法的定义定义 设G是一个文法,如果G中：不存在形如 A 和 A V
7、W的产生式(其中V,WVN ）。即，G中没有右部为或右部具有相邻非终结符号的产生式。称G为算符文法（Operator Grammar，OG）。,算符文法的性质,算符文法的性质,算符优先分析法,文法GE：EEE| E-E| E*E| E/E| EE| (E)| -E| i 是算符文法。 文法GE:E EAE | (E) | -E | i A|*|/| 不是算符文法。因右部EAE具有相邻的非终结符号。,算符优先分析法,2. 算符优先关系的定义假定G是一个算符文法。对于任何一对终结符a、b (1) ab G中含有形如Aab或AaBb的产生式 (2) ab当且仅当G中含有形如ABb的产生式，而B+a或
8、B+aC;,算符优先分析法,算符优先分析法,3. 算符优先文法的定义定义 设有算符文法G如果对任意两个终结符对a，b之间至多只有. ，.， = 三种关系的一种成立则称G为算符优先文法（Operator Precedence Grammar，OPG ）。,算符优先分析法,算符优先分析,直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性,算符优先分析法,4. 算符优先关系表的构造定义两个集合 1）firstVTfirstVT(B)=b|B+b或B+Qb 2）lastVTlastVT(B)=a|B+a或B +aC ,算符优先分析法,构造集合firstVT(P)： 若有Pa或P Qa，则afirstVT(P) 若有P Q，firstVT(Q) 包含于firstVT(P) 构造集合lastVT(P)： 若有P a或P aQ，则alastVT(P) 若有P Q，lastVT(Q)包含于lastVT(P),
