构造覆盖C语言IF条件语句的LL(1)文法冲突修正方法

问题描述 #

构造可覆盖C程序中IF、IF-ELSE、IF-ELSE IF-ELSE条件语句的LL(1)文法时，构建LL(1)分析表阶段发现AUX_PROG规则下，同一终结符}、)对应两个分析表条目，不符合LL(1)文法要求。

初始文法及First、Follow集计算结果 #

<MAIN> ::= int main () { <AUX_PROG> }
<AUX_PROG> ::= <PROG> <AUX_PROG>
| ε
<PROG> ::= <IF_STAT>
| <AUX_OTHER>
<IF_STAT> ::= if (<AUX_OTHER>) {<AUX_PROG>} <ELSE_STAT>
<AUX_OTHER> ::= other <AUX_OTHER>
| ( <AUX_PROG> ) <AUX_OTHER>
| { <AUX_PROG> } <AUX_OTHER>
| <KEYWORD> <AUX_OTHER>
| ε
<ELSE_STAT> ::= else <AUX_ELSE_STAT>
| ε
<AUX_ELSE_STAT> ::= { <AUX_PROG> }
| if (<AUX_OTHER>) {<AUX_PROG>} else <AUX_ELSE_STAT>
<KEYWORD> ::= int
| main

follow(AUX_OTHER) ={)} U follow(PROG) = {if, other, (, {, int, main,"}", )}
follow(ELSE_STAT) = follow(IF_STAT) = {if, other, (, {, int, main,"}", )}
follow(IF_STAT) = follow(PROG) = {if, other, (, {, int, main,"}", )}
follow(PROG) = (first(AUX_PROG) - ε) U follow(AUX_PROG) = {if, other, (, {, int, main,"}", )}
follow(AUX_PROG) = {"}", )}
follow(MAIN) = {$}
follow(AUX_ELSE_STAT) = follow(ELSE_STAT) = {if, other, (, {, int, main,"}", )}
follow(KEYWORD) = (first(AUX_OTHER) - ε) U follow(AUX_OTHER) = {other, (, {, int, main, if,"}", )}

first(MAIN) = {int}
first(AUX_PROG) = {if, other, (, {, int, main, ε}
first(PROG) = {if, other, (, {, int, main, ε}
first(IF_STAT) = {if}
first(ELSE_STAT) = {else, ε}
first(AUX_ELSE_STAT) ={ "{", if }
first(AUX_OTHER) = {other, (, {, int, main, ε}
first(KEYWORD) = {int, main}

已尝试的无效调整 #

曾尝试移除<AUX_OTHER>的ε产生式，修改后规则如下，但分析表仍存在重复条目：

<AUX_OTHER> ::= other <AUX_PROG>
| ( <AUX_PROG> ) <AUX_PROG>
| { <AUX_PROG> } <AUX_PROG>
| <KEYWORD> <AUX_PROG>

冲突根因 #

• 存在二义性：经典悬空else问题未解决，原生if-else嵌套规则天然二义，LL(1)文法不允许二义性，必须显式约定else匹配最近未匹配的if，原有<AUX_ELSE_STAT>规则未落地该约定，导致Follow集交叉。
• 推导边界模糊：<AUX_PROG>的ε推导边界不清晰，其Follow集包含}、)，同时右部递归中<PROG>相关非终结符的First集也包含这两个终结符，导致同一终结符同时出现在<AUX_PROG> → <PROG> <AUX_PROG>和<AUX_PROG> → ε的Select集中，必然出现分析表冲突。
• 非终结符职责混乱：<AUX_OTHER>同时承担普通语句、表达式、括号块、关键字的解析职责，递归规则和ε规则的Select集大量重叠，即使移除ε产生式，也会因为和<AUX_PROG>的递归嵌套产生新的Select集冲突。

调整后的合规LL(1)文法 #

设计思路 #

1. 拆分语句为两类：闭合语句（所有if都有对应else匹配）和开放语句（存在未匹配else的if），从根源解决悬空else二义性，强制else匹配最近的未匹配if。
2. 重新划分非终结符职责，拆分语句序列、表达式、块语句的规则边界，避免ε推导的Select集和递归产生式的Select集重叠。
3. 消除隐式左递归、提取左公共因子，保证所有同名非终结符的不同产生式Select集互不相交。

最终文法规则 #

<MAIN> ::= int main () { <STMT_SEQ> }

// 语句序列：仅允许闭合语句开头，边界为块结束/右括号
<STMT_SEQ> ::= <MATCHED_STMT> <STMT_SEQ_TAIL>
<STMT_SEQ_TAIL> ::= <STMT_SEQ> | ε

// 闭合语句：所有if都绑定对应else，不会抢占后续else
<MATCHED_STMT> ::= if ( <EXPR> ) { <STMT_SEQ> } else <MATCHED_STMT>
                 | <BLOCK_STMT>
                 | <OTHER_STMT>
<BLOCK_STMT> ::= { <STMT_SEQ> }
<OTHER_STMT> ::= other <EXPR_TAIL>
               | <KEYWORD> <EXPR_TAIL>

// 开放语句：存在未匹配else的if，else优先归约到最近的开放if
<UNMATCHED_STMT> ::= if ( <EXPR> ) { <STMT_SEQ> }
                   | if ( <EXPR> ) { <STMT_SEQ> } else <UNMATCHED_STMT>

// 表达式规则：独立边界，不与语句序列规则混用
<EXPR> ::= <EXPR_ITEM> <EXPR_TAIL>
<EXPR_TAIL> ::= <EXPR> | ε
<EXPR_ITEM> ::= other
              | ( <EXPR> )
              | <KEYWORD>
<KEYWORD> ::= int | main

调整有效性说明 #

• 悬空else问题解决：通过闭合/开放语句的分层设计，显式实现了else就近匹配规则，文法无歧义。
• <AUX_PROG>（调整后为<STMT_SEQ>）的冲突解决：<STMT_SEQ>的First集为{if, other, {, int, main}，Follow集为{}, ), $，两个集合完全不相交；<STMT_SEQ> → <MATCHED_STMT> <STMT_SEQ_TAIL>的Select集等于First(MATCHED_STMT)，<STMT_SEQ_TAIL> → ε的Select集等于Follow集{}, )，不存在同一终结符对应多个产生式的问题。
• <AUX_OTHER>的冲突解决：原<AUX_OTHER>承担的表达式、普通语句职责被拆分到独立规则中，边界清晰，递归规则和ε规则的Select集无重叠。
• 经校验，所有非终结符的不同产生式Select集完全无交集，满足LL(1)文法要求，可正确解析IF、IF-ELSE、IF-ELSE IF-ELSE结构。

内容的提问来源于stack exchange，提问作者Luca