1.求首符号集first(对符号串)、向前看集follow(对非终结符)、可选集select(对产生式)
时间: 2023-08-01 21:10:12 浏览: 57
首符号集(first):对于一个符号串,它的首符号集是由该符号串的第一个符号组成的集合。如果该符号是一个非终结符,则需要考虑该非终结符所对应的产生式的首符号集。
向前看集(follow):对于一个非终结符,它的向前看集是由该非终结符后面紧随的终结符或其他非终结符的首符号组成的集合。需要考虑到该非终结符在所有产生式中的出现位置。
可选集(select):对于一个产生式,它的可选集是由该产生式所对应的非终结符的向前看集和产生式右侧符号串的首符号集的交集组成的集合。如果产生式右侧符号串可以推导出空串,则需要将该非终结符的首符号集也加入到可选集中。
相关问题
求一个产生式的右部符号串的first集
要求一个产生式的右部符号串的FIRST集,需要按照以下规则进行处理:
1. 如果右部符号串的第一个符号是终结符,则将这个终结符加入到FIRST集中。
2. 如果右部符号串的第一个符号是非终结符,则将这个非终结符的FIRST集中除了ε之外的所有符号加入到FIRST集中。
3. 如果右部符号串的第一个符号的FIRST集中包含ε,则需要继续处理右部符号串的第二个符号,并将这个符号的FIRST集中除了ε之外的所有符号加入到FIRST集中。如果右部符号串的第二个符号的FIRST集中也包含ε,则需要继续处理右部符号串的第三个符号,以此类推。
4. 如果右部符号串的每一个符号的FIRST集中都包含ε,则需要将ε加入到FIRST集中。
需要注意的是,在处理第三种情况时,如果右部符号串的第一个符号的FIRST集中包含ε,但是右部符号串的第二个符号的FIRST集中不包含ε,则需要将右部符号串的第二个符号的FIRST集中所有符号都加入到FIRST集中,并停止处理后面的符号。这是因为如果后面的符号的FIRST集中包含ε,那么它们的FIRST集中的所有符号都已经被加入到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 集合的影响。