使用Prolog进行前缀解析

Question

所以我有这个语法：

  expr(op(T,B,E)) => [term(T), binop(B), expr(E)].
  expr(T) => [term(T)].

  term(N) => [num(N)].
  term(L) => [lvalue(L)].
  term(pre(O,L)) => [incrop(O), lvalue(L)].
  term(post(L,O)) => [lvalue(L), incrop(O)].
  term(E) => ['(', expr(E), ')'].

  lvalue($(E)) => [$, expr(E)].

  incrop(++) => [++].
  incrop(--) => [--].

  binop(+) => [+].
  binop(-) => [-].

  num(0) => [0].
  num(1) => [1].
  num(2) => [2].
  num(3) => [3].
  num(4) => [4].
  num(5) => [5].
  num(6) => [6].
  num(7) => [7].
  num(8) => [8].
  num(9) => [9].

目标是根据规则解析输入，并分离出剩余的后缀。例如，

| ?- parse_prefix(expr(E), [$,1,+,2], S).

E = op($(1),+,2)
S = [] ? ;

E = $(op(1,+,2))
S = [] ? ;

E = $(1)
S = [+,2] ? ;

no

和

| ?- parse_prefix(expr(E), [9], S).

E = 9
S = [] ? ;

no


| ?- parse_prefix(expr(E), [9,+,$,1,+], S).

E = op(9,+,$(1))
S = [+] ? ;

E = 9
S = [+,$,1,+] ? ;

我写了以下谓词：

%Base Case: No Token, No Suffix
parse_prefix(_,[],[]).

%Direct Matching: ex) parse_prefix(num(9),[9],S)
parse_prefix(NT,[Head|Tail],S):-
    NT =>[Head],
    write('two '),
    parse_prefix(expr(E),Tail,S).
%General Matching: ex) parse_prefix(expr(E),_,S)
parse_prefix(NT,[Head|Tail],S):-
    NT => [Head1|Tail1],
    %write(Head1),
    %write('one\n'),
    parse_prefix(Head1,[Head|Tail],S).

我对递归和回溯有很多困惑..

我将永远爱任何能帮助我的人。

提前谢谢您。

Answer 1

您已经接近解决方案了。最好定义您自己的运算符 =>/2 来表示您自己的 gammar 规则，并且不会与 -->/2 发生冲突。但我在语法规则体的表示方面遇到问题。我没有看到您在语法规则主体中区分终结符和非终结符。

一个建议是投票支持 (A1,...,An) 来代表主体中的连词，而不是 [A1,..,An]。然后使用 [T] 表示终结符，NT 表示非终结符。所以以下规则，

term(E) => ['(', expr(E), ')'].

然后会读到：

term(E) => ['('], expr(E), [')'].

然后您可以调整规则并定义 parse_prefix/3 ，如下所示。我向您展示终结符、合取符和非终结符情况：

parse_prefix([T],I,O) :- !, I=[T|O].
parse_prefix((A,B),I,O) :- !, parse_prefix(A,I,H), parse_prefix(B,H,O).
parse_prefix(NT,I,O) :- (NT => Body), parse_prefix(Body,I,O).

您可以为空产生式 ([]) 和辅助条件 ({}) 添加其他情况，或者使其更加灵活，以便能够使用终端列表 ([T1,..,Tn])。进一步的控制结构也是可能的，但是当你尝试进行剪切（！）时，遵循元解释器方法，事情会变得有点令人讨厌。

除了编写元解释器 parse_prefix/3 之外，您还可以编写自己的术语重写，最终得到一种方法，该方法首先将给定的 gammar 规则转换为普通的 Prolog，然后从那里执行它们。