《编译技术：第04章02 自上而下的语法分析》由会员分享，可在线阅读，更多相关《编译技术：第04章02 自上而下的语法分析（135页珍藏版）》请在金锄头文库上搜索。
1、第四章(02) (02) 自上而下的语法分析词法分析词法分析中间代码生成中间代码生成语法分析语法分析语义分析语义分析中间代码优化中间代码优化目标代码优化目标代码优化目标代码生成目标代码生成源程序机器代码编译的步骤2Zhou, ErqiangSchool of Information and Software EngineeringSchool of Information and Software EngineeringZhou, Erqiang3关于语法分析语法分析的目标语法分析的目标 找出词法记号序列的结构找出词法记号序列的结构 恢复出一棵语法树恢复出一棵语法树语法描述工具语法描述工具 2
2、 2型型文文法：上下文无关文法法：上下文无关文法无关文法无关文法G=(VT, VN, S, P)及符号串及符号串 判断判断是否是是否是G G的句子的句子School of Information and Software EngineeringZhou, Erqiang4关于语法分析语法分析方法的类型语法分析方法的类型 自上而下自上而下( (自顶向下自顶向下) )的分析文法的分析文法 自下而上自下而上( (自底向上自底向上) )的分析文法的分析文法School of Information and Software EngineeringZhou, Erqiang5关于语法分析自上而下语法分析
3、自上而下语法分析 从文法开始符从文法开始符S S出发出发 猜测输入串猜测输入串的的推导序列推导序列自下而上语法分析自下而上语法分析 从输入串从输入串出发出发 猜测猜测归约序列归约序列，使串，使串归约到归约到S S猜测猜测直觉直觉向向理论理论提升过程中的提升过程中的必由之路必由之路仍需要仍需要执着执着的思考！的思考！School of Information and Software EngineeringZhou, Erqiang6自上而下的分析法自上而下语法分析自上而下语法分析 从开始符号从开始符号S S开始开始 对每个源程序对每个源程序 如何找出相应的推导序列？如何找出相应的推导序列？ 没
4、有没有任何可用信息可以利用任何可用信息可以利用 根据已有的经验根据已有的经验/ /直觉直觉从从语法规则语法规则出发检验标识符出发检验标识符 func1iden iden digit iden 1 iden nondigit 1 iden c1 iden nondigit c1 iden nc1 iden nondigit nc1 iden unc1 nondigit unc1 func1Zhou, Erqiang7语法规则School of Information and Software Engineeringiden nondigit iden iden nondigit iden ide
5、n digit digit 0 | 1 | 2 | | 9 nondigit _ | A | B | | Z | a | b | | z推导过程推导过程好像一条好像一条通路通路正确的推导过程总伴随着错误的推导正确的推导过程总伴随着错误的推导所有所有推导推导过程像是一个过程像是一个迷宫迷宫里的所有里的所有道路道路迷宫？！迷宫？！用什么实现？用什么实现？School of Information and Software EngineeringZhou, Erqiang8自上而下的分析法语法分析语法分析对对图图的搜索的搜索 图的节点为句型图的节点为句型 从节点从节点到节点到节点有条边有条边 当且仅
6、当当且仅当 = = School of Information and Software EngineeringZhou, Erqiang9自上而下的分析法E TE T + ET intT (E)ET+E(E)TintT+T(T+E)(T)T+T+Eint+E(int)(E)T+(E)int+Tint+intint+(E)int+T+ESchool of Information and Software EngineeringZhou, Erqiang10自上而下的分析法int + intET+E(E)TintT+T(T+E)(T)T+T+Eint+E(int)(E)T+(E)int+Tint
7、+intint+(E)int+T+ESchool of Information and Software EngineeringZhou, Erqiang11算法1：广度搜索法Q Q为一个为一个“句型句型”的队列的队列 初始时队列仅有开始符号初始时队列仅有开始符号S S当队列不为空当队列不为空 从队列取一个句型从队列取一个句型 如果该句型与输入串匹配，停止如果该句型与输入串匹配，停止 否则将该句型所有的一步推导句型加到否则将该句型所有的一步推导句型加到Q Q根据所使用的产生式确定语法树根据所使用的产生式确定语法树School of Information and Software Engine
8、eringZhou, Erqiang12算法1：广度搜索法E TE T + ET intT (E)int + int队列队列Q QEET+ETT+ETSchool of Information and Software EngineeringZhou, Erqiang13存在问题：存在问题： 效率低下！效率低下！ 时间、空间资源耗费大时间、空间资源耗费大原因分析：原因分析： 检查很多检查很多不可能匹配不可能匹配的句型的句型 高高“分支因子分支因子”如何改进？如何改进？算法1：广度搜索法School of Information and Software EngineeringZhou, Erq
9、iang14针对针对“不可能匹配不可能匹配的句型的句型” 假设输入串为假设输入串为 对句型对句型 T = ，其中，其中 为为终结符终结符串串 为终结符与非终结符串为终结符与非终结符串 如果如果不是不是的前缀的前缀 那那T T的句子不可能与的句子不可能与匹配匹配算法1：广度搜索法School of Information and Software EngineeringZhou, Erqiang15针对高针对高“分支因子分支因子” 句型中有多个非终结符句型中有多个非终结符 分支数为各非终结符分支数为各非终结符 所对应产生式个数之和所对应产生式个数之和 限制选用的产生式，降低分支因子限制选用的产生
10、式，降低分支因子 最左推导最左推导算法1：广度搜索法School of Information and Software EngineeringZhou, Erqiang16算法2：最左广度搜索法E TE T + ET intT (E)int + int队列队列Q QEET+ETT+ETSchool of Information and Software EngineeringZhou, Erqiang17算法2：最左广度搜索法E TE T + ET intT (E)int + int队列队列Q QT(E)intT+ESchool of Information and Software Eng
11、ineeringZhou, Erqiang18算法2：最左广度搜索法E TE T + ET intT (E)int + int队列队列Q QT+E(E)+Eint+Eint+ESchool of Information and Software EngineeringZhou, Erqiang19算法2：最左广度搜索法E TE T + ET intT (E)int + int队列队列Q Qint+Eint+T+Eint+Tint+Tint+T+ESchool of Information and Software EngineeringZhou, Erqiang20算法2：最左广度搜索法E T
12、E T + ET intT (E)int + int队列队列Q Qint+Tint+(E)int+intint+T+Eint+intSchool of Information and Software EngineeringZhou, Erqiang21算法2：最左广度搜索法E TE T + ET intT (E)int + int队列队列Q Qint+T+Eint+(E)+Eint+int+Eint+intSchool of Information and Software EngineeringZhou, Erqiang22算法2：最左广度搜索法E TE T + ET intT (E)in
13、t + int队列队列Q Qint+intSchool of Information and Software EngineeringZhou, Erqiang23算法2：最左广度搜索法总结：总结： 大大提高大大提高了分析的效率了分析的效率 “总能找出总能找出”输入串的推导序列输入串的推导序列 如果存在如果存在 万事大吉？万事大吉？School of Information and Software EngineeringZhou, Erqiang24算法2：存在问题(1)A Aa | Ab | ccaaaaaaa队列队列Q QAAaAbcAaAbSchool of Information a
14、nd Software EngineeringZhou, Erqiang25算法2：存在问题(1)A Aa | Ab | ccaaaaaaa队列队列Q QAbAaAaaAbacaAaaAbaSchool of Information and Software EngineeringZhou, Erqiang26算法2：存在问题(1)A Aa | Ab | ccaaaaaaa队列队列Q QAaaAbAabAbbcbAbaAabAbb左递归左递归School of Information and Software EngineeringZhou, Erqiang27算法2：存在问题(2)S aAS
15、S fA fASA af队列队列Q QSaASfaASSchool of Information and Software EngineeringZhou, Erqiang28算法2：存在问题(2)S aASS fA fASA af队列队列Q QaASafASSaSaS舍弃？舍弃？S School of Information and Software EngineeringZhou, Erqiang29算法2：存在问题(2)S aASS fA fASA af队列队列Q QaSaaASafabSchool of Information and Software EngineeringZhou,
16、 Erqiang30算法2：存在问题(2)S aASS fA fASA af队列队列Q QafSchool of Information and Software EngineeringZhou, Erqiang31算法2：存在问题(3)S xAyA abA axay队列队列Q QSxAyxAyxX X已经匹配已经匹配School of Information and Software EngineeringZhou, Erqiang32算法2：存在问题(3)S xAyA abA axay队列队列Q QxAyxabyxayaaa仅向前检查一个字符仅向前检查一个字符 还是检查多个？还是检查多个？
17、因产生式有因产生式有公共左因子公共左因子 不能立即判断该舍弃不能立即判断该舍弃 哪个分支哪个分支 School of Information and Software EngineeringZhou, Erqiang33算法2：存在问题总结：总结： 时间成时间成指数指数式增长式增长 空间也成空间也成指数指数式增长式增长原因？原因？ 文法文法本身问题本身问题 算法算法处理问题处理问题School of Information and Software EngineeringZhou, Erqiang34算法2：存在问题文法问题文法问题 公共左因子公共左因子 A 1 | 2 左递归左递归 A =*
18、 A 对串对串 产生式产生式School of Information and Software EngineeringZhou, Erqiang35算法2：存在问题算法问题算法问题 广度搜索广度搜索 同时考虑同时考虑多个多个分支！分支！School of Information and Software EngineeringZhou, Erqiang36文法改造公共左因子公共左因子 A 1 | 2 提取公共左因子提取公共左因子文法中有左递归文法中有左递归 消除左递归消除左递归School of Information and Software EngineeringZhou, Erqian
19、g37文法改造公共左因子公共左因子 A 1 | 2 提取公共左因子提取公共左因子SxAyAaba SxAyAaBBb SxAyAa(b ) School of Information and Software EngineeringZhou, Erqiang38文法改造A 1| n|1|m 公共左因子为公共左因子为 1 1| | |m m 不含公共左因子不含公共左因子改造方法改造方法 A B|1|m B 1| n 若在若在 i、 j、 k中仍有中仍有, ,则再提取则再提取School of Information and Software EngineeringZhou, Erqiang39文
20、法改造文法中有左递归文法中有左递归 消除消除直接、间接直接、间接左递归左递归直接左递归的消除直接左递归的消除 PP|改写为右递归形式改写为右递归形式 P P PP| PP 1| | |P n| | 1| | | m （ i ， j不以不以P P开头开头）按公式：按公式： P P( 1| | | | n) | | ( 1| | | m) P ( 1| | | | m ) P P ( 1| | | | m ) P文法改造School of Information and Software Engineering40Zhou, Erqiang PP 1| | |P n| | 1| | | m （ i
21、 ， j不以不以P P开头）开头）改写为改写为: : P 1P| | | | mP P 1P| | | | nP文法改造School of Information and Software Engineering41Zhou, Erqiang例例 算术表达式文法算术表达式文法E E + T | T（ T + T . . . + T ）T T F | F（ F F . . . F ）F ( E ) | id求消除左递归后文法求消除左递归后文法文法改造School of Information and Software Engineering42Zhou, Erqiang消除左递归消除左递归E E
22、 + T | T E TE E + TE | T T F | F T FT T F T | 文法改造School of Information and Software Engineering43Zhou, Erqiang消除左递归后文法消除左递归后文法 E TE E + TE | T FT T F T | F ( E ) | id文法改造School of Information and Software Engineering44Zhou, Erqiang间接左递归间接左递归S Aa | bA Sd | 先变换成直接左递归先变换成直接左递归S Aa | bA Aad | bd | 再消除左
23、递归再消除左递归文法改造S Aa | bA (bd | ) AAadA | S Aa | bA bdA| AAadA | School of Information and Software Engineering45Zhou, Erqiang间接左递归间接左递归 SQcc QRbb RSaa求消除左递归后的文法求消除左递归后的文法 文法改造School of Information and Software Engineering46Zhou, Erqiang解：解：1 1）任意排列递归的非终结符）任意排列递归的非终结符 S S、Q Q、R R排列排列2 2）依次代入产生式）依次代入产生式
24、SQcc 不变不变 QRbb 不变不变 R?文法改造SQccQRbbRSaaRa|Sa a|ca|Qca a|ca|bca|RbcaR bcaRcaRaRR bcaR School of Information and Software Engineering47Zhou, Erqiang解：解：1 1）任意排列递归的非终结符）任意排列递归的非终结符 R R、Q Q、S S排列排列2 2）依次代入产生式）依次代入产生式 RSaa 不变不变 QRbb 不变不变 S?文法改造SQccQRbbRSaaSc|Qc c|bc|Rbc c|bc|abc|SabcS abcSbcScSS abcS Scho
25、ol of Information and Software Engineering48Zhou, ErqiangSchool of Information and Software EngineeringZhou, Erqiang49文法改造课堂练习课堂练习给定文法给定文法G:G: S Aa | Ab | c A Ad | Se | f消除左递归、并提取公共左因子消除左递归、并提取公共左因子School of Information and Software EngineeringZhou, Erqiang50算法3：最左深度搜索法思想：思想： 使用深度搜索法使用深度搜索法 空间：一次仅考虑
26、空间：一次仅考虑一个分支一个分支 时间：对很多文法，运行时间：对很多文法，运行极快极快！ 实现：可递归实现，实现：可递归实现，简单简单！School of Information and Software EngineeringZhou, Erqiang51算法3：最左深度搜索法E TE T + ET intT (E)int + intET+ETint(E)School of Information and Software EngineeringZhou, Erqiang52算法3：最左深度搜索法ET+ET(E)(E)E TE T + ET intT (E)int + intSchool o
27、f Information and Software EngineeringZhou, Erqiang53算法3：最左深度搜索法ET+ETE TE T + ET intT (E)int + intSchool of Information and Software EngineeringZhou, Erqiang54算法3：最左深度搜索法ET+ET+EE TE T + ET intT (E)int + intint+E(E)+Eint+Tint+T+Eint+intSchool of Information and Software EngineeringZhou, Erqiang55算法3：
28、存在问题AAaA Aa | ccAaaAaaaAaaaa左递归左递归School of Information and Software EngineeringZhou, Erqiang56最左分析算法总结最左广度搜索最左广度搜索 所有所有文法文法 时间指数增长时间指数增长 空间空间指数指数增长增长 实际很少使用实际很少使用最左深度搜索最左深度搜索 文法文法无左递归无左递归 时间指数增长时间指数增长 空间空间线性线性增长增长 应用在应用在“递归下递归下降分析法降分析法”中中算法算法1 1至算法至算法3 3 使用搜索的方法使用搜索的方法 分析需要回溯、不确定分析需要回溯、不确定递归下降分析法递归
29、下降分析法和和预测分析法预测分析法 确定的分析方法确定的分析方法 ( (仅针对一些仅针对一些特定特定的文法的文法) )最左分析算法总结School of Information and Software Engineering57Zhou, Erqiang利用函数之间的递归调用利用函数之间的递归调用 模拟语法树自上而下的构造过程模拟语法树自上而下的构造过程文法要求文法要求 无左递归无左递归 无公共左因子无公共左因子 每次所选的产生式确定每次所选的产生式确定有可能有可能构造出不带回溯的分析程序构造出不带回溯的分析程序递归下降分析法School of Information and Softwar
30、e Engineering58Zhou, Erqiang每个非终结符对应一个解析函数每个非终结符对应一个解析函数产生式右侧为其左侧非终结符产生式右侧为其左侧非终结符 所对应解析函数的所对应解析函数的“函数体函数体”产生式右侧终结符产生式右侧终结符 对应从输入串中消耗该终结符对应从输入串中消耗该终结符产生式中的产生式中的| | 对应对应“if-elseif-else”语句语句递归下降分析法School of Information and Software Engineering59Zhou, Erqiang例：对下列文法构造分析程序例：对下列文法构造分析程序递归下降分析法E TE E + TE
31、 | T FT T F T | F ( E ) | iSchool of Information and Software Engineering60Zhou, Erqiang递归下降分析法E TE E + TE | T FT T F T | F ( E ) | ivoid E( )T()；E1()；void E1( )if( sym = + ) advance()； T()； E1()；School of Information and Software Engineering61Zhou, Erqiangvoid T( ) F()； T1()；变量变量sym表示当前符号表示当前符号函数函数
32、advance()() 读取下一字符读取下一字符递归下降分析法E TE E + TE | T FT T F T | F ( E ) | ivoid T1()if( sym = * ) advance()； F()； T1()；void F() if ( sym = ( ) advance()； E()； if ( sym = ) ) advance()； else error()；else if ( sym = i ) advance()；else error()；School of Information and Software Engineering62Zhou, ErqiangETFi
33、iM(i)ETFiiM(i)ETFT+M(+)*#*M(*)i#M( )#M(i)M( )T+M( )School of Information and Software Engineering63Zhou, ErqiangE TE E + TE | T FT T F T | F ( E ) | i串i+i*i# 递归下降分析过程利用利用 正则表达式、有限自动机正则表达式、有限自动机 对文法、程序进行简化对文法、程序进行简化E E + T | TE T + T 自学自学 ( (实验二内容实验二内容) )School of Information and Software Engineering
34、64Zhou, Erqiang扩充的文法课堂练习课堂练习P 216, 9-3P 216, 9-3对文法对文法 S (L) | a L L,S | S消除左递归，写出递归下降分析过程。消除左递归，写出递归下降分析过程。School of Information and Software Engineering65Zhou, Erqiang递归下降分析法总结预测分析法School of Information and Software Engineering66Zhou, Erqiang算法算法1 1至算法至算法3 3需要需要“回溯回溯” 猜测猜测使用哪个产生式使用哪个产生式 分析时需要分析时需要
35、运气运气（不确定）（不确定）另一类算法称为另一类算法称为“预测预测”算法算法 根据剩余输入串（事实）根据剩余输入串（事实） 预测预测哪个产生式（确定）哪个产生式（确定）预测分析法School of Information and Software Engineering67Zhou, Erqiang预测预测算法更算法更“快快” 线性运行时间线性运行时间 表驱动表驱动预测算法更预测算法更“脆弱脆弱” 不支持所有的文法不支持所有的文法在在文法表达力文法表达力与与运行速度运行速度之间寻求平衡之间寻求平衡预测分析法School of Information and Software Engineeri
36、ng68Zhou, Erqiang从开始符号开始，如何选产生式？从开始符号开始，如何选产生式？基本思想基本思想 向前看向前看 在选产生式时，查看当前输入串在选产生式时，查看当前输入串查看的字符个数查看的字符个数越多越多 支持的文法支持的文法越多越多 分析就分析就越复杂越复杂School of Information and Software EngineeringZhou, Erqiang69EE TBB | + ET intT (E)int+intint(+预测分析法TBint+Eint+TB)int+(E)Bint+(intB)Bint+(int+E)Bint+(int+TB)Bint+(
37、int+intB)Bint+(TB)Bint+(int+int)Bint+(int+int)intB如何把如何把选择产生式的经验选择产生式的经验描述出来、描述出来、再提升至理论？再提升至理论？School of Information and Software EngineeringZhou, Erqiang70EE TBB | + ET intT (E)int+intint(+预测分析法TBint+Eint+TB)int+(E)Bint+(intB)Bint+(TB)BintBint()+EBTT (E)T intB +EE TBE TB预测分析法School of Information
38、and Software Engineering71Zhou, ErqiangLL(1)LL(1)分析法分析法 L L：从左到右扫描输入串：从左到右扫描输入串 L L：使用：使用最左推导最左推导 （1 1）：每次只检查）：每次只检查1 1个个“词法记号词法记号”对于输入的对于输入的“词法记号词法记号”序列序列 构建该序列的最左推导构建该序列的最左推导预测分析法School of Information and Software Engineering72Zhou, ErqiangLL(1)LL(1)预测分析表预测分析表E intE (E Op E)Op +Op *int()+*EEintE(E
39、 Op E)OpOp+Op*(int + (int * int)预测分析法School of Information and Software Engineering73Zhou, ErqiangLL(1)LL(1)预测分析表预测分析表1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)int()+*E12Op34预测分析法School of Information and Software Engineering74Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int *
40、int)int()+*E12Op34E预测分析法School of Information and Software Engineering75Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#在输入串在输入串后后加上加上# #做标记做标记 表示输入串已经结束表示输入串已经结束第一个符号是开始符号第一个符号是开始符号 检查分析表检查分析表 确定推导的产生式确定推导的产生式这一步为这一步为预测预测预测分析法School of Information and Software Eng
41、ineering76Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#(int + (int * int)#(E Op E)#2对于所猜测的句型对于所猜测的句型 第一个符号是第一个符号是终结符终结符将将其其与输入串与输入串第一个符号第一个符号 进行匹配进行匹配句型句型左边左边的符号与的符号与 输入串输入串左边左边的符号匹配的符号匹配句型句型逆序逆序压入栈压入栈预测分析法School of Information and Software Engineering77Zhou, Er
42、qiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#(int + (int * int)#(E Op E)#int + (int * int)#E Op E)#2对于所猜测的句型对于所猜测的句型 第一个符号是第一个符号是终结符终结符将将其其与输入串与输入串第一个符号第一个符号 进行匹配进行匹配句型句型左边左边的符号与的符号与 输入串输入串左边左边的符号匹配的符号匹配句型句型逆序逆序压入栈压入栈预测分析法School of Information and Software Engineering78
43、Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#(int + (int * int)#(E Op E)#int + (int * int)#E Op E)#1int + (int * int)#int Op E)#+ (int * int)#Op E)#3+ (int * int)#+ E)# (int * int)#E)#2 (int * int)#(E Op E)# int * int)#E Op E)# int * int)#int Op E)# * int)#Op E)
44、#4 * int)#* E)# int)#E)# int)#int)# )#)# )#)# #预测分析法School of Information and Software Engineering79Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int + (int * int)#int()+*E12Op34E#(int + (int * int)#(E Op E)#int + (int * int)#E Op E)#int + (int * int)#int Op E)#+ (int * int)#Op E)#+ (int * int)#+
45、 E)# (int * int)#E)# (int * int)#(E Op E)# int * int)#E Op E)# int * int)#int Op E)# * int)#Op E)# * int)#* E)# int)#E)# int)#int)# )#)# )#)# #预测分析法错误处理一School of Information and Software Engineering80Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *int + int#int()+*E12Op34E#1int + int#int#+ int#预测分析
46、法错误处理二School of Information and Software Engineering81Zhou, Erqiang1) E int2) E (E Op E)3) Op +4) Op *(int (int)#int()+*E12Op34E#2(int (int)#(E Op E)#int (int)#E Op E)#int (int)#int Op E)#1(int)#Op E)#预测分析法总结School of Information and Software Engineering82Zhou, Erqiang组成组成 一个下推栈一个下推栈 一个分析表一个分析表分析过程初
47、始状态分析过程初始状态 栈：结束符栈：结束符# # 和和 开始符开始符S S 指针：输入串指针：输入串的第一个符号的第一个符号预测分析法总结School of Information and Software Engineering83Zhou, Erqiang分析过程中某一时刻：分析过程中某一时刻： 栈顶符号为栈顶符号为x x，输入符号为，输入符号为a a分析器的动作有下列三种选择：分析器的动作有下列三种选择： 1)1)若若 x = a = #x = a = # 则符号串和栈均为空则符号串和栈均为空 则输入串则输入串是文法的一个合法句子是文法的一个合法句子 分析过程结束分析过程结束预测分析法
48、总结School of Information and Software Engineering84Zhou, Erqiang分析器的动作有下列三种选择：分析器的动作有下列三种选择： 2)2)若若 x = a # 则则x x出栈，指针移向下一个符号出栈，指针移向下一个符号 继续下一次匹配继续下一次匹配预测分析法总结School of Information and Software Engineering85Zhou, Erqiang分析器的动作有下列三种选择：分析器的动作有下列三种选择： 3)3)若若x x为非终结符，则查分析表为非终结符，则查分析表 若若Mx，a中存放中存放 x 则则x出栈
49、，将出栈，将串串逆序逆序压入栈中压入栈中 若若Mx，a中为出错标志中为出错标志 则调用出错处理程序则调用出错处理程序error( )预测分析法总结School of Information and Software Engineering86Zhou, Erqiang预测分析法的关键是预测分析法的关键是分析表分析表 如何构造分析表？如何构造分析表？ 手动构造手动构造 算法构造算法构造School of Information and Software Engineering87Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT |
50、while while EXPREXPR do do STMTSTMT | EXPREXPR ; ;EXPREXPR TERMTERM - id - id | zero? zero? TERMTERM | not not EXPREXPR | + id+ id | - id- idTERMTERM id id | constantconstant预测分析表的构造id - id;id - id;while not zero? idwhile not zero? id do do -id;id;if not zero? id thenif not zero? id then if not zero
51、? id then if not zero? id then constant - id; constant - id;School of Information and Software Engineering88Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5
52、)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)ifthenwhiledozero?not+-idconst;-STMTEXPRTERMSchool of Information and Software Engineering89Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do
53、 do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)910ifthenwhiledozero?not+-idconst;-STMTEXPRTERMSchool of Information and Softw
54、are Engineering90Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9)
55、| constant constant (10)(10)567ifthenwhiledozero?not+-idconst;-STMTEXPRTERM9108School of Information and Software Engineering91Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero?
56、 zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)567844ifthenwhiledozero?not+-idconst;-STMTEXPRTERM910School of Information and Software Engineering92Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(
57、1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)ifthenwhiledozero?not+-idconst;-STMTEXPR567844TERM
58、91012School of Information and Software Engineering93Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | -
59、id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)ifthenwhiledozero?not+-idconst;-STMTEXPR567844TERM910123333School of Information and Software Engineering94Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(
60、3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)ifthenwhiledozero?not+-idconst;-STMTEXPR567844TERM91012333333School of Information and Software Engineering95Zhou, Erq
61、iangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(1
62、0)ifthenwhiledozero?not+-idconst;-STMT12333333EXPR567844TERM910School of Information and Software Engineering96Zhou, Erqiang预测分析表的构造手动方法总结手动方法总结 当前符号当前符号唯一确定一个产生式唯一确定一个产生式 要选择的产生式要选择的产生式 最终能推导出以当前符号开始的串最终能推导出以当前符号开始的串MA,t 为产生式为产生式 A 当且仅当当且仅当能推导出以能推导出以 t 开始的串开始的串School of Information and Software Eng
63、ineering97Zhou, Erqiang预测分析表的构造构造算法构造算法 FIRST集集 和和 FOLLOW集集FIRST集的定义集的定义 对对 ( VT VN )*, ,有有 FIRST() t | * t , a VT 若若=*, ,则则 FIRST()School of Information and Software Engineering98Zhou, Erqiang预测分析表的构造对对 ( VT VN )*, , FIRST() 的构造方法的构造方法使用下列规则，直至使用下列规则，直至FIRST集不在增大集不在增大 若若X VT，则，则FIRST(X) = XSchool o
64、f Information and Software Engineering99Zhou, Erqiang预测分析表的构造若若X VN，且且 1) X 则则 FIRST(X) 2) Xa 则则 a FIRST(X) 3) XY 且且 Y VN 则则 FIRST(Y) FIRST(X)School of Information and Software Engineering100Zhou, ErqiangFIRST集的构造关于规则关于规则（3 3） 3) XYZ 且且 Y =* , Z VN 则则 FIRST(Z) FIRST(X) 例：例： X MNY M m N n Y yFIRST(Y)
65、=y FIRST(N)=n, FIRST(M)=m, FIRST(X)=m, n, ySchool of Information and Software Engineering101Zhou, ErqiangFIRST集的构造1School of Information and Software Engineering102Zhou, ErqiangFIRST集的构造2STMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR do do STMT STMT (2)(2) | EXPREXPR ; ; (
66、3)(3)EXPREXPR TERMTERM - id - id (4)(4) | zero? zero? TERM TERM (5)(5) | not not EXPR EXPR (6)(6) | + id + id (7)(7) | - id - id (8)(8)TERMTERM id id (9)(9) | constant constant (10)(10)STMTEXPRTERMifwhilezero?not+- -idconstantSchool of Information and Software Engineering103Zhou, ErqiangFIRST集的构造2ST
67、MT if EXPR then STMT (1)STMT if EXPR then STMT (1) | while EXPR do STMT (2)while EXPR do STMT (2) | EXPR ; EXPR ; (3)(3)EXPREXPR TERMTERM - id (4) - id (4) | zero? TERM (5)zero? TERM (5) | not EXPR (6)not EXPR (6) | + id (7)+ id (7) | - id (8)- id (8)TERM id (9)TERM id (9) | constant (10)constant (1
68、0)STMTEXPRTERMifzero?idwhilenotconstant+-idconstant 3) XY 且且 Y VN 则则 FIRST(Y) FIRST(X)School of Information and Software Engineering104Zhou, ErqiangFIRST集的构造2STMTSTMT if EXPR then STMT (1)if EXPR then STMT (1) | while EXPR do STMT (2)while EXPR do STMT (2) | EXPREXPR ; ; (3)(3)EXPR TERM - id (4)EXPR
69、 TERM - id (4) | zero? TERM (5)zero? TERM (5) | not EXPR (6)not EXPR (6) | + id (7)+ id (7) | - id (8)- id (8)TERM id (9)TERM id (9) | constant (10)constant (10)STMTEXPRTERMifzero?idwhilenotconstant+-idconstantzero?not+- -idconstantSchool of Information and Software Engineering105Zhou, ErqiangFIRST集
70、的构造3NumNum Sign DigitsSign DigitsSignSign + | - | + | - | DigitsDigits Digit MoreDigit MoreMoreMore DigitDigit | | DigitDigit 0 | 1 | 0 | 1 | | 9 | 9 NumSignDigitsMoreDigit+-0123456789School of Information and Software Engineering106Zhou, ErqiangFIRST集的构造3NumNum Sign DigitsSign DigitsSign + | - | Si
71、gn + | - | Digits Digit MoreDigits Digit MoreMore Digit | More Digit | Digit 0 | 1 | Digit 0 | 1 | | 9 | 9 NumSignDigitsMoreDigit+ -0 12 34 56 78 9+-School of Information and Software Engineering107Zhou, ErqiangFIRST集的构造3Num Sign DigitsNum Sign DigitsSign + | - | Sign + | - | Digits Digit MoreDigits
72、 Digit MoreMore Digit | More Digit | Digit 0 | 1 | Digit 0 | 1 | | 9 | 9 NumSignDigitsMoreDigit+ -+ -0 12 34 56 78 90123456789School of Information and Software Engineering108Zhou, ErqiangFIRST集的构造3Num Sign DigitsNum Sign DigitsSign + | - | Sign + | - | Digits Digit MoreDigits Digit MoreMore Digit |
73、 More Digit | Digit 0 | 1 | Digit 0 | 1 | | 9 | 9 NumSignDigitsMoreDigit+ -+ -0 10 12 32 34 54 56 76 78 98 90123456789School of Information and Software Engineering109Zhou, ErqiangFIRST集的构造3Num Sign DigitsNum Sign DigitsSignSign + | - | + | - | Digits Digit MoreDigits Digit MoreMore More Digit | Dig
74、it | Digit 0 | 1 | Digit 0 | 1 | | 9 | 9 NumSignDigitsMoreDigit+ -+ -0 10 10 12 32 32 34 54 54 56 76 76 78 98 98 9School of Information and Software Engineering110Zhou, ErqiangFIRST集的构造3Num Sign DigitsNum Sign DigitsSign + | - | Sign + | - | Digits Digit MoreDigits Digit MoreMore Digit | More Digit
75、| Digit 0 | 1 | Digit 0 | 1 | | 9 | 9 NumSignDigitsMoreDigit+ -+ -0 10 10 12 32 32 34 54 54 56 76 76 78 98 98 90123456789School of Information and Software Engineering111Zhou, ErqiangFIRST集与LL(1)分析表1MSG MSG HI END HI ENDHI HI hello | heya | yohello | heya | yoEND END world! | world! | MSGHIENDhelloh
76、eyayoworld!MSGHIENDhelloheyayoworld!School of Information and Software Engineering112Zhou, ErqiangFIRST集与LL(1)分析表1MSG MSG HI END HI ENDHI hello | heya | yoHI hello | heya | yoEND world! | END world! | MSGHIENDhelloworld!heyayohelloheyayoworld!MSGHIENDhelloheyayoSchool of Information and Software Eng
77、ineering113Zhou, ErqiangFIRST集与LL(1)分析表1MSGHIENDhellohelloworld!heyaheyayoyohelloheyayoworld!MSGHIENDMSG MSG HI END HI ENDHIHI hello | heya | yohello | heya | yoENDEND world! | world! | MSG HI END MSG HI END MSG HI ENDSchool of Information and Software Engineering114Zhou, ErqiangFIRST集与LL(1)分析表1MSGH
78、IENDhellohelloworld!heyaheyayoyohelloheyayoworld!MSGMSG HI ENDMSG HI ENDMSG HI ENDHIENDMSG MSG HI END HI ENDHIHI hello | heya | yohello | heya | yoENDEND world! | world! | HI helloHI heyaHI yoSchool of Information and Software Engineering115Zhou, ErqiangFIRST集与LL(1)分析表1MSGHIENDhellohelloworld!heyahe
79、yayoyohelloheyayoworld!MSGMSG HI ENDMSG HI ENDMSG HI ENDHIHI helloHI heyaHI yoENDMSG MSG HI END HI ENDHIHI hello | heya | yohello | heya | yoENDEND world! | world! | END world!School of Information and Software Engineering116Zhou, ErqiangFIRST集与LL(1)分析表1helloheyayoworld!MSGMSG HI ENDMSG HI ENDMSG HI
80、 ENDHIHI helloHI heyaHI yoENDEND world!hello#MSG#hello#HI END#MSG HI ENDHI hellohello#hello END#END#School of Information and Software Engineering117Zhou, ErqiangFIRST集与LL(1)分析表1helloheyayoworld!MSGMSG HI ENDMSG HI ENDMSG HI ENDHIHI helloHI heyaHI yoENDEND world!hello#MSG#hello#HI END#hello#hello EN
81、D#END#School of Information and Software Engineering118Zhou, ErqiangFIRST集与LL(1)分析表1helloheyayoworld!MSGMSG HI ENDMSG HI ENDMSG HI ENDHIHI helloHI heyaHI yoENDEND world!hello#MSG#hello#HI END#hello#hello END#END#MSG MSG HI END HI ENDHIHI hello | heya | yohello | heya | yoENDEND world! | world! | #EN
82、D #School of Information and Software Engineering119Zhou, ErqiangFIRST集与LL(1)分析表2i+*()#EETTFE E TE TEE E + +TETET T FT FTT T * *FT FT F F ( (E E) ) i iFirstEETTF( i* ( i+ ( iETEETEE+TETFTTFTT*FT FiF(E)School of Information and Software Engineering120Zhou, ErqiangFIRST集与LL(1)分析表2E E TE TEE E + +TETET
83、 T FT FTT T * *FTFTF F ( (E E) ) i iE E TE TE FT FTE E FT FTE E (E)T (E)TE E (TE (TE)T)TE E (FT (FTE E)T)TE E (iT (iTE E)T)TE E (iE (iE)T)TE E (i)T (i)TE E (i)*FT (i)*FTE E (i)*iT (i)*iTE E (i)*i (i)*iE E (i)*i (i)*ii+*()#EETTFETEETEE+TETFTTFTT*FT FiF(E)School of Information and Software Engineering
84、121Zhou, ErqiangFIRST集与LL(1)分析表2i+*()#EETTFETEETEE+TETFTTFTT*FT FiF(E)(i)*i#E#(i)*i#TE#(i)*i#FTE#(i)*i#(E)TE#i)*i#E)TE#i)*i#TE)TE#i)*i#FTE)TE#E E TE TEE E + +TETET T FT FTT T * *FTFTF F ( (E E) ) i iSchool of Information and Software Engineering122Zhou, ErqiangFIRST集与LL(1)分析表2i+*()#EETTFETEETEE+TETF
85、TTFTT*FT FiF(E)(i)*i#E#(i)*i#i)*i#iTE)TE#)*i#TE)TE#T)T E E TE TEE E + +TETET T FT FTT T * *FTFTF F ( (E E) ) i iSchool of Information and Software Engineering123Zhou, ErqiangFIRST集与LL(1)分析表2i+*()#EETTFETEETEE+TETFTTFTT*FT FiF(E)(i)*i#E#(i)*i#i)*i#iTE)TE#)*i#TE)TE#T)T ?)*i#E)TE#)*i#E)TE#E E TE TEE E
86、+ +TETET T FT FTT T * *FTFTF F ( (E E) ) i iSchool of Information and Software Engineering124Zhou, ErqiangFIRST集与LL(1)分析表2(i)*i#E#(i)*i#i)*i#iTE)TE#)*i#TE)TE#T)*i#E)TE#)*i#E)TE#符号符号）应该属于应该属于T后面符号的后面符号的FIRST集集当文法有当文法有产生式产生式 可能必须查看当前非终结符可能必须查看当前非终结符后面的符号后面的符号 当前非终结符后面会跟当前非终结符后面会跟哪些符号哪些符号E E TE TEE E +
87、 +TETET T FT FTT T * *FTFTF F ( (E E) ) i iSchool of Information and Software Engineering125Zhou, Erqiang预测分析表的构造构造算法构造算法 FIRSTFIRST集集 和和 FOLLOWFOLLOW集集FOLLOWFOLLOW集的定义集的定义 对对A VN ,有有 FOLLOW(A)=a | S * Aa, a VT 若若S * A, 则则 # FOLLOW(A)哪些终结符号可以跟随在哪些终结符号可以跟随在A后面后面School of Information and Software Engi
88、neering126Zhou, Erqiang预测分析表的构造对对A VN FOLLOW(A) 的构造方法的构造方法使用下列规则，直至使用下列规则，直至FOLLOW集不在增大集不在增大 1) # FOLLOW(S) 2)若若 BA 则则FIRST( )- FOLLOW(A)School of Information and Software Engineering127Zhou, Erqiang预测分析表的构造使用下列规则，直至使用下列规则，直至FOLLOW集不在增大集不在增大 3) 3) BA 或者或者 BA 且且 * 则则 FOLLOW(B) FOLLOW(A) mBn = mAn mBn
89、 = mAn = mAn例：例： ETE E+TE TFT T*FT F(E)iSchool of Information and Software Engineering128Zhou, Erqiang预测分析表的构造FirstFollowEETTF( i* ( i+ ( i#)# )BA 或者或者 BA 且且 * 则则 FOLLOW(B) FOLLOW(A)+ E+TE# )ETE+ # )* + # )School of Information and Software Engineering129Zhou, Erqiangi+*()#EETTFFirstFollowE( i# )E+
90、# )T( i+ # )T* + # )F( i* + # )ETEETEE+TETFTTFTT*FT FiF(E)E E T T E E TE TEE E + +TETET T FT FTT T * *FT FT F F ( (E E) ) i iT 预测分析表的构造构造算法：构造算法：对对每个产生式每个产生式A： 1) 1) 对对 x FIRST(), , 将将A 记入记入 MA,x;MA,x; 2) 2) 若若 FIRST(), ,则对则对 b b FOLLOW(FOLLOW(A A) ) 将将A 记入记入 MMA A, ,b b ； 3) 3) 其它表项为空白，表示出错其它表项为空白，
91、表示出错School of Information and Software Engineering130Zhou, Erqiang预测分析表的构造考虑左递归考虑左递归AAb | c： FIRST(A) = =c 是否能构建是否能构建LL(1)LL(1)分析表，为什么分析表，为什么？不能不能唯一唯一的确定产生式的确定产生式School of Information and Software Engineering131Zhou, Erqiang非LL(1)文法bcAAAb Ac 考虑文法考虑文法 ET ET+E Tint T(E)FIRST(E) = int, ( , FIRST(T) = i
92、nt, ( 不能不能唯一唯一的确定产生式的确定产生式School of Information and Software Engineering132Zhou, Erqiang非LL(1)文法+int()EET ET+E ET ET+E TTint T(E) 每一非终结符每一非终结符A A的的任两个任两个产生式产生式 A | 1) FIRST( ) FIRST( ) = 2) 若若 * ，则 FIRST( ) FOLLOW(A) = 即：即：文法文法G G的预测分析表不含多重入口的预测分析表不含多重入口School of Information and Software Engineering133Zhou, ErqiangLL(1)文法Zhou, Erqiang134/16THE ENDQUESTIONSSchool of Information and Software Engineering实验2递归下降分析地点：信软楼303 实验中心时间：10月11日 下午下午14:30至17:302014220301001-312014220302001-31 2014220303001-19时间：10月11日 上午9:00至12:00所有其他同学
