3. 编写编译器¶

编程语言定义的一部分是它的文法。任何编程语言的定义都必须是无歧义的，这一点至关重要，否则两个不同的编译器可以“正确”地编译并执行同一个程序，却给出两种不同的结果。如果我们的程序仅仅因为用不同的编译器编译就表现不同，那就太糟糕了！

传统上，语言的定义是部分（虽然不是全部）用文法给出的。当然，定义的各个方面都必须是无歧义的。有时，两个编译器对同一个程序会给出不同的结果，原因很简单：其中之一有 bug。但有时问题恰恰在于语言定义本身存在二义性。我们已经看到，二义性的一个可能来源就是作为定义一部分的文法。

3.1. 巴科斯-诺尔范式¶

传统上，编译器编写者会尽可能用文法来定义语言。这是因为有一些非常好的工具，可以利用文法自动构建语言的解析器以及部分代码生成器，这节省了大量的编程工作，并消除了一类 bug 的来源（编程中的人工错误）。

巴科斯-诺尔范式（Backus-Naur Form，BNF）是书写上下文无关文法时常用的一种记法。它自 1950 年代末和 1960 年代初就存在，当时它首次被用于早期编程语言 ALGOL 的文法定义中。

文法的巴科斯-诺尔范式：

非终结符用尖括号 \(<>\) 括起来

用 "\(::=\)" 代替 "\(\rightarrow\)"

C++ 程序示例：:

main () {
  int a;     int b;   int sum;
  a = 40;    b = 6;   sum = a + b;
  cout << "sum is "<< sum << endl;
}

用 BNF 为 C++“尝试”写一个 CFG （注：\(<\mbox{program}>\) 是文法的起始符号。）

\[\begin{split}\begin{eqnarray*} <\mbox{program}> &::=& \mbox{main} ()\ <\mbox{block}>\\ <\mbox{block}> &::=& \{\ <\mbox{stmt-list}>\ \}\\ <\mbox{stmt-list}> &::=& <\mbox{stmt}>\ |\ <\mbox{stmt}>\ <\mbox{stmt-list}>\ |\ <\mbox{decl}>\ |\ <\mbox{decl}> <\mbox{stmt-list}> \\ <\mbox{decl}> &::=& \mbox{int}\ <\mbox{id}>\ ;\ |\ \mbox{double}\ <\mbox{id}>\ ; \\ <\mbox{stmt}> &::=& <\mbox{asgn-stmt}>\ |\ <\mbox{cout-stmt}>\\ <\mbox{asgn-stmt}> &::=& <\mbox{id}>\ =\ <\mbox{expr}>\ ;\\ <\mbox{expr}> &::=& <\mbox{expr}>\ +\ <\mbox{expr}>\ |\ <\mbox{expr}>\ *\ <\mbox{expr}>\ |\ (\ <\mbox{expr}>\ )\ |\ <\mbox{id}>\\ <\mbox{cout-stmt}> &::=& \mbox{cout}\ <\mbox{out-list}>\\ \end{eqnarray*}\end{split}\]

等等，必须展开所有非终结符！

所以程序 test 的一个推导看起来像这样：

\[\begin{split}<\mbox{program}> &\Rightarrow&\ \mbox{main} ()\ <\mbox{block}> \\ &\Rightarrow&\ \mbox{main} ()\ \{\ <\mbox{stmt-list}>\ \} \\ &\Rightarrow&\ \mbox{main} ()\ \{\ <\mbox{decl}>\ <\mbox{stmt-list}>\ \} \\ &\Rightarrow&\ \mbox{main} ()\ \{\ \mbox{int}\ <\mbox{id}>\ <\mbox{stmt-list}>\ \} \\ &\Rightarrow&\ \mbox{main} ()\ \{\ \mbox{int}\ \mbox{a}\ <\mbox{stmt-list}>\ \} \\ &\stackrel{*}{\Rightarrow}&\ \mbox{complete C++ program}\end{split}\]

这道题要求你提供一个由 BNF 文法所生成语言的特征描述。完成这道题后，还有一道关于扩展巴科斯-诺尔范式的题目，相关说明位于题目之前。

3.2. 扩展 BNF¶

我们在文法表示中使用的符号合起来构成了所谓的巴科斯-诺尔范式（BNF）。在扩展巴科斯-诺尔范式（EBNF）中，我们在 BNF 记法已经使用的符号基础上增加了五个元符号：

Kleene 闭包运算符 \(*\)，意思是“零个或多个”。因此，如果 \(<fn\_name>\) 是表示合法函数名的非终结符， \(<argument>\) 是表示合法实参的非终结符，那么对于带零个或多个参数（参数之间没有逗号）的函数调用， EBNF 记法将是

\[<fn\_name> "(" <argument>* ")"\]

正闭包运算符 \(+\)。对于必须至少有一个实参的函数调用，EBNF 记法是

\[<fn\_name> "(" <argument>+ ")"\]

两个配对的圆括号符号 \(( \; )\)，用于分组。例如，如果 \(<positive\_number>\) 是表示合法的正数的非终结符，那么下面的 EBNF 将规定数字前面必须有加号或减号

\[(+ | -) <positive\_number>\]

“可选运算符” \(?\)，它规定运算符之前的任何一种文法结构都可以出现零次或一次。例如，如果我们的语言允许数字前面有可选的加号或减号，我们就会使用如下 EBNF：

\[(+ | -)? <positive\_number>\]

EBNF 用于减少一个文法描述语言所需的产生式数量。然而，它并不会增加文法的表达能力，也就是说，任何可以用 EBNF 表达的文法结构，只要愿意使用更多的产生式，也同样可以用 BNF 表达。

这最后一道题是关于给定的 BNF 文法（与上面第 4 部分中的是同一个）与一个更小的 EBNF 文法之间的等价性。

关于 C++ 的 CFG 的更多内容

上一次我们“尝试”为 C++ 写一个 CFG。写一个能识别所有语法上正确的 C++ 程序的 CFG 是可能的，但问题是这个 CFG 也会接受不正确的程序。例如，它无法识别出同一个变量声明两次（一次声明为整数，一次声明为字符）是一个错误。

我们可以写一个 CFG \(G\)，使得 \(L(G) = \{ \mbox{syntactically correct C++ programs} \}\)。

但请注意 \(\{ \mbox{semantically correct C++ programs} \} \subset L(G)\)。

另一个例子：无法识别形参（formal parameters）与实参（actual parameters）在数量和类型上是否匹配：

declare: int Sum(int a, int b, int c) ...

call: newsum = Sum(x,y);

CS4114 形式语言与自动机

Chapter 6 Context-Free Grammars and Languages

3. 编写编译器¶

3.1. 巴科斯-诺尔范式¶

3.2. 扩展 BNF¶