程式語言導論/語法制導翻譯

語法制導翻譯

一個編譯器是一個將用一種程式語言編寫的程式碼轉換為用另一種程式語言編寫的程式碼的程式。通常，編譯器用於將用高階語言編寫的程式碼轉換為機器程式碼。與直譯器類似，語法也提供了編譯器完成其工作所使用的關鍵資料結構。例如，我們將實現一個非常簡單的編譯器，它將用我們自己的算術表示式語言編寫的程式轉換為波蘭表示式。執行此工作的屬性語法可以在下面看到

expr(L) --> mulexp(L1), [+], expr(L2), {append([+], L1, LX), append(LX, L2, L)}.
expr(L) --> mulexp(L).

mulexp(L) --> rootexp(L1), [*], mulexp(L2), {append([*], L1, LX), append(LX, L2, L)}.
mulexp(L) --> rootexp(L).

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

number([N]) --> digit(N).
number([ND|LL]) --> digit(ND), number(LL).

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}.

在這個例子中，我們將轉換後的程式轉儲到列表 L 中。append(L1, L2, LL) 謂詞在列表 LL 等於列表 L1 和 L2 的串聯時為真。符號 [ND|LL] 實現cons 操作，這在函數語言程式設計中很常見。換句話說，[ND|LL] 代表一個包含頭部元素 ND 和尾部 LL 的列表。作為使用示例，下面的執行部分展示了一組使用我們新語法的查詢，這次是在名為 compiler.pl 的檔案中實現的

?- consult(compiler).
true.

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

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