编译原理first,follow,select集求法
|
编译原理
|
436

2805 字
|
14 分钟
本文最后更新于339 天前，其中的信息可能已经过时，如有错误请发送邮件到898599301@qq.com

看了好多文章讲的都不是很清楚，对初学者不是很友好，于是有了这篇通俗易懂的讲解.

注：内容由ai生成

好的，我们来用最通俗易懂的方式理解编译原理中的 FIRST 集、FOLLOW 集和 SELECT 集。

想象一下，你正在给一个机器人解释如何阅读一个非常简单的句子，这个句子遵循一些固定的语法规则。这些集合就是帮助机器人（也就是编译器里的解析器）在阅读过程中做出正确判断的工具。

我们用一个简单的语法规则集合来举例：

语法规则 (Production Rules):
1. E -> T E'
2. E' -> + T E'
3. E' -> ε  (ε 代表空字符串，什么都没有)
4. T -> F T'
5. T' -> * F T'
6. T' -> ε
7. F -> ( E )
8. F -> id   (id 代表一个标识符，比如变量名)

终结符 (Terminals): +, *, (, ), id, $ (这里的 $ 代表句子的结束标记)
非终结符 (Non-terminals): E, E', T, T', F
开始符号 (Start Symbol): E

这个语法描述了一个简单的算术表达式，比如 id + id * id 或者 (id + id).

1. FIRST 集 (首符集)

通俗解释:

FIRST 集就是一个非终结符（或一个符号串）可能推导出的所有句子的第一个终结符的集合。如果它能推导出空字符串 ε，那么 ε 也在它的 FIRST 集里。

就像问：“以‘名词短语’开头的句子，第一个词可能是哪些？” 答案可能是 "the", "a", "my" 等。

求法步骤 (最简单的方式):

  1. 初始化: 对于每个终结符 t，FIRST(t) = { t }。对于 ε，FIRST(ε) = { ε }。对于所有非终结符，它们的 FIRST 集一开始都是空的。
  2. 重复迭代: 不断应用以下规则，直到所有集合不再变化为止：
    • 规则 A (直接是终结符): 如果有一个产生式 A -> a ... (其中 a 是一个终结符)，那么把 a 加入到 FIRST(A) 中。
    • 规则 B (直接是 ε): 如果有一个产生式 A -> ε，那么把 ε 加入到 FIRST(A) 中。
    • 规则 C (以非终结符开头): 如果有一个产生式 A -> B1 B2 ... Bk (其中 B1, B2, ... 是符号)，那么把 FIRST(B1) 中除了 ε 以外的所有元素加入到 FIRST(A) 中。
    • 规则 D (以可推导 ε 的非终结符开头): 如果在规则 C 中，B1 可以推导出 ε (即 ε 在 FIRST(B1) 中)，那么把 FIRST(B2) 中除了 ε 以外的所有元素也加入到 FIRST(A) 中。如果 B1 和 B2 都能推导出 ε，就看 B3，以此类推。如果所有 Bi (从 B1 到 Bk) 都能推导出 ε，那么把 ε 加入到 FIRST(A) 中。

举例计算 FIRST 集:

