判断下面的文法是否为LL(1)文法 0) S-›b N 1) N-›B a N 2) N->€ 3) B-›a b
时间: 2023-09-13 12:05:16 浏览: 104
### 回答1:
首先,LL(1)文法要求每个非终结符的每个产生式的“预测符号集合”互不相交。预测符号是指在读入一个非终结符后,预测下一个终结符的符号。对于每个非终结符A的产生式A → α,预测符号集合包括FIRST(α),以及如果ε∈FIRST(α)则也包括FOLLOW(A)。
对于该文法,我们可以求出每个符号的FIRST集合和FOLLOW集合:
- FIRST(S) = {b}
- FIRST(N) = {a, ε}
- FIRST(B) = {a}
- FOLLOW(S) = {$}
- FOLLOW(N) = {a, $}
- FOLLOW(B) = {a, b}
接下来,我们检查是否存在任何两个产生式的预测符号集合相交。我们来看一下每个非终结符的每个产生式的预测符号集合:
- S → bN:预测符号集合为{b}
- N → BaN:预测符号集合为{a}
- N → ε:预测符号集合为{a, $}
- B → ab:预测符号集合为{a}
可以看出,不存在任何两个产生式的预测符号集合相交,因此该文法是LL(1)文法。
### 回答2:
不是LL(1)文法。
LL(1)文法要求在任何一个非终结符的产生式中,都不能出现左递归,并且每个非终结符的产生式选择时都不能产生First集合之间的冲突。
首先,我们来看一下该文法的每个非终结符的First集合:
- First(S) = {b}
- First(N) = {a, ε}
- First(B) = {a}
可以看到,非终结符N的First集中有一个ε。而LL(1)文法要求,如果一个产生式右部可以推导出ε,那么它的First集合和Follow集合不能有重叠。但是在该文法中,非终结符N的Follow集合由于存在产生式2) N->€,所以Follow(N) = Follow(S) = {b}。
所以,该文法不是LL(1)文法。
### 回答3:
该文法是一个LL(1)文法。
LL(1) 文法的定义是:对于每一个产生式 A->α,对于每一个终结符 a,至多存在一个产生式 A->α适用于输入的单词串首符号为 a。
对于给定的文法:
0) S->b N
1) N->B a N
2) N->€
3) B->a b
我们可以进行以下分析:
对于产生式 0) S->b N:
- 当输入符号为 b 时,可以选择该产生式进行推导。
对于产生式 1) N->B a N:
- 当输入符号为 a 时,可以选择该产生式进行推导。
- 当输入符号为 € 时,无法选择该产生式。
对于产生式 2) N->€:
- 该产生式是ε产生式,不会消耗任何输入符号。
对于产生式 3) B->a b:
- 当输入符号为 a 时,可以选择该产生式进行推导。
综上所述,对于该文法中的每一个产生式和每一个终结符,至多只有一个产生式适用于对应的输入符号,故该文法是LL(1)文法。
阅读全文