编译原理第六章—自顶向下优先分析.ppt

1、第六章 自底向上优先分析,数计学院 宋彩芳,第6章 自底向上优先分析,自底向上优先分析概述 简单优先分析 算符优先分析,文法和语言,自上而下分析的方法是产生语言的过程。 自下而上分析的方法是分析语言的过程。 语法分析处理的对象一开始都是终结符组成的串，而不是文法的开始符号。所以，自下而上分析的方法更自然。,语法分析常用方法,自上而下分析,自下而上分析,确定 不确定,优先分析 LR分析,语法分析的常用方法,递归下降分析程序 LL方法,Ch 5,Ch 6,Ch 7,简单优先 算符优先,例3.27 用移进-归约方法分析abbcde： abbcde=aAbcde=aAcde=aAcBe=S,(1)Sa

2、AcBe (2)Ab (3)AAb (4)Bd,栈剩余输入 动作 #abbcde# 移进 #a bbcde# 移进 #ab bcde# 归约，(2)Ab #aA bcde# 移进 #aAb cde# 归约，(3)AAb #aA cde# 移进 #aAc de# 移进 #aAcd e# 归约，(4)Bd #aAcB e# 移进 #aAcBe # 归约，(1)SaAcBe #S # 接受,自下而上语法分析,思路： 移进：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈入 归约：边移入边分析，一旦栈顶符号串形成某个句型或可规约串时，就用该产生式的左部非终结符代替相应右部的文法符号串，这

3、一步成为归约； 接受：重复上一过程直到归约到栈中只剩文法的开始符号时则分析成功。 构造语法树：从叶子节点（句子）出发，逐步向上归约，直至树的根节点（开始符号）。,上述的每一步归约可以构造一颗语法树：,问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶符号串中就可以归约。 如何知道在栈顶符号串中已经形成可归约串？ 优先分析法通过计算优先关系来确定。,移进-归约分析器的工作模式：,与预测分析对比：,预测分析器： 1.分析方法：推导、匹配 2.依据：预测分析表 3.驱动器（模拟算法） 4. LL（文法、语言、分析器）,移进-归约分析器： 1. 分析方法：移进、归约 2. 依据：LR

4、分析表 3. 驱动器（模拟算法） 4. LR（文法、语言、分析器）,移进-归约分析,第6章 自底向上优先分析,自底向上优先分析概述 简单优先分析 算符优先分析,简单优先分析法,分析思路： 通过反复查找找到当前句型的句柄w，并用A w进行归约。 特点： 自左向右 自下而上 规范归约 规范句型 关键问题：找到句柄。 通过优先关系的定义达到确定的分析。,简单优先分析法,规范句型中a和b可相邻出现的充要条件是G中有形如下列形式之一的产生式： (1) A ab (2) A aB;且B + b (3) A Cb;且C + a (4) A CB;且C + a ; B + b,简单优先分析法,1、优先关系 优

5、先关系的定义 X = Y表示X和Y的优先关系相等 X . Y表示X的优先性比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作为句柄中的相邻符号才可以一起归约。,简单优先分析法,优先关系的计算 优先关系矩阵的构造 例：若有文法GS S bAb A ( B|a B Aa) 构造优先关系矩阵。,

6、简单优先分析法,（1）求=关系 由S bAb；A (B；B Aa)可得： b = A A = b ( = B A = 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）#的优先级 所有符号 . # # .所有符号 # = #,简单优先分析

7、法,简单优先关系矩阵,简单优先分析法,例：若有文法GS 构造优先关系矩阵。 (1)求=关系 由S(R); 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; ,.;,S(R)|a| RT TS,T|S,简单优先分析法,（3）求.关系(A Bb) 由S(R)

8、; R+T+S|S,T +(R)|(R),T + a|a,T + |,T 可得：T.); S.); ).); a.); .); 由TS,T; S +(R)|a| 可得：).,; a.,; .,;,S(R)|A| RT TS,T|S,简单优先分析法,（4）#的优先级 所有符号 . # # .所有符号 # = #,S(R)|A| RT TS,T|S,简单优先分析法,简单优先关系矩阵,S(R)|a| RT TS,T|S,简单优先分析法,2、简单优先文法 若一个文法是简单优先文法必须满足以下条件： 在文法符号集V中，任意两个符号之间最多只有一种优先关系成立； 在文法中任意两个产生式没有相同的右部。（使

