编译原理作业-截止日期: 4.7

编译原理

7-2

提取$S→Aa|Ab|c$的公共左因子：
$S→AS'|c$
$S'→a|b$
消除$A→Ad|Se|f$的直接左递归：
$A→SeA'|fA'$
$A'→dA'|\varepsilon$
消除$S$和$A$的间接左递归：
$S→SeA'S'|fA'S'|c$
消除上式的直接左递归：
$S→fA'S'S''|cS''$
$S''→eA'S'S''|\varepsilon$
综上所述，文法$G$消除左递归并提取公共左因子后为：
$S→fA'S'S''|cS''$
$S'→a|b$
$S''→eA'S'S''|\varepsilon$
$A'→dA'|\varepsilon$

7-3

消除$L→L,S|S$的直接左递归：
$L→SL'$
$L'→,SL'|\varepsilon$
递归下降分析过程：

void S() {
    if (symbol == '(') {
        advance();
        L();
        if (symbol == ')') {
            advance();
        }
        else {
            error();
        }
    }
    else if (symbol == 'a') {
        advance();
    }
    else {
        error();
    }
}
void L() {
    S();
    L'();
}
void L'() {
    if (symbol == ',') {
        advance();
        S();
        L'();
    }
}

7-5

消除$S→A|S:A$的直接左递归：
$S→AS'$
$S'→:AS'|\varepsilon$
消除$A→B|A+B$的直接左递归：
$A→BA'$
$A'→+BA'|\varepsilon$
综上所述，文法$G'$：
$S→AS'$
$S'→:AS'|\varepsilon$
$A→BA'$
$A'→+BA'|\varepsilon$
$B→bS*|a$

预测分析表：

从上表可以看出，$G'$是$LL(1)$文法。