编程语言导论/语法制导翻译

语法制导翻译

一个编译器是一个将用一种编程语言编写的代码转换为用另一种编程语言编写的代码的程序。通常，编译器用于将用高级语言编写的代码转换为机器代码。与解释器类似，语法也提供了编译器完成其工作所使用的关键数据结构。例如，我们将实现一个非常简单的编译器，它将用我们自己的算术表达式语言编写的程序转换为波兰表达式。执行此工作的属性语法可以在下面看到

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.