编译原理(第二版)第6章 自底向上优先分析法.ppt

第六章自底向上优先分析方法 教学要求 掌握算符优先分析法的关系表的构造以及分析过程 了解简单优先分折法 教学重点 归约 算符优先表构造 从输入串开始 朝着文法的开始符号进行最左归约 直到到达文法的开始符号为止 工作方式 移进 归约 方式 自底向上分析法的基本思想 分析程序模型 1 初态时栈内仅有栈底符 读头指针在最左单词符号上 2 语法分析程序执行的动作 a 移进读入一个单词并压入栈内 读头后移 b 归约检查栈顶若干个符号能否进行归约 若能 就以产生式左部替代该符号串 同时输出产生式编号 c 识别成功移进 归约的结局是栈内只剩下栈底符号和文法开始符号 读头也指向语句的结束符 d 识别失败 例如 有文法如下 1 S aAcBe 2 A b 3 A Ab 4 B d问 语句abbcde是不是该文法的合法语句 移进归约的分析过程 G S 1 S aAcBe 2 A b 3 A Ab 4 B d 遇到的问题 1 如何找出进行直接归约的简单短语 2 找出的简单短语应直接归约到哪一个非终结符 关键 确定句柄 常用的分析方法 优先分析和LR分析 6 1自底向上优先分析法概述 分类 1 简单优先分析 对一个文法按一定原则求出所有符号即终结符号和非终结符号之间的优先关系 按照这种关系确定归约过程中的句柄 特点 准确 规范 但分析效率底 使用价值不大 2 算符优先分析 只规定算符 终结符号 之间的优先关系 不考虑非终结符号之间的优先关系 只要找到句柄就归约 不考虑归约到那个非终结符号 特点 不是规范归约 分析速度快 特别适合于表达式的分析 一 基本思想1 自下而上归约2 规定算符 更一般地说 指终结符 的优先级及结合规则 以使得分析过程唯一3 比较相邻两个算符而决定动作注 1 关键是对所有算符定义某种优先关系2 算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法 6 3算符优先分析方法 i i i i i 归约过程如下 i i i i i 设算量级别最高 最先归约 E i i i i E E i i i 同级 先归约左边 E i i i E E i i 不同级 先归约右边 E E E i 先括号内 后括号外E E E E 归约括号内E E E 归约括号对E E E先归约 E E后归约 E结束 接受 例 E E E E E E E E E E i 一 算符文法的定义 1 给定上下文无关文法G 若G中所有产生式右部都不包含两个相继的非终结符 则G为算符文法 注 算符文法保证了两个运算符之间只有一个操作数 2 算符优先文法定义 设G是一个不包含空串产生式的算符文法 并设a b VT P Q R VN 定义关系 1 ab当且仅当G中含有形如P ab 产生式 或者P aQb 产生式 若G中任何终结符序偶 a b 至多满足上述关系之一 则称G为算符优先文法 2 ab当且仅当G中含有形如P aR 的产生式 其中Rb 或RQb 3 ab当且仅当G中有形如P Rb 产生式 其中R a 或R aQ 用语法树来理解更直观 ab ab 注意 表达式文法 E E E E E E i是算符文法 但不是算符优先文法 两个算符之间的优先关系是有序的 允许有ab ba同时存在 而不允许有ab ab ab三种情况之两种同时存在 1 各非终结符P的首终结符集和尾终结符集定义 首终结符集FIRSTVT P a Pa 或PQa a VT P Q VN 尾终结符集LASTVT P a P a或P aQ a VT P Q VN 三 算符优先文法及优先表的构造 注 有了这两个集合 就可通过检查每个产生式的每个候选式 确定满足关系和的所有终结符序偶 2 构造首终结符集和尾终结符集算法1 构造集合FIRSTVT P 的算法根据FIRSTVT P 的定义 按下面的规则来构造 1 若有产生式P a 或P Qa 则a FIRSTVT P 2 若a FIRSTVT Q 且有产生式P Q 则a FIRSTVT P 2 构造LASTVT P 的算法 根据LASTVT的定义 按下面的规则来构造 1 若有产生式P a或P aQ 则a LASTVT P 2 若a LASTVT Q 且有产生式P Q 则a LASTVT P 3 构造算符优先表的算法FOR每条产生式P X1X2 XnDOFOR i 1 i n 1 i ifXi和Xi 1均为终结符then置XiXi 1 ifi n 2andXi和Xi 2均为终结符andXi 1为非终结符then置XiXi 2 ifXi为终结符而Xi 1为非终结符thenforFIRSTVT Xi 1 中的每个aDO 置Xia ifXi为非终结符而Xi 1为终结符thenforLASTVT Xi 中的每个aDO 置aXi 1 注 如果文法G按此算法构造出的优先表没有重定义项 则文法G是个算符优先文法 例 考虑下面文法 0 E E 1 E E T T2 T T F F3 F P F P4 P E i构造优先关系表 解 1 关系 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 LASTVT E LASTVT E i LASTVT T i LASTVT F i LASTVT P i 3 关系 对表达式文法中终结符在前 非终结符在后的相邻符号对有 E T F F E终结符FIRSTVT 非终结符 4 关系 对表达式文法中终结符在后 非终结符在前的相邻符号对有 E E T P E LASTVT 非终结符 终结符 FIRSTVT E FIRSTVT E i FIRSTVT T i FIRSTVT F i FIRSTVT P i 0 E E 1 E E T T2 T T F F3 F P F P4 P E i 5 优先关系表 i i 1 最左素短语在算符优先分析中 可归约的短语不再称为句柄 而称为最左素短语 素短语 至少含有一个终结符 且除它自身外不再包含其他素短语的短语 最左素短语 最左边的素短语 四 算符优先分析方法 例如 考虑非二义的表达式文法G E E E T TT T F FF E i句型 T T F i 的素短语是什么 由定义可知 素短语有 T F i最左素短语 T F 一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj NiaiNi 1 aj 1ai 1根据这个最左素短语的定义可以构造算符优先分析算法 输入 一个输入符号串w和一张优先关系表 输出 若w是一个句子 输出一棵分析树基架 否则输出一个错误信息 方法 分别置放 到栈中和w 到输入缓冲器中 并执行如下所示的程序 2 算符优先分析算法 置ip 使之指向w 的第一个符号 repeatif 在栈顶上并且ip指向 thenreturnelsebegin令a是栈中最靠顶上的终结符号并且令b是ip所指向的符号ifabthen 归约 repeat从栈中弹出符号until栈顶终结符号与最近弹出的符号之间有 关系成立elseerror end 例 根据下面文法及其算符优先表 按通用算符优先分析的算法分析语句ifbthenielsei S ifEbthenEelseEE E T TT T F FF iEb b 解 1 求各非终结符的首终结符集和尾终结符集 为了考虑语句的开始和结束符号 对文法拓广 加一个产生式S S FIRSTVT S if LASTVT S else i FIRSTVT E i LASTVT E i FIRSTVT T i LASTVT T i FIRSTVT F i LASTVT F i FIRSTVT Eb b LASTVT Eb b 2 填写算符优先表 成功 归约 N 10 对i归约 ifNthenNelseN 9 移进 ifNthenNelsei 8 移进 i ifNthenNelse 7 对i归约 elsei ifNthenN 6 移进 elsei ifNtheni 5 移进 ielsei ifNthen 4 thenielsei ifN 3 0 动作 输入串 关系 下推栈 步骤 接受 ifbthenielsei 移进 1 if bthenielsei 移进 2 ifb thenielsei 对b归约 5 算符优先分析的优缺点 优点 1 算符优先文法适用范围比简单优先文法大得多 许多程序设计语言都可以用它来分析 算符优