是C ++上下文无关还是上下文相关？ [英] Is C++ context-free or context-sensitive?
问题描述
我经常听到声称C ++是一种上下文相关的语言。以下例为例：
a b（c）;
这是一个变量定义还是一个函数声明？这取决于符号 c 的含义。如果 c 是变量，则 ab（c）; 类型 a 的code> b 。它直接用 c 初始化。但是如果 c 是类型，则 ab（c）; b 需要 c 并返回 a 。 / p>
如果查找上下文无关语言的定义，它将基本上告诉你，所有语法规则必须有左侧，只有一个非终端符号。另一方面，上下文敏感语法允许左侧的终端和非终端符号的任意字符串。
浏览C ++的附录A编程语言，我找不到一个单一的语法规则，除了一个单一的非终端符号在它的左手边。这意味着C ++是上下文无关的。 （当然，每个上下文无关的语言也是上下文敏感的，因为上下文无关语言形成上下文敏感语言的子集，但这不是一个点。）
所以，是C ++上下文无关的还是上下文相关的？
演示为什么解析C ++是（可能）图灵完成，因为它显示一个程序在句法上是正确的，如果且仅当一个给定的整数是素数。
所以我断言 C ++既不是上下文无关也不是上下文相关。
如果允许在任何产品的两侧使用任意符号序列，则在 Chomsky层次结构，它比上下文相关的语法更强大;无限制语法是图灵完成。上下文敏感（类型1）语法允许在生产的左侧的上下文的多个符号，但是相同的上下文必须出现在生产的右手侧（因此名称为上下文敏感的）。 [1]上下文相关语法相当于线性界限图灵机。
在示例程序中，素数计算可以由线性有界的图灵机执行，因此它不能完全证明图灵等值，但重要的是解析器需要执行计算以执行句法分析。它可以是任何可表达为模板实例化的计算，并且有充分的理由相信C ++模板实例化是图灵完成。例如，请参阅 Todd L. Veldhuizen的2003年论文。
无论如何，C ++可以由计算机解析，因此它可以被图灵机解析。因此，无限制语法可以识别它。实际上写这样的语法将是不切实际的，这就是为什么标准不试图这样做。 （见下文。）
某些表达式的ambiguity问题主要是一个鲱鱼。首先，歧义是特定语法的特征，而不是语言。即使一种语言可以被证明没有明确的语法，如果它可以被一个上下文无关的语法识别，它是上下文无关的。类似地，如果它不能被上下文无关语法识别，但它可以被上下文敏感的语法识别，它是上下文敏感的。歧义不相关。
但在任何情况下，如第21行（即 auto b = foo< IsPrime< 234799>> :: typen< ; 1>（）; ）在下面的程序中，表达式根本不含糊;它们根据上下文不同地被简单地解析。在问题的最简单的表达式中，某些标识符的句法类别取决于它们是如何被声明的（例如，类型和函数），这意味着形式语言必须承认这样的事实，即两个任意长度的字符串相同的程序是相同的（声明和使用）。这可以通过复制语法来建模，该语法是识别相同单词的两个连续精确副本的语法。使用抽取词义可以很容易地证明，这种语言不是上下文无关的。这种语言的上下文敏感语法是可能的，并且在这个问题的答案中提供了类型0语法： http://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language 。
如果试图写一个上下文敏感（或不受限制）的语法来解析C ++，它很可能填充宇宙的涂鸦。编写一个图灵机来解析C ++将是一个同样不可能的事情。即使写一个C ++程序也是困难的，据我所知，没有一个被证明是正确的。这就是为什么标准不试图提供一个完整的正式语法，以及为什么它选择在技术英语中写一些解析规则。
C ++语言中的语法不是C ++语言的语法的完整形式定义。它甚至不是在预处理之后的语言的完整的正式定义，这可能更容易正式化。 （那不会是语言，虽然：标准定义的C ++语言包括预处理器，并且预处理器的操作是用算法描述的，因为在任何语法形式主义中都很难描述，在那一节描述词汇分解的标准，包括必须多次应用的规则。）
各种语法（用于词法分析的两个重叠的语法，在预处理之前发生，另外，在必要时，之后，加上句法语法）被收集在附录A中，并附有这个重要的注释（重点加入）：
这个C ++语法的总结是为了帮助理解。 它不是语言的确切语句。特别地，这里描述的语法接受有效的C ++结构的超集。必须应用消歧规则（6.8,7.1,10.2）来区分表达式和声明。此外，必须使用访问控制，歧义和类型规则来清除语法上有效但无意义的结构。
最后，程序。当且仅当 IsPrime 中的N是素数时，第21行在语法上是正确的。否则， typen 是一个整数而不是模板，因此 typen< 1>（）被解析为（typen <1）>（）这在语法上不正确，因为（）不是语法有效的表达式。
模板< bool V> struct answer {answer（int）{} bool operator（）（）{return V;}};
template< bool no，bool yes，int f，int p> struct IsPrimeHelper
：IsPrimeHelper< p％f == 0，f * f> = p，f + 2，p& {};
template< bool yes，int f，int p> struct IsPrimeHelper< true，yes，f，p> {using type = answer< false> ;; };
template< int f，int p> struct IsPrimeHelper< false，true，f，p> {using type = answer< true> ;; };
template< int I>使用IsPrime = typename IsPrimeHelper<！（I& 1），false，3，I> :: type;
template< int I>
struct X {static const int i = I; int a [i]; };
template< typename A> struct foo;
template<> struct foo< answer< true>> {
template< int I>使用typen = X I;
};
模板<> struct foo< answer< false>> {
static const int typen = 0;
};
int main（）{
auto b = foo< IsPrime< 234799>> :: typen& //语法错误如果不是素数
return 0;
}
更技术上，在上下文相关语法中的每个生产必须是以下形式：
α A& &右箭头; << / c> c
A code>α ，β 可能是空的语法符号序列，γ 是非空序列。 （语法符号可以是终端或非终端）。 这可以读为 A→ γ 仅在上下文 [α]中。。在无上下文（类型2）语法中，α 和β 必须为空。
原来，你也可以用单调限制来限制语法，其中每个生产必须是以下形式：
α &右箭头; β 其中 |α | ≥ |β | > 0 （ |α | 表示α ）
可以证明单调语法所识别的语言集与上下文相关语法所识别的语言集完全相同，而且通常是case更容易基于单调语法的证明。因此，很常见的是，上下文相关用于表示单调。
I often hear claims that C++ is a context-sensitive language. Take the following example:
a b(c);
Is this a variable definition or a function declaration? That depends on the meaning of the symbol c. If c is a variable, then a b(c); defines a variable named b of type a. It is directly initialized with c. But if c is a type, then a b(c); declares a function named b that takes a c and returns an a.
If you look up the definition of context-free languages, it will basically tell you that all grammar rules must have left-hand sides that consist of exactly one non-terminal symbol. Context-sensitive grammars, on the other hand, allow arbitrary strings of terminal and non-terminal symbols on the left-hand side.
Browsing through Appendix A of "The C++ Programming Language", I couldn't find a single grammar rule that had anything else besides a single non-terminal symbol on its left-hand side. That would imply that C++ is context-free. (Of course, every context-free language is also context-sensitive in the sense that the context-free languages form a subset of the context-sensitive languages, but that is not the point.)
So, is C++ context-free or context-sensitive?
Below is my (current) favorite demonstration of why parsing C++ is (probably) Turing-complete, since it shows a program which is syntactically correct if and only if a given integer is prime.
So I assert that C++ is neither context-free nor context-sensitive.
If you allow arbitrary symbol sequences on both sides of any production, you produce an Type-0 grammar ("unrestricted") in the Chomsky hierarchy, which is more powerful than a context-sensitive grammar; unrestricted grammars are Turing-complete. A context-sensitive (Type-1) grammar allows multiple symbols of context on the left hand side of a production, but the same context must appear on the right hand side of the production (hence the name "context-sensitive"). [1] Context-sensitive grammars are equivalent to linear-bounded Turing machines.
In the example program, the prime computation could be performed by a linear-bounded Turing machine, so it does not quite prove Turing equivalence, but the important part is that the parser needs to perform the computation in order to perform syntactic analysis. It could have been any computation expressible as a template instantiation and there is every reason to believe that C++ template instantiation is Turing-complete. See, for example, Todd L. Veldhuizen's 2003 paper.
Regardless, C++ can be parsed by a computer, so it could certainly be parsed by a Turing machine. Consequently, an unrestricted grammar could recognize it. Actually writing such a grammar would be impractical, which is why the standard doesn't try to do so. (See below.)
The issue with "ambiguity" of certain expressions is mostly a red herring. To start with, ambiguity is a feature of a particular grammar, not a language. Even if a language can be proven to have no unambiguous grammars, if it can be recognized by a context-free grammar, it's context-free. Similarly, if it cannot be recognized by a context-free grammar but it can be recognized by a context-sensitive grammar, it's context-sensitive. Ambiguity is not relevant.
But in any event, like line 21 (i.e. auto b = foo<IsPrime<234799>>::typen<1>();) in the program below, the expressions are not ambiguous at all; they are simply parsed differently depending on context. In the simplest expression of the issue, the syntactic category of certain identifiers is dependent on how they have been declared (types and functions, for example), which means that the formal language would have to recognize the fact that two arbitrary-length strings in the same program are identical (declaration and use). This can be modelled by the "copy" grammar, which is the grammar which recognizes two consecutive exact copies of the same word. It's easy to prove with the pumping lemma that this language is not context-free. A context-sensitive grammar for this language is possible, and a Type-0 grammar is provided in the answer to this question: http://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language .
If one were to attempt to write a context-sensitive (or unrestricted) grammar to parse C++, it would quite possibly fill the universe with scribblings. Writing a Turing machine to parse C++ would be an equally impossible undertaking. Even writing a C++ program is difficult, and as far as I know none have been proven correct. This is why the standard does not attempt to provide a complete formal grammar, and why it chooses to write some of the parsing rules in technical English.
What looks like a formal grammar in the C++ standard is not the complete formal definition of the syntax of the C++ language. It's not even the complete formal definition of the language after preprocessing, which might be easier to formalize. (That wouldn't be the language, though: the C++ language as defined by the standard includes the preprocessor, and the operation of the preprocessor is described algorithmically since it would be extremely hard to describe in any grammatical formalism. It is in that section of the standard where lexical decomposition is described, including the rules where it must be applied more than once.)
The various grammars (two overlapping grammars for lexical analysis, one which takes place before preprocessing and the other, if necessary, afterwards, plus the "syntactic" grammar) are collected in Appendix A, with this important note (emphasis added):
This summary of C++ syntax is intended to be an aid to comprehension. It is not an exact statement of the language. In particular, the grammar described here accepts a superset of valid C++ constructs. Disambiguation rules (6.8, 7.1, 10.2) must be applied to distinguish expressions from declarations. Further, access control, ambiguity, and type rules must be used to weed out syntactically valid but meaningless constructs.
Finally, here's the promised program. Line 21 is syntactically correct if and only if the N in IsPrime<N> is prime. Otherwise, typen is an integer, not a template, so typen<1>() is parsed as (typen<1)>() which is syntactically incorrect because () is not a syntactically valid expression.
template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};
template<bool no, bool yes, int f, int p> struct IsPrimeHelper
: IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };
template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; };
template<typename A> struct foo;
template<>struct foo<answer<true>>{
template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
static const int typen = 0;
};
int main() {
auto b = foo<IsPrime<234799>>::typen<1>(); // Syntax error if not prime
return 0;
}
[1] To put it more technically, every production in a context-sensitive grammar must be of the form:
αAβ → αγβ
where A is a non-terminal and α, β are possibly empty sequences of grammar symbols, and γ is a non-empty sequence. (Grammar symbols may be either terminals or non-terminals).
This can be read as A → γ only in the context [α, β]. In a context-free (Type 2) grammar, α and β must be empty.
It turns out that you can also restrict grammars with the "monotonic" restriction, where every production must be of the form:
α → β where |α| ≥ |β| > 0 (|α| means "the length of α")
It's possible to prove that the set of languages recognized by monotonic grammars is exactly the same as the set of languages recognized by context-sensitive grammars, and it's often the case that it's easier to base proofs on monotonic grammars. Consequently, it's pretty common to see "context-sensitive" used as though it meant "monotonic".
这篇关于是C ++上下文无关还是上下文相关？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
