LL（1）文法 ：解决 if-else/if-else 产生式二义性问题

注：本文适合对编译感兴趣的朋友阅读。

最近尝试用LL（1）文法构造 类似C语言结构的产生式。在构造 if/else 语句时，发现语法存在二义性（Statement、Expression部分省略 ）：

Statement-> if ( Expression ) IfBlock

IfBlock-> Statement ElseBlock

ElseBlock-> else Statement |∑

 

算法分析结果指出：ElseBlock的首符集和随符集 同时出现 else 助记符；

结果一出，我顿时发懵，努力去修改产生式去消除 二义性，但是尝试2、3天后无果。于是在网上的一篇帖子中发现：这是if-else固有的二义属性；同时指出具体解决方法参考紫龙书 例4.33：

 

 

解决方法：

产生式采用：

Statement-> if (Expression) IfBlock

ifBlock-> Statement ElseBlock

ElseBlock-> else Statment

我使用了一种捷径：在词法分析阶段，对Tokens序列进行检查。若if 分支后未监测到else，则在适当位置插入一个‘else；’序列，此阶段后在进行常规编译；

优点：既实现了if-else的灵活组合，又降低编译器的实现难度（不存在二义性问题）。

 

自研产品介绍：Plang高级编程语言