6

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

  1. {ww | w 是一个字符串}
  2. {一个n b n c n | a,b,c 是符号}

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

4

1 回答 1

10

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

上下文相关语言的一个真实例子是 C 编程语言。像先声明变量然后再使用它们这样的特性使 C 语言成为一种上下文敏感语言(CSL)。（我不知道无类型的 lambda 演算）。

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

在自然语言处理(NLP)中也使用上下文相关语法。大多数自然语言都是上下文相关语言的例子。（我不确定梵文）。

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

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]

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

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

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

参考：您可以观看Arun Kumar 博士的讲座。 在某些讲座中，他准确地解释了您感兴趣的内容。

于 2012-12-31T08:39:44.517 回答