上下文无关文法简介

形式语法

“语法”一词会让人联想到小学语文课，在那里我们学习了母语的语法规则。而形式语法（如我们此前所见）则是基于20世纪50年代的研究（尤其是诺姆·乔姆斯基的工作）对语言结构进行抽象化描述的一种尝试。一个形式语法包含以下组成部分：

• 非终结符（也称为变量），其中一个是起始符号。
• 终结符（即所用字母表中的“字母”，记作 $\Sigma$）。
• 一组重写规则（rewrite rules），从起始变量开始，通过逐步替换变量，最终得到仅由终结符组成的语言中的字符串。

这些重写规则也被称为产生式规则，或简称为产生式。考虑下面这个简单的语法，它可以生成随机句子：

\begin{align*} \langle sentence\rangle & \rightarrow \langle noun\text{-}phrase:\rangle \langle verb\text{-}phrase\rangle \ \langle noun\text{-}phrase\rangle & \rightarrow the: \langle noun\rangle \ \langle verb\text{-}phrase\rangle & \rightarrow \langle verb\rangle : \langle noun\text{-}phrase\rangle \ \langle verb\rangle & \rightarrow moves ;|; annoys ;|; deserves \ \langle noun\rangle & \rightarrow student ;|; cow ;|; vegetable ;|; worm ;|; pot \end{align*}

通常情况下，我们在语法中使用单个大写字母表示变量。当变量由多个字母组成时，我们会将其置于尖括号中，以便与终结符字符串区分开来。以下推导过程生成了句子 "The cow annoys the student"：

\begin{align*} \langle sentence\rangle & \Rightarrow \langle noun\text{-}phrase\rangle : \langle verb\text{-}phrase\rangle \ & \Rightarrow the : \langle noun\rangle : \langle verb\text{-}phrase\rangle \ & \Rightarrow the :cow : : \langle verb\text{-}phrase\rangle \ & \Rightarrow the :cow : \langle verb\rangle : \langle noun phrase\rangle \ & \Rightarrow the :cow : :annoys : \langle noun phrase\rangle \ & \Rightarrow the :cow :annoys :the : \langle noun\rangle \ & \Rightarrow the :cow :annoys :the :student \end{align*}

推导过程中的每一步都称为一个句型（sentential form）。语法只规定句子的结构（即句法），而不涉及其含义（即语义），因此可能生成无意义的句子，例如：“The vegetable deserves the student”（蔬菜配得上学生）。

上述语法规则的每一项左边都仅包含一个非终结符。这种语法被称为上下文无关文法（context-free），因为无论非终结符出现在何种上下文中，都可以用其对应的任意右侧字符串进行替换。

在推导过程中，通常每次只替换一个变量，并且优先替换最左边的变量，这样的推导方式称为最左推导（leftmost derivation）。

生成随机句子

以下 Python 程序使用该语法生成五个随机句子。注意观察每个产生式规则是如何通过独立函数实现的：

1import random
2
3def sentence():
4    return noun_phrase() + ' ' + verb_phrase()
5def noun_phrase():
6    return 'the ' + noun()
7def verb_phrase():
8    return verb() + ' ' + noun_phrase()
9def verb():
10    return random.choice(['moves', 'annoys', 'deserves'])
11def noun():
12    return random.choice(['student', 'cow', 'vegetable', 'worm', 'pot'])
13
14print("Sample output:")
15
16for i in range(5):
17    print(sentence())

代码说明

以下是上述代码的逐行解析：

• 第1行：导入内置的 random 模块，用于生成随机数以及从列表中随机选择元素。
• 第3行：定义名为 sentence 的函数。
• 第4行：定义 sentence 函数的函数体，返回一个名词短语、一个空格和一个动词短语拼接后的结果。调用 noun_phrase 和 verb_phrase 函数来生成句子的相应部分。
• 第5行：定义名为 noun_phrase 的函数。
• 第6行：定义 noun_phrase 函数的函数体，返回字符串 "the" 与一个随机名词拼接的结果。通过调用 noun 函数生成该名词。
• 第7行：定义名为 verb_phrase 的函数。
• 第8行：定义 verb_phrase 函数的函数体，返回一个动词、一个空格和一个名词短语拼接的结果。调用 verb 和 noun_phrase 函数生成动词短语的各部分。
• 第9行：定义名为 verb 的函数。
• 第10行：定义 verb 函数的函数体，从列表 ['moves', 'annoys', 'deserves'] 中随机选择一个动词并返回。使用 random.choice 函数实现随机选取。
• 第11行：定义名为 noun 的函数。
• 第12行：定义 noun 函数的函数体，从列表 ['student', 'cow', 'vegetable', 'worm', 'pot'] 中随机选择一个名词并返回。同样使用 random.choice 函数进行随机选择。
• 第14行：打印字符串 "Sample Output:"。
• 第16行：开始一个 for 循环，循环5次，用于生成五个随机句子。
• 第17行：调用 sentence 函数生成一个句子，并打印结果。

该程序的输出为五条随机生成的句子，格式为 “the <名词> <动词> the <名词>”。