扩展至 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.但它是什么?真的已经是 type-0 了吗?
Clearly, this is no longer CFG (type-2). It includes type-1. But what is it? Really type-0 already?
定从句语法中允许使用此特定扩展名dcg 在 Prolog 中.(为了避免误解,我在这里不考虑 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.请参阅 N253 DIN 草案 DCG 2014-04-08 - ISO/IEC WDTR13211-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].
所以半"在这里意味着一半"——类似于半群,其中一个群的一半代数性质成立.
So "semi" means here "half" - similar to a semigroup where half of the algebraic properties of a group hold.
这篇关于扩展至 CFG,它是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!