对文法G[S]:S→a|∧|(T);T→T,S|S。对文法进行改写
时间: 2023-06-01 08:02:20 浏览: 208
可以将文法G[S]改写为G'[S']:
S' → a | ε | (TS')
T → TS' | S'
其中,ε表示空串。
解释:
- S'可以推导出a、空串、以及括号内为T和S'的组合,即可以递归地构造出任意数量的S。
- T可以推导出TS'或者S',即可以递归地构造出任意数量的T和S。
这样改写后,原本存在左递归的文法得到了消除。
相关问题
对文法G[S]:S→a|∧|(T);T→T,S|S。对文法进行改写,对每个非终结符写出不带回溯的递归子程序
改写后的文法如下:
S → aS' | ∧
S' → TS' | S'
T → T,S | S
对应的不带回溯的递归子程序如下:
```
void S() {
if (lookahead == 'a') {
match('a');
S'();
} else if (lookahead == EPSILON) {
// do nothing
} else {
error();
}
}
void S'() {
if (lookahead == 'a') {
match('a');
S'();
} else if (lookahead == '(' || lookahead == 'a') {
T();
S'();
} else if (lookahead == ')' || lookahead == '$') {
// do nothing
} else {
error();
}
}
void T() {
if (lookahead == '(' || lookahead == 'a') {
S();
T_();
} else {
error();
}
}
void T_() {
if (lookahead == ',') {
match(',');
S();
T_();
} else if (lookahead == ')' || lookahead == '$') {
// do nothing
} else {
error();
}
}
```
对文法G[S]:S→a|∧|(T);T→T,S|S。对文法进行改写,然后对每个非终结符写出不带回溯的递归子程序
改写后的文法:
S → aS' | ∧
S' → TS' | S'
T → TS' | S
递归子程序:
void S() {
if (lookahead == 'a') {
match('a');
S_prime();
} else if (lookahead == '∧') {
match('∧');
} else if (lookahead == '(') {
match('(');
S();
match(')');
S_prime();
} else {
// 报错
}
}
void S_prime() {
if (lookahead == 'T' || lookahead == 'a' || lookahead == '∧' || lookahead == '(') {
T();
S_prime();
} else if (lookahead == 'S') {
match('S');
S_prime();
} else {
// 不做任何操作,即 S' → ε
}
}
void T() {
if (lookahead == 'T' || lookahead == 'a' || lookahead == '∧' || lookahead == '(') {
S();
S_prime();
} else {
// 报错
}
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)