处理序言上下文无关文法 [英] Handling prolog context free grammar

查看:108
本文介绍了处理序言上下文无关文法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

给出CFG

S --> a S b | c | d

我想写一个谓词,例如 grammar('S',句子) strong>会生成所有可能的

I wanna write a predicate like, grammar('S', sentence) which generates all possible

sentences like
sentence=acb,
sentence=acd,
sentence=c,
sentence=ab......................

使用最左导数,如果遇到的符号是 terminal ,则应打印出该终端,如果遇到符号为非终结符 'S',它应回溯和替换,并使用语法 a S b或c或d 之一并重复该过程。

Using left most derivation, if the encountered symbol is terminal it should print out that terminal, and if the encountered symbol is non terminal 'S', it should backtrack and substitute and one of the grammar a S b or c or d and repeat the process.

我不想要任何代码...只是帮助我一些技巧,以开始使用

I dont want any code...just help me with some tips how to start with

推荐答案

让我们使用DCG逐字地对您的语法进行编码!

Let's use DCGs to encode your grammar literally!

s --> [a], s, [b] | [c] | [d].

?- phrase(s,Xs).
ERROR: Out of local stack

该查询似乎没有终止。即Prolog非常简单的执行策略没有找到解决方案。另一方面,请考虑一下:您的语法描述了无限的句子集。如果要枚举无限集,则很容易错误地开始。这就是Prolog在这里实际要做的。

Seems that this query does not terminate. I.e. Prolog's very simple execution strategy did not find a solution. On the other hand, think of it: Your grammar describes an infinite set of sentences. If you are enumerating an infinite set it is easy to start "at the wrong end". That's what Prolog actually does here.

但是事情一点也不糟。枚举固定长度的所有句子呢?我会尝试5:

But things are not that bad at all. What about enumerating all sentences of a fixed length. I will try 5:

?- length(Xs,5), phrase(s,Xs).
Xs = "aacbb" ;
Xs = "aadbb" ;
false.

在这种情况下,所有句子都被找到,Prolog甚至向我们保证没有其他句子。 / p>

In this case, all sentences are found and Prolog even assures us that there are no further sentences.

?- length(Xs,4), phrase(s,Xs).
false.

没有长度为4的句子。

我们现在可以枚举所有句子,按长度

We can now enumerate all sentences, by length.

?- length(Xs,N), phrase(s,Xs).
Xs = "c",
N = 1 ;
Xs = "d",
N = 1 ;
Xs = "acb",
N = 3 ;
Xs = "adb",
N = 3 ;
Xs = "aacbb",
N = 5 ;
Xs = "aadbb",
N = 5 ;
Xs = "aaacbbb",
N = 7

什么样的推导我们在这里使用吗?老实说,我不知道,我不在乎。重要的是要知道Prolog何时终止。在这种情况下,如果长度已知,它将终止。这就是我们需要知道的,以确保我们有一个无限集的公平枚举。情况甚至会稍微好一些: s // 0 也会在长度未知的情况下终止

What kind of derivation did we use here? Honestly, I don't know and I don't care. What is important to know is when Prolog will terminate. In this case, it will terminate, if the length is known. And that is all we need to know to guarantee that we have a fair enumeration of the infinite set. Things are even slightly better: s//0 will also terminate in cases where the length is not known like

?- Xs = [a,a,b|_], phrase(s,Xs).
false.

?- Xs = [a,a,c|_], phrase(s,Xs).
Xs = "aacbb" ;
false.

?- dif(X,Y), Xs = [X,Y|_], phrase(s,Xs).
X = a,
Y = c,
Xs = "acb" ;
X = a,
Y = d,
Xs = "adb" ;
false.

编辑:我对使用 acb 以获取列表 [a,c,b] :请参阅此答案以作解释并 库(double_quotes)

I got some questions about the toplevel answers using "acb" for a list [a,c,b]: Please refer to this answer for an explanation and to library(double_quotes).

这篇关于处理序言上下文无关文法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