grammar - 有人可以举一个上下文相关语法的简单但非玩具示例吗？

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改进这个问题？ Update the question所以它是on-topic对于堆栈溢出。

9年前关闭。




Improve this question




我正在尝试理解上下文相关的语法，并且我理解为什么语言喜欢

1. {ww | w is a string}
2. {aⁿ bⁿ cⁿ | a,b,c are symbols}

不是上下文无关的，但是我想知道类似于无类型 lambda 演算的语言是否对上下文敏感。我想看一个简单但非玩具的示例(我考虑上面的玩具示例)，上下文相关语法的示例，对于某些生产规则，例如，判断是否有一些符号字符串当前在范围内(例如，在生成函数体时)。上下文相关的语法是否足够强大，可以使未定义/未声明/未绑定(bind)的变量成为语法(而不是语义)错误？

Answer 1

是的，上下文相关语法 (CSG) 足够强大，可以检查未定义/未声明/未绑定(bind)的变量，但不幸的是，我们不知道任何有效的算法来解析 CSG 字符串。

上下文相关语言的一个真实例子是 C 编程语言。像先声明变量然后使用它们这样的特性使 C 语言成为 context-sensitive language (中超)。 (我不知道无类型的 lambda 演算)。

而且因为我们不知道 CSL(或 CSG)的任何线性解析算法。这就是编译器设计中的原因，我们使用 CFG(及其解析算法)进行语法检查，因为我们知道解析 CFG 的有效算法(如果它是受限形式)。编译器首先解析上下文无关特征，然后以有问题的方式处理上下文相关特征(例如，检查符号表中是否已定义任何使用的变量。否则，它会产生错误)。

natural-language processing 中也使用了上下文相关的语法。 (自然语言处理)。大多数自然语言都是上下文相关语言的例子。 (我不确定 Sanskrit 语言)。

我将尝试用一个愚蠢但简单的例子来解释它(这只是一个想法，你可以完善它):

NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>

现在，使用这个语法，我们可以生成一些正确的语句，但也有一些是错误的。例如，

SENTENCE --> <NOUN>   <TENSE>   <VERB>
             Grijesh    is       working       [Correct statement]

但

             Grijesh    am       working       [wrong statement]

原因: 的值取决于 值(例如， I <TENSE> --> I am)，因此语法不会生成正确的英语语句。

实际上，我们不能为完整的英语编写上下文无关的语法!

您可能已经注意到，任何自然语言翻译器或语法检查器都无法正常工作(尝试使用长语句)。因为这个问题属于上下文相关的解析算法。

引用 : 你可以看 Dr. Arun Kumar's lectures .
在某些讲座中，他准确地解释了您感兴趣的内容。