9、得归约唯一）,简单优先分析法,3、简单优先分析法 移进-归约分析法 基本思想（如何应用优先关系表确定移进和归约）： 首先，根据优先文法构造优先关系矩阵； 按照优先关系矩阵进行移进-归约分析： （1）将输入符号串a1a2an#依次移进符号栈S， 直到遇到（栈顶符号）ai .ai+1（下一个输入符号）时为止； 此时，栈顶当前符号ai为句柄尾，由此向左在栈中找句柄头符号ak，若( ak-1. ak),即找到句柄akai为止； （3）查找右部为句柄akai的产生式，进行归约。 若找不到，则出错； （4）重复（1）、（2）、（3）步骤 直到输入串结束，栈中为文法开始符号时成功。,简单优先分析法,S bA

10、b A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析

11、串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)#,简单优先分析法,S bAb A ( B|a B Aa),例：分析串b(aa)b#,第6章 自底向上优先分析,自底向上优先分析概述 简单优先分析 算符优先分析,算符优先分析,直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性,算符优先分析,直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性,算符优先分

12、析法,文法G: EE+E EE*E Ei,例：分析串i1+i2*i3 #,算符优先分析法,由于文法GE： E EE | E-E | E*E | E/E | EE | (E) | -E | i 是一个二义文法，它的句子往往有不同的规范推导。 按传统的习惯规定优先级从高到低为： （1）优先级：i * / + - ； （2）i 和，右结合； （3）+和- ，*和/，左结合； （4）有括号时，先括号内后括号外，内括号的优先性大于外括号； （5）#的优先性低于与其相邻的算符。,算符优先分析法,直观算符优先关系表,算符优先分析法,这个归约过程是唯一的。 上述归约过程中起决定作用的是相邻两个终结符号之间的优

13、先关系。 一旦确定了这种优先关系，就可以借助这种关系去寻找可归约串并进行归约。,文法的句子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,算符优先分析,直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性,算符优先分析

14、法,1. 算符文法的定义 定义 设G是一个文法,如果G中： 不存在形如 A 和 A VW的产生式 (其中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) a

15、b G中含有形如Aab或AaBb的产生式 (2) ab 当且仅当G中含有形如ABb的产生式，而B+a或B+aC;,算符优先分析法,算符优先分析法,3. 算符优先文法的定义 定义 设有算符文法G 如果对任意两个终结符对a，b之间至多只有. ，.， = 三种关系的一种成立 则称G为算符优先文法（Operator Precedence Grammar，OPG ）。,算符优先分析法,算符优先分析,直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性,算符优先分析法,4. 算符优先关系表的构造 定义两个集合 1）firstVT firstVT(

16、B)=b|B+b或B+Qb 2）lastVT lastVT(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),算符优先分析法,三种优先关系计算 ab 直接查看产生式的右部，对有形如Aab或A aBb的产生式，则ab。 ab 求出每个lastVT(B) ，对有形如A Bb的产生式，对任何alastVT(B), 有 ab 。,算符优

17、先分析法,构造文法G的优先表算法如下： FOR 每一条产生式PX1X2Xn FOR i:=1 TO n-1 DO BEGIN IF Xi , Xi+1 VT THEN 置 Xi=Xi+1 IF i Xi+1 END,算符优先分析法,算符优先分析法,(1)求=关系 由产生式 E#E# 和 P(E) 可得： #=# (=),算符优先分析法,算符优先分析法,算符优先分析法,算符优先分析法,构造优先关系矩阵的算法,算符优先分析法,构造firstVT集基于的规则： 若有Aa或A Ba，则afirstVT(A) 若有A B，firstVT(B) 包含于firstVT(A) 算法： 建立布尔数组FiA,ja

18、, 并按规则1对每个数组元素赋初值； 若FiA,ja值为真，将（A,a）推入栈中； 将栈顶弹出，设为（B,a）; 按照规则2检查形为A B的产生式，并设FiA,ja为真； 如此重复直到栈弹空为止；,算符优先分析法,算符优先分析法,算符优先分析法,算符优先分析法,算符优先分析法,算符优先分析法,算符优先分析法,算符优先分析法,由简单关系图构建firstVT集 图中的结点为某个非终结符的firstVT集或终结符； 对每个形如Aa或A Ba的产生式，用箭弧连接firstVT(A)到a； 对每个形如A B的产生式，用箭弧连接firstVT(A)到firstVT(B)； 若有firstVT(A)到a，则

