6

使用 SWI Prolog(Win x64)的开发版本,我为确定性词法分析器(托管在 github)编写了 DCG 谓词(因此所有外部谓词都没有选择点):

read_token(parser(Grammar, Tables),
       lexer(dfa-DFAIndex, last_accept-LastAccept, chars-Chars0),
       Token) -->
(   [Input],
    {
     dfa:current(Tables, DFAIndex, DFA),
     char_and_code(Input, Char, Code),
     dfa:find_edge(Tables, DFA, Code, TargetIndex)
    }
->  { table:item(dfa_table, Tables, TargetIndex, TargetDFA),
      dfa:accept(TargetDFA, Accept),
      atom_concat(Chars0, Char, Chars),
      NewState = lexer(dfa-TargetIndex,
                       last_accept-Accept,
                       chars-Chars)
    },
    read_token(parser(Grammar, Tables), NewState, Token)
;   {
     (   LastAccept \= none
     ->  Token = LastAccept-Chars0
     ;   (   ground(Input)
         ->  once(symbol:by_type_name(Tables, error, Index, _)),
             try_restore_input(Input, FailedInput, InputR),
             Input = [FailedInput | InputR],
             format(atom(Error), '~w', [FailedInput]),
             Token = Index-Error
         ;   once(symbol:by_type_name(Tables, eof, Index, _)),
             Token = Index-''
         )
     )
    }
).

现在使用(;)->很多,我想知道 SWI-Prolog 是否可以read_token(parser(Grammar, Tables), NewState, Token)使用 Tail-Call-Optimization 优化递归,或者我是否必须手动将谓词拆分为几个子句。我只是不知道如何找出解释器的作用,尤其是知道在运行调试器时 TCO 被禁用。

4

1 回答 1

6

为了回答您的问题,我首先寻找可能会阻止最后通话优化的“琐碎”目标。如果发现一些:

     ; (接地(输入)
         -> 一次(符号:by_type_name(表,错误,索引,_)),
             try_restore_input(输入,失败输入,InputR),
             输入 = [失败输入 | 输入R],
             格式(原子(错误),'〜w',[FailedInput]),
             令牌 = 索引错误
         ; 一次(符号:by_type_name(表,eof,索引,_)),
             令牌 = 索引-''
         )

在这两种情况下,仅这些目标就可以防止 LCO。

现在,我遵守了您的规则并查看了扩展listing

?- 列表(read_token)。
read_token(解析器(O,B),词法分析器(dfa-C,last_accept-T,chars-J),Q,A,S):-
        ( A=[D|G],
            dfa:当前(B,C,E),
            char_and_code(D, K, F),
            dfa:find_edge(B, E, F, H),
            N=G
        -> 表:项目(dfa_table,B,H,I),
            dfa:接受(我,L),
            atom_concat(J, K, M),
            P=lexer(dfa-H, last_accept-L, chars-M),
            R=N,
            read_token(解析器(O,B),
                       磷,
                       问,
                       R,
                       S) %1:看起来不错!
        ; ( T\=无
            -> Q=TJ
            ; 地面(D)
            -> 一次(符号:按类型名称(B,错误,W,_)),
                try_restore_input(D, U, V),
                D=[U|V],
                格式(原子(X),'〜w',[U]),
                Q=WX % 2:防止LCO
            ; 一次(符号:by_type_name(B,eof,W,_)),
                Q=W-'' % 3:防止LCO
            ),
            S=A     % 4:防止LCO
        )。

广告 1)这是您最有可能正在寻找的递归案例。在这里,一切似乎都很好。

ad 2,3) 上面已经讨论过了,也许你想交换目标

广告 4) 这是 DCG 中精确、{}//1稳定的处理方式的效果。根据经验:实施者宁愿坚定不移,也不愿争取 LCO-ness。请参考:DCG扩展:坚定不移?

另请注意,这不仅仅是调用框架的简单重用。与垃圾收集有很多交互。为了克服 SWI 中的所有这些问题,需要一个额外的 GC 阶段。

有关更多信息,请参阅Prolog 中 Precise Garbage Collection 中的微小基准

所以最后回答你的问题:你的规则可能会优化;前提是在递归目标之前没有选择点。


对此也有真正的低级方法。我从不将它用于代码开发:vm_list. 该清单最终向您展示了 SWI 是否会考虑 LCO(前提是没有选择点)。

