编译原理与技术 自顶向下分析.ppt

2020 3 1 编译原理与技术 讲义 1 编译原理与技术 自顶向下分析 2020 3 1 编译原理与技术 讲义 2 自顶向下分析 分析树的建立从根 开始符号 出发 从上而下 从左自右为输入串建立分析树为输入串寻找一个最左推导 e g 1文法g0如下s abca ab bc c输入串abc 串结束符 2020 3 1 编译原理与技术 讲义 3 自顶向下分析 e g 1文法g0 s abca ab bc c abc s 当前记号 指针 2020 3 1 编译原理与技术 讲义 4 自顶向下分析 e g 1文法g0 s abca ab bc c abc s abc 2020 3 1 编译原理与技术 讲义 5 自顶向下分析 e g 1文法g0 s abca ab bc c abc s abc a 2020 3 1 编译原理与技术 讲义 6 自顶向下分析 e g 1文法g0 s abca ab bc c abc s abc a 终结符叶子与当前符号匹配 2020 3 1 编译原理与技术 讲义 7 自顶向下分析 e g 1文法g0 s abca ab bc c abc s abc a b 指向下一记号 2020 3 1 编译原理与技术 讲义 8 自顶向下分析 e g 1文法g0 s abca ab bc c abc s abc a b 2020 3 1 编译原理与技术 讲义 9 自顶向下分析 e g 1文法g0 s abca ab bc c abc s abc a b c 2020 3 1 编译原理与技术 讲义 10 自顶向下分析 e g 1文法g0 s abca ab bc c abc s abc a b c 2020 3 1 编译原理与技术 讲义 11 自顶向下分析 e g 1文法g0 s abca ab bc c abc s abc a b c ok 输入串分析成功 2020 3 1 编译原理与技术 讲义 12 自顶向下分析 e g 1文法g0 s abca ab bc c 串abc 的最左推导过程 s abc abc abc abc 2020 3 1 编译原理与技术 讲义 13 自顶向下分析 文法g0较简单 非终结符只有唯一的产生式试探分析法当待分析 展开 的非终结符对应多条产生式 可以选择其一进行尝试分析 最左推导 当此产生式无法与输入串 匹配 时则需要 回溯 即放弃已建立的部分分析树 同时调整输入串指针恢复到此次分析前位置 再另选一产生式重新分析 只有当所有的所有的尝试均不成功 分析失败 2020 3 1 编译原理与技术 讲义 14 自顶向下分析 试探分析法e g 2文法g1如下s xaya aba a输入串xay 的分析过程 2020 3 1 编译原理与技术 讲义 15 自顶向下分析 试探分析法e g 2文法g1 1 s xay 2 a ab 3 a a输入串xay 的分析过程 s xay 终结符叶子x与输入符x匹配 ab 选用产生式 1 选用产生式 2 匹配失败 2020 3 1 编译原理与技术 讲义 16 自顶向下分析 试探分析法e g 2文法g1 1 s xay 2 a ab 3 a a输入串xay 的分析过程 s xay ab 选用产生式 1 选用产生式 2 匹配失败 回溯 重新分析a 2020 3 1 编译原理与技术 讲义 17 自顶向下分析 试探分析法e g 2文法g1 1 s xay 2 a ab 3 a a输入串xay 的分析过程 s xay 选用产生式 1 a 选用产生式 3 终结符叶子a与输入符a匹配 分析成功 2020 3 1 编译原理与技术 讲义 18 试探分析法在文法有左递归特征时 可能导致无限循环而此时无法读入任何输入符 输入指针保持不变 如表达式文法g2 e e t tt t f ff e id 自顶向下分析 e e t e t 2020 3 1 编译原理与技术 讲义 19 自顶向下分析 预测分析法对于待分析的非终结符a 可以根据当前输入符号 记号 来准确唯一地选择a的某一产生式 若该产生式 匹配 成功 则意味着a分析成功 若匹配失败 则即使选择a的其它产生式也会导致a分析失败 因而不需要回溯 case1 文法g1a aba的两个产生式右部具有a a相同的 非空 前缀a那么a面临输入符a选择谁呢 2020 3 1 编译原理与技术 讲义 20 预测分析法提左因子的文法变换文法g1中 a aba aa a aa b 自顶向下分析 a 1a 2 1和 2不含相同前缀 提左因子 a a a 1 2引入非终结符a 提左因子 2020 3 1 编译原理与技术 讲义 21 预测分析法e g 3文法g1中 a aba aa a aa b a面临a时有唯一的产生式a aa a 面临b时可以选a b 空产生式a 何时选用呢 自顶向下分析 提左因子 可以考虑 除b外的 任一符号c 可以与之 匹配 2020 3 1 编译原理与技术 讲义 22 预测分析法提左因子变换的一般形式 自顶向下分析 a 1 2 na i不含相同前缀 不含 前缀 提左因子变换后 a a a 1 2 n 2020 3 1 编译原理与技术 讲义 23 预测分析法case2 文法g2e e te的产生式的 直接 左递归妨碍了e t输入符号的有效读入 实际上不读 并导致死循环 消除左递归 a a 的文法变换 直接左递归的消除 a a 自顶向下分析 a a a 消除直接左递归 a a a a 引入非终结符a 形成右递归文法 2020 3 1 编译原理与技术 讲义 24 预测分析法e g 4消除文法g2中的直接左递归 e e te te e te te t t ft ft t ft ft f e f e f idf id 自顶向下分析 含左递归的文法g2 不含左递归的文法g2 2020 3 1 编译原理与技术 讲义 25 e e t t f i i f t i f 文法g2 i i i的分析树 e t e f t i t e f t i f t i 文法g2 i i i的分析树 2020 3 1 编译原理与技术 讲义 26 自顶向下分析 预测分析法消除左递归 a a 的文法变换 间接左递归的消除 a b a 对于含间接左递归的文法g 可以先设法变换为含有直接左递归的文法g 通常将较简单的产生式逐次代入较复杂的产生式 然后再行消除g 中的直接左递归即可 2020 3 1 编译原理与技术 讲义 27 自顶向下分析 预测分析法e g 5消除文法g3中的 间接 左递归 s aa a ba ac c sd将s相应产生式分别代入a相关产生式 得到文法g3 s aa a ba ac c aad ad bd消除g3 中 a的 直接左递归 则有 2020 3 1 编译原理与技术 讲义 28 自顶向下分析 预测分析法e g 5消除文法g3中的 间接 左递归 s aa a ba ca ada bda a ca ada 上述文法不再含有左递归 2020 3 1 编译原理与技术 讲义 29 自顶向下分析 回顾一下什么是预测分析法 对于待分析的非终结符a 可以根据当前输入符号 记号 来准确唯一地选择a的某一产生式 若该产生式 匹配 成功 则意味着a分析成功 若匹配失败 则即使选择a的其它产生式也会导致a分析失败 因而不需要回溯 在对文法提左因子和消除左递归后 可以实施预测分析了 但是 待分析或展开的非终结符a如何利用当前输入符 记号 来选择产生式呢 2020 3 1 编译原理与技术 讲义 30 first集合 首符号集合 first a a 其中a vt vt vn first a a a vt a vn 考查a的每个产生式 a x1x2 xn xi vt vn 计算first a 初始为 1 把firtst x1 加入first a 如果 first x1 则结束计算first a 否则2 把firtst x2 加入first a 如果 first x2 则结束计算first a 否则 n 把firtst xn 加入first a 如果 first xn 则结束计算first a 否则n 1 加入first a 2020 3 1 编译原理与技术 讲义 31 e g 6文法g2 的first集合 e te e te t ft t ft f e f id first f id 2020 3 1 编译原理与技术 讲义 32 e g 6文法g2 的first集合 e te e te t ft t ft f e f id first t 2020 3 1 编译原理与技术 讲义 33 e g 6文法g2 的first集合 e te e te t ft t ft f e f id first t first f id 2020 3 1 编译原理与技术 讲义 34 e g 6文法g2 的first集合 e te e te t ft t ft f e f id first e 2020 3 1 编译原理与技术 讲义 35 e g 6文法g2 的first集合 e te e te t ft t ft f e f id first e first t first f id 2020 3 1 编译原理与技术 讲义 36 e g 6文法g2 的first集合 e te e te t ft t ft f e f id first e first t first f id first e first t first f id first t first f id 2020 3 1 编译原理与技术 讲义 37 follow集合 后继符号集合 follow a a s aa 其中a vt a vn vt vn follow s 若a b p 则把first 加入follow b 若a b p或a b p且 即 first 则把follow a 加入follow b s aa s aa b a ba b a ba 显然a follow a follow b 2020 3 1 编译原理与技术 讲义 38 e g 7文法g2 的follow集合 e te e te t ft t ft f e f id follow e follow e 2020 3 1 编译原理与技术 讲义 39 e g 7文法g2 的follow集合 e te e te t ft t ft f e f id follow e follow e 2020 3 1 编译原理与技术 讲义 40 e g 7文法g2 的follow集合 e te e te t ft t ft f e f id follow t first e follow e 2020 3 1 编译原理与技术 讲义 41 e g 7文法g2 的follow集合 e te e te t ft t ft f e f id follow t follow t 2020 3 1 编译原理与技术 讲义 42 e g 7文法g2 的follow集合 e te e te t ft t ft f e f id follow f first t follow t follow t 2020 3 1 编译原理与技术 讲义 43 e g 7文法g2 的follow集合 e te e te t ft t ft f e f id follow f follow t follow t follow e follow e 2020 3 1 编译原理与技术 讲义 44 自顶向下分析a时 如果a只产生非空符号串 那么a期望 看到 的当前输入的符号最好是a first a 这样的话 选用产生式a 来分析 即能产生 推导 出以a开头的串并期待与相应输入串匹配 2020 3 1 编译原理与技术 讲义 45 自顶向下分析a时 如果a只产生的是不包含任何有效符号的串 则它 看到 的当前输入的符号只能是b follow a 这时选用产生式a 来 结束 对a的分析而开始 的分析 2020 3 1 编译原理与技术 讲义 46 自顶向下分析a时 如果a既产生非空串也可以产生 则它可能 看到 的当前输入的符号来自a first a 或者来自b follow a 但a最不期望的是a b 因为这样 a面临两难的选择 a 还是a 2020 3 1 编译原理与技术 讲义 47 ll 1 文法 一般的 文法g是ll 1 文法 如果任何a vn 其产生式 a 1 2 n 满足 first i first j i j i j 1 2 n 若 first k 则first i follow a i k readfromlefttoright leftmostderivation 1lookhead 2020 3 1 编译原理与技术 讲义 48 ll 1 文法 产生式不含左递归具有相同左部的产生式不含左因子ll 1 文法g进行自顶向下分析时 非终结符a面临当前输入符号a时即可作出唯一的产生式的选择决定 2020 3 1 编译原理与技术 讲义 49 自顶向下分析 ll 1 文法的递归下降分析为ll 1 文法g 无左因子 左递归 构造一个无回溯的预测分析器 文法g的每一个非终结符a对应一个 递归 分析过程a 分析过程a 1 由当前输入符号 lookhead 决定产生式的选取 2 产生式a x1x2 xn的分析过程 从左往右逐个分析 xi vt 则调用匹配过程match xi xi vn 则调用分析过程xi 3 空产生式a 直接返回 2020 3 1 编译原理与技术 讲义 50 递归分析过程a voida if lookhead first x1x2 xn 产生式a x1x2 xn的分析过程 elseif a的其它非空产生式的分析 elseif lookhead follow a anda p return 空产生式 直接返回 elseerror 语法错误 2020 3 1 编译原理与技术 讲义 51 递归下降分析 匹配过程match tokent voidmatch tokent if lookhead t 终结符叶子和输入符是否匹配 相同 lookhead next token 若匹配则获取下一记号 即向前移动输入指针 elseerror 否则语法错误 需要符号t 2020 3 1 编译原理与技术 讲义 52 递归下降分析 e g 8编写文法g2 的递归分析过程 e te e te t ft t ft f e f id voide if lookhead lookhead id t e elseerror 2020 3 1 编译原理与技术 讲义 53 e g 8编写文法g2 的递归分析过程 e te e te t ft t ft f e f id voide if lookhead match t e else return 将 看成与任一符号匹配 从而将以下程序省略 if lookhead lookhead return elseerror 2020 3 1 编译原理与技术 讲义 54 e g 8编写文法g2 的递归分析过程 e te e te t ft t ft f e f id voidt if lookhead lookhead id f t elseerror 2020 3 1 编译原理与技术 讲义 55 e g 8编写文法g2 的递归分析过程 e te e te t ft t ft f e f id voidt if lookhead match f t else return 将 看成与任一符号匹配 从而将以下程序省略 if lookhead lookhead lookhead return elseerror 2020 3 1 编译原理与技术 讲义 56 e g 8编写文法g2 的递归分析过程 e te e te t ft t ft f e f id voidf if lookhead match e match elseif lookhead id match id elseerror 2020 3 1 编译原理与技术 讲义 57 自顶向下分析 ll 1 文法的非递归的预测分析方法表驱动的预测分析 通过查表决定产生式的选取 输入串 控制程序 预测分析器 预测分析表 分析栈 输出 top bottom 2020 3 1 编译原理与技术 讲义 58 非递归的预测分析方法 分析栈 stack 栈的内容 vt vn 开始分析时 位于栈底 s位于栈顶 分析表m vn vt p error 对于a vn a vt 有a pm a a error 错误恢复例程控制程序 2020 3 1 编译原理与技术 讲义 59 非递归的预测分析方法 控制程序由当前栈顶符号x和当前输入符号a决定采取的分析动作 x vt x a 则分析成功 stop x a 则1 popup 从栈顶弹出x2 移动输入指针至下一符号 x a error 匹配失败 调用错误恢复程序 2020 3 1 编译原理与技术 讲义 60 非递归的预测分析方法 控制程序 x vn m x a x uvw 则popup 弹出xpush w push v push u 产生式右部符号以逆序入栈 m x a error 则调用错误恢复程序 2020 3 1 编译原理与技术 讲义 61 e g 9表达式文法g2 的预测分析表 2020 3 1 编译原理与技术 讲义 62 e g 10表达式id id id的非递归预测分析过程 2020 3 1 编译原理与技术 讲义 63 e g 10表达式id id id的非递归预测分析过程 续 2020 3 1 编译原理与技术 讲义 64 e g 10表达式id id id的非递归预测分析过程 续 分析成功 2020 3 1 编译原理与技术 讲义 65 预测分析表的构造 考查任意产生式a m a a a 如果a first m a b a 如果 first 且b follow a 所有无定义的表项填上error 预测分析表如果不含多重定义表项则相应文法是ll 1 的 2020 3 1 编译原理与技术 讲义 66 文法g4 if then else 1 s ietss 2 s a3 s es4 s 5 e b e g 11构造文法g4的预测分析表 first s i a first s e first e b follow s e follow s e follow e t 2020 3 1 编译原理与技术 讲义 67 e g 11构造文法g4的预测分析表 1 s ietss i first ietss 故而m s i s ietss 2 s a 显然 m s a s a 3 s es 显然 m s e s es 4 s 则对于follow s e 中的每个符号 有 m s s 和m s e s 5 e b 显然 m e b e b 2020 3 1 编译原理与技术 讲义 68 e g 11构造文法g4的预测分析表 有多重定义 2020 3 1 编译原理与技术 讲义 69 二义性文法决不是ll 1 文法 其预测分析表有多重定义表项 文法g4不是ll 1 文法 文法g4具有二义性 对于串ibtibtaea有两个不同的最左推导 s ietss ibtss ibtietss s ibtibtss s ibtibtas s ibtibtaess ibtibtaeas ibtibtaea ibtibtaea ibtibta s ibtibtas ibtibtaes ibtibtaea 1 2 2020 3 1 编译原理与技术 讲义 70 e g 12文法g5不是ll 1 文法 文法g5 1 a aaa2 a 文法g5产生串长为偶数的a串 它是非二义文法 但却不是ll 1 文法 因为 first a a follow a a 分析表中m a a a aaa a 有多重定义 或者 由于a 为空产生式 而first a aaa follow a a 2020 3 1 编译原理与技术 讲义 71 a aaa aaa 文法g5关于串aaaa的最左推导与分析树 a1 aaa2 aaaaa3 aa aa4 aaaa 显然 在只有在偶数长 2 的a串的前一半a被产生 推导 出来后 产生式a 方被选择来作分析 推导 而此前只用a aaa 2020 3 1 编译原理与技术 讲义 72 a aaaa 输入串 自顶向下分析输入a串 即寻找一个产生a串的最左推导过程 但遗憾是 输入串是从左往右一个一个符号地被读入 每当读入一个符号a时 由于不知道输入串中总共有多少符号a 也就无法判定此时是否已经 读完了 a串的前一半a 这就造成了a面临输入a时的存在矛盾 或多重 的产生式选择 2020 3 1 编译原理与技术 讲义 73 错误恢复 程序的错误类型编译时错误 compileerror 词法错误 如出现非法字符语法错误 如括号不配对 语句结束无分号 静态 语义错误 如形 实参数类型不匹配运行时错误 run timeerror 动态 运行时 语义错误 无限递归 循环 地址 指针 越界 栈上溢 overflow 和下溢 underflow 异常 exception 2020 3 1 编译原理与技术 讲义 74 错误恢复 错误恢复的目标错误 性质 报告准确 错误位置精准能快速地从当前错误中恢复 以期发现后面的错误 任何 编译 错误不能导致编译器崩溃对常见的错误应该有很好的恢复措施尽量减少 株连 错误的产生 2020 3 1 编译原理与技术 讲义 75 错误恢复 错误恢复的策略紧急方式 panicmode 发现错误时 分析器将抛弃若干输入符号 直到遇上希望的输入 同步符号为止 该方法较容易实现且不会陷入死循环 但对忽略的输入无法进行分析 同步符号 集合 的选取 若待分析语法成份为a 则同步符号 集合 synch a 的可以考虑 1 follow a 考虑结束a的分析工作2 first a 重新开始a的分析 2020 3 1 编译原理与技术 讲义 76 e g 13紧急方式错误恢复 a exprif 寻找 因为 follow stat 被跳过的输入串 missing 2020 3 1 编译原理与技术 讲义 77 e g 13紧急方式错误恢复 a exprif 3 为避免忽略过多的输入符号 可以考虑将较高层次的语法单位的首符号 first 加入低层结构的同步符号集合中 如语句stat的首符号if加入synch stat 这样 当某一语句分析出错时 可以抛弃该语句中的其它输入符号 而开始下一个新语句的分析 新的分析起点 2020 3 1 编译原理与技术 讲义 78 错误恢复 错误恢复的其它策略短语级恢复 phraselevel 对输入串作局部校正 插入或删除符号出错产生式 errorproduction 将出错情况用产生式的形式来描述 参见yacc 如stat error 描述语句分析时出错时将跳过若干输入符号直至 出现全局校正 globalcorrection 2020 3 1 编译原理与技术 讲义 79 预测分析的错误恢复 递归下降分析的错误恢复为每个分析过程增加一个参数 同步符号集合一般地 当错误发生时 错误恢复例程error 将反复调用词法程序忽略若干输入符号 直至同步集合 可以考虑follow集合 中的符号出现为止 然后分析过程结束返回 2020 3 1 编译原理与技术 讲义 80 e g 14文法g2 带有错误恢复的分析过程 e te e te t ft t ft f e f id voide syncset if lookhead lookhead id t syncset e syncset elseerrore syncset 2020 3 1 编译原理与技术 讲义 81 e g 14文法g2 带有错误恢复的分析过程 e te e te t ft t ft f e f id voide syncset if lookhead match t sy