19、afirstVT(A),算符优先分析法,算符优先分析,直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性,栈 剩余输入 动作 # i+i# 移进 #i +i# 移进 #P +i# 归约 #F +i# 归约 #T +i# 归约 #E +i# 归约 #E+ i# 移进 #E+i # 移进 #E+P # 归约 #E+F # 归约 #E+T # 归约 #E # 接受,栈 剩余输入 动作 # i+i# 移进 #i +i# 归约 #F +i# 移进 #F+ i# 移进 #F+i # 归约 #F+F # 归约 #F # 接受,算符优先分析算法,为

20、了刻画什么是“可归约串”我们将定义算符优先文法的句型的“最左素短语”这个概念。 所谓素短语是指这样的一个短语，它至少含有一个终结符，并且出它自身外，不再含有更小的素短语。 所谓最左素短语，是指处于句型最左边的那个素短语。,文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,句型#T+T*F+i#其短语有：T+T*F+iT+T*FTT*Fi 其直接短语有： TT*Fi,+,素短语为：T*F i 最左素短语为：T*F,句型#N+N*N+i#的归约过程： （结构归约）,P,句柄和素短语的区别：,E,E,+,T,*,F,T,F,id,id,

21、T,F,id,E,E,+,E,*,E,E,id,id,id,文法GE: E E+E E*E (E) id,文法GE: EE+TT T T*FF F (E) id,算符优先分析算法,算符优先分析句型的性质： 由算符性质可知，其句型（括在两个#号之间）的一般形式为： #N1a1N2a2NnanNn+1# 其中每个ai都是终结符，Ni是可有可无的非终结符。 若有句型NiaiNjajNj+1aj+1, 当aiNjaj属于句柄时，Ni和Nj+1也在句柄中。 该句柄中终结符关系为： a i-1aj+1,算符优先分析法,改造后的算符优先分析按照最左素短语来确定句柄。 已知算符文法的任一句型为如下形式： #N

22、1a1N2a2.NnanNn+1#, 其中N1，N2.Nn为非终结符，a1，a2. 为终结符 根据算符之间的优先关系，如果有 ai-1 ai+1， 我们就认为句型Niai.NjajNj+1为句柄。,算符优先分析算法,算符优先分析句型的性质： 如果aNb（或ab）出现在句型r中，则a和b之间有且只有一种优先关系，即： 若ab，则在r中必含有a而不含b的短语存在 若a=b，则在r中必含有a的短语必含有b 结论： 算符优先文法在归约过程中只考虑终结符之间的优先关系确定句柄，而与非终结符无关；,算符优先分析法,一个算符优先文法G的的最左素短语是满足如下条件的最左子串：NjajNiaiNi+1, a j

23、-1ai+1,算符优先分析,直观算符优先分析法 算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 优先函数 算符优先分析法的局限性,算符优先分析法的局限性,由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取了一些检查措施，但仍难完全避免把错误的句子得到正确的归约。 如文法： S S;D|D D D(T)|H H a|(S) T T+S|S 对串（a+a）能正确归约,自底向上优先分析概述,简单优先分析法 优先关系表：所有符号（VT和VN）的优先关系； 规范归约：确定句柄 算符优先分析法 优先关系表：终结符号（VT）的优先关系； 结构归约：确定最左素短

24、语,简单优先分析法,定义两个集合 1）firstV firstV(P)=Q | P +Qa, Q VN VT而a (VN VT )* 2）lastV lastV(P)=Q | P +aQ, Q VN VT而a (VN VT )* 构造集合firstV(P)： 若有Pa或P Qa，则a,QfirstV(P) 若有P Q，firstV(Q) 包含于firstV(P) 构造集合lastV(P)： 若有P a或P aQ，则a,QlastV(P) 若有P Q，lastV(Q)包含于lastV(P),算符优先分析法,优先关系计算 ab 直接查看产生式的右部，对有形如Aab或A aBb的产生式，则ab。 ab 求出每个lastVT(B) ，对有形如A Bb的产生式，对任何alastVT(B), 有 ab 。,算符优先分析法,构造集合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),自底向上优先分析概述,简单优先分析法 对一个文法按照所有符号