CFG的扩展，这是什么？ [英] Extension to CFG, what is it?

问题描述

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

Consider the following extension to context-free grammars that permits rules to have in the left-hand side, one (or more) terminal on the right side of the non-terminal. That is, rules of the form:

A b -> ...

右侧可能是任何东西，例如无上下文语法。特别是，不需要是必须的，右侧的末尾将具有完全相同的端子符号。在这种情况下，此扩展将是上下文相关的。但是终端不仅仅是上下文。有时，此终端称为回送。

The right-hand side may be anything, like in context-free grammars. In particular, it is not required, that the right-hand side will have exactly the same terminal symbol at the end. In that case, this extension would be context-sensitive. But the terminal is not just a context. Sometimes, this terminal is called "pushback".

很显然，它不再是CFG（类型2）。它包括类型1。那是什么

Clearly, this is no longer CFG (type-2). It includes type-1. But what is it? Really type-0 already?

此特定扩展名已在确定子句语法中允许使用。 dcg 。 （为避免误解，我在这里不考虑Prolog的完整扩展。即，我假设终端来自有限的字母并且不是任意术语，我也不考虑DCG中允许的Prolog的其他参数，这些参数也输入-已经是0。）

This particular extension is permitted in Definite Clause Grammars dcg in Prolog. (To avoid misunderstandings, I do not consider here Prolog's full extensions. I.e. I assume terminals to come from a finite alphabet and not being arbitrary terms, also I do not consider Prolog's additional arguments that are permitted in DCGs, which also go into type-0 already.)

编辑：这是描述扩展名的更简单方法：添加到以下形式的CFG规则

Here is a simpler way to describe the extension: Add to a CFG rules of the form

A b -> <epsilon>

推荐答案

要回答有关Prolog DCG形式主义的问题，此扩展程序现在称为 semicontext 。参见 DCG的N253 DIN草案2014-04-08-ISO / IEC WDTR 13211-3：2014-04-08

To answer my question with respect to Prolog's DCG formalism, this extension is now called a semicontext. See N253 DIN Draft for DCGs 2014-04-08 - ISO/IEC WDTR 13211-3:2014-04-08

给定

a1, [b] --> ... .

a2, [b,b] --> ... .

终端序列 [b] 为现在是一个半上下文，以及终端序列 [b，b] 。

The terminal-sequence [b] is now a semicontext, as well as the terminal-sequence [b,b].

将具有相同的终端序列现在出现在规则的末尾，我们会有一个上下文：

Would the same terminal sequence now appear at the end of the rule, we would have a context:

a3, [b,b] --> ..., [b,b].

所以 semi在这里的意思是一半-类似于半群，其中半数的代数性质一群人。

So "semi" means here "half" - similar to a semigroup where half of the algebraic properties of a group hold.

这篇关于CFG的扩展，这是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！