编译原理(第六章).pptVIP

第六章 自底向上的优先分析法 自底向上的分析(移进-归约分析)基本思想：对输入符号串从左向右逐个扫描并移到分析栈中，一边移入，一边分析，一旦栈顶符号串形成某个句型的句柄或可归约串（即：某产生式的右部），就用该产生式左部的非终结符取代栈中句柄（称之为“归约”）。重复上述移进-归约动作，直到输入符号串扫描完毕且栈中仅剩文法的开始符号时，表明分析成功（输入符号串为文法的句子），否则分析不成功（输入符号串不是文法的句子）。 优先分析法 自底向上的分析法 LR分析法 6.1 自底向上的优先分析概述 6.2 简单优先分析法 6.3 算符优先分析法 直观算符优先分析法 直观算符优先的定义 算符优先关系表的构造 优先函数 算符优先分析法的局限性 6.1 自底向上的优先分析概述 简单优先分析法 优先分析法 算符优先分析法 一、简单优先分析 将文法中的文法符号，按一定原则给出其优先关系，并按该优先关系确定分析栈中的句柄。 特点：分析准确、规范，但分析效率低，使用价值不大。 二、算符优先分析法 将文法中的终结符号，按一定原则给出其优先关系，并按该优先关系确定分析栈中的句柄。 特点：分析效率高，适合于表达式，但分析过程不规范。 6.2 简单优先分析法 一、优先关系 任意两个文法符号之间的优先三种关系 P104 例6.2 P104-105 二、简单优先文法的定义 简单优先文法满足如下条件： 1）任意两个文法符号最多只有一种优先关系 2）任意两个产生式没有相同的右部 三、简单优先分析法的分析步骤 分析算法： （1）-（4）P105-106 6.3 算符优先分析法 自底向上分析算法模型----移进归约 算符优先分析不是规范归约 算符优先分析的可归约 串是句型的最左素短语 定义 cfg（上下文无关文法） G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语。 文法G[S] S αAδ且A ?则称?是句型α ? δ相对于非终结符A的短语 6.3 算符优先分析法 自下而上分析算法 模型----移进归约 算符优先分析不是规范归约 算符优先分析的可归约 串是句型的最左素短语 定义 cfg（上下文无关文法） G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语 文法G[S] S αAδ且A ?则称?是句型α ? δ相对于非终结符A的短语 文法G[E]：(1) E→E+T(2) E→T(3) T→T*F(4) T→F(5) F→P?F|P(6) P→(E)(7) P→i 句型T+T*F+i其短语有：T+T*F+iT+T*FTT*Fi E E T + + E T F * F T T i 最左素短语为：T*F 句型T+T+F的素短语为：T+T E + + T F E 句型T+T+i的素短语为： i 素短语为：T*F， i E T T i 分析程序模型 总控程序 算符优先关系表 产生式 输入串# # 输出 如何确定算符优先关系？ 人为确定： （1）i的优先级最高 （1） ?优先级次于i，右结合 （2）*和/优先级次之，左结合 （3）+和-优先级最低，左结合 （4）括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号 （5）#的优先性低于与其相邻的算符 文法G[E]：E→E+E|E-E|E*E|E/E|E?E|(E)|i 算符优先关系表 算符优先文法的定义 定义：如果不含空产生式的上下文无关文法 G 中没有形如 A?…BC…的产生式，其中B，C∈VN 则称G 为算符文法（OG）。 例 G[E]：E→E+E|E-|E*E|E/E|E?E|(E)|I 性质1：在算符文法中任何句型都不包含两个相邻的非终结符。 性质2：如 Ab 或 bA 出现在算符文法的 句型 ? 中，其中 A∈VN，b∈VT， 则 ? 中任何 含 b 的短语必含有A。 算符优先关系 在OG中 定义 （算符优先关系） a = b