c# - C# 是否被视为上下文无关语言？

Question

我一直在寻找这个，但是在MSDN 论坛上这个问题有很多不同的答案。

有人说“所有计算机语言语法都是上下文无关的”，其他人说任何具有空格敏感语法的语言都可能是上下文相关的，因此不是上下文无关的（F# 和 Python）。

谁会是一个很好的明确答案，也许是一些证据。

Answer 1

我会将 C# 描述为具有上下文无关的语法，但该语言具有语法中未表达的上下文相关规则。

来自维基百科（形式语法）：

上下文无关文法是一种文法，其中每个产生式规则的左侧仅包含一个非终结符。

从 C# 4.0 规范，第 2.2.1 节（语法符号）：

词汇和句法语法使用语法产生式呈现。每个语法产生式都定义了一个非终结符号以及该非终结符号可能扩展为非终结符号或终结符号的序列。

当我读到它时，这意味着定义 C# 语言的生产规则是上下文无关的。每个产生式规则的左侧是一个非终结符。相比之下，上下文相关文法在产生式规则的左侧可能有多个终结符号和非终结符号。

然而，规范中有许多与上下文相关的规则。例如，“必须在获得其值的每个位置明确分配局部变量（第 5.3 节）。” 此外，“方法的签名在声明该方法的类中必须是唯一的。” 在这两种情况下，任何特定片段的有效性都取决于它出现的上下文。

当然，许多编程语言都有类似的要求，包括 C。我怀疑大多数人会认为 C 是一种上下文相关的语言。我认为这个答案总结得很好：

语法正确的程序集对于几乎所有语言都是无上下文的。几乎所有语言的编译程序集都不是上下文无关的。

至于 Python 和 F#，正如我在评论中所说，这些语言通常被描述为具有不区分上下文的语义（或有时是语法）空格。

Answer 2

C# 不是上下文无关的。考虑以下上下文中的输入序列“>>”：

List<List<int>> foo;
int x = 1234 >> 1;

在第一种情况下，词法分析器为每个“>”返回一个单独的标记。可以在它们之间放置空白甚至是注释。'List<List /* comment */ >' 是一个完全有效的类型！

在第二种情况下，词法分析器为运算符“>>”（以及“>>=”）返回单个标记。表达式 '1234 > > 1' 将产生语法错误。

词法分析器需要知道上下文是类型还是表达式，因此 C# 不是上下文无关语法，