LL(1)文法
# LL(1) 文法
# 产生式的可选集 -- SELECT 集
预测分析法的工作过程
- 从文法开始符号出发,在每一步推导过程中根据当前句型的最左非终结符
和当前输入符号 ,选择正确的 产生式 - 为保证分析的确定性,选出的候选式必须是唯一的
产生式的可选集的定义
- 产生式
的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为 - 由定义可得:
- 由定义可得:
由可选集的定义可知,为了确保预测分析的正确性,需要确保具有相同左部的产生式有不相交的可选集
# S_ 文法
S_文法(简单的确定性文法,Korenjak & Hopcroft,1966) 的定义
- 每个产生式的右部都以终结符开始
- 同一非终结符的各个候选式的首终结符都不同
- 不含
产生式
含有 ε 产生式的示例
- 推导
的过程中,在使用 4 号 产生式,就可判断出这个输入是错误的,因为紧跟着 的终结符只能是 , 不可能出现在 的后面 - 也就是说应该定义
- 也就是说应该定义
S_ 方法的局限性是不含 ε 产生式
- 如果要在文法中引入 ε 产生式,为了使用预测分析法,就要确保 ε 产生式的可选集,与其它具有相同左部的产生式的候选集不相同
- 由此引入非终结符的后继符号集和
文法
- 由此引入非终结符的后继符号集和
# 非终结符的后继符号集 -- FOLLOW 集
定义
- 为了更准确的定义
- 产生式的候选集,引入非终结符后继符号集的概念 - 非终结符
的后继符号集定义为: - 可能在某个句型中紧跟在
后边的终结符 的集合,记为 - 如果
是某个句型的最右符号,则将结束符 "$" 添加到 中
- 可能在某个句型中紧跟在
示例
引入非终结符的后继符号集的概念后,可以进一步的完善可选集的定义
# q_ 文法
定义
- 由可选集的定义,可定义
文法如下: - 每个产生式的右部或为
, 或以终结符开始 - 具有相同左部的产生式有不相交的可选集
- 每个产生式的右部或为
q_ 文法不含右部以非终结符打头的产生式,为了提高适用性,因此引入串首终结符集的概念
# 文法符号串的串首终结符集 -- FIRST 集
定义
- 串着终结符的定义
- 串首的第一个符号,并且是终结符,简称串首终结符
可以看做一个特殊的终结符
- 串首的第一个符号,并且是终结符,简称串首终结符
- 给定一个文法符号串
, 的串首终结符集 被定义为 - 可以从
推导出的所有串首终结符构成的集合 - 如果
,那么 也在 中 - 定义的集合描述
- 对于
,
- 对于
- 可以从
由此可得产生式的可选集为
# LL(1)文法的定义
定义
- 文法
是 的,当且仅当 的任意两个具有相同左部的产生式 满足下面的条件 - 不存在终结符
使得 和 都能够推导出以 开头的串 和 至多有一个能推导出 - 如果
,则
如果,则
- 不存在终结符
定义中的 3 个条件,均是为了满足具有相同左部的产生式的可选集互不相交
- 由公式(1) 即可验证,数学描述如下:
LL(1) 文法命名的含义
- 第一个“L”表示从左向右扫描输入
- 第二个“ L”表示产生最左推导
- “1”表示在每一步中只需要向前看一个输入符号来决定语法分析动作
编辑 (opens new window)