LL分析方法自顶向下分析.ppt

LL分析方法 自顶向下分析 LL 1 是LL k 的特例 其中的k则表示向前看k个符号 LL 1 方法和递归下降法属于同一级别的自顶向下分析法 但有一些区别 递归下降法对每个非终极符产生子程序 而LL 1 方法则产生LL分析表 递归下降法能判断每个产生式的结束 而LL 1 方法则不能 递归下降法分析法不用符号栈 而LL 1 方法则用符号栈 LL 1 分析方法的条件 对于任一非终极符A 其任意两个产生式A 和A 都要满足下面条件 Predict A Predict A 满足这一条件的文法称为LL 1 文法 LL 1 分析例 文法G A A aBc 1 B d 2 bB 3 输入串 abbdc分析过程 A abbdc 1 cBa abbdc cB bbdc 3 cBb bbdc cB bdc 3 cBb bdc cB dc 2 cd dc c c LL 1 分析的动作 替换 当X1 VN时选相应候选式 去替换X1 匹配 当X1 VT时它与Y1进行匹配 其结果可能成功 也可能失败 如果成功则去掉X1和Y1 否则报错 接受 当格局为 空 空 时报分析成功 报错 出错后 停止分析 LL 1 分析表 T VN VT P Error T A t A 若t Predict A T A t Error否则其中P表示所有产生式的集合 LL 1 分析的驱动器 LL Driver 1 初始化 Stack empty Push S 2 读下一个输入符 Read a 3 若当前格局是 empty 则成功结束 否则转下 4 设当前格局为 X a 则 若X VT X a则 Pop 1 Read a goto 3 若X VT X a则Error 若X VN 则 ifT X a X Y1Y2Ynthen Pop 1 Push Yn Y1 goto 3 elseError LL分析实例 文法G E TE 1 E TE 2 3 T FT 4 T FT 5 6 F id 7 E 8 符号串i i i 的LL 1 分析过程 Predict 1 first TE id Predict 2 first TE Predict 3 follow E Predict 4 first FT id Predict 5 first FT Predict 6 follow T Predict 7 first id id Predict 8 first E 分析栈S输入流T矩阵元素 Ei i i LL E i 1 E Ti i i LL T i 4 E T Fi i i LL F i 7 E T ii i i Match E T i i LL T 6 E i i LL E 2 E T i i Match E Ti i LL T i 4 E T Fi i LL F i 7 E T ii i Match E T i LL T 5 E T F i Match E T Fi LL F i 7 E T ii Match E T LL T 6 E LL E