编程语言入门/逻辑语法
在本章中，我们将探讨语法如何在实践中被编译器和解释器使用。我们将使用 确定子句语法 (DCG)，这是 Prolog 编程语言的一个特性，来演示我们的例子。从现在开始，我们将 DCG 称为 *逻辑语法*。Prolog 非常擅长语法。正如我们将在本章中看到的那样，这种编程语言提供了许多帮助开发人员解析和处理语言的抽象。
Prolog 为开发人员提供了一种特殊的语法来实现语法。这种表示法与我们之前见过的 BNF 形式非常相似。例如，上一章中的英语语法可以用 Prolog 重新编写如下
sentence --> noun_phrase, verb_phrase . noun_phrase --> determiner, noun . noun_phrase --> determiner, noun, prepositional_phrase . verb_phrase --> verb . verb_phrase --> verb, noun_phrase . verb_phrase --> verb, noun_phrase, prepositional_phrase . prepositional_phrase --> preposition, noun_phrase . noun --> [student] ; [professor] ; [book] ; [university] ; [lesson] ; [programming language] ; [glasses]. determiner --> [a] ; [the] . verb --> [taught] ; [learned] ; [read] ; [studied] ; [saw]. preposition --> [by] ; [with] ; [about] .
如果我们复制上面的文本，并将其保存到一个文件中，例如 grammar.pl，那么我们就可以解析句子。下面，我们给出了一个典型的 Prolog Swipl 解释器部分的屏幕截图，展示了如何使用语法。请注意，查询包含一个非终结符，例如 sentence，一个包含要解析的句子的列表，以及一个空列表。我们不会在这本书中解释这种看似神秘的语法，但感兴趣的读者可以在 在线 找到更多信息。
1 ?- consult(grammar). 2 % ex1 compiled 0.00 sec, 0 bytes 3 true. 4 5 ?- sentence([the, professor, saw, the, student], []). 6 true ; 7 false. 8 9 ?- sentence([the, professor, saw, the, student, with, the, glasses], []). 10 true ; 11 true ; 12 false. 13 14 ?- sentence([the, professor, saw, the, bird], []). 15 false.
每次 Prolog 为句子找到一个推导树时，它都会输出查询的值 true。如果同一个句子有多个推导树，那么它会对所有推导树都成功。在上面的例子中，我们得到了句子“教授带着眼镜看到了学生”的两个肯定答案，正如我们在上一章中看到的，它有两个不同的解析树。如果 Prolog 无法为句子找到解析树，那么它将输出值 false。这发生在上面例子的第 15 行。它也发生在第 7 行和第 12 行。Prolog 会尝试找到解析句子的所有可能方法。如果它无法找到，即使在找到了一些成功的推导之后，它也会向用户返回 false。
可以将属性嵌入到逻辑语法中。这样，我们可以使用 Prolog 来构建 属性语法。我们可以将属性用于许多不同的目的。例如，下面我们修改了英语语法，以计算一个句子中的单词数。一些非终结符现在与一个属性 W 相关联，这是一个整数，表示从该非终结符推导出的单词数。在编译器行话中，我们说 W 是一个 合成属性，因为它是在从子节点获取的属性的函数基础上构建的。
sentence(W) --> noun_phrase(W1), verb_phrase(W2), {W is W1 + W2} .
noun_phrase(2) --> determiner, noun .
noun_phrase(W) --> determiner, noun, prepositional_phrase(W1), {W is W1 + 1} .
verb_phrase(1) --> verb .
verb_phrase(W) --> verb, noun_phrase(W1), {W is W1 + 1} .
verb_phrase(W) --> verb, noun_phrase(W1), prepositional_phrase(W2), {W is W1 + W2} .
prepositional_phrase(W) --> preposition, noun_phrase(W1), {W is W1 + 1} .
noun --> [student] ; [professor] ; [book] ; [university] ; [lesson] ; [glasses].
determiner --> [a] ; [the] .
verb --> [taught] ; [learned] ; [saw] ; [studied] .
preposition --> [by] ; [with] ; [about] .
使用属性语法的查询必须有一个参数，该参数将被 Prolog 执行环境为属性找到的最终值替换。下面我们有一个 Prolog 部分，其中包含三个不同的查询。歧义仍然会导致我们在第二个查询中得到两个答案。
?- consult(grammar). % ex1 compiled 0.00 sec, 0 bytes true. ?- sentence(W, [the, professor, saw, the, student], []). W = 5 ; false. ?- sentence(W, [the, professor, saw, the, student, with, the, glasses], []). W = 7 ; W = 7 ; false. ?- sentence(W, [the, professor, saw, the, bird], []). false.
属性可以提高语法的计算能力。例如，上下文无关语法无法识别具有相同数量的 a、b 和 c 的字符串的句子 a^nb^nc^n。我们说这种语言不是 上下文无关的。但是，属性语法可以轻松地解析这种语言。
abc --> as(N), bs(N), cs(N).
as(0) --> [].
as(M) --> [a], as(N), {M is N + 1}.
bs(0) --> [].
bs(M) --> [b], bs(N), {M is N + 1}.
cs(0) --> [].
cs(M) --> [c], cs(N), {M is N + 1}.