对文法G[S]：S→a|∧|(T)；T→T，S|S，对文法进行改写，然后对每个非终极符写出不带回溯的递归子程序

改写后的文法：

S → a | ε | (T)
T → ST'

T' → ,ST' | ε

不带回溯的递归子程序：

void S() {
if (lookahead == 'a') {
match('a');
} else if (lookahead == '(') {
match('(');
T();
match(')');
} else {
// ε
}
}

void T() {
S();
T'();
}

void T'() {
if (lookahead == ',') {
match(',');
S();
T'();
} else {
// ε
}
}

相关问题

对文法G[S]：S→a|∧|(T)；T→T，S|S。对文法进行改写

可以将文法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();
    }
}