数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究什么是 FIRST 和 FOLLOW 以及如何计算它们？
FIRST 和 FOLLOW 是与语法相关的两个函数，它们帮助我们填充 M 表的条目。
FIRST ()− 它是一个函数，给出从产生式规则导出的字符串开头的终结符集。
当且仅当 α ⇒ cβ 对某些语法符号序列 β 成立时，符号 c 位于 FIRST (α) 中。
当且仅当存在从语法的开始符号 S 的推导，使得 S ⇒ αNαβ，其中 α 和 β 是语法符号的（可能为空的）序列时，终结符 a 位于 FOLLOW (N) 中。换句话说，如果在推导的某个时刻 c 可以跟随 N，则终结符 c 位于 FOLLOW (N) 中。
FIRST ( ) 和 FOLLOW ( ) 的好处
它可用于证明语法的 LL (K) 特性。
它可用于促进预测分析表的构建。
它为递归下降解析器提供选择信息。
FIRST 的计算
FIRST (α) 定义为从 α 导出的字符串的第一个字母的终结符集合。
FIRST (α) = {α |α →∗ αβ 对于某个字符串 β }
如果 X 是语法符号，则 First (X) 将为 −
- 如果 X 是终结符，则 FIRST(X) = {X}
- 如果 X → ε，则 FIRST(X) = {ε}
- 如果 X 是非终结符 & X → a α，则 FIRST (X) = {a}
- 如果 X → Y1, Y2, Y3，则 FIRST (X) 将为
(a) 如果 Y 是终结符，则
FIRST (X) = FIRST (Y1, Y2, Y3) = {Y1}
(b) 如果 Y1 是非终结符并且
如果 Y1 不能推导出空字符串，即如果 FIRST (Y1) 不包含 ε，则 FIRST (X) = FIRST (Y1, Y2, Y3) = FIRST(Y1)
(c) 如果 FIRST (Y1) 包含 ε，则。
FIRST (X) = FIRST (Y1, Y2, Y3) = FIRST(Y1) − {ε} ∪ FIRST(Y2, Y3)
类似地，FIRST (Y2, Y3) = {Y2}，如果 Y2 是终结符，否则如果 Y2 是非终结符，则
FIRST (Y2, Y3) = FIRST (Y2)，如果 FIRST (Y2) 不包含 ε。
如果 FIRST (Y2) 包含 ε，则
FIRST (Y2, Y3) = FIRST (Y2) − {ε} ∪ FIRST (Y3)
类似地，此方法将对后续语法符号重复，即对于 Y4, Y5, Y6 … . YK。
FOLLOW 的计算
Follow (A) 定义为直接出现在 A 右侧的终结符集合。
FOLLOW(A) = {a|S ⇒* αAaβ 其中 α、β 可以是任何字符串}
查找 FOLLOW 的规则
如果 S 是开始符号，则 FOLLOW (S) ={$}
如果产生式形式为 A → α B β，β ≠ ε。
(a) 如果 FIRST (β) 不包含 ε，则 FOLLOW (B) = {FIRST (β)}
或者
(b) 如果 FIRST (β) 包含 ε（即 β ⇒* ε），则
FOLLOW (B) = FIRST (β) − {ε} ∪ FOLLOW (A)
∵ 当 β 推导出 ε 时，A 之后的终结符将跟随 B。
- 如果产生式形式为 A → αB，则 Follow (B) ={FOLLOW (A)}。
54K+ 浏览量
