对于给定的文法: D->TL; T->i; T->f; T->L,x; L->x;如何消除左递归
时间: 2024-05-23 09:12:06 浏览: 19
对于这个文法,可以按照以下步骤进行左递归消除:
1. 将所有左递归的产生式提取出来,如下所示:
D -> TL;
T -> i;
T -> f;
T -> L,x;
L -> x;
2. 对于每一个左递归的产生式 A -> Aα1 | Aα2 | ... | Aαn | β,可以将其改写为 A -> βA',A' -> α1A' | α2A' | ... | αnA' | ε 的形式。
根据这个方法,我们可以对 D -> TL; 进行消除左递归:
D -> TL;
D -> TL;
D' -> ε;
然后对于 T -> L,x; 进行消除左递归:
T -> i;
T -> f;
T -> L,T';
T' -> ,x | ε;
L -> x;
最终得到消除左递归后的文法:
D -> TL;
D' -> ε;
T -> i | f | L,T';
T' -> ,x | ε;
L -> x;
相关问题
对于给定的文法: D->TL; T->i; T->f; T->L,x; L->x;如何构造first和follow集合
首先,我们需要明确一下文法的起始符号是什么。假设起始符号是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) = {, , ;, $}
D->TL;T->i;T->f;T->L,x;L->x;如何消除左递归
为了消除左递归,我们需要将产生式改写为右递归形式。对于给定的文法:
D->TL;
T->i;
T->f;
T->L,x;
L->x;
我们可以将其改写为右递归形式如下:
D->TL';
L'->,TL';
L'->ε
T->i;
T->f;
T->L;
其中,L'是L的一个替代符号。这里我们添加了两个新的产生式,其中一个产生式生成逗号和一个新的非终结符L',它可以继续扩展为一个L和一个逗号,或者为空。这个新的产生式可以将原来的产生式D->TL,x转换为右递归形式D->TL',而不是左递归形式。同样地,我们可以使用L'来将T->L,x转换为右递归形式T->L,L'。最后,我们将L->x保持不变,因为它不涉及到左递归。这样,我们就成功地消除了左递归。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)