First 和 Follow 集合
时间: 2024-06-16 12:07:29 浏览: 18
First集合和Follow集合是在编译原理中用于构造语法分析表的重要概念。
1. First集合:
- First集合是对文法产生式右部的一种预测性分析,表示该产生式右部能够推导出的终结符号集合。
- 对于一个非终结符号A,它的First集合包括它的所有产生式右部的第一个终结符号,如果产生式右部可以推导出空串,则还需要包括下一个终结符号。
- First集合的计算可以通过以下步骤进行迭代计算,直到不再发生改变:
- 如果X是一个终结符号,则First(X) = {X}。
- 如果X是一个非终结符号,则遍历它的每个产生式右部:
- 如果右部的第一个符号Y是一个终结符号,则将Y加入到First(X)中。
- 如果右部的第一个符号Y是一个非终结符号,则将First(Y)中的所有终结符号加入到First(X)中,如果Y能够推导出空串,则将下一个符号也加入到First(X)中。
2. Follow集合:
- Follow集合是对文法产生式左部非终结符号的一种预测性分析,表示该非终结符号出现在右部中的哪些位置。
- 对于一个非终结符号A,它的Follow集合包括所有能够紧随A出现的终结符号。
- Follow集合的计算可以通过以下步骤进行迭代计算,直到不再发生改变:
- 将文法开始符号的结束符号($)加入到Follow(开始符号)中。
- 遍历每个产生式右部,对于每个产生式右部的非终结符号A:
- 将Follow(A)加入到A后面的非终结符号的Follow集合中。
- 如果A后面跟着一个可以推导出空串的非终结符号B或者是A是右部最后一个符号,则将Follow(A)加入到B的Follow集合中。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)