FIRST集与FOLLOW集的计算
# FIRST 集与 FOLLOW 集的运算
# FIRST 集的运算
# 计算文法符号 X 的 FIRST(X)
算法实现
- 不断应用下列规则,直到没有新的终结符或
可以被加入到任何 集合中为止 - 如果
是一个终结符,那么 - 如果
是一个非终结符,且 - 如果对于某个
, 在 中且 在所有的 中(即 , 就把 加入到 中 - 如果对于所有的
, 在 中,那么将 加入到
- 如果对于某个
- 如果
,那么将 加入到 中
- 如果
计算示例
# 计算文法符号串的 FIRST 集合
计算过程
- 向
加入 中所有的非 符号 - 如果
在 中, 再加入 中的所有非 符号; - 如果
在 和 中, 再加入 中的所有非 符号, 以此类推
- 如果
- 最后,如果对所有的
, 都在 中,那么将 加入到 中
# FOLLOW 集的运算
算法实现
- 不断应用下列规则,直到没有新的终结符可以被加入到任何
集合中为止 - 将 "$" 放入
中,其中 是开始符号,"$" 是输入右端的结束标记 - 如果存在一个产生式
,那么 中除 之外的所有符号都在 中 - 如果存在一个产生式
,或存在产生式 且 包含 ,那么 中的所有符号都在 中 (可以根据 集的定义进行证明)
- 将 "$" 放入
#
FOLLOW 集计算示例
- 计算过程
- 结合上述结论,可得各个非终结符的
集
- 结合上述结论,可得各个非终结符的
# 计算 SELECT 集
计算示例
- 先计算各个非终结符的
集和 集 - 具体计算过程参照 FOLLOW集计算示例
产生式 | |||
---|---|---|---|
- 根据各个非终结符的
集和 集借助 集的计算公式来计算 集
序号 | 产生式 | |
---|---|---|
(1) | ||
(2) | ||
(3) | ||
(4) | ||
(5) | ||
(6) | ||
(7) | ||
(8) |
# 预测分析表
- 可由
SELECT
集生成预测分析表- 输入是 (非终结符,终结符),输出是对应的以非终结行为左部的产生式
- 相当于是二维查表
示例
- SELECT 集
序号 | 产生式 | |
---|---|---|
(1) | ||
(2) | ||
(3) | ||
(4) | ||
(5) | ||
(6) | ||
(7) | ||
(8) |
- 预测分析表
- 一个终结符和一个非终结符对应一个特定产生式,即当输入字符(终结符)和产生式的左部(非终结符)确定后,可选的产生式不超过
个 - 如果没有可选的产生式,则说明输入符号与文法不匹配
- 一个终结符和一个非终结符对应一个特定产生式,即当输入字符(终结符)和产生式的左部(非终结符)确定后,可选的产生式不超过
编辑 (opens new window)