对于给定的文法: D->TL; T->i; T->f; T->L,x; L->x;如何构造first和follow集合
时间: 2024-06-02 15:11:28 浏览: 95
首先,我们需要明确一下文法的起始符号是什么。假设起始符号是D。
构造First集合:
1. 对于终结符号i和f,First(T) = {i, f}。
2. 对于终结符号x,First(L) = {x}。
3. 对于非终结符号T,如果T可以推导出空串,那么First(T)中还要包含空串。因为T可以推导出空串的条件是它可以推导出L,x,而L可以推导出空串。
4. 对于非终结符号D,First(D) = First(T) = {i, f},因为D的产生式只有一个,且右部以T开头。
构造Follow集合:
1. 首先,D的Follow集合中必须包含$,表示输入串的结束符号。
2. 对于非终结符号T,如果T在D的右部出现,那么Follow(T)中应该包含D的Follow集合。因为D推导出T,所以输入串的结束符号必须跟在T的后面。
3. 对于非终结符号L,如果L在T的右部出现,那么Follow(L)中应该包含T的Follow集合。因为T可以推导出L,x,所以如果L后面有别的符号,那么输入串的结束符号就不一定跟在L的后面。
4. 如果L的右部可以推导出空串,那么Follow(L)中还应该包含T的First集合。因为L可以推导出空串,所以如果L后面是T,那么输入串的结束符号必须跟在T的后面。
5. 如果T的右部可以推导出空串,那么Follow(T)中还应该包含D的Follow集合。因为T可以推导出空串,所以如果T后面是D,那么输入串的结束符号必须跟在D的后面。
6. 如果T的右部以L,x开头,那么Follow(L)中还应该包含T的Follow集合。因为L后面可能有别的符号,所以输入串的结束符号就不一定跟在L的后面。
按照上述规则,可以得到如下的First和Follow集合:
First集合:
First(D) = {i, f}
First(T) = {i, f, x, ε}
First(L) = {x}
Follow集合:
Follow(D) = {$}
Follow(T) = {;, $}
Follow(L) = {, , ;, $}
阅读全文