编译原理自上而下语法分析.ppt

第四章自上向下语法分析 语法分析的任务本章要点 自上而下语法分析的思想LL 1 方法递归下降分析预测分析 基本思想 主旨对任何输入串 试图用一切可能 从文法的开始符号出发 自上而下地为输入串建立一棵语法树 或者为输入串寻找一个最左推导 本质上是一种试探过程 要解决的基本问题 例 G S S xAyA 考虑输入串x y对于特定的非终结符号 使用哪个产生式来替换 带回溯的自上而下语法分析存在的困难和缺点 文法的递归性虚假匹配错误的位置难以确定效率低 代价高 无回溯的自上向下分析技术 先决条件 无左递归既没有直接左递归 也没有间接左递归 无回溯性对于任一非终结符号U的产生式右部x1 x2 xn 各xi的首终结符号两两不相交 文法的左递归性 定义 文法的左递归性是指文法具有以下形式的直接左递归 U Ux y或间接左递归 U Ux 具有左递归性的文法举例 E E T TT T F FF E i 消除文法的直接左递归 P P 1 P n 1 m改写为 P 1P mP P 1P nP 例子 消除左递归前E E T TT T F FF E i 消除左递归后E TE E TE T FT T FT F E i 间接左递归举例 S Qc cQ Rb bR Sa a以上文法不含直接左递归 但S Q R都是左递归的 因为 S Qc Rbc SabcQ Rb Sab QabcR Sa Qca Rbca 消除文法的左递归 前提 如果一个文法不含回路 形如P P的推导 也不含以 为右部的产生式 那么可以通过执行消除文法左递归的算法消除文法的一切左递归 改写后的文法可能含有以 为右部的产生式 消除文法的一切左递归的算法 1 把文法的所有非终结符按任一顺序排序2 FORi 1TOnDO 1 FORj 1TOi 1DO把形如Pi Pj 的规则改写成Pi 1 k 其中Pj 1 k是关于Pj的所有规则 2 消除关于规则的直接左递归3 化简由2所得的文法 例子 A BcdB Ce fC Ab c 消除回溯的基本思想 必须保证对文法的任何非终结符 当要它去匹配输入串时 能够根据它所面临的输入符号 指派它的一个候选 右部 去执行任务 并且此候选的工作结果应是确定无疑的 即要么匹配成功 要么不可能获得匹配 消除回溯对文法的要求 1 首先 文法不得含有左递归 2 设文法G不含左递归 对G的所有非终结符的每个候选 定义其终结首符集FIRST 为FIRST a a a VT 特别是 若 则规定 FIRST 如果非终结符A的所有候选首符集两两不相交 那么 当要求A匹配输入串时 A就能根据它所面临的第一个输入符号a 准确地指派某一个候选去执行任务 这个候选就是那个终结首符集含a的 消除回溯方法 提取公共左因子 假设关于A的产生式是A 1 2 n n 1那么 可以将其改写为A A n 1A 1 2 n经过反复提取左因子 就能够把每个非终结符 包括新引进者 的多有候选首符集变成为两两不相交 代价 引入大量新的非终结符和空产生式 G S S BxB x 考虑输入串xFOLLOW U b S xUby b VT x y VN VT 特别地 FOLLOW S LL 1 分析条件 文法不含左递归设U是文法G的任一个非终结符 其产生式为U x1 x2 xn如果FIRST xi FIRST xj i j i j 1 2 n 当 FIRST xi 时 有FIRST xi FOLLOW U 则文法G为LL 1 文法 LL 1 方法 基本思想 从S出发 生成句子的最左推导 选择合适产生式 从左到右扫描源程序 每次通过向前查看1个字符 选择合适的产生式 适用范围 仅对LL 1 文法适用 FIRST 和FOLLOW U 定义 1 FIRST a a a VT VN VT 特别地 如果 那么 我们规定 FIRST 2 FOLLOW U b S xUby b VT x y VN VT 特别地 FOLLOW S 直观地讲 FIRST u 包含了u对应的字的所有可能的首终结符号 FOLLOW U 表示了句型中可能紧跟再U后面的终结符号 FIRST 构造算法 对于X VN VT FIRST X 的构造1 若X VT 则FIRST X X 2 若X VN 且有产生式X a a VT 则a FIRST X 如果X 那么 FIRST X 3 若有产生式X Y Y VN 则FIRST Y FIRST X 如果有产生式X Y1Y2 YK 其中Y1 Y2 Yi 1 VN且Y1Y2 Yi 1 则FIRST Yi FIRST X 若Y1Y2 YK 则 FIRST X FIRST 构造算法 续 设 VN VT X1X2 Xn FIRST 的构造1 若 则FIRST 2 若 则FIRST X1 FIRST 3 若X1X2 Xi 1 则FIRST Xi FIRST 若X1X2 Xn 则 FIRST FOLLOW U 的构造算法 1 FOLLOW S 2 如果有产生式A xUy 那么FIRST y FOLLOW U 3 如果有产生式A xU或则A xUy且y 那么FOLLOW A FOLLOW U 注意 步骤3需要重复执行 直到没有哪个非终结符号的FOLLOW集合增长为止 FIRST的例子 文法G E E TE E TE T FT T FT F E iFIRST F i FIRST T FIRST F i FIRST E FIRST T FOLLOW例子 文法G E E TE E TE T FT T FT F E iFOLLOW E FOLLOW E FOLLOW E FOLLOW T FIRST E FOLLOW E FOLLOW T FOLLOW T FOLLOW F FIRST T FOLLOW T 例子 求FIRST集与FOLLOW举例 文法G A A BB X B B AB X aX bX X aX bX 递归下降分析程序 实现思想 实现思想 识别程序由一组子程序组成 每个子程序对应于一个非终结符号 每一个子程序的功能是 选择正确的右部 扫描完相应的字 在右部中有非终结符号时 调用该非终结符号对应的子程序来完成 基本架构 1 变量 sym 当前符号函数 advance 读输入串下一符号对于每个非终结符号U 1 2 n处理的方法如下 P U ifsym FIRST 1 thenP 1 处理 1的程序部分elseifsym FIRST 2 thenP 2 处理 2的程序部分 elseifsym FIRST n thenP n elseifsym FOLLOW U thenreturn 处理空产生式情况elseerror 对于无回溯的文法保证选择是唯一的 基本架构 2 对于每个右部 x1x2 xn的处理架构如下 P P x1 处理x1的程序P x2 处理x2的程序 P xn 处理xn的程序 说明 如果右部为空 则不处理 基本架构 3 对于右部中的每个符号xi如果xi为终结符号 if sym a sym 下一输入符号 对于终结符 直接将指针前调elseerror如果xi为非终结符号 直接调用相应的过程 P xi 扩展的BNF表示法 花括号 x 表示符号串x出现0次或多次 即x x nm m表示符号串x能出现的最大次数 n表示符号串x能出现的最小次数方括号 表示 x 01 圆括号 利用圆括号可以提出非终结符的多个产生式右部的公共因子 E E T E T T可改成E T T T T T F T F F可改成T F F F 用扩展的BNF表示法消除左递归 例子 以上标识符产生式含有左递归 可以改写为 Z U aUb E T E T E TE T T T T F T F T FT F F F 有文法G Z Z AcB BdA AaB cB aA a设计递归下降分析程序 思考题 预测分析程序的结构 使用一个二维分析表和栈联合进行控制来实现语法分析 总控程序大同小异 而LL 1 分析表却千差万别 LL 1 分析表是进行LL 1 分析的核心 输入符号串 分析栈 LL 1 总控程序 分析表 输出流 预测分析表的结构 分析表实际上是一个从VN VT 到产生式的映射 通常以矩阵表示 其元素M U a 中可能存放一条非终结符U的产生式 说明当符号栈S的栈顶元素非终结符U遇到当前输入字符a时 所应选择的产生式 元素M U a 也可存放一个出错标志 说明符号栈S的栈顶元素非终结符U不应遇到当前输入符号a 预测分析器的总控原理 在任何时候 总控程序都是按照栈顶符号X和当前输入符号a工作的 对于任何 X a 总控程序每次都执行下述三种可能的动作之一 1 若X a 则宣布分析成功 停止分析过程 2 若X a 则把X从栈顶逐出 让a指向下一输入符号 3 若X是一个非终结符 则查看分析表M 若M中存放着一条关于X的产生式 那么 首先把X逐出栈顶 然后 把产生式的右部符号按反序一一推进栈 同时做这个产生式相应的语义动作 目前不管 若M X a 中存放着一条出错标志 则调用出错诊查程序Error 例子 文法G E E TE E TE T FT T FT F E i 例子 预测分析表的生成 从前面的论述我们看到 预测分析法的总控程序是固定的 对于某个文法 分析表是分析过程的核心 表中M U a U X1X2 Xn 表示对应于X1X2 Xn字的首符号可以是a 就是说X1X2 Xn a 我们可以通过这个方式来确定分析表中的值 预测分析表的生成 一般来讲 对于一个符号串X1X2 Xn的字的第一个终结符号就是X1对应的字的第一个终结符号 但是空产生式的存在使情况有一点复杂 对于U1U2 Un 如果U1 那么符号串对应的字的首符号也可以是U2对应的字的首符号 计算一个符号串对应的字的首符号的算法也需要考虑到这些 预测分析表的构造 基本思想 当我们需要将U选择某个产生式展开时 如果当前的输入为a 表示我们要将U展开为以a为首符号的字 如果有产生式U u 且a FIRST u 那么表示这个产生式是个好的选择 分析表构造算法 对于每个产生式U 执行一下步骤对于每个终结符号a FIRST M U a U 如果 FIRST 对于每个终结符号b FOLLOW U M U b U 将其它未定义的分析表元素置为ERROR 分析表的例子 文法G E E TE E TE T FT T FT F E i 分析表的冲突 文法G S S iCtSS aS eS C bFIRST iCtSS i FIRST eS e FIRST S i a FIRST C b FIRST S e FOLLOW S FOLLOW S e LL 1 文法 LL 1 文法 其预测分析表中没有多重定义的元素 则该文法被称为LL 1 文法 LL 1 文法是无二义性的