编译技术：第04章02 自上而下的语法分析

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+i

7、ntint+(E)int+T+ESchool of Information and Software EngineeringZhou, Erqiang11算法1：广度搜索法Q Q为一个为一个“句型句型”的队列的队列 初始时队列仅有开始符号初始时队列仅有开始符号S S当队列不为空当队列不为空 从队列取一个句型从队列取一个句型 如果该句型与输入串匹配，停止如果该句型与输入串匹配，停止 否则将该句型所有的一步推导句型加到否则将该句型所有的一步推导句型加到Q Q根据所使用的产生式确定语法树根据所使用的产生式确定语法树School of Information and Software Engineer

8、ingZhou, 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, Erqia

9、ng14针对针对“不可能匹配不可能匹配的句型的句型” 假设输入串为假设输入串为 对句型对句型 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 Engin

11、eeringZhou, 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 TE

12、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)int

13、+ 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 and

14、 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 aASS

15、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, E

16、rqiang30算法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 =* A

18、 对串对串 产生式产生式School of Information and Software EngineeringZhou, Erqiang35算法2：存在问题算法问题算法问题 广度搜索广度搜索 同时考虑同时考虑多个多个分支！分支！School of Information and Software EngineeringZhou, Erqiang36文法改造公共左因子公共左因子 A 1 | 2 提取公共左因子提取公共左因子文法中有左递归文法中有左递归 消除左递归消除左递归School of Information and Software EngineeringZhou, Erqiang3

19、7文法改造公共左因子公共左因子 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）依次代入产生式）依次代入产生式 SQ

24、cc 不变不变 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 School

25、 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 of

27、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 Software

30、Engineering58Zhou, Erqiang每个非终结符对应一个解析函数每个非终结符对应一个解析函数产生式右侧为其左侧非终结符产生式右侧为其左侧非终结符 所对应解析函数的所对应解析函数的“函数体函数体”产生式右侧终结符产生式右侧终结符 对应从输入串中消耗该终结符对应从输入串中消耗该终结符产生式中的产生式中的| 对应对应“if-else”if-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表示当前符号表示当前符号函数函数adv

32、ance()() 读取下一字符读取下一字符递归下降分析法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, ErqiangETFiiM(

33、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 Engineering64

34、Zhou, 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 Engineering

36、68Zhou, 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+(in

37、t+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 an

38、d 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 O

39、p 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 * in

40、t)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 Engin

41、eering76Zhou, 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, Erqi

42、ang1) 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 Engineering78Zh

43、ou, 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)#4

44、 * 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)#+ E

45、)# (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 zer

51、o? 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 (

52、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;-STMTEXPRTERMSchool of Information and Software Engineering89Zhou, ErqiangSTMTSTMT if if EXPREXPR then then STMT STMT (1)(1) | while while EXPREXPR d

53、o 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 Soft

54、ware 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;-STMTEXPR567844TER

58、M91012School 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, Er