有文法G[S]:S→AB A→ab|ε B→ac 1.计算所有符号串的FIRST集 2.计算所有非终结符的FOLLOW集 3.计算所有产生式的SELECT集 4.该文法是不是LL(1)文法?
时间: 2024-05-22 22:11:05 浏览: 150
《编译原理》课程试卷A及答案.docx
1. 所有符号串的FIRST集:
FIRST(S) = {a, ε}
FIRST(A) = {a, ε}
FIRST(B) = {a}
2. 所有非终结符的FOLLOW集:
FOLLOW(S) = {$}
FOLLOW(A) = {b, c}
FOLLOW(B) = {b, c, $}
3. 所有产生式的SELECT集:
SELECT(S → AB) = {a}
SELECT(A → ab) = {a}
SELECT(A → ε) = {b, c}
SELECT(B → ac) = {a}
4. 判断是否为LL(1)文法:
对于同一非终结符的两个产生式,它们的SELECT集不能有交集。
对于产生式A → ε 和其他产生式,如果它们的FIRST集有交集,则不能为LL(1)文法。
根据上述规则,可以得到:
SELECT(A → ab) ∩ SELECT(A → ε) = {a},因此不是LL(1)文法。
因此,该文法不是LL(1)文法。
阅读全文