编译原理(清华)第六章自底向上优先分析.ppt

第六章自底向上优先分析法 学习目标 掌握 构造算符优先关系表 进行算符优先分析 构造优先函数理解 算符优先文法 最左素短语了解 简单优先分析法 6 1自底向上分析方法概述6 2自底向上优先分析方法概述6 3算符优先分析法 6 1自底向上分析方法概述 基本思想从输入符号串开始 利用文法的产生式逐步进行归约 试图归约到文法开始符从语法树角度看 是以输入符号串作为语法树的末端结点符号串 自底向上的构造语法树 使文法开始符正好是该语法树的根 如果最终根结点是开始符 则输入符号串是语言的一个句子 否则不是 自底向上分析过程实际上是一个不断进行直接归约的过程 遇到的问题如何找出进行直接归约的 可归约串 句柄 基本实现方法 移进 归约 方法引进一个先进后出的符号栈来存放符号对输入符号串自左向右进行扫描 并把当前输入符号下推入栈中 移进 边移进边分析 一旦栈顶符号串形成某个句型的句柄 为某产生式的右部 时 就用相应的非终结符 产生式的左部 替换它 归约 重复这一过程 直到输入符号串的末端 此时如果栈中只剩文法开始符号 则输入符号串是文法的句子 否则不是 规范归约 自底向上分析的移进 归约过程是自顶向下最右推导的逆过程 因为最右推导为规范推导 所以自左向右的归约称为规范归约 例文法 1 S aAcBe 2 A b 3 A Ab 4 B d输入串abbcde 的最右推导的过程为 S aAcBe aAcde aAbcde abbcde自底向上分析的过程为 abbcde aAbcde aAcde aAcBe S 例文法 1 S aAcBe 2 A b 3 A Ab 4 B d判断输入串abbcde 是否为该文法的句子 用符号栈对输入符号串自底向上的分析过程为 关键问题 如何在分析的过程中确定句柄何时移进 栈顶未形成句柄何时归约 栈顶形成句柄常用自底向上分析法 算符优先分析法 6 3 LR类分析法 第7章 6 2自底向上优先分析法概述 优先分析法两类 简单优先分析法基本思想 按一定原则定义文法中所有符号 终结符和非终结符 之间的优先关系 按照这种关系确定归约过程中的句柄并实行归约 是一种规范归约 简单优先分析法准确 规范 但效率低 不实用 不介绍 算符优先分析法基本思想 只定义文法中终结符之间的优先关系 不考虑非终结符 并由这种关系指导分析过程不是规范归约算符优先分析法分析速度快 特别适用于表达式的分析 缺点是不规范 常常要采用适当措施克服其缺点 6 3算符优先分析法 算符优先分析法特别适用于表达式的分析从表达式得到的启发 表达式的归约顺序与运算顺序是一样的通常算术表达式的运算次序是先乘除后加减 同优先级时服从左结合 E E T TT T F FF E i 符号串E T T F的归约过程为 E T T F E T F E T E 运算次序只与运算符 优先级 结合性 有关 与运算对象无关可以根据运算符 终结符 的优先关系指导归约过程 与运算对象 非终结符 无关 6 3 1优先关系6 3 2算符优先文法的定义6 3 3算符优先关系表的构造6 3 4算符优先分析算法6 3 5优先函数6 3 6算符优先分析法的局限性 6 3 1优先关系 优先关系只存在于句型中相邻出现的符号相邻 算符优先分析法只考虑终结符之间的优先关系 不考虑非终结符 所以两个终结符相邻指其中没有其他的终结符 但可以有非终结符 如 E T i 和 相邻 和i相邻 但 和i不相邻终结符间优先关系表示 终结符a和b之间的优先关系表示如下 ab表示a的优先级高于b 优先关系定义的依据在当前句柄中的符号优先于与其相邻的不在句柄中的符号被归约 其优先关系大同一句柄中的相邻符号同时被归约 其优先关系相同 不可能相邻出现在任何句型中的两个符号 无法比较其归约的先后 故它们之间无优先关系 E E T TT T F FF E i 句型 E T的句柄是 E 所以 注意 是三种有序关系 与数学中的不同 所以a b不意味b a a b不意味b a 如 但是 不成立 因为 和 不可能相邻出现在任何句型中 它们之间没有优先关系 E E T TT T F FF E i 在句型 E T中得 在 E T 中得 按公认的计算顺序规定优先级和结合性 得到优先关系如下 的优先级高 遵循左结合 得 的优先级低 遵循左结合 得 规定括号的优先级大于括号外的运算符 小于括号内的运算符 如 E E T 有 运算对象i的优先级最高优先关系表如右图所示 说明 表中为空的元素表示 在该文法的任何句型中都不会出现这两个终结符相邻 所以他们无优先关系 如不会有这样的表达式 i 算符优先分析法1文法要满足一定的条件 即为算符优先文法2根据文法按一定规则计算算符之间的优先关系3按优先关系进行算符优先分析 6 3 2算符优先文法的定义 算符文法定义 设有上下文无关文法G 如果G中产生式的右部没有两个非终结符相连 则称G为算符文法 OperaterGrammar 也称OG文法例如 表达式文法E E E E E E i是算符文法性质 1 在算符文法中任何句型都不包含两个相连的非终结符 2 如果Ab或bA出现在算符文法的句型r中 其中A VN b VT 则r中任何含b的短语必含有A 含A的短语不一定含有b 句型E T T F短语有 E TT FE T T F 2 算符优先关系的定义设G是一个不含 产生式的算符文法 a和b是任意两个终结符 A B C是非终结符 算符优先关系定义如下 a b当且仅当G中有形如A ab 或A aBb 的产生式 说明 为 或B a b在用一句柄中同时归约所以优先级相同 例如 有产生式F E 所以 a b 或B Cb 说明 为 或C a b不在同一句柄中 b先归约 所以a的优先级低于b 文法E E T TT T F FF E i由E E TT T F得 a b当且仅当G中有形如A Bb 的产生式 且B a或B aC 说明 为 或C a b不在同一句柄中 a先归约 所以a的优先级大于b 文法E E T TT T F FF E i由E E TE T F得 3 算符优先文法定义 设有一不含 产生式的算符文法G 如果对任意两个终结符对a b之间至多只有一种优先关系成立 则称G是一个算符优先文法 OperaterPrecedenceGrammar 即OPG文法 说明 两个终结符之间的优先关系是有序的 算符优先文法允许a b b a同时存在 而不允许有a b a 同时存在 不允许 和 同时存在 例表达式文法E E E E E E i由E E E且E E E得 E E得 和 的优先关系不唯一 所以不是算符优先文法 包含优先级和结合性的表达式文法是算符优先文法E E T TT T F FF E i 6 3 3算符优先关系表的构造 最左终结符集FIRSTVTFIRSTVT B b B b 或B Cb 其中b VT B C VN直观上说FIRSTVT B 是由B推导出的最左终结符 允许左边有一非终结符 的集合 与FIRST a VT a 对照文法符号串 的开始符号集是由 推导出的开头的终结符 包括 组成 例文法 E E T TT T F FF E i FIRSTVT F i FIRSTVT T i FIRSTVT E i FIRST F i FIRST T i FIRST E i 构造FIRSTVT A 的算法令每个非终结符的FIRSTVT集为空依次扫描文法中的每条产生式 根据规则 a b 求各非终结符的FIRSTVT集 a 若产生式A a 或A Ba 则a FIRSTVT A b 若有产生式A B 且a FIRSTVT B 则a FIRSTVT A 重复2 直到每个FIRSTVT集合都不发生变化为止 例文法 E E T TT T F FF E i求各非终结符的FIRSTVT集 第三次 F T E 第二次 i 第一次 第四次迭代的时候 E T F的FIRSTVT集都不再发生变换 算法终止 i i a 若产生式A a 或A Ba 则a FIRSTVT A b 若有产生式A B 且a FIRSTVT B 则a FIRSTVT A 最右终结符集LASTVTLASTVT B a B a或B aC 其中a VT B C VN直观上说LASTVT B 是由B推导出的最右终结符 允许右边有一非终结符 的集合 例文法 E E T TT T F FF E i LASTVT F i LASTVT T i LASTVT E i 构造LASTVT A 的算法与构造FIRSTVT A 算法相似根据下面两条规则若产生式A a 或A aB 则a LASTVT A 若有产生式A B 且a LASTVT B 则a LASTVT A 例文法 E E T TT T F FF E i求各非终结符的LASTVT集 第三次 F T E 第二次 i 第一次 第四次迭代的时候 E T F的LASTVT集都不再发生变换 算法终止 i i a 若产生式A a 或A aB 则a LASTVT A b 若有产生式A B 且a LASTVT B 则a LASTVT A 优先关系的确定 关系 查看产生式右部 有形如A ab 或A aBb 的产生式 则a b例E E 则有 关系 若有形如A Bb 的产生式 对每个a LASTVT B 都有a b例E E T LASTVT E i 则有 i 构造算符优先关系表算法逐条扫描文法中的每条产生式 按以下四种情况处理 对产生式右部终结符相邻的符号对 即产生式右部有形如A ab 的符号对 a b 则a b对产生式右部两终结符之间为一个非终结符的符号对 即产生式右部有形如A aBb 的符号对 a b 则a b对产生式右部终结符在前非终结符在后的相邻符号对 即产生式右部有形如A aB 的符号对 a B 则aa 例文法E E T TT T F FF E i FIRSTVT E i FIRSTVT T i FIRSTVT F i LASTVT E i LASTVT T i LASTVT F i 依次考察每个产生式的右部 由E 和LASTVT E i 得到 i i i 由 T和FIRSTVT T i 得到 i 由 E和FIRSTVT E i 得到 i i i 例文法E E T TT T F FF E i 由T 和LASTVT T i 得到 i 由 F和FIRSTVT F i 得到 i 由 E 得到 由E 和LASTVT E i 得到 i 关于 的优先关系 可认为有产生式E E 而获得 由E 得LASTVT E 即 i 由 E 得 FIRSTVT E 即 i 根据算符优先关系表可以判断文法是否为算符优先文法 文法E E T TT T F FF E I的算符优先关系表为 优先关系表中无多重定义此文法是算符优先文法 6 3 4算符优先分析算法 说明 算符优先分析法的归约过程与规范归约不同 文法E E T TT T F FF E i 输入串i i的语法树 i i的规范归约 i i F i T i E i E F E T Ei i的算符优先分析 i i F i F F E 当单个非终结符是句柄时 算符优先法无法确定该非终结符为句柄 算符优先法每次归约最左素短语而不是句柄最左素短语的定义和确定方法是算符优先分析算法的关键 1 最左素短语的定义定义 设有文法G S 其句型的素短语是一个短语 它至少包含一个终结符 并除自身外不包含其它素短语 最左边的素短语称为最左素短语 例文法 E E T TT T F FF E i的一个句型为T T F i 短语为 素短语为 最左素短语为 规范归约每次归约当前句型中的句柄 上面句型的句柄是T算符优先分析每次归约当前句型的最左素短语 T F 去掉了单非终结符的归约 因为若只有一个非终结符时 无法与句型中该非终结符的左部和右部的串比较优先关系 也就无法确定该非终结符为句柄 T T F i T T F T T F i T F i T F 2 最左素短语的确定最左素短语的形式为 NiaiNi 1ai 1 NjajNj 1其中Nk i K j 1 为非终结符或空ak i K j 1 为终结符 最左素短语NiaiNi 1ai 1 NjajNj 1满足 ai 1aj 1根据上述关系 可以构造出算符优先分析算法 先利用关系 找到最左素短语的尾 再利用关系 找到最左素短语的头 从而确定最左素短语 4 算符优先分析算法此算法用到一个符号栈S 算法大意为 将输入符号串a1a2 at依次逐个存入符号栈S中 直至符号栈顶终结符aj与当前输入符aj 1的关系为aj aj 1为止 最左素短语尾已在符号栈S的栈顶 由栈顶向下找最左素短语的头符号 即找到第一个 关系ai 1 ai 已找到最左素短语NiaiNi 1ai 1 NjajNj 1 用相应的产生式进行归约4 重复上述过程 当处理到输入符号串尾 时 若栈中只剩 N N为任何一个非终结符 则分析成功 否则分析失败 例文法E E T TT T F FF E i算符优先关系表如右图 输入串i i 的归约过程如下 动作 剩余输入串 当前符号 优先关系 栈 步骤 算法说明 算法中每次都取终结符进行比较 当栈顶符号不是终结符时 便取其下面符号 这时一定是终结符 归约时检查是否有与最左素短语对应的产生式 查看产生式的右部 符号个数与该素短语的符号个数相等非终结符位置对应 不管其符号名是什么终结符名字和位置都对应相等 若有满足以上条件的产生式才归约 否则出错 对输入串i i 的规范归约过程 10 9 8 7 6 5 4 3 2 1 归约用产生式 句柄 剩余输入串 栈 步骤 E E T TT T F FF E i 采用规范归约识别i i的过程 采用算符优先分析识别i i的过程 规范归约与算符优先分析1 规范归约将输入符号串归约为文法的开始符算符优先分析将输入符号串归约为任意一个非终结符2 规范归约每次归约句柄算符优先分析每次归约最左素短语 去掉了单非终结符的归约 3 规范归约选取右部与句柄一致的产生式进行归约算符优先分析归约时选择产生式时不管非终结符的名字 6 3 5优先函数 在实际应用中用优先函数来代替优先矩阵表示优先关系优先函数的定义对给定的优先关系表 定义两个函数f g 它们应满足 当a b则令f a g b 当ab则令f a g b 我们称f g为优先函数 其取值可用整数表示 优先函数的优缺点 优先关系表 n 1 2个单元 优先函数表2 n 1 个单元 优点 节省大量内存缺点 原先无优先关系的对 如 i i 变成有关系 f i 6 g i 7 不能准确指出错