划掉下列文法 G[S]中多余的产生式 1) S→Be 2) B→Ce 3)B→Af 4) A→Ae 5) A→e 6) C→Cf 7) D→f
时间: 2024-06-18 09:06:13 浏览: 9
在 G[S] 文法中,划掉下列多余的产生式:
1) S→Be
2) B→Ce
4) A→Ae
5) A→e
这是因为这些产生式可以被其他产生式所替代,不会对文法的语言造成影响。具体来说:
1) S 可以直接推导出 Be,也可以由其他推导出 B,再由 B 推导出 Be,因此该产生式可以被删去。
2) B 可以直接推导出 Ce,也可以由其他推导出 A,再由 A 推导出 Af,再由 F 推导出 Ce,因此该产生式可以被删去。
4) A 可以由其他产生式推导出 Ae,因此该产生式可以被删去。
5) A 可以作为一个空串存在于文法中,因此该产生式可以被删去。
相关问题
构造下列文法的LR(1)分析表 S→AA|ε A→aA|b
首先,我们需要求出该文法的所有 LR(1) 项目集。
项目集 I0:
S'-> .S
S -> .AA
S -> .
A -> .aA
A -> .b
项目集 I1:
S'-> S.
A -> .aA
A -> .b
项目集 I2:
S -> A.A
A -> .aA
A -> .b
项目集 I3:
S -> AA.
A -> .aA
A -> .b
项目集 I4:
A -> a.A
A -> .aA
A -> .b
项目集 I5:
A -> b.
A -> .aA
A -> .b
由于该文法没有移进-规约冲突或规约-规约冲突,因此可以使用 LR(1) 分析表对其进行分析。分析表的构造过程如下:
状态 | a | b | $ | A | S |
---- | --------| --------| --------| --------| --------|
0 | s4 | s5 | | s1 | |
1 | s4 | s5 | acc | s2 | |
2 | s4 | s5 | | s3 | |
3 | r2 | r2 | r2 | | |
4 | s4 | s5 | | s1 | |
5 | r1 | r1 | r1 | | |
其中,s 表示移进操作,r 表示规约操作,acc 表示接受操作。分析表中的每个单元格表示当前状态下对应输入符号所需要执行的操作。例如,表格中第一行第二列的 s5 表示在状态 0 下读入输入符号 b 时需要将其移入栈中并转移到状态 5。
因此,该文法的 LR(1) 分析表如下:
状态 | a | b | $ | A | S |
---- | --------| --------| --------| --------| --------|
0 | s4 | s5 | | s1 | |
1 | s4 | s5 | acc | s2 | |
2 | s4 | s5 | | s3 | |
3 | r2 | r2 | r2 | | |
4 | s4 | s5 | | s1 | |
5 | r1 | r1 | r1 | | |
其中,$ 表示输入串的结束符。
消除文法G: S→a|b|(T) T→TcS|S 的左递归;
消除文法的左递归是为了让文法满足LL(1)文法的要求,方便语法分析器进行处理。对于文法G:S→a|b|(T) T→TcS|S,我们可以按照以下步骤进行左递归的消除:
1. 将所有的直接左递归都消除,即将T→TcS转化为T→SU,其中U→cSU|ε;
2. 对于每一个非终结符号A,找到其所有能够推导出ε的直接或间接子孙非终结符号B1,B2,...Bn,并将其从A的产生式中删除;
3. 将删除ε后的产生式中的右部替换为其所有可能的组合,例如T→SU可以替换为T→cST|S;
4. 将新产生的文法规则加入原有文法中。
经过消除左递归后,G的新文法为:
S → a | b | '(' T ')'
T → SU
U → cSU | ε
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)