程式語言入門/邏輯語法
在本章中，我們將探討語法如何在實踐中被編譯器和直譯器使用。我們將使用 確定子句語法 (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}.