i_call并且i_callm永远不会执行 LCO。只会i_depart做。在:142 i_depart(read_token/5)

?- vm_list(read_token)。
==================================================== =======================
read_token/5
==================================================== =======================
   0 s_处女
   1 i_exit
--------------------------------------
第 1 条((0x1cc4710)):
--------------------------------------
   0 h_functor(解析器/2)
   2 h_firstvar(5)
   4 h_firstvar(6)
   6 h_pop
   7 h_functor(lexer/3)
   9 h_functor((-)/2)
  11 h_const(dfa)
  13 h_firstvar(7)
  15 h_pop
  16 h_functor((-)/2)
  18 h_const(last_accept)
  20 h_firstvar(8)
  22 h_pop
  23 h_rfunctor((-)/2)
  25 h_const(字符)
  27 h_firstvar(9)
  29 h_pop
  30 i_enter
  31 c_ifthenelse(26,118)
  34 b_unify_var(3)
  36 h_list_ff(10,11)
  39 b_unify_exit
  40 b_var(6)
  42 b_var(7)
  44 b_firstvar(12)
  46 i_callm(dfa,dfa:当前/3)
  49 b_var(10)
  51 b_firstvar(13)
  53 b_firstvar(14)
  55 i_call(char_and_code/3)
  57 b_var(6)
  59 b_var(12)
  61 b_var(14)
  63 b_firstvar(15)
  65 i_callm(dfa,dfa:find_edge/4)
  68 b_unify_fv(16,11)
  71 c_cut(26)
  73 b_const(dfa_table)
  75 b_var(6)
  第77章(15)
  79 b_firstvar(17)
  81 i_callm(表,表:项目/4)
  第84章(17)
  86 b_firstvar(18)
  88 i_callm(dfa,dfa:接受/2)
  91 b_var(9)
  第93章(13)
  95 b_firstvar(19)
  97 i_call(atom_concat/3)
  99 b_unify_firstvar(20)
 101 b_functor(词法分析器/3)
 103 b_functor((-)/2)
 第105章
 第107章(15)
 第109章
 110 b_functor((-)/2)
 第112章
 第114章(18)
 第116章
 117 b_rfunctor((-)/2)
 第119章
 第121章(19)
 第123章
 第124章
 125 b_unify_fv(21,16)
 128 b_functor(解析器/2)
 第130章(5)
 第132章(6)
 第134章
 第135章(20)
 第137章
 第138章(21)
 第140章(4)
142 i_depart(读取令牌/5)
 144 c_var_n(22,2)
 147 c_var_n(24,2)
 150 c_jmp(152)
 152 c_ifthenelse(27,28)
 第155章(8)
 第157章
 159 i_call((\=)/2)
 第161章(27)
 第163章(2)
 165 h_functor((-)/2)
 第167章(8)
 第169章(9)
 第171章
 第172章
 第173章(10)
 175 c_var_n(22,2)
 178 c_var_n(24,2)
 第181章(101)
 183 c_ifthenelse(28,65)
 第186章(10)
 188 i_call(地面/1)
 第190章(28)
 192 b_functor((:)/2)
 第194章
 196 b_rfunctor(by_type_name/4)
 第198章(6)
 200 b_const(错误)
 第202章(22)
 第204章
 第205章
 206 i_call(一次/1)
 第208章(10)
 第210章(23)
 第212章(24)
 214 i_call(try_restore_input/3)
 第216章(10)
 第218章
 第219章(23)
 第221章(24)
 第223章
 第224章
 225 b_functor(原子/1)
 第227章(25)
 第229章
 第230章
 第232章
 第233章(23)
 第235章
 第236章
 237 i_call(格式/3)
 第239章(2)
 241 h_functor((-)/2)
 第243章(22)
 第245章(25)
 第247章
 第248章
 第249章(33)
 251 b_functor((:)/2)
 第253章
 255 b_rfunctor(by_type_name/4)
 第257章(6)
 第259章
 第261章(22)
 第263章
 第264章
 265 i_call(一次/1)
 第267章(2)
 第269章
 第271章(22)
 第273章
 第275章
 第276章
 第277章(10)
 第279章 (23,2)
 第282章(25)
 第284章 (4,3)
 第287章 (11,2)
 290 c_var_n(13,2)
 293 c_var_n(15,2)
 296 c_var_n(17,2)
 第299章(19,2)
 第302章(21)
 第304章
于 2013-03-15T16:07:42.013 回答