编译原理 算符优先分析法文档.ppt

4.3 自下而上分析法的一般原理 1 自下而上语法分析概述 基本思想：用一个寄存文法符号的栈，将一个输入串反向归约至文法的开始符号。 特点：效率高、文法限制少。 1 自下而上语法分析概述 移进－归约过程实例。 例4.11 设有文法G[A]： (1)A aBcDe (2)B b (3)B Bb (4)D d 对输入串abbcde$的移进－归约分析过程 对输入串abbcde$移进－归约分析过程： 步骤 符号栈 输入串 动作 0 1 2 3 4 5 6 7 8 9 10 $ $a $ab $aB $aBb $aB $aBc $aBcd $aBcD $aBcDe $A abbcde$ bbcde$ bcde$ bcde$ cde$ cde$ de$ e$ e$ $ $ a进栈 b进栈 用B b归约 b进栈 用B Bb归约 c进栈 d进栈 用D d归约 e进栈 用A aBcDe归约 分析成功 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)E *优先于＋： ＋优先于*： 4.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， 如果