第6章 自底向上优先分析法

第6章自底向上优先分析法 6 1概述 原理 在采用自左向右扫描 自底向上分析的前提下 该类分析方法是从输入符号串入手 通过反复查找当前句型的句柄 最左简单短语 并使用文法的产生式把句柄归约成相应的非终结符来一步步地进行分析的 最终把输入串归约成文法的开始符号 表明分析成功 所以 任何自底向上分析方法的关键就是要找出当前句型的句柄 然后根据产生式判别将它归约成什么样的非终结符号 下面 我们结合具体的实现方法 介绍在分析过程中如何来识别句柄的 我们首先介绍自底向上分析的一般过程 再介绍两种常用的分析技术 简单优先分析法和LR分析方法 一 自底向上分析的一般过程 先设置一个寄存符号的栈 称为分析栈 其作用是用来记录分析的历史和指示分析的下一步动作 分析进行时 把输入符号一个一个地按扫描顺序移进栈中 当栈顶符号形成一个句柄 即为某产生式的右部 时 就进行一次归约 即把栈顶构成句柄的那个符号串用相应的产生式左部符号来替换 接着再检查在栈顶是否又出现了新的句柄 则再进行归约 直至整个输入符号串处理完 最终如果栈顶为文法的开始符号 则所分析的输入符号串为合法的符号串 报告分析成功 否则 是不合格的符号串 报告错误 例 考虑文法G E E E T TT T F FF i E 并假定输入串为 i i i 考察自底向上的分析过程 例 考虑文法G E E E T TT T F FF i E 并假定输入串为 i i i 考察自底向上的分析过程 二 分析过程图表 为了具体实现上的方便 我们仍统一约定以 作为输入串的左右分界符 开始和结束标志 作为初始状态 先将符号串的开始标志 压入分析栈中 作为栈底符号 则分析过程为 步骤分析栈输入串动作 i i i 移进 i i i 移进 i i i 归约 F i i 归约 T i i 归约 E i i 移进 E i i 移进 E i i 归约 E F i 归约 步骤分析栈输入串动作10 E T i 归约11 E i 移进12 E i 归约13 F i 归约14 T i 移进15 T i 移进16 T i 归约17 T F 归约18 T 归约19 E 接受 分析过程图表 步骤分析栈输入串动作 i i i 移进 i i i 移进 i i i 归约 F i i 归约 T i i 归约 E i i 移进 E i i 移进 E i i 归约 E F i 归约 步骤分析栈输入串动作10 E T i 归约11 E i 移进12 E i 归约13 F i 归约14 T i 移进15 T i 移进16 T i 归约17 T F 归约18 T 归约19 E 接受 需要说明的是分析栈顶形成的候选式不一定是句柄 例如 在第14步对栈顶为T 它是E的一候选式 但它不是句柄 不能归约成E 判定候选式是极为简单的事情 但判定句柄就不那么容易 而不同的自底向上方法给出不同的判定方法 从上述例子可知 自底向上方法主要包括以下四个动作 移进 把输入流的头符读到分析栈中 归约 把分析栈顶的句柄归约为一非终极符 接受 分析成功 报错 处理错误 6 2简单优先方法 一 概述 简单优先方法是一种简单直观 广为使用的自底向上的分析方法 它是经由算符优先方法变化而来的 这种方法特别有利于分析表达式 大家知道 在做算术式的四则运算时 为了保证计算过程和结果的唯一性 人们作了统一的四则运算规则的规定 这个法则的主要方面就是规定运算符之间的优先顺序 即先乘除后加减 同优先级的运算符先左后右 左结合律 还有先括号内后括号外的规定 而简单优先方法就是根据上述算术运算的计算原理而设计的一种语法分析方法 这种方法的基本思想为 首先规定文法符号之间的优先关系 然后再利用这种关系 通过比较句型中两个相邻的符号之间的优先关系来确定句型的 句柄 并进行归约 二 相邻关系 设Si和Sj是文法G的任意两个符号 那么它们在句型中可相邻出现的充要条件是必须满足下列条件之一 1 有形如U SiSj 的产生式 1 有形如U SiSj 的产生式 三 优先关系 为了把上述条件加以形式化 引进三种优先关系 其定义如下 在实际使用这些优先关系去识别句子时 我们希望采用一种简洁的方法去表示这些关系 优先关系矩阵是一种常用的方式 其定义为 例 设有文法Gz Z bMbM a LL Ma 则可根据定义求出其优先矩阵来 如下 优先关系矩阵 Z bMbM a LL Ma 构造优先矩阵的一种简便方法 STEP1对每个非终极符W求下面两种集合 STEP2对每个符号对Si Sj填写优先关系矩阵元素 其中W V VN 四 简单优先文法的分析方法 1 简单优先文法的定义 2 简单优先文法的句柄 这个定理给我们提供确定句柄的一种方法 简单优先文法分析算法的主要思想是找出句柄并归纳之 而给定一个句型X 寻找它的句柄是这样进行的 从左向右进行扫描 每次只查看两个相邻的文法符号 并由此得知什么时候查到句柄的尾Sj 然后再返过头来向句型左端进行加工 仍然只查看相邻的两个运算符 找出句柄的头Si 此时就可以进行归约了 3 分析算法的要点 STEP3 用SiSi 1 Sj去查产生式表的右部 并用相应的左部符号代替 归约 句柄Si Sj 若查不到 则为出错 STEP4 重复上述过程 直至归约完为止 4 语法分析程序 首先设置保存句型前端的S栈和输入串后端的T队列 然后用Sj1 Sj1 1 Si去查生产式表 则从栈中退掉子串Sj1 Sj1 1 Si 并把U进栈 然后转 2 若查不到转出错处理 5 若T j 并且S栈的内容为 Z Z为文法开始符号 则正确停机 否则 出错停机 1 置初始状态 S 1 i 1 j 1 2 若S i 与T j 无任何关系 则出错停机 此五部分是语法分析所涉及到的几部分 分析栈和输入流中的内容合起来表示当前被归约的句型 每步的动作将由栈顶符号和当前的输入符的优先关系矩阵来确定 如果两种符号之间不存在优先关系 则表示输入符是错误的 而产生式表则用来确定归约时应选用的产生式 6 3算符优先分析 算符优先分析的基本思想是只规定算符 广义为终结符 之间的优先关系 也就是只考虑终结符之间的优先关系 不考虑非终结符之间的优先关系 在归约过程中只要找到可归约串就归约 并不考虑归约到那个非终结符名 算符优先分析的可归约串不一定是规范句型的句柄 所以算符优先归约不是规范归约 算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语 例6 4 若有文法G为 E E EE E EE i考察对输入串i1 i2 i3的归约过程 解 归约过程见分析过程表6 3 P106页 在分析到第6步时 栈顶的符号串为E E 若只从移进 归约的角度讲 栈顶已出现了产生式 1 的右部 可以进行归约 但从通常四则运算的习惯来看应先乘后加 所以应移进 这就提出了算符优先的问题 例6 5 下面给出一个表达式的文法为 E E E E E E E E E E E E i 本文法是二义性的 由于人为地规定了算符之间的优先级别和同一个级别中的结合性质 所以可能构造出确定的分析过程 我们可以对此表达式的文法按公认的计算顺序规定优先级和结合性如下 优先级最高 遵循右结合 优先级其次 服从左结合 优先级最低 服从左结合 对 规定括号的优先性大于括号外的运算符 小于括号内的运算符 内括号的优先性大于外括号 对于句子括号 号规定与它相邻的任何运算符的优先性都比它大 此外 对运算对象的终结符i其优先级最高 综上所述 我们可对表达式运算符的优先关系构造如表6 4 很显然所给表达式文法是二义性的 但我们人为直观地给出运算符之间的优先关系 由优先关系表6 4可知这种优先关系是唯一的 有了这个优先关系表我们对前面表达式的输入串i1 i2 i3归约过程就能唯一确定了 也就是说在表6 3分析到第6 步时 栈中出现了 E E 可归约为E 但当前输入符为 由于规定 所以应移进 这里只简单介绍直观算符优先分析法 仅仅是为了易于理解算符优先分析法的概念 后面将介绍对任意给定的一个文法如何按形式算法的规则计算算符之间的优先关系 6 3 1算符优先文法及优先表构造 一 算符文法的定义 算符文法定义6 2 设有一文法G 如果G中没有形如A BC 的产生式 其中B和C为非终结符 则称G为算符文法 OperaterGrammar 也称OG文法 例如 表达式文法E E E E E E i其中任何一个产生式中都不包含两个非终结符相邻的情况 因此该文法是算符文法 算符文法有如下两个性质 性质1 在算符文法中任何句型都不包含两个相邻的非终结符 性质2 如果Ab或 bA 出现在算符文法的句型 中 其中A VN b VT 则 中任何含b的短语必含有A 二 算符优先关系的定义 由定义6 3可有如下推论 a 若有产生式A a 或A Ba 则a FIRSTVT A 其中A B为非终结符 a为终结符 b 若a FIRSTVT B 且有产生式A B 则有a FIRSTVT A 三 算符优先文法的定义 结论 算符优先文法是无二义性的 四 算符优先关系表的构造 由定义6 3我们可计算出给定的算符文法中任何两个终结符对 a b 之间的优先关系 其算法如下 首先定义如下两个集合 例6 5 现在可用上述算法计算下列表达式文法的算符优先关系 若有表达式文法为 0 E 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 为了求 和 关系 需先由定义6 2计算每个非终结符的FIRSTVT集合和LASTVT集合 结果为 FIRSTVT E FIRSTVT E i FIRSTVT T i FIRSTVT F i FIRSTVT P i LASTVT E LASTVT E i LASTVT T i LASTVT F i LASTVT P i 在计算每个非终结符的FIRSTVT集合和LASTVT集合时 可先考虑文法中含有E T T F F P形式的产生式 由定义6 3的推论可知P的FIRSTVT集合和LASTVT集合也属于F的FIRSTVT集合和LASTVT集合 同样F的也属于T的 T的也属于E的 集合中的其它元素可根据定义由产生式直接计算 然后逐条扫描产生式寻找终结符在前非终结符在后的相邻符号对和非终结符在前终结符在后的相邻符号对 即产生式右部有形如A aB 和A Bb 的产生式 b 关系 对所给表达式