第四章_2 算符优先分析法.pptxVIP

4.3 自下而上分析法的一般原理1 自下而上语法分析概述 基本思想：用一个寄存文法符号的栈，将一个输入串反向归约至文法的开始符号。 特点：效率高、文法限制少。1 自下而上语法分析概述移进－归约过程实例。 例4.11 设有文法G[A]： (1)A aBcDe (2)B b (3)B Bb (4)D d对输入串abbcde$的移进－归约分析过程 对输入串abbcde$移进－归约分析过程： 步骤 符号栈 输入串 动作a进栈abbcde$0$b进栈bbcde$1$abcde$用B b归约2$abbcde$b进栈$aB3cde$用B Bb归约$aBb4$aBcde$c进栈5de$$aBcd进栈6$aBcde$用D d归约7$aBcDe$e进栈8$aBcDe$用A aBcDe归约910$A$分析成功2 移进－归约的基本思想 (1)用一个栈寄存文法符号，移进将一个终结符推进栈; (2)归约是将0个或多个符号从栈中弹出，用相应产生式的左部一个非终结符压入栈; 把栈顶被归约的一串符号称为可归约串; (3)重复这一过程直至整个输入串分析完毕; (4)最终栈中只剩下左界符$和开始符号S，则所分析的输入串是文法的正确句子;否则，出错。可归约串3 分类 ◆算符优先分析法 ◆规范归约分析法 简单优先分析法 LR分析法用 最左素短语 刻画可归约串用 句柄 刻画可归约串4.4 算符优先分析法4.4.1 方法概述1 特点 适合分析各类表达式; 宜于手工实现; 规定运算符之间的优先顺序(优先关系，结合性质)。 通过比较算符之间的优先关系确定可归约串。4.4.1 方法概述2 优先关系 例 文法G[E]： E E+E|E*E|(E)|id 对输入串id+id*id的规范归约过程。*优先于＋：＋优先于*：(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E+E(6)E(1)id+id*id(2)E+id*id(3)E+E*id(4)E*id(5)E*E(6)E4.4.1 方法概述3 优先关系种类 任何两个相邻的终结符a和b可能的优先关系有3种： a b: a的优先级低于b a b: a的优先级等于b a b: a的优先级高于b注：优先关系与出现的左右次序有关，不同于数学符号,=,。4.4.1 方法概述4 优先关系矩阵(表) 矩阵的行和列都是文法的终结符; 矩阵元素是两终结符间的优先关系。 算符优先分析法借助优先关系表寻找句型的可归约串。 算符优先关系表实例当前输入串首字符 + * id ( ) $ + * id ( ) $栈中第一个终结符4.4.2 算符优先文法的定义1 算符文法的定义 设有文法G，若G中没有形如U …VW…的规则，其中V和W为非终结符，则G称为算符文法，也称OG文法。性质： 1.在算符文法中任何句型都不包含两个相邻的非终结符。 2.如Ab或bA出现在算符文法的句型 中，则 中任何含b的短语必含有A。4.4.2 算符优先文法的定义2 算符优先关系的定义 在OG中定义算符优先关系： (1)a b :含有P…ab…，或P…aQb…的 规则。 (2)a b :含有P…aR…的规则，且R b…或 R Qb… (3)a b:含有P…Rb…的规则，且R…a或 R…aQ。4.4.2 算符优先文法的定义2 算符优先关系的定义 规定： 若S a…或S Ca…，则$ a 若S…a或S…aC，则a$4.4.2 算符优先文法的定义3 算符优先文法的定义 设有一个不含 规则的OG文法G， 如果任意两个终结符间至多有一种算符关系存在， 则称G是算符优先文法，也称OPG文法。 结论：算符优先文法是无二义的。4.4.3 算符优先关系表的构造1 FIRSTVT集、 LASTVT集 FIRSTVT(A)={b|A b… 或 A Bb… ,b VT,B VN} 即：非终结符Ａ往下推导所有可能出现的首个算符的集合．　LASTVT(A)={a|A…a A…aB, a VT,B VN} 即：非终结符Ａ往下推导所有可能出现的最后一个算符的集合．2 算符优先关系表的构造方法 (1)为每个非终结符Ａ计算FIRSTVT(A),LASTVT(A) (2)计算算符之间的优先关系，并填表。计算方法： ★ 关系:若A　…ab… 或A…aBb,则a b ★ 关系:若A…aB…,则b FIRSTVT(B),a b ★ 关系:若A…Bb…,则a LASTVT(B),a b (