检查是否字符串包含在语言（序言）

这是CFG：检查是否字符串包含在语言（序言）

S -> T | V 
T -> UU 
U -> aUb | ab 
V -> aVb | aWb 
W -> bWa | ba

所以这会接受某种形式的：

{a^n b^n a^m b^m | n,m >= 1} U {a^n b^m a^m b^n | n,m >= 1}

这里是我的代码有工作：

in_lang([]). 
in_lang(L) :- 
    mapS(L), !. 

mapS(L) :- 
    mapT(L) ; mapV(L),!. 

mapT(L) :- 
    append(L1, mapU(L), L), mapU(L1), !. 

mapU([a|T]) :- 
    ((append(L1,[b],T), mapU(L1)) ; (T = b)),!. 

mapV([a|T]) :- 
    ((append(L1,[b],T), mapV(L1)) ; 
    (append(L1,[b],T), mapW(L1))), 
    !. 

mapW([b|T]) :- 
    ((append(L1,[a],T), mapW(L1)) ; 
    (T = a)), 
    !.

截至目前，这是出于以下三个字符串返回false：

[a,a,b,b,a,b] // this should be true 
[a,a,a,b,b,a,a,b,b,b] // this should be true as well 
[a,a,a,b,b,a,b,b,b] // this one IS false

任何帮助或洞察力将不胜感激，我对Prolog不太舒服，因此自己调试一直是一个挑战。

来源

2016-04-25 csh1579

所有这些切割（'！'），它们是干什么用的？谓词定义的最后一个切点是非常强烈的代码味道。 – 2016-04-25 15:39:29

首先，请注意这个代码是没有意义的：

... append(L1, mapU(L), L) ...

在Prolog有谓词，而不是函数...

一个CFG产生式规则（非终端）应该“吃”一些令牌，而在Prolog中，这意味着您至少需要2个参数：输入令牌列表，以及生产成功匹配相关输入部分后剩下的参数。

即，附加/ 3不是必需的：只是模式匹配，通过统一运算符（=）进行/ 2

mapS(L1, L) :- mapT(L1,L) ; mapV(L1,L). 
mapT(L1, L) :- mapU(L1,L2), mapU(L2,L). 
mapU(L1, L) :- L1=[a|L2], mapU(L2,L3), L3=[b|L] ; L1=[a,b|L]. 
... complete the translation

然后调用它：

?- mapS([a,a,b,b,a,b],R). 
R = [] ; 
false.

R = []意味着整个序列已匹配...

来源

2016-04-25 17:39:18 CapelliC

在mapT的定义中，您试图使用mapU的“返回值”作为append的参数。但mapU是一个谓词，谓词没有返回值。相反，人们通常用一个未绑定的变量来写谓词，谓词绑定到所需的“返回值”。在predciate被证明之后，现在绑定的变量可以用于后续的谓词。

来源

2016-04-25 15:48:30

我最初尝试做T1是mapU（L），mapU（T1）。然而，这一直抛出一个异常，指出“错误是/ 2：类型错误：'[]'预期，发现'[a，a，b，b，a，b]'（”x“必须包含一个字符）“ ，我不太清楚如何解决这个问题，同时仍然使用一个未绑定的变量。 – csh1579

从这个描述中你完全不清楚你试图做什么，更不用说它为什么不起作用。也许如果你展示了实际的代码，而不仅仅是一个不明身份的描述。 –

只需使用dcg！和library(double_quotes)。

:- set_prolog_flag(double_quotes, chars). 

s --> t | v. 
t --> u, u. 
u --> "a",u,"b" | "ab". 
v --> "a",v,"b" | "a",w,"b". 
w --> "b",w,"a" | "ba". 

| ?- use_module(library(double_quotes)). 

| ?- length(L,N), phrase(s, L). 
L = "abab", N = 4 ? ; 
L = "abab", N = 4 ? ; 
L = "aabbab", N = 6 ? ; 
L = "abaabb", N = 6 ? ; 
L = "aababb", N = 6 ? ; 
L = "abbaab", N = 6 ? ; 
L = "aaabbbab", N = 8 ? ; 
L = "aabbaabb", N = 8 ? ; 
L = "abaaabbb", N = 8 ? ; 
L = "aaababbb", N = 8 ? ...

来源

2016-04-25 15:58:12 false

这不会成为一个家庭作业的问题，不是吗？ –

@ScottHunter至少从1965年到1972年，人们无意中涉足这个问题：如何恰当地编码一种语法。他们都尝试了一些类似append的野兽。我们不要让这个黑暗时刻永存。自1972年夏天以来，没有任何借口！ – false

因此，OP对dcg的明显无知并不意味着它可能不会被使用？将CFG翻译成dcg是一项非常简单的练习，这使得它成为一个很好的*解决方案*，但糟糕的*作业*。这是我的观点。 –

检查是否字符串包含在语言（序言）

回答

相关问题