程式語言導論/語法制導解釋

語法制導解釋

一個直譯器是一個程式，它模擬用特定程式語言編寫的程式的執行。有很多方法可以實現直譯器，但典型實現依賴於解析樹作為核心資料結構。在這種情況下，直譯器是一個訪問者，它遍歷程式的推導樹，模擬此樹中每個節點的語義。例如，我們將為算術表示式的語言構建一個直譯器，其邏輯語法如下

expr --> mulexp, [+], expr.
expr --> mulexp.

mulexp --> rootexp, [*], mulexp.
mulexp --> rootexp.

rootexp --> ['('], expr, [')'].
rootexp --> number.

number --> digit.
number --> digit, number.

digit --> [0] ; [1] ; [2] ; [3] ; [4] ; [5] ; [6] ; [7] ; [8] ; [9].

這種簡單程式語言中的任何程式最終都是一個數字。也就是說，我們可以將用這種語言編寫的程式的含義歸結為該程式所代表的數字。因此，解釋程式等同於找到該程式所表示的數字。下面的屬性語法實現了這樣的直譯器

expr(N) --> mulexp(N1), [+], expr(N2), {N is N1 + N2}.
expr(N) --> mulexp(N).

mulexp(N) --> rootexp(N1), [*], mulexp(N2), {N is N1 * N2}.
mulexp(N) --> rootexp(N).

rootexp(N) --> ['('], expr(N), [')'].
rootexp(N) --> number(N, _).

number(N, 1) --> digit(N).
number(N, C) --> digit(ND), number(NN, C1), {
  C is C1 * 10,
  N is ND * C + NN
}.

digit(N) --> [0], {N is 0}
           ; [1], {N is 1}
           ; [2], {N is 2}
           ; [3], {N is 3}
           ; [4], {N is 4}
           ; [5], {N is 5}
           ; [6], {N is 6}
           ; [7], {N is 7}
           ; [8], {N is 8}
           ; [9], {N is 9}.

注意，我們可以在推導樹的每個節點上使用多個屬性。例如，節點number有兩個屬性，我們用它們來計算數字序列的值。下面是一些我們可以用這種語言發出的查詢示例，假設我們已將語法儲存在名為interpreter.pl的檔案中

?- consult(interpreter).
% num2 compiled 0.00 sec, 4,340 bytes
true.

?- expr(N, [2, *, 1, 2, 3, +, 3, 2, 1], []).
N = 567 ;
false.

?- expr(N, [2, *, '(', 1, 2, 3, +, 3, 2, 1, ')'], []).
N = 888 ;
false.