编译原理-陈火旺版-第四章.ppt

1 编译方法 中国人民大学信息学院陈文萍 2 第四章语法分析 自上而下分析 4 1语法分析器的功能4 2自上而下分析面临的问题4 3LL 1 分析法4 4递归下降分析程序构造4 5预测分析程序4 6LL 1 分析中的错误处理 3 4 1语法分析器的功能 语法分析器的地位分类自上而下分析自下而上分析 词法分析器 语法分析器 编译程序后续部分 符号表 源程序 单词符号 取下一个单词符号 语法分析树 4 4 2自上而下分析 定义 也称面向目标的分析方法 从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子 主旨 对任何输入串 试图用一切可能的办法 从文法开始符号着手 自上而下地为输入串构造一棵语法树 本质上是一个试探过程 反复使用不同的产生式谋求匹配输入串的过程 5 自上而下分析的问题 1 左递归例 例文法G0 S 1 S Sa 2 S b分析baa是不是文法的句子按照自上而下的分析思想 选用产生式 1 来推导S Sa 语法树末端结点最左符号为非终结符 所以选用 1 继续推导S Sa Saa此时语法树末端结点最左符号为非终结符 选用 1 继续推导S Sa Saa Saaa试图用S匹配输入串时 出现 在没有识别任何输入符号的情况下 又得重新要求S去进行新的匹配 分析过程陷入无限循环 6 自上而下分析的问题 2 回溯例 G S S xAy A ab a若当前输入串为xay 首先构造的推导S xAy 匹配 进一步推导对A可选择A ab替换 得S xAy xabyxayxaby 匹配 xa都已匹配 当前面临输入符为y与b不能匹配 所以将输入串指针退回到a 对A的替换重新选用下一个产生式A a进行试探 S xAy xay输入串中当前符a得到匹配 指针向前移动到y 与语法树中y匹配 匹配成功 由于相同左部的产生式的右部开始符号相同而引起回溯 7 自上而下分析的问题 3 分析过程中 匹配成功可能是暂时的 最终分析不成功 很难知道输入串中出错的确切位置 带回溯 效率低 代价高 8 4 3LL 1 分析法 左递归的消除消除回溯LL 1 分析条件 9 直接左递归的消除 左递归 一个文法是含有左递归的 如果存在非终结符P P P 形如 P P 其中 不为 不以P打头消除直接左递归改写为 P P P P 一般来说 若P P 1 P 2 P m 1 2 n i不为 i不以P打头 消除直接左递归就把规则改写为 P 1P 2P nP P 1P 2P mP 例 E E T T T T F F F E i消除直接左递归后变为 E TE E TE T FT T FT F E i 10 文法左递归的消除 消除一个文法左递归 对文法的要求无回路 不含以 为右部的产生式消除左递归算法 1 以某种顺序将文法非终结符排列P1 P2 Pn 2 fori 1tondobeginforj 1toi 1do用Pi 1r 2r kr替代形如Pi Pjr的规则其中Pj 1 2 k是关于Pj的全部产生式 消除Pi规则的直接左递归 end 3 化简由2得到的文法 11 左递归的消除 例 文法S Qc c Q Rb b R Sa a1 非终结符排序为 S Q R2 替换规则对于S 无需替换 S Qc c对于Q 无需替换 Q Rb b关于R 替换为 R Rbca bca ca a 消除直接左递归为R bcaR caR aR R bcaR 非终结符的顺序不同 文法的形式可能不同 但都是等价的 12 消除回溯 不回溯 对文法的要求设G是一个不含左递归的文法 对G的所有非终结符的每个候选 它的终结首符集FIRST 为FIRST a a a VT 若 则规定 FIRST 若非终结符A的所有候选首符集两两不相交 即A的任何两个不同候选 和 FIRST FIRST 则可消除回溯改造文法的方法 提左公因子将产生式 1 n 1 m变换为 B 1 mB 1 n 13 LL 1 分析条件 例如 文法 E TE E TE T FT T FT F E i输入串i i 语法分析树FIRST TE i FIRST TE FIRST FT i FIRST FT FIRST E FIRST i i E T E i T E T F F T i 14 LL 1 分析条件 S是文法G的开始符号 对G的任何非终结 定义FOLLOW A a S Aa 且a VT 若S A 则 FOLLOW A 一个文法G是LL 1 的 当且仅当对于G的每一个非终结符 的任何两个不同产生式 下面的条件成立 1 文法不含左递归 2 FIRST FIRST 也就是 和 推导不出以同一个终结符a为首的符号串 它们不应该都能推出空字 3 假若 那么 FIRST FOLLOW A 也就是 若 则 所能推出的串的首符号不应在FOLLOW A 中 15 LL 1 分析条件 文法是LL 1 的第一个L从左到右扫描输入串第二个L生成的是最左推导1向前看一个输入符号 16 4 4递归下降分析程序构造 递归分析器 不带回溯的自上而下的分析程序例 文法 E TE E TE T FT T FT F E i递归子程序为 PROCEDUREE BEGINT E END PROCEDUREE IFSYM THENBEGINADVANCE T E END 17 4 4递归下降分析程序构造 PROCEDURET BEGINF T END PROCEDURET IFSYM THENBEGINADVANCE F T END PROCEDUREF IFSYM i THENADVANCEELSEIFSYM THENBEGINADVANCE E IFSYM THENADVANCEELSEERRORENDELSEERROR 18 4 4递归下降分析程序构造 扩充的巴科斯范式用 a 表示闭包运算a 用表示a可任意重复0次到n次 用 a 表示 即a的出现可有可无例如 文法E T E T T F T F F E I可以表示成E T T T F F F E IPROCEDUREE BEGINT WHILESYM DOBEGINADVANCE TENDEND 19 4 4递归下降分析程序构造 PROCEDUREF IFSYM THENADVANCEELSEIFSYM THENBEGINADVANCE E IFSYM THENADVANCEELSEERRORENDELSEERROR PROCEDURET BEGINF WHILESYM DOBEGINADVANCE F ENDEND 20 4 4LL 1 分析器 LL 1 分析器的模型 a b XYZ LL 1 分析算法 LL 1 分析表M 输入缓冲区 分析栈 输出 21 LL 1 分析器 分析要件输入缓冲区 存放要分析的符号串 在串的末尾加符号 表示输入结束 预测分析表 看作矩阵 存放文法中非终结符A和终结符a的关系 矩阵元素M A a 表示A对于输入符号a所采用的候选 结束标记符 作为一个终结符号 栈 分析过程中 存放当前句型中尚待分析的文法符号 包括终结符号和非终结符号 栈底用 标记结束 初始化时 把 和文法的开始符号放在栈顶 22 LL 1 预测分析表 例 G E 1 E TE 2 E TE 3 E T FT 5 T FT 6 T 7 F E 8 F i 23 预测分析表的构造 计算FIRST集合的方法1 若X V 则FIRST X X 2 若X VN 且有产生式X a 则把a加入到FIRST X 中 若X 也是一条产生式 则把 也加到FIRST X 中 3 若X Y 是一个产生式且Y VN 则把FIRST Y 中的所有非 元素都加到FIRST X 中 若X Y1Y2 YK是一个产生式 Y1 Y2 Y i 1 都是非终结符 而且 对于任何j 1 j i 1 FIRST Yj 都含有 即Y1 Y i 1 则把FIRST Yj 中的所有非 元素都加到FIRST X 中 特别是 若所有的FIRST Yj j 1 2 K 均含有 则把 加到FRIST X 中 24 预测分析表的构造 计算FOLLOW集1 对于文法的开始符号S 置 于FOLLOW S 中 2 若 B 是一个产生式 则把FIRST 加至FOLLOW B 中 3 若 B是一个产生式 或 B 是一个产生式而 即 FIRST 则把FOLLOW A 加至FOLLOW B 中 25 预测分析表的构造 例 文法G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 非终结符的FIRST集合 FIRST E a FIRST E FIRST T a FIRST T FIRST F a 非终结符的FOLLOW集合 FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F 26 预测分析表构造算法 1 对文法G的每个产生式 执行第二步和第三步 2 对每个终结符a FIRST 把 加至 A a 中 3 若 FIRST 则对任何b FOLLOW A 把 加至 A b 中 4 把所有无定义的 A a 标上 出错标志 可以证明 一个文法G的预测分析表不含多重入口 当且仅当该文法是LL 1 的 27 预测分析程序 预测分析程序算法 首先把 然后把文法开始符号推入栈 把第一个输入符号读进a FLAG TRUE WHILEFLAGDOBEGIN把栈顶符号上托出去并放在 中 IFX VtTHENIFX aTHEN把下一个输入符号读进aELSEERRORELSEIFX THENIFX aTHENFLAG FALSEELSEERRORELSEIF X a X X1X2 XK THEN把XK XK 1 X1一一推进栈ELSEERRORENDOFWHILE STOP 分析成功 过程完毕 28 预测分析程序 分析步骤栈内容栈顶符号当前输入余留串M X a 1 EEi i E TE 2 E TTi i T FT 3 E T FFi i F i4 E T iii i 5 E T T i T 6 E E i E TE 7 E T i 8 E TTi T FT 9 E T FFi F i10 E T iii 11 E T T T 12 E E E 13 29 4 6LL 1 分析中的错误处理 发现错误栈顶的终结符与当前输入符不匹配非终结符A于栈顶 面临的输入符为a 但分析表M的M A a 为空应急恢复策略跳过输入串中的一些符号直至遇到 同步符号 为止 30 4 6LL 1 分析中的错误处理 同步符号集的选择把FOLLOW A 中的所有符号作为A的同步符号 跳过输入串中的一些符号直至遇到这些 同步符号 把A从栈中弹出 可使分析继续错误处理若M A a 为空 跳过输入符号a