问题标签 [dcg-semicontext]

考虑以下对上下文无关文法的扩展，它允许规则在左侧具有一个（或多个）终结符在非终结符的右侧。也就是说，形式的规则：

右手边可以是任何东西，比如在上下文无关文法中。特别是，不需要右手边的末尾有完全相同的终端符号。在这种情况下，此扩展将是上下文相关的。但终端不仅仅是一个上下文。有时，这个终端被称为“推回”。

显然，这不再是 CFG（类型 2）。它包括类型 1。但它是什么？真的已经是 type-0 了吗？

Prolog 中的定句语法dcg允许此特定扩展。（为了避免误解，我在这里不考虑 Prolog 的完整扩展。即我假设终端来自有限的字母表而不是任意术语，我也不考虑 DCG 中允许的 Prolog 的附加参数，这些参数也进入类型- 0 已经。）

编辑：这是描述扩展的更简单方法：添加到表单的 CFG 规则

在这个站点中，我找到了一个解释如何使用 DCG 构建右手上下文符号的部分

有人通过示例帮助我弄清楚这种方法并说明它对解析上下文无关语法的好处

长序列和短序列之间的距离是短序列与长序列的任何与短序列长度相同的子序列之间的最小距离。

我使用的距离是我认为的曼哈顿距离。（但这应该不重要，因为我希望能够改变距离函数）。

第一个版本展示了一个简单的实现，没有提前放弃。我生成所有相同长度的子序列，映射它们以找到它们与短序列之间的距离，然后使用 aggregate/3 找到最小值。

示例查询：

这个下一个版本应该更有效，因为一旦距离超过已经找到的最小值，它将放弃计算长序列的子序列和短序列之间的距离。

询问：

但是在这里我使用了 assert 和 Retract，所以我想要一个执行相同算法但没有这些算法的版本。我认为我应该能够使用带有半上下文符号的 dcg 来做到这一点，但发现很难掌握......我如何跟踪我通过回溯生成的子序列以及最小距离的“状态”到目前为止找到了吗？

我遇到的问题.. seq_subseq/2 是通过回溯生成子序列。测试的第一个子序列需要设置为最小距离。然后我想循环，所以回溯生成另一个序列。但要回溯，我必须失败。但是我不能带回到目前为止的最小距离来检查下一个序列。

如果我不想使用回溯，我想我需要定义一个状态转换谓词来按顺序生成子序列。

眼下

所以我想我需要定义一个关系：

这将像：

和

但我需要以一种有效的方式做到这一点。

更新- 感谢 Mat 的回答，我现在有了这个，我认为这是一个很大的改进。谁能看到对此的进一步改进？我有一个双嵌套 -> 结构和一个！在 accumulate_dis/4 定义中，这两者看起来都很难看。我还让它返回长序列的子序列，它是距短序列最短的距离。

它需要使用非整数，所以我认为 clpfd 不合适。

询问：

我想计算列表是二叉树上的 bfs 顺序。此外，它应该在第二面工作 - 列出它找到树。
你能给我一些提示吗，到目前为止我都使用过类似的东西，当然它不起作用......

这是Mat 的回答中的一个较早问题的后续问题

从此开始

然后阅读

对于一个变量，使用一个包含仅包含该变量的单个元素的列表。如果要传递多个变量，请使用包含 f(...) 形式的单个项的列表，捕获所有要传递的变量。这也很值得提出自己的问题。

演变成这样

哪个有效，但要注意use a list that contains a single term of the form f(...)，这里f(...)不在列表中。

我是不是哪里出错了？

补充

参考

• Markus Triska在美国思考
• Markus Triska 的Prolog DCG 入门
• 立即学习 Prolog 的额外参数！

隐式状态传递的变量名称约定

通常在使用隐式状态传递时，变量被命名

S0→ S1→…→S

但是对于我的一元二叉树示例，我将它们命名为

S0→ S1→…→Sn

以Sn代替结尾S。

例如

标准

这里

原因是这个例子有一个相当罕见的属性，即每个 DCG 谓词的长度都在增加，

例如

所以结尾xn给了我对准确性的另一次检查。

参考：ISO/IEC DTR 13211–3:2006 定句语法规则

