编译原理第四章语法分析-自上而下分析.ppt

第四章语法分析 自上而下分析 4 1语法分析器的功能4 2自上而下分析面临的问题4 3LL 1 分析法4 4递归下降分析程序构造4 5预测分析程序4 6LL 1 分析中的错误处理 4 1语法分析器的功能 功能定义 按照文法产生式 识别输入符号串是否为一个句子 技术路线 是否能从文法的开始符号出发推导出这个输入串 或者 建立一颗与输入串相匹配的语法分析树 策略 自上而下分析法 自下而上分析法 图4 1语法分析器在编译程序中的地位 接收词法分析器输出的记号串 检查是否合乎语法 报告语法错误 并恢复语法错误 从而可以继续分析 输出是分析树的某种形式 分析时其它任务 将各种记号的信息收入符号表 类型检查和其它语义检查 中间代码的生成 这些放在 前端的其它部分 完成 4 2自上而下分析面临的问题 例4 1假定有文法 1 S xAy 2 A 对输入串x y 构造语法树 构造过程 1 把S作为根 2 用S的产生式构造子树 3 让输入串指示器IP指向输入串的第一个符号 4 调整输入串指示器IP与叶结点进行匹配 5 如果为非终结符 用A的下一个产生式构建子树 6 如果匹配成功则结束 否则 回溯到步骤 4 自上而下分析法的缺点 是文法的左递归性问题 一个文法是含有左递归的自上而下的分析过程陷入无限循环 如P P 由于有回溯 就会产生一大堆麻烦事情 在上述的自上而下分析过程中 当一个非终结符用某一候选匹配成功时 这种成功可能仅是暂时的 这种虚假现象 我们需要更复杂的回溯技术 一般说 要消除虚假匹配是很困难的 当最终报告分析不成功时 我们不知道输入串中出错的确切位置 4 3LL 1 分析法 4 3 1左递归的消除4 3 2消除回溯 提左因子4 3 3LL 1 分析条件 4 3 1左递归的消除 一个简单例子 已知文法 P P 是一个左递归文法 它的等价的非左递归文法为 P P P P 例2 2一般转换规则有 P P 1 P 2 P m 1 2 n改写成P 1P 2P nP P 1P 2P mP 其中 i都不以P开头 I不等于 一个反例 文法 S Qc c Q Rb b R Sa a虽然不是直接左递归 但S Q R都是左递归 消除左递归算法 算法的思想是 首先构造直接左递归 再利用一般转换规则 消除直接左递归化简文法 下面算法在不含P P 也不含 在右部产生式时可以消除左递归 消除一个文法的左递归算法 1 把文法G的所有非终结符按任一种顺利排列成P1 Pn 按此顺序执行 2 FORi 1TOnDOBEGINFORj 1TOi 1DO把形如Pj 1 Pj 的规则改写成Pj 1 1 1 k 其中Pj 1 1 k是关于Pj的所有规则 消除关于Pi规则的直接左递归性 END化简由 所得的文法 即去除那些从开始符号出发永远无法到达的非终结符的产生规则 例子4 3 对4 3文法 它的非终结符排序为R Q S 把R代入Q Q代入S得到 S Sabc abc bc c消除左递归后得到 S abcS bcS cS S abcS Q Sab ab b 化简消去 R Sa a 化简后消去 对不同的排列 会有不同形式的无左递归文法 但它们等价 4 3 2消除回溯 提左因子 消除回溯的思路 对输入符号a 指派一个A的候选式 1与a匹配 而再没有其他候选式 i的字符与a匹配 通过提取公共左因子 判断首字符集的差异 首字符集定义 对G的所有非终结符的每个候选 它的首字符集为FIRST a a a VT 若 则规定 FIRST 提取公共左因子算法 A 1 2 n 1 2 m 其中每个 不以 开头 那么可以把这些规则改写成 A A 1 2 mA 1 2 n例4 4上述算法的不足 当非终结符A面临输入符号a 且a不属于A的任意候选首符集 但A的某个候选首符集包 含时 就一定可以使A自动匹配 这是一种错误 4 3 3LL 1 分析条件 定义FOLLOW A 集合 假定S是文法G的开始符号 对于G的任何非终结符A 我们定义FOLLOW A a S Aa a VT 若S A 则规定 FOLLOW A LL 1 文法的充分必要条件 文法不含左递归 若 1 2 n 则FIRST i FIRST j i j 对文法中的每个非终结符A 若它存在某个候选首符集包含 则FIRST A FOLLOW A LL 1 匹配算法 对输入符号a A的所有产生式为 1 2 n 1 若a FIRST i 则指派 I去执行匹配任务 2 若a不属于任何一个候选首符集 则 FIRST i 且a FOLLOW A 则让A i 与 a 自动匹配 否则 a的出现是一种语法错误 例4 4 4 4递归下降分析程序构造 递归下降分析器 这个分析程序由一组递归过程组成的 每个过程对应文法的一个非终结符 E TE E TE T FT T FT F E i PROCEDUREEPROCEDURETBEGINBEGINT E F T ENDENDPROCEDUREE PROCEDURET IFSYM THENIFSYM THENBEGINBEGINADVANCE ADVANCE T E F T ENDEND PROCEDUREFIFSYM i THENADVANCEELSEIFSYM THENBEGINADVANCE E IFSYM THENADVANCEELSEERRORENDELSEERROR 扩展巴科斯范式 BackusNaurForm 用花括号 表示闭包运算 用 n0表示 可任意重复 次至n次 00 0 用方括号 表示 0 即表示 的出现可有可无 等价于 例4 5 文法E T E TT F T FF i E 可表示成E T T F F F F E I 4 5预测分析程序 4 5 1预测分析程序工作过程4 5 2预测分析表的构造 预测分析器思想 栈 表4 1文法4 2的LL 1 分析表 预测分析程序的总控程序 其具体工作过程是首先把文法开始符号和 压入栈 然后总控程序在任何时候都是按STACK栈顶符号X和当前输入符号a行事的 如图所示 对于任何 X a 总控程序每次都执行下述三种可能的动作之一 若X a 则宣布分析成功 停止分析过程 若X a 则把X从STACK栈顶逐出 让a 指示器 指向下一个输入符号 若X是一个非终结符 则查看分析表M 若M A a 中存放着关于X的一个产生式 则X出栈 把X产生式右部符号串按反序压栈 如果M A a 中存放出错标志 则调用诊断程序 预测分析程序的总控程序描述是 BEGIN首先把 然后把文法开始符号推进STACK栈 把第一个输入符号读进a FLAG TRUE WHILEFLAGDOBEGIN把STACK栈顶符号上托出并放在X中 IFX VTTHENIFX aTHEN把下一输入符号读进aELSEERRORELSEIFX THENIFX aTHENFLAG FALSEELSEERROR ELSEIFM A a X X1X2 Xk THEN把Xk Xk 1 X1一一推进STACK栈 若X1X2 Xk 不推任何字进栈 ELSEERRORENDOFWHILE STOP 分析成功 过程完毕 END 例4 6 输入串为i1 i2 i3 利用分析表进行预测分析的步骤步骤符号栈输入串所用产生式0 Ei1 i2 i3 1 E Ti1 i2 i3 E TE 2 E T Fi1 i2 i3 T FT 3 E T ii1 i2 i3 F i4 E T i2 i3 5 E T F i2 i3 T FT 15 E T 16 E 4 5 2预测分析表的构造 FIRST X 集的构造算法 若X VT 则FIRST X X 若X Vn 且有产生式X a 则把a加入到FIRST X 中 若X 也是一条产生式 则把 也加到FIRST X 中 若X Y 是一个产生式 且Y Vn 则把FIRST Y 中所有非 元素都加到FIRST X 中 若X Y1 Yi 1是一个产生式且Y Vn 且对任何的j 1 j i 1 FIRST Yj 都含有 即Y1 Yi 1 则把FIRST Yj 中的所有非 元素都加到FIRST X 中 特别地 若FIRST Yj 都含有 把 加入FIRST X 中 重复以上操作 直到FIRST X 不再增大为止 上述算法可以推广到FIRST X1 Xk 非终结符B的FOLLOW B 构造算法 对于文法的开始符号S 置 于FOLLOW B 中 若A B 是一个产生式 则把FIRST 加至FOLLOW B 中 若A B是一个产生式 或A B 是一个产生式而 即 FIRST 则把FOLLOW A 加至FOLLOW B 中 构造分析表M的算法 1 对文法G的每个产生式A 执行第 步和第 步 2 对每个终结符a FIRST 把A 加至M A a 中 3 若 FIRST 则对任何b follow A 把 加至M A b 中 4 把所有无定义的M A a 标上 出错标志 例4 7 4 8 4 6LL 1 分析中的错误处理 错误类型 栈顶的终结符与当前的输入符号不匹配 非终结符A处于栈顶 面临的输入符号为a 但分析表M中的M A a 为空 错误处理方法 跳过输入串中的一些符号直至遇到 同步符号 为止 同步符号集合的选择方法 把FLLOWO A 加入A的同步活动集 把FIRST A 加入到A的同步活动集 直接弹出站顶元素 并发送信息告知插入下一个终结符后 继续分析 例4 9 表4 2加入同步符号的LL 1 分析表 表4 3对 id i的语法分析与错误处理