问题标签 [context-sensitive-grammar]

在乔姆斯基的层次结构中，没有定义递归语言集。我知道递归语言是递归可枚举语言的子集，并且所有递归语言都是可判定的。

我很好奇的是递归语言与上下文相关语言的比较。我可以假设上下文相关语言是递归语言的严格子集，因此所有上下文相关语言都是可判定的吗？

i am reading the Definitive ANTLR reference by Terence Parr, where he says:

Semantic predicates are a powerful means of recognizing context-sensitive language structures by allowing runtime information to drive recognition

But the examples in the book are very simple. What i need to know is: can ANTLR parse context-sensitive rules like:

xAy --> xBy

If ANTLR can't parse these rules, is there is another tool that deals with context-sensitive grammars?

有人可以向我解释为什么这种语法[上下文无关语法和上下文相关语法]接受字符串吗？

我所知道的是

上下文无关文法是一种形式文法，其中每个产生（重写）规则都是 V→w 的一种形式，其中 V 是单个非终结符，w 是一串终结符和/或非终结符。w 可以为空

上下文相关文法是一种形式文法，其中任何产生（重写）规则的左侧和右侧都可能被终结符号和非终结符号的上下文包围。

但是我怎么能解释为什么这些语法接受一个字符串呢？

我在谷歌上搜索了上下文敏感的引理，它似乎只产生上下文无关语言的结果。

抽引理只允许证明一种语言是上下文无关的吗？并且不区分上下文？

知道怎么做吗？

如何使用非确定性图灵机显示语言对上下文敏感？

我知道线性绑定自动机（LBA）接受的语言是上下文相关的语言。LBA 是一个非确定性的图灵机。

知道如何将所有这些联系起来并表明一种语言是上下文相关的吗？

我试图找到乔姆斯基提出的 4 级形式语法（无限制、上下文相关、上下文无关、常规）的简单（即非形式）解释。

自从我学习形式语法以来已经过去了一个时代，现在各种定义让我难以想象。需要明确的是，我不是在寻找随处可见的正式定义（例如这里和这里——我可以和其他任何人一样使用谷歌搜索），甚至不是任何形式的正式定义。相反，我希望找到的是简洁明了的解释，不会为了完整性而牺牲清晰度。

语言 X = { 0^m 使得 m = 2n+1 其中 n >= 0}

有人可以帮我找到 X 的上下文相关语法吗？我已经尝试了很多年，但我仍然没有接近。

我现在拥有的：

S -> B0C|00

B0 -> DD0|00

BD -> DD

0C -> 0EE|00

欧共体-> EE

D -> B

E -> C

但这不起作用。我不知道如何将零的数量加倍。

我必须编写一个函数来检查输入字符串对于给定的语言规范是否有效。我认为这将是一个标准的 CFG -> Chomsky Normal Form，然后是 CYK 解析，但是语言中的一条规则是防止这种情况发生。

有些规则很简单，如果我们定义了 terminal {a,b,c,d,e,f,P,Q,R,S}，那么有效的字符串就是

1) 任何孤立的小写终端
2) 如果 'x' 是一个有效的字符串，那么 Sx 也是

但是第三条规则是

3) 如果 X 和 Y 是有效的输入字符串，那么 PXY、QXY、RXY 也是

其中{P,Q,R}是剩余的大写终结符，X 和 Y 是非终结符。

这个的生产规则是什么样的？我以为会是这样的

但这有两个问题。首先，这不是 CFG 规则——这是否意味着该语言定义了 CSG？

第二个是这行不通，因为

XY -> PXY -> PPXY

在所有情况下都不是有效的消息。

可能重复：
上下文相关语法和上下文无关语法

在我的教科书中，这是对这两个术语的解释：

上下文相关语法：

语法可以有 w1 → w2 形式的产生式，其中 w1 = lAr 和 w2 = lwr，其中 A 是非终结符，l 和 r 是零个或多个终结符或非终结符的字符串，w 是终结符或非终结符的非空字符串非终结符号。只要 S 不出现在任何其他产生式的右侧，它也可以有产生式 S → λ。

上下文无关语法：

文法只能有 w1 → w2 形式的产生式，其中 w1 是单个符号，不是终结符号。类型 3 文法只能有 w1 → w2 形式的产生式，其中 w1 = A 且 w2 = aB 或 w2 = a，其中 A 和 B 是非终结符号，a 是终结符号，或者 w1 = S 和 w2 = λ。

在我的教科书中，作者说：CSG是CFG的一个特例。但是，我不明白这一点。因为在 CSG 中，lAr -> lwr。l 和 r 可以是零个或多个终结符或非终结符的字符串。因此，当它是零字符串时（意味着：长度 = 0）。我们可以将 lAr 写为 A。因此，CSG 将是 CFG。所以，CSG就是CFG

我理解错了吗？请为我更正。

谢谢 ：）

我想知道用于解析编程语法的解析算法是什么。除了 IEEE 研究论文之外，我可以阅读有关编程语法和解析算法的任何链接、博客或任何内容吗？