6

根据Scala 中的这个答案 =>，关键字有两种不同的含义：1表示函数类型：2表示创建 lambda 表达式：。Double => Double(x: Double): Double => 2*x

这与形式语法有什么关系，即这是否使 Scala 上下文敏感？

我知道大多数语言都不是上下文无关的，但我不确定我所描述的情况是否与此有关。

编辑：

似乎我对上下文相关语法的理解不够好。我知道生产规则应该是什么样子，以及它们的含义（“这个生产只适用于 A 被这些符号包围”），但我只是不确定它们与实际（编程）语言有何关系。

我认为我的困惑源于阅读了诸如“乔姆斯基引入这个术语，因为一个词的含义可能取决于它的上下文”之类的内容，并且我=>将引用中的“词”这个词联系起来，并且它的这两种用法是两个不同的上下文。

如果答案能解决我的困惑，那就太好了。

4

1 回答 1

6

自从我处理形式语言理论以来已经有一段时间了，但我会咬一口。

“上下文无关”是指相应语法中要求的产生式规则没有“上下文”。这并不意味着特定符号不能出现在不同的规则中。

解决编辑问题：换句话说（更非正式地），决定一种语言是上下文无关的还是上下文敏感的，归结为不查看特定“单词”或“单词”的“含义”。相反，它相当于查看该语言中所有法律表达式的集合，并查看是否可以仅通过考虑组件“单词”彼此之间的位置关系来“编码”它们。这本质上就是Pumping Lemma检查的内容。

例如：

S → Type"="Body
Type → "Double"
Type → "Double""=>""Double"
Body → Lambda
Body → NormalBody
NormalBody → "x"
Lambda -> "x""=>"NormalBody

当然，开始符号在哪里S，大写的 ID 是非终结符，带引号的字符串是终结符。显然，这可以生成如下字符串：

Double=>Double=x=>x

但语法仍然是上下文无关的。

因此，正如观察到非终结符“=>”可以出现在程序的两个“位置”中一样，这并不会使 Scala 上下文敏感。

但是，这并不意味着：

  • 整个Scala语言是上下文无关的，
  • 它是上下文相关的——它可能更复杂，
  • 如果您想将 Scala 的语义编码为语法，您最终会得到上下文无关或上下文相关的语法。

最后一件事特别相关，因为您在正式语言的（nomen omen）上下文中提到了“意义”。

于 2014-03-08T19:20:12.333 回答