编译原理与实践流程设计-扩展BNF语法图

采用巴科斯范式（BNF）描述文法产生式使得文法表达形式严谨、简洁。此外，通过扩充BNF的符号增加其描述能力，可以实现不通过文法形式变换消除左递归的情况下，设计递归下降分析程序。扩展BNF是为了更紧密地映射递归下降分析程序的代码而设计的。

1.扩展BNF

重复和可选结构在程序设计语言中非常普遍，因此在文法规则中也是一样的。通过增加以下元符号对BNF进行扩展，得到的扩展BNF可以方便地表示重复和可选结构。

用{}描述重复

{α}表示符号串α出现零次或多次。例如，“字母开头的，字母和数字组成的标识符”可以表示为

＜标识符＞→＜字母＞{＜字母＞|＜数字＞}

此外，还可以通过上标表示符号串出现的最大次数，下标表示出现的最小次数。

符号串的重复形式是由文法规则中的递归产生式描述的。如下形式的左递归文法

A→x|y|·|z|Av

可以表示为

A→(x|y|·|z){v}

其中，（）表示串之间的拼接。（α|β）γ是对αγ|βγ的拼接符号串的简洁表示方法。

利用上述符号，使用扩展BNF描述算术表达式文法

E→T{+T}

T→F{*F}

F→(E)|i

{}中的内容可以直接映射为分析程序中的循环结构。用（）提取公共因子

如果候选式以相同的符号开头，则不知道应该选择哪个候选完成下一步的推导。（）可用于提取出一个非终结符多个产生式右部的公共因子。假设，非终结符A具有如下形式的产生式

A→xy|xw|·|xz(www.xing528.com)

则可以将其改写为

A→x(y|w|·|z)

用[]描述可选结构

特殊的，如果产生式具有形式为A→xy|x，提取出左因子后可得A→x（y|ε）。这种情况下，可用[]将产生式改写更加的简洁形式。

[α]表示符号串α出现1次或不出现。因此，A→x（y|ε）可改写为A→x[y]。例如，具有左公因子的if语句的文法

S→if B then S else S

|if B then S

利用[]可以提取出左公因子，而改写为

S→if B then S[else S]

2.语法图法

扩展BNF也可以采用语法图显式地进行设计。文法中的非终结符都将对应一张语法图。图中结点表示产生式右部的终结符或非终结符，非终结符表示调用与其对应的子过程，终结符表示匹配输入串中的相应符号。结点之间的连线具有方向，表明执行顺序。算术表达式的扩展BNF对应的语法图如图4-9所示。

图4-9　文法的状态转换图

根据状态转换图很容易写出递归的语法分析程序，程序编写方式如下。

（1）语法分析器由开始符号的语法图出发，输入指针指向输入符号串的第一个符号。

（2）依据箭头的指向设计程序的控制流程，如果遇到：

①标记为终结符的结点，则判断与输入符号是否匹配。如果匹配，移动输入指针指向下一个输入符号。

②标记为非终结符A的结点，语法分析器进入A的语法图，不移动输入指针。