编程语言导论/语法制导解释

语法制导解释

一个解释器是一个程序，它模拟用特定编程语言编写的程序的执行。有很多方法可以实现解释器，但典型实现依赖于解析树作为核心数据结构。在这种情况下，解释器是一个访问者，它遍历程序的推导树，模拟此树中每个节点的语义。例如，我们将为算术表达式的语言构建一个解释器，其逻辑语法如下

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.