LL(1)分析法
- 构造不带回溯的自上而下分析算法
- 消除文法的左递归性
- 克服回溯
-
编译原理重点 LL(1)
- L:表示从左向右扫描输入串
- L:最左推导
- 1:向前看1步
左递归的消除
- 直接消除在产生式中的左递归:
- 如非终结符P的规则为:
- 其中
不以 为开头
- 其中
-
编译原理重点 我们可以把
的规则等价的改写为如下的非直接左递归形式:将左递归变为了右递归
- 如非终结符P的规则为:
-
编译原理重点 一般而言,假定
关于的全部产生式是:\( \)- 消除
的直接左递归性即将规则改写为:\( \)
- 消除
- 有的文法可能没有直接左递归,但也可能是左递归的:
- 一个文法消除左递归的条件:
- 不含以
为右部的产生式 - 不含回路:
- 不含以
- 消除左递归的算法:
- 将文法
的所有非终结符按照某一种顺序排列,并逐个执行: - 化简所得到的文法,去除从开始符号出发永远无法到达的非终结符的产生规则
- 将文法
- 算法的注意事项:
- 适用于:消除了
产生式和不以 为右部的产生式文法 - 第二步中所作的工作:
- 若为直接左递归,则消除直接左递归
- 若右部的最左符号是非终结符且序号大于左部的非终结符,则不进行替换
- 若序号小于左部的非终结符,则将序号小的非终结符用其右部的串进行替换,然后消除新的直接左递归
- 这样,每次替换的非终结符均为前面已经处理过的非终结符
- 适用于:消除了
消除回溯,提取左公因子
- 产生回溯的原因:推导时,若产生式存在多个候选式,选择哪个进行推导存在不确定性
-
编译原理重点 提取左公因子:
LL(1)分析条件
-
编译原理重点 如果一个文法是LL(1)文法,则满足:
- 文法不含左递归
- 对于文法中每个非终结符A的各个产生是的候选首符集两两不相交
- 若
- 则
- 若
- 对于文法中的每个非终结符A,存在某个候选首符集包含
,则
#编译原理重点 FIRST
:可以从 推导得到的串的首符号的集合\( \)- 算法:
- 如果
是一个终结符号,那么 - 如果
是一个非终结符号,且- 如果对于某个
, 在 中,且 在所有的 、 、 、 中,则将a添加到 中
- 如果对于某个
- 如果
是一个产生式,则将 添加到 中
- 如果
- 主要看产生式左边
- 自下而上求
#编译原理重点 FOLLOW
:可能在某些句型中紧跟在A右边的终结符号集合\( \)- 算法:
- 将
添加到 中,其中 是开始符号, 是右端的结束标记 - 如果存在产生式
,则 中除了 之外的所有符号都在 中 - 如果存在
或存在产生式 且 中包含了 (可以理解为同一种情况 ),则将 中的所有符号都放在 中
- 将
- 只看产生式右边
- 自上而下求