什么是 FIRST 和 FOLLOW，它们是如何计算的？

  • Z时代
  • 2024-01-10
  • 分类：综合

FIRST 和 FOLLOW 是两个与语法相关的函数，可以帮助我们填充 M 表的条目。

FIRST () - 它是一个函数，它给出了从产生式规则派生的字符串开始的终端集。

符号 c 在 FIRST (α) 中当且仅当对于某个语法符号序列 β α ⇒ cβ。

终结符 a 在 FOLLOW (N) 中当且仅当存在从文法的起始符号 S 的派生使得 S ⇒ α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 → Y 1 , Y 2 , Y 3，则 FIRST (X) 将是

(a) 如果 Y 是终结点，则

      第一 (X) = 第一 (Y 1 , Y 2 , Y 3 ) = {Y 1 }

(b) 如果 Y 1是非终结符且

      如果 Y 1不导出为空字符串，即，如果 FIRST (Y 1 ) 不包含 ε，则 FIRST (X) = FIRST (Y 1 , Y 2 , Y 3 ) = FIRST(Y 1 )

(c) 如果 FIRST (Y 1 ) 包含 ε，则。

     FIRST (X) = FIRST (Y 1 , Y 2 , Y 3 ) = FIRST(Y 1 ) − {ε} ∪ FIRST(Y 2 , Y 3 )

类似地，FIRST (Y 2 , Y 3 ) = {Y 2 }，如果 Y 2是终结符，否则如果 Y 2是非终结符，则

  • FIRST (Y 2 , Y 3 ) = FIRST (Y 2 )，如果FIRST (Y 2 ) 不包含ε。

  • 如果 FIRST (Y 2 ) 包含 ε，则

  • FIRST (Y 2 , Y 3 ) = FIRST (Y 2 ) − {ε} ∪ FIRST (Y 3 )

类似地，对于进一步的语法符号，即对于Y 4、Y 5、Y 6 ... ，将重复该方法。ÿ ķ。

FOLLOW的计算

Follow (A) 定义为直接出现在 A 右侧的终结符的集合。

FOLLOW(A) = {a|S ⇒* αAaβ 其中 α, β 可以是任何字符串}

查找规则 FOLLOW

  • 如果S是起始符号，FOLLOW(S)={$}

  • 如果生产形式为 A → α B β，则 β ≠ ε。

(a) 如果 FIRST (β) 不包含 ε，则 FOLLOW (B) = {FIRST (β)}

或者

(b) 如果 FIRST (β) 包含 ε（即 β ⇒* ε），则

        跟随 (B) = 第一 (β) − {ε} ∪ 跟随 (A)

∵ 当 β 导出 ε 时，则 A 之后的终结点将跟随 B。

  • 如果生产形式为 A → αB，则 Follow (B) ={FOLLOW (A)}。

以上是 什么是 FIRST 和 FOLLOW，它们是如何计算的？ 的全部内容， 来源链接： utcz.com/z/335432.html

回到顶部