或者，更准确一点：哪些编程语言是由上下文无关文法定义的？
据我所知，由于宏和模板之类的原因，C++ 不是上下文无关的。我的直觉告诉我，函数式语言可能是上下文无关的，但我没有任何硬数据来支持它。
简洁示例的额外代表:-)
问问题
31228 次
9 回答
57
哪些编程语言是上下文无关的？[...]
我的直觉告诉我，函数式语言可能是上下文无关的[...]
简短的版本：几乎没有任何现实世界的编程语言在任何意义上都是上下文无关的。一种语言是否与上下文无关与它的功能无关。这只是语法复杂程度的问题。
这是命令式语言Brainfuck的 CFG ：
Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'
这是功能性 SKI 组合器演算的 CFG ：
Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'
这些 CFG 识别两种语言的所有有效程序，因为它们非常简单。
更长的版本：通常，上下文无关语法 (CFG) 仅用于粗略地指定语言的语法。必须区分语法正确的程序和正确编译/评估的程序。最常见的是，编译器将语言分析分为构建和验证一段代码的一般结构的语法分析和验证程序含义的语义分析。
如果“上下文无关语言”的意思是“ ……所有程序都为其编译”，那么答案是：几乎没有。符合这一要求的语言几乎没有任何规则或复杂的特性，例如变量的存在、空格敏感性、类型系统或任何其他上下文：在一个地方定义并在另一个地方依赖的信息。
另一方面，如果“上下文无关语言”仅意味着“ ......所有程序都通过了语法分析”，那么答案就是语法本身的复杂程度。有许多句法特征很难或不可能单独用 CFG 来描述。通过向解析器添加额外的状态来跟踪计数器、查找表等，可以克服其中的一些问题。
无法用 CFG 表达的句法特征示例：
缩进和空格敏感的语言，如 Python 和 Haskell。跟踪任意嵌套的缩进级别本质上是上下文相关的，并且需要单独的缩进级别计数器；每个级别使用多少空间以及有多少级别。
通过为每个缩进级别复制语法来仅允许使用固定数量的空格的固定级别的缩进将起作用，但实际上这很不方便。
C Typedef Parsing Problem表示 C 程序在词法分析期间是模棱两可的，因为它无法仅从语法中知道某物是常规标识符还是现有类型的 typedef 别名。
例子是：
typedef int my_int; my_int x;在分号处，需要使用 my_int 的条目来更新类型环境。但是，如果词法分析器已经提前查看了 my_int，它会将其作为标识符而不是类型名称进行词法分析。
在上下文无关的语法术语中，
X → ...触发的规则my_int是模棱两可的：它可能是产生标识符的规则，也可能是产生typedef'ed 类型的规则；知道哪个依赖于语法本身之外的查找表（上下文）。基于宏和模板的语言，如 Lisp、C++、Template Haskell、Nim 等。由于语法在解析时会发生变化，因此一种解决方案是将解析器变成一个自修改程序。另请参阅C++ 是上下文无关的还是上下文敏感的？
通常，即使有可能，运算符优先级和关联性也不会直接在 CFG 中表达。例如，对于小表达式语法的 CFG，其中 ^ 绑定比 × 更紧密，而 × 绑定比 + 更紧密，可能如下所示：
E → E ^ E E → E × E E → E + E E → (E) E → num然而，这个 CFG 是模棱两可的，并且通常伴随着一个优先级/关联性表，例如 ^ 绑定最紧密，× 绑定比 + 更紧密， ^ 是右关联的，并且 × 和 + 是左关联的。
优先级和关联性可以以机械方式编码到 CFG 中，这样它是明确的，并且只生成运算符行为正确的语法树。上面语法的一个例子：
E₀ → EA E₁ EA → E₁ + EA EA → ε E₁ → EM E₂ EM → E₂ × EM EM → ε E₂ → E₃ EP EP → ^ E₃ EP E₃ → num E₃ → (E₀)但是模棱两可的 CFG + 优先级/关联性表很常见，因为它们更具可读性，而且各种类型的LR 解析器生成器库可以通过消除移位/归约冲突而不是处理一个明确的、已转换的更大尺寸的语法来生成更高效的解析器。
理论上，所有有限字符串集都是正则语言，因此所有有界大小的合法程序都是正则的。由于常规语言是上下文无关语言的子集，所有有界大小的程序都是上下文无关的。争论还在继续，
虽然可以说，对于一种语言来说，只允许少于一百万行的程序是可以接受的限制，但将编程语言描述为常规语言是不切实际的：描述太大了。
— Torben Morgensen 的《编译器设计基础》，ch。2.10.2
CFG 也是如此。为了解决您的子问题有点不同，
哪些编程语言是由上下文无关文法定义的？
大多数现实世界的编程语言都是由它们的实现定义的，大多数现实世界的编程语言的解析器要么是手写的，要么使用扩展上下文无关解析的解析器生成器。不幸的是，为您最喜欢的语言找到精确的 CFG 并不常见。当您这样做时，它通常采用巴科斯-瑙尔形式(BNF)，或者很可能不是纯上下文无关的解析器规范。
来自野外的语法规范示例：
于 2013-07-16T20:18:45.113 回答
46
语法正确的程序集对于几乎所有语言都是无上下文的。
几乎所有语言的编译程序集都不是上下文无关的。例如，如果所有编译 C 程序的集合都是上下文无关的，那么通过与正则语言（也称为正则表达式）相交，匹配的所有编译 C 程序集合
^int main\(void\) { int a+; a+ = a+; return 0; }$
将是上下文无关的，但这显然与语言 a^kba^kba^k 同构，众所周知，它不是上下文无关的。
于 2009-05-22T15:37:22.427 回答
8
根据您对问题的理解，答案会发生变化。但是 IMNSHO，正确的答案是所有现代编程语言实际上都是上下文敏感的。例如，没有上下文无关文法只接受语法正确的 C 程序。指向 C 的 yacc/bison 上下文无关语法的人没有抓住重点。
于 2011-08-02T06:50:53.430 回答
6
举一个非上下文无关语法的最引人注目的例子，据我所知，Perl 的语法是图灵完备的。
于 2009-08-18T03:14:29.610 回答
3
如果我理解您的问题，您正在寻找可以由上下文无关语法 (cfg) 描述的编程语言，以便 cfg 生成所有有效程序并且仅生成有效程序。
我相信大多数（如果不是全部）现代编程语言因此不是上下文无关的。例如，一旦您拥有用户定义的类型（在现代语言中非常常见），您就会自动对上下文敏感。
验证语法和验证程序的语义正确性是有区别的。检查语法是上下文无关的，而检查语义正确性不是（同样，在大多数语言中）。
然而，这并不意味着这种语言不存在。例如，无类型 lambda 演算可以使用上下文无关文法来描述，并且当然是图灵完备的。
于 2012-06-25T13:46:31.917 回答
2
大多数现代编程语言都不是上下文无关的语言。作为证明，如果我深入研究 CFL 的根，其对应的机器 PDA 无法处理字符串匹配，例如{ww | w is a string}. 所以大多数编程语言都需要这个。
例子：
int fa; // w
fa=1; // ww as parser treat it like this
于 2013-04-01T14:51:32.890 回答
2
于 2009-05-22T15:46:43.393 回答
0
让我们以 Swift 为例，用户可以在其中定义运算符，包括运算符优先级和关联性。例如，运算符 + 和 * 实际上是在标准库中定义的。
上下文无关语法和词法分析器可能能够解析 a + b - c * d + e，但语义是“五个操作数 a、b、c、d 和 e，由运算符 +、-、* 和 + 分隔”。这就是解析器在不了解运算符的情况下可以实现的。上下文无关文法和词法分析器也可以解析 a +-+ b -+- c，它是由运算符 +-+ 和 -+- 分隔的三个操作数 a、b 和 c。
解析器可以根据上下文无关的 Swift 语法“解析”源文件，但这还远远不够。另一个步骤是收集有关运算符的知识，然后将 a + b - c * d + e 的语义更改为与 operator+ (operator- (operator+ (a, b), operator* (c, d)) 相同， e)。
所以有（或者也许有，我没有仔细检查过）上下文无关语法，但它只能让你解析一个程序。
于 2020-09-08T22:13:54.783 回答