布尔表达式的文法与代码结构在编译原理中属于**中间代码生成**阶段的重要内容

布尔表达式的文法与代码结构在编译原理中属于中间代码生成阶段的重要内容，主要用于将高级语言中的逻辑判断（如if、while中的条件）转换为带有控制流信息的中间表示（如四元式），并利用“短路求值”机制优化执行效率。

一、布尔表达式的上下文无关文法（CFG）

常见的布尔表达式文法可定义如下（经过左递归消除以适用于自顶向下分析）：

E → E1 or T { E.tc = Merge(E1.tc, T.tc); E.fc = T.fc; } | T { E.tc = T.tc; E.fc = T.fc; } T → T1 and F { T.tc = F.tc; T.fc = Merge(T1.fc, F.fc); } | F { T.tc = F.tc; T.fc = F.fc; } F → not F1 { F.tc = F1.fc; F.fc = F1.tc; } | ( E ) { F.tc = E.tc; F.fc = E.fc; } | rel { F.tc = NewLabel(); F.fc = NewLabel(); Gen('if', rel.op, 'goto', F.tc); Gen('goto', '', '', F.fc); }

其中：

• rel表示关系表达式（如a < b）
• tc：真出口（true chain），当表达式为真时跳转的目标标签链
• fc：假出口（false chain），当表达式为假时跳转的目标标签链
• NewLabel()：生成新的标签
• Gen(op, arg1, arg2, result)：生成一条四元式
• Merge(c1, c2)：合并两个出口链，返回合并后的链头
• Backpatch(chain, label)：将链中所有待填地址回填为label

二、关键概念解析

1.短路计算（Short-Circuit Evaluation）

• A and B：若 A 为假，则不计算 B
• A or B：若 A 为真，则不计算 B
• 编译时通过控制流跳转实现，无需实际求值

2.真出口（tc）与假出口（fc）

每个非终结符（如 E、T、F）携带两个属性：

• tc：指向“应跳往真分支”的标签链（即该子表达式为真时需跳转的位置）
• fc：指向“应跳往假分支”的标签链

这些不是立即确定的地址，而是待回填的跳转链表（拉链法）

3.拉链与回填技术

• 拉链（Chaining）：将尚未确定目标地址的跳转指令组织成链（通过链接字段指向下一条待填指令编号）
• 回填（Backpatch）：当目标地址确定后，遍历链中所有指令并填写正确地址

例如：

defBackpatch(chain,label):whilechain:instruction[chain.index].target=label chain=chain.next

三、翻译示例：E → E¹ and E²

语义动作：

E.tc=E².tc E.fc=Merge(E¹.fc,E².fc)Backpatch(E¹.tc,E².begin_label)# 若E¹为真，继续计算E²

说明：

• 只有当E¹为真时才需要评估E²
• 所以要把E¹的真出口（tc）回填到E²的起始位置
• E整体为真的出口是E²为真的出口
• E整体为假的出口是E¹或E²为假的出口合并而成

四、常见语句的翻译

1.if (B) S1

• B.true_chain回填到S1起始
• B.false_chain是整个if结束后的出口
• 无 else 时，直接回填B.fc到next_instruction

2.if (B) S1 else S2

• B.tc→S1.begin
• B.fc→S2.begin
• S1.chain和S2.chain合并为后续语句入口

3.while (B) S

• 生成循环开始标签L1
• B的tc指向S.begin
• B的fc指向循环结束L2
• S.chain回填到L1实现循环
• 使用Gen('goto', '', '', L1)在S后跳回

五、四元式示例（基于GEN函数）

假设表达式：(a < b) or (c > d)

生成的四元式可能如下：

100: if a < b goto 102 101: goto 103 102: goto 105 ; // 真出口直接跳过整个or的假分支 103: if c > d goto 105 104: goto 106 105: ... ; // 真出口汇聚点 106: ... ; // 假出口

注意：实际中使用链式管理，避免立即指定具体标号。