第6章自底向上优先分析法-2013详解.ppt

第六章 自底向上优先分析法;;一、自底向上分析的基本思想 对输入串从左到右扫描，并逐个移入栈中。边移入边分析，一旦栈顶符号串形成某个句型的可归约串（它对应某产生式右部），就用该产生式左部的非终极符号代替它，完成进一步归约。 重复这一过程直到归约到栈中，只剩下开始符号和右边界符’#’，成功。否则，报错。;例.(p94) (1) S ?aAcBe (2) A ?b (3) A ? Ab (4) B ?d, 对输入串abbcde#语法分析走一遍动作。 符号栈 输入串 0 # abbcde# 1 #a bbcde# 2 #ab bcde# 用A?b归约 3 #aA bcde# 4 #aAb cde# 用A?Ab归约 5 #aA cde# 6 #aAc de# 7 #aAcd e# 用B?d归约 8 #aAcB e# 9 #aAcBe # 用S?aAcBe归约 10 #S #;二、自底向上分析的关键;6.1 自底向上优先分析法概述;6.2 简单优先分析法（了解）;6.2.2 简单优先文法的定义;二、简单优先分析法;6.3 算符优先分析法;一、方法 算符优先分析法就是依据四则运算过程而设计的一种语言分析方法。首先要规定运算符（广义为终结符）之间的优先关系和结合性质，然后比较相邻运算符的优先级来确定句型的可归约串并进行归约;实例分析：G[E]:E?E+E | E*E |(E)|id（歧义文法） 句子id+id*id有两个不同的规范归约(归约中句柄不唯一)： 第1个规范归约: (1)id+id*id (2)E+id*id (3)E+E*id (4)E+E*E (5)E+E (6)E 第2个规范归约过程： (1)id+id*id (2)E+id*id (3)E+E*id (4)E*id (5)E*E (6)E;分析：句型E+E*id (1) id是它的句柄 (2) E+E是它的句柄 原因：没有定义+和*的优先关系 (1) 假定*优先于+，不能立即把E+E归约为E (2) 假定+优先于*，因此先把E+E归约为E 决定因素：相邻两个终极符之间的优先关系;二、算符优先分析法的关键;三、适用范围;6.3.2 算符优先文法的定义;2. 定义任意两个终结符号之间的优先关系;图（a）：δ为ε或为C（a，b在同一可归约串中，同时归约） 图（b）：a，b不在同一可归约串中，b先归约，所以a ·b） 图（c）???a，b不在同一可归约串中，a先归约，所以a ·b）;3. 算符优先文法的定义(Operater Precedence G);（1）G[E]是OG文法 （2）G[E]不是OPG文法;6.3.3 算符优先关系表的构造（由定义）;1.算法基于两条规则 求得每个VN的FIRSTVT(A)） (1) 若有产生式A?a…或A?Ba…, 则a∈FIRSTVT(A) (2) 若a∈FIRSTVT(B)，且有产生式A?B…，则 a∈FIRSTVT(A) 类似的方法求得每个VN的LASTVT(A) (1) 若有产生式A? …a或A? …aB, 则a∈LASTVT(A) (2) 若a∈LASTVT(B)，且有产生式A? …B，则a a∈LASTVT(A);2. 算法描述;例： 0 E‘?# E # 1 E ?E+T | T 3 T ?T*F | F 5 F ?P | F | P 7 P ?(E) 8 P ?I 对表达式求所有VN的FIRST(B) ;构造G的优先关系表算法;例：设有G[E]: E?E+T | T, T?T*F | F, F?(E) | id， 构造出算符优先关系表;6.3.4 算符优先分析算法;（2）句型的素短语 至