哪些编程语言是无上下文的？ [英] What programming languages are context-free?

问题描述

或者，更准确地说：哪种编程语言是由上下文无关的语法定义的？

Or, to be a little more precise: which programming languages are defined by a context-free grammar?

根据我的收集，C ++并非上下文无关的诸如宏和模板之类的东西。我的直觉告诉我，功能语言可能是上下文无关的，但是我没有任何硬数据可以支持。

From what I gather C++ is not context-free due to things like macros and templates. My gut tells me that functional languages might be context free, but I don't have any hard data to back that up with.

简洁的示例的额外代表:-)

Extra rep for concise examples :-)

推荐答案

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

The set of programs that are syntactically correct is context-free for almost all languages.

几乎所有语言的编译程序集都不是上下文无关的。例如，如果所有编译的C程序的集合都是上下文无关的，则通过与常规语言（也称为正则表达式）相交，可以找到与所有匹配的所有编译的C程序集合

The set of programs that compile is not context-free for almost all languages. For example, if the set of all compiling C programs were context free, then by intersecting with a regular language (also known as a regex), the set of all compiling C programs that match

^int main\(void\) { int a+; a+ = a+; return 0; }$

将不受上下文限制，但这显然与a ^ kba ^ kba语言同构^ k，这是众所周知的 not 与上下文无关。

would be context-free, but this is clearly isomorphic to the language a^kba^kba^k, which is well-known not to be context-free.

这篇关于哪些编程语言是无上下文的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！