有没有办法或算法将 DCG 转换为 Prolog 中的普通定句? [英] Is there a way or an algorithm to convert DCG into normal definite clauses in Prolog?

问题描述

I am a newbie in Prolog, and I am trying to understand how a grammar can be translated into a normal definite clause from a DCG. I understood that DCG notation is just syntactic sugar for normal definite clauses in Prolog. I started to depict some similarities between the normal definite grammars, and the DCGs, but failed to apply the same pattern, so I am asking is there some rules that I am missing or an algorithm of conversion that might work.

Here is the grammar that I am working on, and here is what I did in order to translate that grammar:

expr --> term, addterm.
addterm --> [].
addterm --> [+], expr.
term --> factor, multfactor.
multfactor --> [].
multfactor --> [*], term.
factor --> [I], {integer(I)}.
factor --> ['('], expr, [')'].

This grammar actually checks the syntactic correctness of arithmetic operations. The first rule is actually easy to convert as its pattern is similar to normal definite grammars, and so is the 4th one. However I have no clue about the other four. Here is How I converted the rule:

expr(E0,E) :- term(E0,E1), addterm(E1,E).

解决方案

You are on the right track! Keep on going and you will get to something like this:

expr(Xs0,Xs) :-                         % expr -->
   term(Xs0,Xs1),                       %    term,
   addterm(Xs1,Xs).                     %    addterm.

addterm(Xs0,Xs) :-                      % addterm --> 
   Xs0 = Xs.                            %    [].
addterm(Xs0,Xs) :-                      % addterm -->
   Xs0 = [+|Xs1],                       %    [+], 
   expr(Xs1,Xs).                        %    expr. 

term(Xs0,Xs) :-                         % term --> 
   factor(Xs0,Xs1),                     %    factor,
   multfactor(Xs1,Xs).                  %    multfactor.

multfactor(Xs0,Xs) :-                   % multfactor -->
   Xs0 = Xs.                            %    [].
multfactor(Xs0,Xs) :-                   % multfactor -->
   Xs0 = [*|Xs1],                       %    [*],
   term(Xs1,Xs).                        %    term.  

factor(Xs0,Xs) :-                       % factor --> 
   Xs0 = [I|Xs],                        %    [I],
   integer(I).                          %    {integer(I)}.
factor(Xs0,Xs) :-                       % factor --> 
   Xs0 = ['('|Xs1],                     %    ['('], 
   expr(Xs1,Xs2),                       %    expr,
   Xs2 = [')'|Xs]. `                    %    [')'].      

这篇关于有没有办法或算法将 DCG 转换为 Prolog 中的普通定句?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！