编译原理第五章——语法分析（中）LL(1)分析

编译原理第五章——语法分析（中）

5.4 LL(1)分析法基本思想

5.4.1 什么是LL(1)分析法

LL(1)分析法是指从左到右扫描(第一个L)、 最左推导(第二个L) 和 只查看一个当前符号(括号中的1) 之意;
LL(1)分析法又称预测分析法，属于确定的自顶向下语法分析方法。

即每次推导使用的产生式是确定的

5.4.2 LL(1)分析算法概要

说明：
①读到的单词是非终结符，将产生式右部的字符串替换
②读到的是终结符，直接弹出，再读下一个单词
③结束时，栈里只剩下一个#，当前读的单词也是#，此时语法分析结束，语法结构是合法的

注意：
①步压栈时是逆序压栈
NEXT(w)是读下一个单词

示例：

问题：
1.选择推导产生式后，为什么要逆序压栈
解：栈后进先出，为了让产生式最左侧的b与当前符号匹配，逆序压栈才可以
2.当栈顶为A，当前单词为c时，为什么选择A->ε进行推导
解：因为c出现在A的FOLLOW集中，这样对下一步的推导有好处

5.5 LL(1)分析器的设计

5.5.1 LL(1)分析表

表项：表示当前这一行的非终结符遇到当前这一列的终结符用哪个产生式进行推导

select集求法：

LL(1)文法是指文法中，具有相同左部的各产生式，其选择符集合不相交

示例：

①与②不想交，③与④不想交，所以是一个LL(1)文法

因为select不相交，所以栈顶遇到的终结符不论是哪个，都可以确定的使用一个产生式

5.5.2 LL(1)分析法控制程序

示例：
1.判断是否是LL(1)文法

结论：三对选择集不相交，所以G`(E)是LL(1)文法
2.构造LL(1)分析表

蓝色的{}是构造的选择集合
每一行填的产生式序号都只能是它的候选符号集
分析表中填的是产生select集需要哪个产生式

3.分析过程（创建分析栈

ω1指的是加号or减号

结论：推导结束，a+b#是一个正确的表达式