6.1.3 终端序列的变量名约定

此 TR 使用名为 S0、S1、...、S 的变量来表示在处理语法规则或将语法规则扩展为子句时用作参数的终端序列。在这种表示法中，变量 S0、S1、...、S 可以看作是一系列状态，其中 S0 代表初始状态，变量 S 代表最终状态。因此，如果变量 Si 表示给定状态下的终端序列，则变量 Si+1 将表示用语法规则解析 Si 后剩余的终端序列。

我对生成乔姆斯基所描述的上下文相关语言的元素感兴趣，如乔姆斯基语法分类中 “类型 - 1 语法”一节中所述。

（基本上，类似于标准的上下文无关语法，但允许在生产规则的左侧使用多个符号，包括终端）。

我知道 Prolog 中的确定子句语法，但我看不到这些语法与乔姆斯基的上下文相关语言之间的明显映射。是否有一种“通用”的方式来使用 DCG 框架来描述左侧带有多个符号的生产规则，或者我是否需要针对每种单独的语言使用一种特别的方法？

由于这个问题使用列表，我想使用 DCG 解决它。在这个过程中，我意识到可以使用半上下文。( DCG 入门)

最初的问题是返回列表中项目的计数，但如果两个相同的项目彼此相邻，则不要增加计数。

虽然我的代码适用于某些测试用例，但它不适用于其他测试用例。这只是一个失败的条款。在使用调试器查看代码时，似乎第二个状态变量，即返回的列表，在我认为它应该未绑定时，在调用该子句时被绑定。编辑在下面解决了这部分问题。

我正在使用 SWI-Prolog 8.0。

导致问题的子句：

注意：C1 被标记为Singleton variables: [C1]

通常我会更改C1为，_但在这种情况下，我需要指出当前正在处理的第一个和第二个项目是不同的。换句话说，它是在以统一的失败作为保护。

使用 Listing/1 查看 DCG 会发现_可能是问题但不确定的用途。

使用 DCG 解决问题的正确方法是什么？

请参阅后续问题。

当前源代码

测试用例

运行测试

编辑 1

意识到需要对两个谓词进行尾调用

代码仍然无法正常工作，但这解释了为什么状态变量在我期望它未绑定时被绑定。

编辑 2

虽然没有像我希望的那样使用 DCG 半上下文，但使用半上下文的变体作为前瞻，代码可以工作。不将此作为答案发布，因为我希望答案要么显示 DCG 代码与子句标题上的半上下文一起使用，要么解释为什么这是错误的。

运行测试

作为对提出问题的这个问题的后续行动

返回列表中项目的计数，但如果两个相同的项目彼此相邻，则不要增加计数。

这段代码是我最接近用 DCG 和 semicontext 解决这个问题的。

在子句头部使用带有半上下文的 DCG 解决问题的正确方法是什么？

想知道从句头上半上下文的变化是否可能。如果可能，则需要工作示例代码，如果不可能，则需要解释。

如何在解析文本时传递状态（并在需要时更改它）！？

https://www.metalevel.at/prolog/dcg

该示例正在计数..

不知道我应该如何通过初始状态。我必须将其作为调用参数还是作为列表中的第一个元素？每当我想使用 State 时，我是否必须将 state(S) 作为首要目标？

======

假设我必须解析字符串“添加项目 5”。

如果状态是 "list" ，假设它应该打印 "5=>list"

如果“设置”然后“5 =>设置”

或者可能是更复杂的字符串“new list.add 5”......其中解析“new list”应该设置State=list，以便解析下一部分知道上下文并且解释是“add 5 to a list ” 与“将 5 加到一组中”。

无需使用这些示例，我只是想弄清楚何时使用半上下文表示法以及如何将上下文作为参数传递给 first/top 规则。

如您所见，我很困惑，但这是我在互联网上可以找到的唯一示例，并且序言文档一如既往地密集，简洁且不是很有帮助；（没有示例。

澄清 ：

在这个例子中，我在每个级别传递上下文，即使我没有在 add() 中使用它。我可以为 add() 删除它，但如果有子规则我必须保留它。

我知道使用状态线程只需要在顶级规则中声明 Ctx 并且无论何时使用它