我们用上面的语法来计算：

  • 终结符:

    • FIRST(+) = { + }
    • FIRST(*) = { * }
    • FIRST(() = { ( }
    • FIRST()) = { ) }
    • FIRST(id) = { id }
    • FIRST(ε) = { ε }

  • 非终结符 (迭代过程):

    • 第一轮:

      • F -> ( E ): 根据规则 A，FIRST(F) 加入 (.
      • F -> id: 根据规则 A，FIRST(F) 加入 id.
      • E' -> ε: 根据规则 B，FIRST(E') 加入 ε.
      • T' -> ε: 根据规则 B，FIRST(T') 加入 ε.
      • E' -> + T E': 根据规则 A，FIRST(E') 加入 +.
      • T' -> * F T': 根据规则 A，FIRST(T') 加入 *.
      • E -> T E': 根据规则 C，FIRST(E) 加入 FIRST(T) (目前 T 的 FIRST 集是空的，所以没变化).
      • T -> F T': 根据规则 C，FIRST(T) 加入 FIRST(F) (目前 FIRST(F) 是 { (, id })。

    • 第一轮结束时的集合:

      • FIRST(F) = { (, id }
      • FIRST(E') = { ε, + }
      • FIRST(T') = { ε, * }
      • FIRST(T) = { (, id } (从 F 复制过来)
      • FIRST(E) = { } (从 T 复制，T 当时是空的)

    • 第二轮 (检查是否有变化):

      • E -> T E': 根据规则 C，FIRST(E) 加入 FIRST(T). 现在 FIRST(T) = { (, id }. FIRST(E) 变成 { (, id }. (有变化!)
      • 其他规则再检查一遍，发现没有新的元素加入任何 FIRST 集了。

    • 迭代停止。最终的 FIRST 集:

      • FIRST(F) = { (, id }
      • FIRST(E') = { ε, + }
      • FIRST(T') = { ε, * }
      • FIRST(T) = { (, id }
      • FIRST(E) = { (, id }

2. FOLLOW 集 (随符集)

通俗解释:

FOLLOW 集是一个非终结符 A 在任何可能推导出的句子中，紧跟在 A 后面的终结符的集合。开始符号的 FOLLOW 集至少包含结束标记 $.

就像问：“在任何一个合法的句子中，如果‘名词短语’出现了，它后面紧跟着的词可能是哪些？” 答案可能是动词的开头词，或者是句号（如果名词短语是句子的结尾）。

求法步骤 (最简单的方式):

  1. 初始化: 对于开始符号 S，FOLLOW(S) 中加入结束标记 $. 对于所有其他非终结符，它们的 FOLLOW 集一开始都是空的。
  2. 重复迭代: 不断应用以下规则，直到所有集合不再变化为止：
    • 规则 A (紧跟在 A 后面的是终结符): 如果有一个产生式 B -> ... A a ... (其中 a 是一个终结符)，那么把 a 加入到 FOLLOW(A) 中。
    • 规则 B (紧跟在 A 后面的是非终结符): 如果有一个产生式 B -> ... A C ... (其中 C 是一个非终结符)，那么把 FIRST(C) 中除了 ε 以外的所有元素加入到 FOLLOW(A) 中。
    • 规则 C (A 在产生式末尾): 如果有一个产生式 B -> ... A，那么把 FOLLOW(B) 中所有元素加入到 FOLLOW(A) 中。
    • 规则 D (A 后面的非终结符可以推导出 ε): 如果有一个产生式 B -> ... A C ... (其中 C 可以推导出 ε，即 ε 在 FIRST(C) 中)，那么把 FOLLOW(B) 中所有元素加入到 FOLLOW(A) 中。 (注意：规则 D 是规则 B 的补充，当 C 推导出 ε 时，相当于 A 后面直接跟着 B 后面的东西)。

举例计算 FOLLOW 集:

我们用上面的语法和已经计算好的 FIRST 集来计算：

  • 初始化: FOLLOW(E) = { $ }. 其他非终结符的 FOLLOW 集为空。

  • 迭代过程:

    • 第一轮:

      • E -> T E':
        • 在 T 后面是 E'. FOLLOW(T) 加入 FIRST(E'). FIRST(E') = { ε, + }. 所以 FOLLOW(T) 加入 { + }. 因为 ε 在 FIRST(E') 中，根据规则 D，FOLLOW(T) 还要加入 FOLLOW(E). FOLLOW(E) = { $ }. 所以 FOLLOW(T) 变成 { +, $ }.
        • E' 在产生式末尾。根据规则 C，FOLLOW(E') 加入 FOLLOW(E). FOLLOW(E') 变成 { $ }.
      • E' -> + T E':
        • 在 T 后面是 E'. FOLLOW(T) 加入 FIRST(E') (除了 ε). FIRST(E') = { ε, + }. FOLLOW(T) 加入 { + }. (已存在). 因为 ε 在 FIRST(E') 中，FOLLOW(T) 还要加入 FOLLOW(E'). FOLLOW(E') = { $ }. FOLLOW(T) 变成 { +, $ }. (无变化).
        • E' 在产生式末尾。FOLLOW(E') 加入 FOLLOW(E'). (无变化).
      • T -> F T':
        • 在 F 后面是 T'. FOLLOW(F) 加入 FIRST(T') (除了 ε). FIRST(T') = { ε, * }. FOLLOW(F) 加入 { * }. 因为 ε 在 FIRST(T') 中，FOLLOW(F) 还要加入 FOLLOW(T). FOLLOW(T) = { +, $ }. FOLLOW(F) 变成 { *, +, $ }.
        • T' 在产生式末尾。FOLLOW(T') 加入 FOLLOW(T). FOLLOW(T') 变成 { +, $ }.
      • T' -> * F T':
        • 在 F 后面是 T'. FOLLOW(F) 加入 FIRST(T') (除了 ε). FIRST(T') = { ε, * }. FOLLOW(F) 加入 { * }. (已存在). 因为 ε 在 FIRST(T') 中，FOLLOW(F) 还要加入 FOLLOW(T'). FOLLOW(T') = { +, $ }. FOLLOW(F) 变成 { *, +, $ }. (无变化).
        • T' 在产生式末尾。FOLLOW(T') 加入 FOLLOW(T'). (无变化).
      • F -> ( E ):
        • 在 E 后面是 ). 根据规则 A，FOLLOW(E) 加入 ). FOLLOW(E) 变成 { $, ) }.

    • 第一轮结束时的集合:

      • FOLLOW(E) = { $, ) }
      • FOLLOW(E') = { $ }
      • FOLLOW(T) = { +, $ }
      • FOLLOW(T') = { +, $ }
      • FOLLOW(F) = { *, +, $ }

    • 第二轮 (检查是否有变化):

      • 重新检查所有规则，看看基于第一轮的结果是否有新的元素加入。
      • E -> T E': FOLLOW(T) 加入 FOLLOW(E). FOLLOW(T) 变成 { +, $ } U { $, ) } = { +, $, ) }. (有变化!) FOLLOW(E') 加入 FOLLOW(E). FOLLOW(E') 变成 { $ } U { $, ) } = { $, ) }. (有变化!)
      • E' -> + T E': FOLLOW(T) 加入 FOLLOW(E'). FOLLOW(T) 变成 { +, $, ) } U { $, ) } = { +, $, ) }. (无变化). FOLLOW(E') 加入 FOLLOW(E'). (无变化).
      • T -> F T': FOLLOW(F) 加入 FOLLOW(T). FOLLOW(F) 变成 { *, +, $ } U { +, $, ) } = { *, +, $, ) }. (有变化!) FOLLOW(T') 加入 FOLLOW(T). FOLLOW(T') 变成 { +, $ } U { +, $, ) } = { +, $, ) }. (有变化!)
      • T' -> * F T': FOLLOW(F) 加入 FOLLOW(T'). FOLLOW(F) 变成 { *, +, $, ) } U { +, $, ) } = { *, +, $, ) }. (无变化). FOLLOW(T') 加入 FOLLOW(T'). (无变化).
      • F -> ( E ): FOLLOW(E) 加入 ). (已存在).

    • 第二轮结束时的集合:

      • FOLLOW(E) = { $, ) }
      • FOLLOW(E') = { $, ) }
      • FOLLOW(T) = { +, $, ) }
      • FOLLOW(T') = { +, $, ) }
      • FOLLOW(F) = { *, +, $, ) }

    • 第三轮 (检查是否有变化): 再检查一遍，发现没有新的元素加入任何 FOLLOW 集了。

    • 迭代停止。最终的 FOLLOW 集:

      • FOLLOW(E) = { $, ) }
      • FOLLOW(E') = { $, ) }
      • FOLLOW(T) = { +, $, ) }
      • FOLLOW(T') = { +, $, ) }
      • FOLLOW(F) = { *, +, $, ) }

3. SELECT 集 (选择集)

通俗解释:

SELECT 集是针对每一个产生式而言的。它表示：当解析器需要展开非终结符 A 时，如果当前输入流中的下一个终结符是 SELECT 集中某个元素，那么就应该选择使用 A -> alpha 这个产生式。

这就像机器人要解析一个“名词短语”，它有两个可能的规则：“名词短语 -> 冠词 名词” 或 “名词短语 -> 专有名词”。如果下一个词是 "the"，它就应该选择第一个规则；如果下一个词是 "John"，它就应该选择第二个规则。SELECT 集就是告诉机器人这种对应关系。

求法步骤 (最简单的方式):

对于一个产生式 A -> alpha (其中 alpha 是产生式右部的符号串):

  • 规则 A (alpha 不能推导出 ε): SELECT(A -> alpha) = FIRST(alpha).
  • 规则 B (alpha 可以推导出 ε): SELECT(A -> alpha) = (FIRST(alpha) - { ε }) U FOLLOW(A). 也就是说，把 FIRST(alpha) 中除了 ε 以外的元素，以及 FOLLOW(A) 中的所有元素加在一起。

重要用途 (用于判断 LL(1) 文法):

一个文法是 LL(1) 文法（一种容易进行预测分析的文法）的必要条件是：对于同一个非终结符 A 的所有不同产生式 A -> alpha1, A -> alpha2, ...，它们的 SELECT 集必须两两互不相交。如果相交了，当遇到一个属于相交部分的终结符时，解析器就不知道该选择哪个产生式了。

举例计算 SELECT 集:

我们使用上面计算好的 FIRST 集和 FOLLOW 集：

  • 产生式 1: E -> T E'

    • 右部是 T E'. FIRST(T E') = FIRST(T) (因为 T 不能推导出 ε). FIRST(T) = { (, id }.
    • SELECT(E -> T E') = { (, id }.

  • 产生式 2: E' -> + T E'

    • 右部是 + T E'. FIRST(+ T E') = { + }.
    • SELECT(E' -> + T E') = { + }.

  • 产生式 3: E' -> ε

    • 右部是 ε. FIRST(ε) = { ε }. 右部可以推导出 ε.
    • SELECT(E' -> ε) = (FIRST(ε) - { ε }) U FOLLOW(E') = ( { ε } - { ε } ) U { $, ) } = { } U { $, ) } = { $, ) }.

  • 产生式 4: T -> F T'

    • 右部是 F T'. FIRST(F T') = FIRST(F) (因为 F 不能推导出 ε). FIRST(F) = { (, id }.
    • SELECT(T -> F T') = { (, id }.

  • *产生式 5: T' -> F T'**

    • 右部是 * F T'. FIRST(* F T') = { * }.
    • SELECT(T' -> * F T') = { * }.

  • 产生式 6: T' -> ε

    • 右部是 ε. FIRST(ε) = { ε }. 右部可以推导出 ε.
    • SELECT(T' -> ε) = (FIRST(ε) - { ε }) U FOLLOW(T') = ( { ε } - { ε } ) U { +, $, ) } = { } U { +, $, ) } = { +, $, ) }.

  • 产生式 7: F -> ( E )

    • 右部是 ( E ). FIRST(( E )) = { ( }.
    • SELECT(F -> ( E )) = { ( }.

  • 产生式 8: F -> id

    • 右部是 id. FIRST(id) = { id }.
    • SELECT(F -> id) = { id }.

最终的 SELECT 集:

  • SELECT(E -> T E') = { (, id }
  • SELECT(E' -> + T E') = { + }
  • SELECT(E' -> ε) = { $, ) }
  • SELECT(T -> F T') = { (, id }
  • SELECT(T' -> * F T') = { * }
  • SELECT(T' -> ε) = { +, $, ) }
  • SELECT(F -> ( E )) = { ( }
  • SELECT(F -> id) = { id }

检查 LL(1) 条件:

  • 非终结符 E 只有一个产生式，没问题。
  • 非终结符 E' 有两个产生式: E' -> + T E' 和 E' -> ε.
    • SELECT(E' -> + T E') = { + }
    • SELECT(E' -> ε) = { $, ) }
    • 这两个集合 { + } 和 { $, ) } 是互不相交的。E' 没问题。
  • 非终结符 T 只有一个产生式，没问题。
  • 非终结符 T' 有两个产生式: T' -> * F T' 和 T' -> ε.
    • SELECT(T' -> * F T') = { * }
    • SELECT(T' -> ε) = { +, $, ) }
    • 这两个集合 { * } 和 { +, $, ) } 是互不相交的。T' 没问题。
  • 非终结符 F 有两个产生式: F -> ( E ) 和 F -> id.
    • SELECT(F -> ( E )) = { ( }
    • SELECT(F -> id) = { id }
    • 这两个集合 { ( } 和 { id } 是互不相交的。F 没问题。

因为所有非终结符的产生式的 SELECT 集都两两不相交，所以这个语法是 LL(1) 文法。

总结:

  • FIRST 集: 预测一个符号串开头可能是什么终结符。
  • FOLLOW 集: 预测一个非终结符后面可能跟着什么终结符。
  • SELECT 集: 结合 FIRST 和 FOLLOW (处理 ε 的情况)，决定当看到某个终结符时，应该选择哪个产生式来展开当前的非终结符。

这三个集合是构建预测分析器（特别是 LL(1) 分析器）的基础。求它们的过程就是不断应用规则，直到集合不再变化为止，这是一个迭代的过程。希望这个通俗的解释和详细的例子能帮助你理解！

文末附加内容
编译原理
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
一个例题解决预测分析表求法