在预测分析表的构造过程中,何时能够用到 FOLLOW 集的计算?其主要 作用是什么?
时间: 2024-05-30 17:11:53 浏览: 12
在预测分析表的构造过程中,FOLLOW集主要用于处理文法中的带有空串的非终结符号。具体来说,FOLLOW集可用于以下两种情况:
1. 构造 SELECT 集。在构造 SELECT 集时,需要用到 FIRST 集和 FOLLOW 集。对于某个产生式 A -> X1X2...Xn,其SELECT集为:
SELECT(A -> X1X2...Xn) = FIRST(X1X2...Xn)除去空串
如果 FIRST(X1X2...Xn)中包含空串,则需要将 FOLLOW(A)加入到SELECT(A -> X1X2...Xn)中。
2. 填充预测分析表。在填充预测分析表时,需要考虑到语法分析器在遇到某些非终结符号时,应该选择哪个产生式进行展开。这时,需要用到 FOLLOW 集来判断。具体来说,对于某个非终结符号A,如果存在一个产生式A -> X1X2...Xn,那么对于每个终结符号a属于FOLLOW(A),都应该将M[A, a]设为A -> X1X2...Xn。这样,在语法分析时,遇到一个非终结符号A时,就会根据当前输入符号来查找预测分析表中对应的产生式进行展开。
因此,FOLLOW集在预测分析表的构造过程中扮演着至关重要的角色,它可以帮助我们处理文法中的空串以及确定语法分析器在遇到某些非终结符号时应该如何展开。
相关问题
FOLLOW 的计算过程中,何时会用到 FIRST 集的计算?举例说明。
在进行语法分析时,FOLLOW 集合通常用于计算非终结符的 Follow 集合,以确定其后跟哪些终结符或非终结符。在计算 FOLLOW 集合时,需要考虑产生式右部中的每个符号,以确定它们可能后跟哪些符号。如果一个产生式右部的符号串可以推导为空串,那么其左部的 FOLLOW 集合应该包含产生式左部的 FOLLOW 集合。
举个例子,假设有以下的产生式:
```
S -> A B C
A -> a
B -> b | ε
C -> c
```
首先,我们需要计算出所有终结符的 FOLLOW 集合。因为 S 是起始符号,所以 $S$ 的 FOLLOW 集合包含 $EOF$ 符号。
然后,我们需要计算非终结符的 FOLLOW 集合。根据上述产生式,$A$ 的 FOLLOW 集合应该是 $B$ 的 FIRST 集合和 $S$ 的 FOLLOW 集合。因为 $B$ 可能推导为空串,所以需要将 $S$ 的 FOLLOW 集合也加入到 $A$ 的 FOLLOW 集合中。
接下来,我们计算 $B$ 的 FOLLOW 集合。因为 $B$ 可能推导为空串,所以需要考虑 $C$ 的 FIRST 集合和 $S$ 的 FOLLOW 集合。因为 $C$ 不是一个可空的非终结符,所以只需要将 $S$ 的 FOLLOW 集合加入到 $B$ 的 FOLLOW 集合中。
最后,我们计算 $C$ 的 FOLLOW 集合。因为 $C$ 在产生式右部出现在最后一个位置,所以其 FOLLOW 集合包含 $S$ 的 FOLLOW 集合。
因此,最终得到的 FOLLOW 集合如下:
```
FOLLOW(A) = {b, EOF}
FOLLOW(B) = {c, EOF}
FOLLOW(C) = {EOF}
```
first集_编译原理中FIRST集和FOLLOW集是什么东西?
在编译原理中,FIRST集和FOLLOW集是用于描述文法的一种符号集合。
首先,FIRST集表示一个文法符号能够推导出的所有可能的字符串的首字符集合。对于一个文法符号,它的FIRST集包括以下内容:
1. 如果这个符号是一个终结符(即不再能够被进一步推导的符号),那么它的FIRST集就是该终结符本身。
2. 如果这个符号能够推导出一个或多个以终结符开头的字符串,那么它的FIRST集就包括这些字符串的首字符。
3. 如果这个符号能够推导出一个或多个以非终结符开头的字符串,那么它的FIRST集就包括这些非终结符的FIRST集。
其次,FOLLOW集表示一个文法符号在某个产生式中的右侧能够紧随其后的所有可能的符号集合。对于一个文法符号,它的FOLLOW集包括以下内容:
1. 如果这个符号是文法的开始符号,那么它的FOLLOW集就包括文法的结束符号。
2. 如果这个符号在某个产生式的右侧能够紧随其后,那么它的FOLLOW集就包括该产生式左侧符号的FOLLOW集。
3. 如果这个符号在某个产生式的右侧能够紧随其后,且该符号右侧的字符串能够推导出 ε(即空串),那么它的FOLLOW集就包括该产生式左侧符号的FOLLOW集。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)