VisFormalLang 形式语言可视化

第 6 章 上下文无关文法与语言

| 关于   英文版   «  5.2. 性质   ::   目录   ::   6.2. 文法转换  »

6.1. 上下文无关语言

6.1.1. 上下文无关语言

在前几章中，我们看到有些语言是正则语言，这意味着我们可以为它们定义 DFA、NFA、正则表达式或正则文法。

正则语言的例子：

  • 编程语言中的关键字

  • 标识符的名字

  • 整数

  • 一列有限的杂项符号：= ;

然后我们学习了泵引理，它是用来证明某个语言不是正则的工具。

非正则语言的例子：

  • 表达式：\(((a + b) - c)\)

  • 块结构（Java/C++ 中的 \(\{\}\) 以及 Pascal 中的 begin... end ）

我们知道并非所有语言都是正则的，因为我们已经证明了其中一些不是正则的。现在我们将研究一类比正则语言更大、也更强大的语言：上下文无关语言。

定义： 如果文法 \(G = (V, T, S, P)\) 的所有产生式都具有形式

\(A \rightarrow x\)
其中 \(A \in V\)，\(x \in (V \cup T)^*\)。
（\(T\) 包含 \(\lambda\)。）

定义: \(L\) 是一个上下文无关语言（CFL），当且仅当存在一个上下文无关文法（CFG） \(G\) 使得 \(L = L(G)\) 。

上面关于文法的定义与我们自本书第一章以来一直使用的定义完全相同。这意味着我们使用过的所有文法（包括正则文法）都是上下文无关文法。

定义： 线性文法（linear grammar）的任何产生式右侧至多有一个变元。因此，右线性文法和左线性文法也都是线性文法。

所以，这是一个线性文法。

定义： 字符串推导（derivation）就是从文法的起点开始，不断地做替换，直到不能再做任何替换为止。文法中的一个变元可以被替换成它所在规则右侧的内容。

通过前面的例子可以看到，有些句型含有多个变元，这就引出一个问题：应该替换哪个变元？为了写出执行替换的算法，我们需要某种顺序。我们在后面学习分析算法时会看到这一点。

定义： 最左推导（leftmost derivation）：在推导的每一步，替换最左边的变元。（见上面的推导 1。）

定义： 最右推导（rightmost derivation）：在推导的每一步，替换最右边的变元。（见上面的推导 2。）

推导树（derivation tree） （也称为"语法分析树（parse tree）"）：推导树表示一次推导，但不展示各个产生式被应用的顺序。

让我们看看前面的那棵语法分析树是如何构建出来的。

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

定义： 部分推导树 —— 推导树的子树。

如果一棵部分推导树的根是 \(S\)，那么它就表示一个句型。

推导树中从左到右的叶子构成这棵树的 结果（yield） 。

如果 \(w\) 是某棵推导树的结果，那么必然有 \(w \in L(G)\)。

上面那个例子的结果是 \(aacbb\)。

成员资格 ：给定 CFG \(G\) 和字符串 \(w \in \Sigma^*\) ，是否为 \(w \in L(G)\) ？

如果我们能找到 \(w\) 的一个推导，那么我们就能知道 \(w\) 在 \(L(G)\) 中。

为什么会有人想这样做？考虑这样一种情况：\(G\) 是 Java 的文法，而 \(w\) 是一个 Java 程序。 \(w\) 是一个语法正确的程序吗？这正是编译器所做工作的一部分。你写一个程序，然后编译它，编译器会找出你所有的语法错误。（它还会把程序"翻译"成"字节码"以便执行。在本课程中我们不会过多谈论编译器的这方面。）

穷举搜索算法

如果你在 OpenFLAP 中运行这个算法，它会花很长时间，但最终会接受。问题在于这种方法相当低效，因为它对从起始符号出发的所有展开方式做了穷举搜索。

对所有 \(i = 1, 2, 3, \ldots\)
检查由 \(i\) 次替换产生的所有句型

问题：如果 \(w\) 不在 \(L(G)\) 中会怎样？算法中的循环什么时候停止，我们才能确定 \(w\) 永远不可能被推导出来？ \(S \Rightarrow SS \Rightarrow ... \Rightarrow SSSSSSSSSS \Rightarrow ...\) 这个过程无法确定 \(baaba\) 不是 \(L(G)\) 中的字符串。

我们希望考虑一些特殊形式的上下文无关文法，以便能够确定一个字符串到底在不在语言中。事实证明，把一个上下文无关文法转换成一种特殊形式是很容易的，这种形式使成员测试变得更容易。

