编译原理4.3.4-LL文法的判别.ppt

第四章 4 1语法分析器的功能4 2自上而下分析面临的问题4 3LL 1 分析法4 4递归下降分析程序构造4 5预测分析程序4 6LL 1 分析中的错误处理 4 3LL 1 分析法 4 3 1左递归的消除4 3 2消除回溯 提左因子4 3 3LL 1 分析条件4 3 4LL 1 文法的判别 4 5 2 4 3 4LL 1 文法的判别 4 5 2 文法中不得含有有害规则和多余规则消除左递归和提左公因子求出能 的非终结符 补充 计算FIRST集计算FOLLOW集计算SELECT集 补充 例4 7文法4 2P79G E E T TT T F FF E i 消除左递归 G E TE E TE T FT T FT F E i 1 求出能推出 的非终结符 建立一个一维数组X 用以记录非终结符能否推出 将数组X 中对应每一非终结符的标记置初值为 未定 算法描述 补充 扫描文法中的产生式 a 若某一非终结符的某一产生式右部为 则将数组中对应该非终结符的标志置为 是 并从文法中删除该非终结符的所有产生式 b 若某一产生式右部含有终结符 则删除该产生式 右部含有终结符 一定无法推出 若这使得以某一非终结符为左部的所有产生式都被删除 则将数组中对应该非终结符的标记值改为 否 扫描产生式右部的每一符号 此时产生式右部全部为非终结符 a 若所扫描到的非终结符号在数组中对应的标志是 是 则删去该非终结符 若这使产生式右部为空 则对产生式左部的非终结符在数组中对应的标志改 是 并删除该非终结符为左部的所有产生式 b 若所扫描到的非终结符号在数组中对应的标志是 否 则删去该产生式 若这使产生式左部非终结符的有关产生式都被删去 则把在数组中该非终结符对应的标志改成 否 重复 直到扫描完一遍文法的产生式 数组中非终结符对应的特征再没有改变为止 2 计算FIRST集 对每一文法符号X V 计算FIRST X a 若X VT 则FIRST X X b 若X VN 且有产生式X a a VT 则a FIRST X 即把a加入到FIRSR X 中 c 若X VN 且有产生式X 则 FIRST X P78 d 若X VN 且有产生式X Y1Y2 Yi 1Yi Yn 当Y1Y2 Yi 1都能推出 时 则FIRST Y1 FIRST Y2 FIRST Yi 1 FIRST Yi 都包含在FIRST X 中 e 当 d 中X Y1Y2 Yn所有Yj都可以推出 j 1 2 n 则FIRST Y1 FIRST Y2 FIRST Yn 都包含在FIRST X 中反复使用上述 b e 步直到每个符号的FIRST集合不再增大为止 求一个符号串 的FIRST集合 若符号串 V X1X2 Xi 1Xi Xn 若X1不能推导出 则FIRST FIRST X1 若对任何j 1 j i 1 2 i n FIRST Xj 若对任何j 1 j n FIRST Xj 例4 7文法4 2求FIRST集P79 G E TE E TE T FT T FT F E i 解题过程见黑板 3 计算FOLLOW集 a 设S为文法中开始符号 把 加入FOLLOW S 中 b 若A B 是一个产生式 则把FIRST 加入FOLLOW B 中 c 若A B是一个产生式 或A B 是一个产生式 且 可推出 即 FIRST 则把FOLLOW A 也加入FOLLOW B 中 d 反复使用 b 直到每个非终结符的FOLLOW集不再增大为止 例4 7文法4 2求FOLLOW集P79 G E TE E TE T FT T FT F E i 解题过程见黑板 例4 7文法4 2LL 1 文法判别P79 G E TE E TE T FT T FT F E i FIRST TE FIRST FIRST E FOLLOW E FIRST FT FIRST FIRST T FOLLOW T FIRST E FIRST i 该文法是LL 1 文法 4 计算SELECT集 给定上下文无关文法的产生式A A VN V 若 SELECT A FIRST 若 SELECT A FIRST FOLLOW A 补充例 判断文法是否是LL1文法 文法中不得含有有害规则和多余规则消除左递归和提左公因子求出能推出 的非终结符计算FIRST集计算FOLLOW集计算SELECT集 G S ABS bCA bA B B aDC bC ADD aSD c 3 求出能推出 的非终结符 G S ABS bCA bA B B aDC bC ADD aSD c 4 求FIRST集 1 求每个非终结符的FIRST集 G S ABS bCA bA B B aDC bC ADD aSD c 2 求每个产生式右部的FIRST集 FIRST AB a b FIRST bC b FIRST AB FIRST bC b 所以 该文法不是LL 1 文法 5 求F