在 LL(1)文法中,为什么要求同一非终结符的多个候选式的 FIRST 集的交 集为空?
时间: 2023-06-15 19:04:38 浏览: 138
LL(1)文法是一类特殊的上下文无关文法,它可以被用于构建递归下降分析器。在LL(1)文法中,为了避免产生二义性,同一个非终结符的不同候选式必须满足FIRST集的交集为空。
这是因为在递归下降分析器中,为了选择正确的产生式,需要先预测下一个终结符号。如果同一个非终结符有多个产生式可以被选择,那么这个预测就不准确了,会出现二义性。
因此,为了避免这种情况,我们要求同一个非终结符的多个候选式的FIRST集的交集为空。这意味着任何时候,只有一个候选式可以被选择,从而消除了二义性。
相关问题
LL(1)文法,若非终结符有多个候选式,则所有候选式的FIRST集的交集为空集吗
不一定。如果一个非终结符的多个候选式的FIRST集存在交集,则这个文法不是LL(1)文法,因为在LL(1)分析过程中,需要通过读取输入符号来选择正确的候选式,而如果存在交集,则无法确定应该选择哪个候选式。但是,如果对于一个非终结符的多个候选式,它们的FIRST集的交集为空集,则这个文法可以是LL(1)文法。这是因为在这种情况下,对于任何一个输入符号,都只有一个候选式的FIRST集包含这个符号,因此可以唯一确定应该选择哪个候选式。
LL(1)文法的非终结符FIRST集
对于一个LL(1)文法中的非终结符A,它的FIRST集可以通过以下步骤计算:
1. 如果产生式A → ε存在,则将 ε 加入 FIRST(A) 中。
2. 对于每个产生式A → X1X2...Xn,将 FIRST(X1) 中的所有非空终结符都加入 FIRST(A) 中。
3. 如果 FIRST(X1) 包含 ε,则将 FIRST(X2) 中的所有非空终结符都加入 FIRST(A) 中,以此类推,直到某个 Xi 的 FIRST集不包含 ε。
4. 如果所有 Xi 的 FIRST集都包含 ε,则将 ε 加入 FIRST(A) 中。
需要注意的是,如果某个非终结符的 FIRST 集合中包含了 ε,那么在对这个非终结符进行 FOLLOW 集合的计算时,还需要考虑到这个 ε 对 FOLLOW 集合的影响。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)