下一章，我们将学习如何把一个文法转换成等价（或几乎等价）的文法。我们会看到，在能否写出求解成员问题的实用算法方面，为某个语言编写文法的某些方式会优于其他方式。现在，这里给出另一种能让成员测试更容易的形式。

定义： 简单文法（simple grammar，或 s-grammar）的所有产生式都具有形式：

\(A \rightarrow ax\)

其中 \(A \in V\)，\(a \in T\)，\(x \in V^*\)，并且任何一对 \((A, a)\) 至多可以出现在一条规则中。

如果你用穷举搜索法来判断 \(w \in L(G)\) 是否成立，其中 \(G\) 是一个 s-文法，那么每次推导后终结符的数量都会增加。

6.1.2. 二义性

定义 ：一个 CFG \(G\) 是模棱两可的，如果 \(\exists\) 有些 \(w \in L(G)\) ，它们具有两个不同的派生树。

定义： 如果 \(L\) 是 CFL，并且存在无二义的（unambiguous）CFG \(G\) 使得 \(L = L(G)\)，那么 \(L\) 是无二义的。

备注

我们为什么要研究 CFL？因为我们想要能够表示语法正确的程序。

本模块的复习题集包含四道复习题，前三道都指向同一个文法。第一道题是关于确定给定串在给定文法中有多少棵语法分析树。

6.1.2.1. 二义文法（2）

这道题同样是关于确定给定串在给定文法中有多少棵语法分析树。

6.1.2.2. 二义文法（3）

这道题再次是关于确定给定串在给定文法中有多少棵语法分析树。

6.1.2.3. 二义文法（4）

这道题将帮助你发现文法中的二义性，并让自己确信某个文法不是二义的。

6.1.3. 消除文法二义性

一般来说，消除文法的二义性并没有通用的万灵药。不过，针对手头的具体文法，有一些技巧可以帮助消除二义性。这些常用技巧是：

  • 运算符优先级

  • 运算符结合性

  • 从头重写文法

6.1.3.1. 优先级

看一下文法 前面的文法 ，我们会注意到表达式 2+4*2 有两种不同的结果。差异来自我们先对哪个运算符求值。在第一棵树中，我们可以看到乘法符号位于树中更深的位置。所以我们必须先于加法对它求值，这就使乘法具有比加法更高的优先级。在另一棵推导树中，加法比乘法更深，在这种情况下，我们赋予了加法比乘法更高的优先级。所以，要消除该文法的二义性，我们需要为算术运算确保正确的优先级规则。换句话说，我们需要确保总是先对乘法求值。

这道题展示了文法结构如何影响算术表达式的求值，从而影响程序的语义。注意， 要在这道题上拿分， 你必须连续三次正确作答，因为这道题是随机出题的。当你答对一次之后， Check Answer （检查答案）按钮才会允许你进入这道题的下一实例。

现在让我们尝试消除文法 前面的文法 的二义性。

让我们看看前面的那棵语法分析树是如何构建出来的。

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

6.1.3.2. 结合性

6.1.3.3. 优先级与结合性

这道题展示了文法结构如何影响算术运算符的结合性以及优先级顺序。

文法的 巴科斯-瑙尔范式（Backus-Naur Form，BNF） ：

非终结符括在尖括号 \(<>\) 中
用 "\(::=\)" 代替 "\(\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 文法所生成的语言的特征。完成之后，还有一道关于扩展巴科斯-瑙尔范式（Extended Backus-Naur Form）的题目，其内容已经在这道题之前介绍。

6.1.4. 扩展 BNF

我们在表示文法时使用的这些符号共同构成了所谓的 巴科斯-瑙尔范式 （BNF）。在 扩展巴科斯-瑙尔范式 （EBNF）中，我们在 BNF 记法已经使用的符号之外又增加了五个元符号：

  1. 克莱尼闭包运算符 \(*\)，表示"零个或多个"。因此，如果 \(<fn\_name>\) 是表示合法函数名的非终结符，\(<argument>\) 是表示合法参数的非终结符，那么具有零个或多个参数（参数之间没有逗号）的函数调用的 EBNF 记法将是

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

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

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

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

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

  1. "可选用法运算符" \(?\)，它规定位于运算符之前的任何文法结构可以有零个或一个。例如，如果我们的语言允许数字前面有一个可选的加号或减号，我们就会使用 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)\)。

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

declare: int Sum(int a, int b, int c) ...
call: newsum = Sum(x,y);

   «  5.2. 性质   ::   目录   ::   6.2. 文法转换  »

© Copyright 2011-2025 by OpenDSA Project Contributors and distributed under an MIT license. 最后更新于 10月 25, 2026. Created using Sphinx 8.2.0.
关闭窗口