能够读取命题逻辑表达式的DCG

Question

正如我在标题中所说，我正在尝试做一个练习，我需要编写一个能够读取命题逻辑的 DCG，命题逻辑由小写字母、运算符（not、and 和 or)，标记由空格分隔。所以表达式：

a or not b and c

被解析为

a or ( not b and c )

生成如下所示的解析树：

or(
  a,
  and(
    not(b),
    c
  )
)

老实说，我一直很难理解如何有效地使用 DCG，但这就是我目前所知道的：

bexpr([T]) --> [T].
bexpr(not,R1) --> oper(not), bexpr(R1).
bexpr(R1,or,R2) --> bexpr(R1),oper(or), bexpr(R2).
bexpr(R1, and ,R2) --> bexpr(R1),oper(and), bexpr(R2).
oper(X) --> X.

对于练习本身或如何更好地理解 DCG 的任何建议，我将不胜感激。

Answer 1

理解 DCG 的关键是它们是编写递归下降解析器的语法糖。您需要考虑 运算符优先级 （您的运算符绑定有多紧密？）。这里，运算符的优先级从最紧到最松是

没有
和
或

所以 a or not b and c 被评估为 a or ( (not b) and c ) ).

我们可以这样说（我也包括了括号表达式，因为它们做起来很简单）：


% the infix OR operator is the lowest priority, so we start with that.
expr --> infix_OR.

% and an infix OR expression is either the next highest priority operator (AND),
% or... it's an actual OR expression.
infix_OR --> infix_AND(T).
infix_OR --> infix_AND(X), [or], infix_OR(Y).

% and an infix AND expression is either next highest priority operator (NOT)
% or... it's an actual AND expression.
infix_AND --> unary_NOT(T).
infix_AND --> unary_NOT(X), [and], infix_AND(Y).

% and the unary NOT expression is either a primary expression
% or... an actual unary NOT expression
unary_NOT  --> primary(T).
unary_NOT  --> [not], primary(X).

% and a primary expression is either an identifer
% or... it's a parenthetical expression.
%
% NOTE that the body of the parenthetical expression starts parsing at the root level.
primary --> identifier(ID).
primary --> ['(', expr(T), ')' ].

identifier --> [X], {id(X)}. % the stuff in '{...}' is evaluated as normal prolog code.

id(a).
id(b).
id(c).
id(d).
id(e).
id(f).
id(g).
id(h).
id(i).
id(j).
id(k).
id(l).
id(m).
id(n).
id(o).
id(p).
id(q).
id(r).
id(s).
id(t).
id(u).
id(v).
id(w).
id(x).
id(y).
id(z).

但请注意，这一切所做的只是识别个语法句子（专业提示：如果您正确编写语法，它也应该能够生成所有可能的有效句子语法）。请注意，这可能需要一段时间才能完成，具体取决于您的语法。

因此，要使用解析 DO 做一些事情，您需要添加一些额外的东西。我们通过向 DCG 添加额外的参数来做到这一点，即：

expr(       T        ) --> infix_OR(T).

infix_OR(   T        ) --> infix_AND(T).
infix_OR(   or(X,Y)  ) --> infix_AND(X), [or], infix_OR(Y).

infix_AND(  T        ) --> unary_NOT(T).
infix_AND(  and(X,Y) ) --> unary_NOT(X), [and], infix_AND(Y).

unary_NOT(  T        ) --> primary(T).
unary_NOT(  not(X)   ) --> [not], primary(X).

primary(    ID       ) --> identifier(ID).
primary(    T        ) --> ['(', expr(T), ')' ].

identifier( ID       ) --> [X], { id(X), ID = X }.

id(a).
id(b).
id(c).
id(d).
id(e).
id(f).
id(g).
id(h).
id(i).
id(j).
id(k).
id(l).
id(m).
id(n).
id(o).
id(p).
id(q).
id(r).
id(s).
id(t).
id(u).
id(v).
id(w).
id(x).
id(y).
id(z).

这就是构建解析树的地方。有人可能会注意到，可以很容易地评估表达式而不是构建解析树...然后您就可以编写一种解释性语言了。

您可以 fiddle 在这个 fiddle: https://swish.swi-prolog.org/p/gyFsAeAz.pl

您会注意到执行目标 phrase(expr(T),[a, or, not, b, and, c]). 会产生所需的解析 T = or(a, and(not(b), c))。

能够读取命题逻辑表达式的DCG

DCG capable of reading a propositional logic expression

prolog