编译原理_第4章_第2节_LL(1)分析法.ppt

如果非终结符A的任何两个候选式 i和 j 不考虑 的情况 有FIRST i FIRST j 那么要求A匹配输入串时 A就能根据它所面临的第一个输入符号a 准确的指派某个候选去执行匹配任务 4 2 1LL 1 文法 FIRST集合 4 2 1LL 1 文法 文法G S A x y z S xAy z A S xy S 当前输入符号为a A 1 2 n a FIRST i FIRST j 是否可以用 匹配A 只有a是跟在A后面的终结符时 才能运行A自动匹配 否则 a在这里的出现就是一种语法错误 4 2 1LL 1 文法 当前输入符号为a A 1 2 n a FIRST i FIRST j 是否可以用 匹配A 1 若a FOLLOW A 则可以用 匹配A 2 若a FOLLOW A 则不可以用 匹配A FOLLOW集合 4 2 1消除回溯 提左因子 为了消除回溯就必须保证 对文法的任何非终结符 当要它去匹配输入串时 能够根据它所面临的输入符号准确地指派它的一个候选去执行任务 并且此候选的工作结果应是确信无疑的 A 1 2 n 4 2 1消除回溯 提左因子 P A1 A2 An 1 2 mP A 1 2 mA A1 A2 An 例 S ifBthenS1elseS2 ifBthenS1 S ifBthenS1S3S3 elseS2 例 S ifBthenS1elseS2 ifBthenS1 S ifBthenS1S3S3 elseS2 经过反复提取左因子 就能够把每个非终结符 包括新引进者 的所有候选首符集变成为两两不相交 1 文法不含左递归 2 对每个非终结符A 若A 1 2 n 有FIRST i FIRST j i j 3 对每个非终结符A 若A 1 2 n FIRST i 有FIRST i FOLLOW A 如果文法G满足以上条件 则该文法称为LL 1 文法 第一个L表示从左到右扫描输入串 第二个L表示最左推导 1表示分析时每步只需向右查看一个符号 构造不带回溯的自上而下分析的文法条件 4 2 1LL 1 文法 构造无回溯文法算法的问题 如何构造FIRST 如何构造FOLLOW A 如何根据当前输入符号a决定A的匹配式 文法G S 中的产生式S xAyS zA A x y S y a 若x VT 则FIRST x x b 若x VN 且有产生式x a a VT 则a FIRST x 当产生式为x 时 FIRST x 4 2 2求FIRST x 4 2 2求FIRST x 1 若x VN VT a 若x VT 则FIRST x x b 若x VN 且有产生式x a a VT 则a FIRST x 当产生式为x 时 FIRST x 4 2 2求FIRST x 2 若x VN VT 不妨设x x1x2x3 xn a FIRST x1 FIRST x b 对任何1 j i 1 若 FIRST xj 则FIRST xi FIRST x c 对任何1 i n 若 FIRST xi 则 FIRST x X Y1Y2Y3Y4Y5 Y1 a Y2 b Y3 c Y4 d Y5 e FIRST Y1 a FIRST Y2 b FIRST Y3 c FIRST Y4 d FIRST Y5 e FIRST X a b c d e 例 求FIRST X 4 2 2求FIRST x 文法G S 中的产生式S xAyS zA A xy S y 4 2 3求FOLLOW A 4 2 3求FOLLOW A 1 置初值 对任一A VN 令FOLLOW A 若A是开始符号 FOLLOW A 2 若有A B B VN 置FOLLOW B 3 若有A B 置FOLLOW B 5 重复 3 4 直到每个FOLLOW A 都不再增大为止 FOLLOW B FIRST FOLLOW B FOLLOW A FOLLOW B FOLLOW A FIRST E FIRST E FIRST T FIRST T FIRST F FIRST E FIRST T FIRST F i FIRST T i FIRST E i E TE E TE T FT T FT F E i 例 求FOLLOW A 4 2 3求FOLLOW A 4 2 4确定匹配产生式 A可以用候选式 匹配的条件 1 a FIRST 2 FIRST a FOLLOW A G VN VT P S 构造分析表 列为a VT 行为A VN A与a对应的元素记为M A a 对所有的产生式A 1 若a FIRST 则置M A a A 2 若 FIRST 且b FOLLOW A 则置M A b A 3 若M A a 为空 则表示出错 用上述方法构造的分析表称为LL 1 分析表 4 2 4确定匹配产生式 E TE E TE T FT T FT F E i FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F FIRST TE i FIRST TE FIRST FIRST FT i FIRST FT FIRST E FIRST i i E TE E TE E TE E TE E TE E TE E E E E T FT T FT T FT T FT T FT T FT T T T T T T F E F E F i F i 例 构造LL 1 分析表 4 2 4确定匹配产生式 4 2 5LL 1 分析法 设文法符号栈为STACK 初始值存放句子左界符 和开始符号 总控程序根据STACK栈顶符号X和当前输入符号a查LL 1 分析表 1 若X a 分析成功 退出 2 若X a POP X 并从输入串中读入下一个符号存入a 3 若X VT 且X a ERROR 退出 4 若X VN 若M X a 为一产生式 则POP X 并将X右部反序进栈 若候选式为 则 不进栈 若M X a 为空白 ERROR 退出 5 转 1 例 LL 1 分析法 i i i LL 1 分析法的分析过程 对每个A的每个候选式 构造FIRST 对每个A 构造FOLLOW A 根据FIRST 和FOLLOW A 构造LL 1 分析表 根据分析表 使用主控程序进行分析 4 2 6if then else文法 stmt ifexprthenstmtelsestmt ifexprthenstmt other 文法含有左公因子 因此必存在冲突 当已推导或归约出ifexprthenstmt 遇到else时会出现冲突 规定else与最接近的if配对 因此ifexprthenstmtelsestmt优先 推广 当一个候选式是另外一个候选式的前缀时 规定较长的候选式优先 4 2 7非LL 1 文法的LL 1 分析 S iCtSS aS eS C b 对任意产生式A 1 若a First 则M A a A 2 若 First 对任何b Follow A 置M A b A First S i a First S e First C b Follow S Follow S e Follow C t a b e i t S S C S iCtSS S a S eS S S eS C b 4 2 8如何判定是否为LL 1 文法 根