c++是上下文无关的还是上下文敏感的?

我经常听到有人说c++是一种上下文敏感的语言。举个例子:

a b(c);

这是变量定义还是函数声明?这取决于符号c的含义。如果c是c1，那么a b(c);定义了一个名为b的类型为a的变量。它直接用c初始化。但如果c是c2，则a b(c);声明一个名为b的函数，该函数接受c并返回a。

如果您查找上下文无关语言的定义，它基本上会告诉您，所有语法规则的左侧必须恰好包含一个非终结符。另一方面，上下文敏感语法允许在左侧使用任意的终结符和非终结符字符串。

浏览“c++程序设计语言”的附录A，我找不到一条语法规则，它的左边除了一个非终结符之外，还有其他任何东西。这意味着c++是上下文无关的。(当然，每一种与上下文无关的语言也是与上下文相关的，因为与上下文无关的语言构成了与上下文相关的语言的一个子集，但这不是重点。)

那么，c++是上下文无关的还是上下文敏感的?

70976 次浏览
小开

真正的:)

斯坦利·沃福德。计算机系统。页341 - 346。

小开

使用GLR解析器解析c++。这意味着在解析源代码期间，解析器五月遇到歧义，但它应该继续并决定使用哪个语法规则晚些时候。

还看,

为什么c++不能用LR(1)解析器解析?< / >

记住上下文无关语法不能描述了编程语言语法的规则。例如，属性语法用于检查表达式类型的有效性。

int x;
x = 9 + 1.0;
You 不能用上下文无关语法描述以下规则: 赋值的右边应该与左边的类型相同

小开

c++不是上下文无关的。我以前在编译器课上学过。快速搜索得到了这个链接，其中“语法或语义”部分解释了为什么C和c++不是上下文无关的:

Wikipedia Talk: Context-Free grammar

< br > < p >问候, Ovanes < / p >
小开

是的。下面的表达式根据类型解析上下文有不同的操作顺序:

编辑:当实际操作顺序发生变化时，使用“常规”编译器在修饰AST(传播类型信息)之前解析未修饰的AST会变得非常困难。与此相比，提到的其他上下文敏感的事情“相当容易”(并不是说模板计算一点都不容易)。

#if FIRST_MEANING
template<bool B>
class foo
{ };
#else
static const int foo = 0;
static const int bar = 15;
#endif

紧随其后的是:

static int foobar( foo < 2 ? 1 < 1 : 0 > & bar );
小开

有时候更糟:当人们说c++有“不可判定语法”时，他们的意思是什么?

小开

你可能想看看Bjarne Stroustrup的设计&c++的发展。在这篇文章中，他描述了他在尝试使用yacc(或类似的)来解析早期版本的c++时遇到的问题，并希望他当时使用的是递归下降。

小开

显然，如果逐字逐句地回答这个问题，几乎所有带有标识符的语言都是上下文敏感的。

一个人需要知道一个标识符是一个类型名(一个类名，一个由typedef引入的名字，一个typename模板参数)，一个模板名还是其他一些名称，以便能够正确地使用标识符。例如:

x = (name)(expression);

如果name是类型名，则为类型转换;如果name是函数名，则为函数调用。另一种情况是所谓的“最恼人的解析”，其中不可能区分变量定义和函数声明(有一个规则说它是函数声明)。

这一困难引入了typename和template具有依赖名称的需求。据我所知，c++的其余部分不是上下文敏感的(也就是说，可以为它编写上下文无关的语法)。

小开

Meta-S”是Quinn Tyler Jackson开发的上下文敏感解析引擎。我没有用过，但他讲了一个令人印象深刻的故事。在comp.compilers中查看他的评论，并查看rnaparse.com/MetaS%20defined.htm - Ira Baxter 7月25日10:42

正确的链接是解析enigines

Meta-S是一家已经倒闭的tho栖公司的财产。我可以将Meta-S的免费副本发送给任何感兴趣的人，我已经在rna解析研究中使用了它。请注意，示例文件夹中包含的“伪结语法”是由一个非生物信息学的、成熟的程序员编写的，基本上不起作用。我的语法采用了一种不同的方法，而且效果很好。

小开

c++模板已经被证明是图灵强大的。虽然不是正式的参考资料，但从这方面来看，我们可以从以下几个方面入手:

http://cpptruths.blogspot.com/2005/11/c-templates-are-turing-complete.html

我大胆地猜测一下(古老的民间和简明的CACM证明表明，60年代的ALGOL不能用CFG表示)，并说c++因此不能仅用CFG正确地解析。cfg与各种TP机制结合在一起，无论是在树通道还是在减少事件中——这是另一个故事。一般来说，由于停止问题，存在一些c++程序不能被证明是正确的/不正确的，但仍然是正确的/不正确的。

{PS-作为Meta-S的作者(上面有几个人提到过)，我可以很肯定地说Thothic并没有消失，也不是免费的软件。也许我这样回答是为了不被删除或被投票降至-3。

小开

是的，c++是上下文敏感的，非常上下文敏感。您不能通过使用上下文无关的解析器简单地解析文件来构建语法树，因为在某些情况下，您需要从以前的知识中了解符号来决定(例如。在解析时构建一个符号表)。

第一个例子:

A*B;

这是一个乘法表达式吗?

或

这是声明B变量为A类型的指针吗?

如果A是一个变量，那么它就是一个表达式，如果A是类型，它就是一个指针声明。

第二个例子:

A B(bar);

这是一个函数原型接受bar类型的参数吗?

或

是否声明类型为A的变量B，并调用A的构造函数，将bar常量作为初始化项?

你需要再次知道bar是一个变量还是符号表中的类型。

第三个例子:

class Foo
{
public:
void fn(){x*y;}
int x, y;
};

当解析时构建符号表没有帮助时，就是这种情况，因为x和y的声明在函数定义之后。因此，您需要首先浏览类定义，然后在第二步查看方法定义，以确定x*y是一个表达式，而不是指针声明或其他东西。

小开

它是上下文敏感的，因为a b(c);有两个有效的解析——声明和变量。当你说“If c是一个类型”时，这就是上下文，就在那里，你已经准确地描述了c++对它的敏感程度。如果你没有“c是什么?”的上下文，你就不能明确地解析它。

在这里，上下文通过标记的选择来表示——如果标识符指定了类型，解析器将其读取为typename标记。这是最简单的解决方案，避免了上下文敏感的复杂性(在本例中)。

编辑:当然，还有更多的上下文敏感性问题，我只是关注你展示的那个。模板在这方面尤其糟糕。

小开
最佳答案

下面是我(目前)最喜欢的演示，说明为什么解析c++(可能)是turing，因为它显示了当且仅当给定整数为素数时语法正确的程序。

因此，我断言c++既不是上下文无关的，也不是上下文敏感的。

如果在任意结果的两边允许任意符号序列，则在乔姆斯基层次结构中生成Type-0语法("unrestricted")，这比上下文敏感语法更强大;无限制语法是图灵完备的。上下文敏感型(Type-1)语法允许在产物的左侧出现多个上下文符号，但必须在产物的右侧出现相同的上下文(因此称为“上下文敏感型”)。[1]上下文敏感语法等价于线性有界图灵机。

在示例程序中，质数计算可以由线性有界的图灵机执行，因此它不能完全证明图灵等价，但重要的部分是解析器需要执行计算以便执行语法分析。它可以是任何可以表示为模板实例化的计算，并且有充分的理由相信c++模板实例化是图灵完备的。例如，参见Todd L. Veldhuizen 2003年的论文。

不管怎样，c++可以被计算机解析，所以它当然可以被图灵机解析。因此，不受限制的语法可以识别它。实际上，编写这样的语法是不切实际的，这就是标准没有尝试这样做的原因。(见下文)。

某些表达的“模糊性”问题主要是转移注意力。首先，歧义是一种特定语法的特征，而不是一种语言。即使一种语言可以被证明没有明确的语法，如果它可以被上下文无关的语法识别，那么它就是上下文无关的。类似地，如果它不能被上下文无关的语法识别，但可以被上下文敏感的语法识别，那么它就是上下文敏感的。模棱两可无关紧要。

但在任何情况下，就像下面程序中的第21行(即auto b = foo<IsPrime<234799>>::typen<1>();)一样，表达式根本就不是二义性的;它们只是根据上下文进行不同的解析。在这个问题的最简单的表达式中，某些标识符的语法类别取决于它们是如何声明的(例如类型和函数)，这意味着形式语言必须识别同一程序中两个任意长度的字符串是相同的这一事实(声明和使用)。这可以通过“copy”语法来建模，该语法可以识别同一个单词的两个连续的精确副本。用泵引理很容易证明这种语言不是上下文无关的。这种语言可以使用上下文敏感的语法，并且在这个问题的答案中提供了Type-0语法:https://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>中的N是质数时，第21行在语法上是正确的。否则，typen是一个整数，而不是一个模板，因此typen<1>()被解析为(typen<1)>()，这是语法不正确的，因为()不是一个语法有效的表达式。

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;
}

更专业地说，上下文敏感语法中的每个结果都必须是这样的:

αAβ → αγβ

其中A是非终结符，α， β可能是语法符号的空序列，而γ是非空序列。(语法符号可以是终结符也可以是非终结符)。

这只能在上下文[α, β]中读取为A → γ。在上下文无关(类型2)语法中，α和β必须为空。

事实证明，你也可以用“单调”限制语法，其中每个结果必须是这样的形式:

α → β其中|α| ≥ |β| > 0  (|α|表示“α的长度”)

可以证明单调语法所识别的语言集与上下文敏感语法所识别的语言集完全相同，而且通常更容易将证明建立在单调语法的基础上。因此，我们经常看到“上下文敏感”被当作“单调”的意思来使用。

小开

我感觉在“上下文敏感”的正式定义和“上下文敏感”的非正式使用之间存在一些混淆。前者有明确的含义。后者用于表示“为了解析输入，您需要上下文”。

这里也问了这个问题: 上下文敏感性vs模糊性 . < / p >

这是一个与上下文无关的语法:

<a> ::= <b> | <c>
<b> ::= "x"
<c> ::= "x"

它是模棱两可的，所以为了解析输入“x”，你需要一些上下文(或者忍受这种模棱两可，或者发出“警告:E8271 - input is ambiguous in line 115”)。但它肯定不是上下文敏感的语法。

小开

首先，你正确地观察到c++标准末尾的语法中没有上下文敏感的规则，因此语法是与上下文无关。

然而，这种语法并不能精确地描述c++语言，因为它生成的是非c++程序，例如

int m() { m++; }

或

typedef static int int;

c++语言被定义为“一组格式良好的c++程序”，它不是与上下文无关的(可以证明，仅仅要求声明变量就可以做到这一点)。理论上，您可以在模板中编写图灵完备程序，并根据其结果使程序具有病态形式，因此它甚至不是上下文敏感的。

现在，(无知的)人们(通常不是语言理论家，而是解析器设计者)通常在以下一些含义中使用“not context-free”

  • 模棱两可的
  • 不能用Bison解析
  • 而不是LL(k) LR(k) LALR(k)或任何他们选择的解析器定义的语言类

标准后面的语法不满足这些类别(即它是模糊的，不是LL(k)…)，所以c++语法对他们来说“不是上下文无关的”。从某种意义上说，他们是对的，要创建一个工作的c++解析器是非常困难的。

注意，这里使用的属性只与上下文无关的语言有微弱的联系——歧义与上下文无关没有任何关系(事实上，上下文敏感的规则通常有助于消除歧义)，另外两个只是上下文无关语言的子集。解析与上下文无关的语言不是一个线性过程(尽管解析确定性语言是)。

小开

要回答你的问题，你需要区分两个不同的问题。

  1. 几乎每一种编程语言的语法都与上下文无关。通常，它是作为扩展的Backus-Naur形式或上下文无关语法给出的。

  2. 然而，即使程序符合编程语言定义的上下文无关语法，它也不一定是valid程序。为了成为一个有效的程序，程序必须满足许多与上下文无关的属性。例如，最简单的属性是变量的作用域。

综上所述，c++是否与上下文无关取决于你问的问题。

小开

没有一种类algol语言是与上下文无关的，因为它们有规则约束表达式和语句，标识符可以根据它们的类型出现在这些表达式和语句中，并且因为在声明和使用之间可以出现的语句数量没有限制。

通常的解决方案是编写一个上下文无关的解析器，它实际上接受有效程序的超集，并将上下文敏感的部分放在附加到规则的特别的“语义”代码中。

c++的图灵完备模板系统远远超越了这一点。看到堆栈溢出问题794015。

小开

c++标准中的结果是与上下文无关的，但正如我们所知，它并没有真正精确地定义语言。大多数人认为当前语言中的一些歧义可以(我相信)用上下文敏感的语法明确地解决。

对于最明显的例子，让我们考虑最恼人的解析:int f(X);。如果X是一个值，则将f定义为一个将用X初始化的变量。如果X是一个类型，它将f定义为一个接受单个类型X形参的函数。

从语法的角度来看，我们可以这样看:

A variable_decl ::= <type> <identifier> '(' initializer ')' ';'


B function_decl ::= <type> <identifier> '(' param_decl ')' ';'


A ::= [declaration of X as value]
B ::= [declaration of X as type]

当然，为了完全正确，我们需要添加一些额外的“东西”来解释其他类型的介入声明的可能性(即，A和B都应该是“声明，包括将X声明为…”，或者类似的顺序)。

这与典型的CSG还是有很大不同的(至少在我印象中是这样)。这取决于正在构造的符号表——这个部分专门将X识别为类型或值，而不仅仅是在此之前的某种类型的语句，而是正确的符号/标识符的正确语句类型。

因此，我必须做一些研究来确定，但我的直接猜测是，这并不是真正的CSG，至少从通常使用的术语来看是这样的。

小开

非上下文无关语法最简单的例子是解析包含模板的表达式。

a<b<c>()

这可以解析为任意一种

template
|
a < expr > ()
|
<
/   \
b     c

或

 expr
|
<
/   \
a   template
|
b < expr > ()
|
c

这两个AST只能通过检查'a'的声明来消除歧义——如果'a'是模板，则前者为AST，如果'a'不是模板，则后者为AST。

小开

这个答案说c++不是上下文无关的…有一个暗示(不是由回答者)，它不能被解析，并且回答提供了一个困难的代码示例，如果某个常量不是质数，就会产生一个无效的c++程序。

正如其他人观察到的，关于语言是否上下文敏感/自由的问题与关于特定语法的相同问题是不同的。

为了解决可解析性的问题，我提供了经验证据，证明c++中有可以使用的上下文无关语法 生成一个AST，用于源文本的上下文无关的解析 实际上，通过使用现有的基于glr -parser的工具进行解析，该工具由显式语法驱动

是的，它的成功在于“接受太多”;并不是它接受的所有东西都是有效的c++程序，这就是为什么它后面会有额外的检查(类型检查)。是的，类型检查器可能会遇到可计算性问题。在实践中，工具没有这个问题;如果人们编写这样的程序，没有人会编译。(我认为标准实际上限制了展开模板的计算量，所以实际上计算量是有限的，但可能相当大)。

如果你的意思是，确定源程序是否是成员 的集合有效的c++源程序，那么我将同意 问题就难多了。但这不是解析的问题 该工具通过隔离解析和类型检查来解决这个问题 解析后的程序。(这里有多种解释 在没有上下文的情况下，它记录一个模棱两可节点 在解析树中有几个可能的解析;类型 检查决定哪一个是正确的，并消除无效的 子树)。你可以在下面的例子中看到一个(部分的)解析树;整棵树太大了，无法容纳一个SO答案。注意，无论使用值234797还是234799，你都会得到一个解析树

在原始值为234799的AST上运行工具的名称/类型解析器成功。如果值为234797，名称解析器将失败(正如预期的那样)，并给出错误消息“typen不是类型”，因此该版本不是有效的c++程序。

967 tree nodes in tree.
15 ambiguity nodes in tree.
(translation_unit@Cpp~GCC5=2#6b11a20^0 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
(declaration_seq@Cpp~GCC5=1021#6b06640^1#6b11a20:1 {10} Line 1 Column 1 File C:/temp/prime_with_templates.cpp
(pp_declaration_seq@Cpp~GCC5=1022#6b049a0^1#6b06640:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
(declaration@Cpp~GCC5=1036#6b04980^1#6b049a0:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
|(template_declaration@Cpp~GCC5=2079#6b04960^1#6b04980:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
| (template_parameter_list@Cpp~GCC5=2082#6afbde0^1#6b04960:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
|  (template_parameter@Cpp~GCC5=2085#6afbd80^1#6afbde0:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
|   (parameter_declaration@Cpp~GCC5=1611#6afbd40^1#6afbd80:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
|   |(basic_decl_specifier_seq@Cpp~GCC5=1070#6afb880^1#6afbd40:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
|   | (decl_specifier@Cpp~GCC5=1073#6afb840^1#6afb880:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
|   |  (trailing_type_specifier@Cpp~GCC5=1118#6afb7e0^1#6afb840:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
|   |   (simple_type_specifier@Cpp~GCC5=1138#6afb7a0^1#6afb7e0:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp)simple_type_specifier
|   |  )trailing_type_specifier#6afb7e0
|   | )decl_specifier#6afb840
|   |)basic_decl_specifier_seq#6afb880
|   |(ptr_declarator@Cpp~GCC5=1417#6afbc40^1#6afbd40:2 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
|   | (noptr_declarator@Cpp~GCC5=1421#6afbba0^1#6afbc40:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
|   |  (declarator_id@Cpp~GCC5=1487#6afbb80^1#6afbba0:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
|   |   (id_expression@Cpp~GCC5=317#6afbaa0^1#6afbb80:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
|   |   |(unqualified_id@Cpp~GCC5=319#6afb9c0^1#6afbaa0:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
|   |   | (IDENTIFIER@Cpp~GCC5=3368#6afb780^1#6afb9c0:1[`V'] Line 1 Column 15 File C:/temp/prime_with_templates.cpp)IDENTIFIER
|   |   |)unqualified_id#6afb9c0
|   |   )id_expression#6afbaa0
|   |  )declarator_id#6afbb80
|   | )noptr_declarator#6afbba0
|   |)ptr_declarator#6afbc40
|   )parameter_declaration#6afbd40
|  )template_parameter#6afbd80
| )template_parameter_list#6afbde0
| (declaration@Cpp~GCC5=1033#6b04940^1#6b04960:2 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
|  (block_declaration@Cpp~GCC5=1050#6b04920^1#6b04940:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
|   (simple_declaration@Cpp~GCC5=1060#6b04900^1#6b04920:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
|   |(basic_decl_specifier_seq@Cpp~GCC5=1070#6b048e0^1#6b04900:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
|   | (decl_specifier@Cpp~GCC5=1073#6b048c0^1#6b048e0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
|   |  (type_specifier@Cpp~GCC5=1110#6b048a0^1#6b048c0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
|   |   (class_specifier@Cpp~GCC5=1761#6b04880^1#6b048a0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
|   |   |(class_head@Cpp~GCC5=1763#6afb980^1#6b04880:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
|   |   | (class_key@Cpp~GCC5=1791#6afbca0^1#6afb980:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp)class_key
|   |   | (IDENTIFIER@Cpp~GCC5=3368#6afbcc0^1#6afb980:2[`answer'] Line 1 Column 25 File C:/temp/prime_with_templates.cpp)IDENTIFIER
|   |   | (optional_base_clause@Cpp~GCC5=1872#6afba60^1#6afb980:3 Line 1 Column 32 File C:/temp/prime_with_templates.cpp)optional_base_clause
|   |   |)class_head#6afb980
|   |   |(member_specification@Cpp~GCC5=1794#6b042e0^1#6b04880:2 {2} Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   | (member_declaration_or_access_specifier@Cpp~GCC5=1806#6b04060^1#6b042e0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |  (member_declaration@Cpp~GCC5=1822#6b04040^1#6b04060:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   (function_definition@Cpp~GCC5=1632#6b04020^1#6b04040:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   |(function_head@Cpp~GCC5=1673#6afbec0^1#6b04020:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   | (ptr_declarator@Cpp~GCC5=1417#6afbfe0^1#6afbec0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   |  (noptr_declarator@Cpp~GCC5=1422#6afbf80^1#6afbfe0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   |   (noptr_declarator@Cpp~GCC5=1421#6afbf60^1#6afbf80:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   |   |(declarator_id@Cpp~GCC5=1487#6afbea0^1#6afbf60:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   |   | (id_expression@Cpp~GCC5=317#6afbb40^1#6afbea0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   |   |  (unqualified_id@Cpp~GCC5=319#6afbc80^1#6afbb40:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   (IDENTIFIER@Cpp~GCC5=3368#6afbc20^1#6afbc80:1[`answer'] Line 1 Column 34 File C:/temp/prime_with_templates.cpp)IDENTIFIER
|   |   |   |   |  )unqualified_id#6afbc80
|   |   |   |   | )id_expression#6afbb40
|   |   |   |   |)declarator_id#6afbea0
|   |   |   |   )noptr_declarator#6afbf60
|   |   |   |   (parameter_declaration_clause@Cpp~GCC5=1559#6afbd00^1#6afbf80:2 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
|   |   |   |   |(pp_parameter_declaration_list@Cpp~GCC5=1570#6afb940^1#6afbd00:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
|   |   |   |   | (pp_parameter_declaration_seq@Cpp~GCC5=1574#6afb800^1#6afb940:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
|   |   |   |   |  (parameter_declaration@Cpp~GCC5=1610#6afb9a0^1#6afb800:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   (basic_decl_specifier_seq@Cpp~GCC5=1070#6afbf40^1#6afb9a0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   |(decl_specifier@Cpp~GCC5=1073#6afbfa0^1#6afbf40:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   | (trailing_type_specifier@Cpp~GCC5=1118#6afbfc0^1#6afbfa0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   |  (simple_type_specifier@Cpp~GCC5=1140#6afb860^1#6afbfc0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp)simple_type_specifier
|   |   |   |   |   | )trailing_type_specifier#6afbfc0
|   |   |   |   |   |)decl_specifier#6afbfa0
|   |   |   |   |   )basic_decl_specifier_seq#6afbf40
|   |   |   |   |  )parameter_declaration#6afb9a0
|   |   |   |   | )pp_parameter_declaration_seq#6afb800
|   |   |   |   |)pp_parameter_declaration_list#6afb940
|   |   |   |   )parameter_declaration_clause#6afbd00
|   |   |   |   (function_qualifiers@Cpp~GCC5=1438#6afbce0^1#6afbf80:3 Line 1 Column 46 File C:/temp/prime_with_templates.cpp)function_qualifiers
|   |   |   |  )noptr_declarator#6afbf80
|   |   |   | )ptr_declarator#6afbfe0
|   |   |   |)function_head#6afbec0
|   |   |   |(function_body@Cpp~GCC5=1680#6b04000^1#6b04020:2 Line 1 Column 46 File C:/temp/prime_with_templates.cpp
|   |   |   | (compound_statement@Cpp~GCC5=888#6afbee0^1#6b04000:1 Line 1 Column 46 File C:/temp/prime_with_templates.cpp)compound_statement
|   |   |   |)function_body#6b04000
|   |   |   )function_definition#6b04020
|   |   |  )member_declaration#6b04040
|   |   | )member_declaration_or_access_specifier#6b04060
|   |   | (member_declaration_or_access_specifier@Cpp~GCC5=1806#6b042c0^1#6b042e0:2 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
|   |   |  (member_declaration@Cpp~GCC5=1822#6b04820^1#6b042c0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
|   |   |   (function_definition@Cpp~GCC5=1632#6b04280^1#6b04820:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
|   |   |   |(function_head@Cpp~GCC5=1674#6b04220^1#6b04280:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
|   |   |   | (basic_decl_specifier_seq@Cpp~GCC5=1070#6b040e0^1#6b04220:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
|   |   |   |  (decl_specifier@Cpp~GCC5=1073#6b040c0^1#6b040e0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
|   |   |   |   (trailing_type_specifier@Cpp~GCC5=1118#6b040a0^1#6b040c0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
|   |   |   |   |(simple_type_specifier@Cpp~GCC5=1138#6b04080^1#6b040a0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp)simple_type_specifier
|   |   |   |   )trailing_type_specifier#6b040a0
|   |   |   |  )decl_specifier#6b040c0
|   |   |   | )basic_decl_specifier_seq#6b040e0
|   |   |   | (ptr_declarator@Cpp~GCC5=1417#6b04200^1#6b04220:2 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
|   |   |   |  (noptr_declarator@Cpp~GCC5=1422#6b041e0^1#6b04200:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
|   |   |   |   (noptr_declarator@Cpp~GCC5=1421#6b041a0^1#6b041e0:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
|   |   |   |   |(declarator_id@Cpp~GCC5=1487#6b04180^1#6b041a0:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
|   |   |   |   | (id_expression@Cpp~GCC5=317#6b04160^1#6b04180:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
|   |   |   |   |  (unqualified_id@Cpp~GCC5=320#6b04140^1#6b04160:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   (operator_function_id@Cpp~GCC5=2027#6b04120^1#6b04140:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   |(operator@Cpp~GCC5=2070#6b04100^1#6b04120:1 Line 1 Column 62 File C:/temp/prime_with_templates.cpp)operator
|   |   |   |   |   )operator_function_id#6b04120
|   |   |   |   |  )unqualified_id#6b04140
|   |   |   |   | )id_expression#6b04160
|   |   |   |   |)declarator_id#6b04180
|   |   |   |   )noptr_declarator#6b041a0
|   |   |   |   (parameter_declaration_clause@Cpp~GCC5=1558#6afba40^1#6b041e0:2 Line 1 Column 65 File C:/temp/prime_with_templates.cpp)parameter_declaration_clause
|   |   |   |   (function_qualifiers@Cpp~GCC5=1438#6b041c0^1#6b041e0:3 Line 1 Column 66 File C:/temp/prime_with_templates.cpp)function_qualifiers
|   |   |   |  )noptr_declarator#6b041e0
|   |   |   | )ptr_declarator#6b04200
|   |   |   |)function_head#6b04220
|   |   |   |(function_body@Cpp~GCC5=1680#6b04300^1#6b04280:2 Line 1 Column 66 File C:/temp/prime_with_templates.cpp
|   |   |   | (compound_statement@Cpp~GCC5=889#6b04760^1#6b04300:1 Line 1 Column 66 File C:/temp/prime_with_templates.cpp
|   |   |   |  (pp_statement_seq@Cpp~GCC5=894#6b04780^1#6b04760:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
|   |   |   |   (statement@Cpp~GCC5=857#6b04440^1#6b04780:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
|   |   |   |   |(jump_statement@Cpp~GCC5=1011#6afba80^1#6b04440:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
|   |   |   |   | (pm_expression@Cpp~GCC5=551#6b04380^1#6afba80:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
|   |   |   |   |  (cast_expression@Cpp~GCC5=543#6b04360^1#6b04380:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   (unary_expression@Cpp~GCC5=465#6b04340^1#6b04360:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   |(primary_expression@Cpp~GCC5=307#6b04320^1#6b04340:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   | (id_expression@Cpp~GCC5=317#6b042a0^1#6b04320:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   |  (unqualified_id@Cpp~GCC5=319#6b04260^1#6b042a0:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
|   |   |   |   |   |   (IDENTIFIER@Cpp~GCC5=3368#6b04240^1#6b04260:1[`V'] Line 1 Column 74 File C:/temp/prime_with_templates.cpp)IDENTIFIER
|   |   |   |   |   |  )unqualified_id#6b04260
|   |   |   |   |   | )id_expression#6b042a0
|   |   |   |   |   |)primary_expression#6b04320
|   |   |   |   |   )unary_expression#6b04340
|   |   |   |   |  )cast_expression#6b04360
|   |   |   |   | )pm_expression#6b04380
|   |   |   |   |)jump_statement#6afba80
|   |   |   |   )statement#6b04440
|   |   |   |  )pp_statement_seq#6b04780
|   |   |   | )compound_statement#6b04760
|   |   |   |)function_body#6b04300
|   |   |   )function_definition#6b04280
|   |   |  )member_declaration#6b04820
|   |   | )member_declaration_or_access_specifier#6b042c0
|   |   |)member_specification#6b042e0
|   |   )class_specifier#6b04880
|   |  )type_specifier#6b048a0
|   | )decl_specifier#6b048c0
|   |)basic_decl_specifier_seq#6b048e0
|   )simple_declaration#6b04900
|  )block_declaration#6b04920
| )declaration#6b04940
|)template_declaration#6b04960
)declaration#6b04980
)pp_declaration_seq#6b049a0
(pp_declaration_seq@Cpp~GCC5=1022#6b06620^1#6b06640:2 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
(declaration@Cpp~GCC5=1036#6b06600^1#6b06620:1 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
|(template_declaration@Cpp~GCC5=2079#6b065e0^1#6b06600:1 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
| (template_parameter_list@Cpp~GCC5=2083#6b05460^1#6b065e0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|  (template_parameter_list@Cpp~GCC5=2083#6b05140^1#6b05460:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|   (template_parameter_list@Cpp~GCC5=2083#6b04ee0^1#6b05140:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|   |(template_parameter_list@Cpp~GCC5=2082#6b04cc0^1#6b04ee0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|   | (template_parameter@Cpp~GCC5=2085#6b04ca0^1#6b04cc0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|   |  (parameter_declaration@Cpp~GCC5=1611#6b04c80^1#6b04ca0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|   |   (basic_decl_specifier_seq@Cpp~GCC5=1070#6b04a40^1#6b04c80:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|   |   |(decl_specifier@Cpp~GCC5=1073#6b04a20^1#6b04a40:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|   |   | (trailing_type_specifier@Cpp~GCC5=1118#6b04a00^1#6b04a20:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
|   |   |  (simple_type_specifier@Cpp~GCC5=1138#6b049e0^1#6b04a00:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp)simple_type_specifier
|   |   | )trailing_type_specifier#6b04a00
|   |   |)decl_specifier#6b04a20
|   |   )basic_decl_specifier_seq#6b04a40
|   |   (ptr_declarator@Cpp~GCC5=1417#6b04c40^1#6b04c80:2 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
|   |   |(noptr_declarator@Cpp~GCC5=1421#6b04be0^1#6b04c40:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
|   |   | (declarator_id@Cpp~GCC5=1487#6b04bc0^1#6b04be0:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
|   |   |  (id_expression@Cpp~GCC5=317#6b04b60^1#6b04bc0:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
|   |   |   (unqualified_id@Cpp~GCC5=319#6b04ac0^1#6b04b60:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
|   |   |   |(IDENTIFIER@Cpp~GCC5=3368#6b049c0^1#6b04ac0:1[`no'] Line 3 Column 15 File C:/temp/prime_with_templates.cpp)IDENTIFIER
|   |   |   )unqualified_id#6b04ac0
|   |   |  )id_expression#6b04b60
|   |   | )declarator_id#6b04bc0
|   |   |)noptr_declarator#6b04be0
|   |   )ptr_declarator#6b04c40
|   |  )parameter_declaration#6b04c80
|   | )template_parameter#6b04ca0
|   |)template_parameter_list#6b04cc0
|   |(template_parameter@Cpp~GCC5=2085#6b04ec0^1#6b04ee0:2 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
|   | (parameter_declaration@Cpp~GCC5=1611#6b04ea0^1#6b04ec0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
|   |  (basic_decl_specifier_seq@Cpp~GCC5=1070#6b04b40^1#6b04ea0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
|   |   (decl_specifier@Cpp~GCC5=1073#6b04ba0^1#6b04b40:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
|   |   |(trailing_type_specifier@Cpp~GCC5=1118#6b04c60^1#6b04ba0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
|   |   | (simple_type_specifier@Cpp~GCC5=1138#6b04580^1#6b04c60:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp)simple_type_specifier
|   |   |)trailing_type_specifier#6b04c60
|   |   )decl_specifier#6b04ba0
|   |  )basic_decl_specifier_seq#6b04b40
|   |  (ptr_declarator@Cpp~GCC5=1417#6b04e60^1#6b04ea0:2 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
|   |   (noptr_declarator@Cpp~GCC5=1421#6b04e40^1#6b04e60:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
|   |   |(declarator_id@Cpp~GCC5=1487#6b04de0^1#6b04e40:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
|   |   | (id_expression@Cpp~GCC5=317#6b04d80^1#6b04de0:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
|   |   |  (unqualified_id@Cpp~GCC5=319#6b04ce0^1#6b04d80:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
|   |   |   (IDENTIFIER@Cpp~GCC5=3368#6b04560^1#6b04ce0:1[`yes'] Line 3 Column 24 File C:/temp/prime_with_templates.cpp)IDENTIFIER
|   |   |  )unqualified_id#6b04ce0
|   |   | )id_expression#6b04d80
|   |   |)declarator_id#6b04de0
|   |   )noptr_declarator#6b04e40
|   |  )ptr_declarator#6b04e60
|   | )parameter_declaration#6b04ea0
|   |)template_parameter#6b04ec0
|   )template_parameter_list#6b04ee0
|   (template_parameter@Cpp~GCC5=2085#6b05120^1#6b05140:2 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
|   |(parameter_declaration@Cpp~GCC5=1611#6b05100^1#6b05120:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
|   | (basic_decl_specifier_seq@Cpp~GCC5=1070#6b04d20^1#6b05100:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
|   |  (decl_specifier@Cpp~GCC5=1073#6b04dc0^1#6b04d20:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
|   |   (trailing_type_specifier@Cpp~GCC5=1118#6b04e80^1#6b04dc0:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
|   |   |(simple_type_specifier@Cpp~GCC5=1140#6b046e0^1#6b04e80:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp)simple_type_specifier
|   |   )trailing_type_specifier#6b04e80
|   |  )decl_specifier#6b04dc0
|   | )basic_decl_specifier_seq#6b04d20
|   | (ptr_declarator@Cpp~GCC5=1417#6b05080^1#6b05100:2 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
|   |  (noptr_declarator@Cpp~GCC5=1421#6b05020^1#6b05080:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
|   |   (declarator_id@Cpp~GCC5=1487#6b05000^1#6b05020:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
|   |   |(id_expression@Cpp~GCC5=317#6b04fa0^1#6b05000:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
|   |   | (unqualified_id@Cpp~GCC5=319#6b04f00^1#6b04fa0:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
|   |   |  (IDENTIFIER@Cpp~GCC5=3368#6b046c0^1#6b04f00:1[`f'] Line 3 Column 33 File C:/temp/prime_with_templates.cpp)IDENTIFIER
|   |   | )unqualified_id#6b04f00
|   |   |)id_expression#6b04fa0
|   |   )declarator_id#6b05000
|   |  )noptr_declarator#6b05020
|   | )ptr_declarator#6b05080
|   |)parameter_declaration#6b05100
|   )template_parameter#6b05120
|  )template_parameter_list#6b05140
|  (template_parameter@Cpp~GCC5=2085#6b05440^1#6b05460:2 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
|   (parameter_declaration@Cpp~GCC5=1611#6b05420^1#6b05440:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
|   |(basic_decl_specifier_seq@Cpp~GCC5=1070#6b05160^1#6b05420:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
|   | (decl_specifier@Cpp~GCC5=1073#6b04fe0^1#6b05160:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
|   |  (trailing_type_specifier@Cpp~GCC5=1118#6b050e0^1#6b04fe0:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
|   |   (simple_type_specifier@Cpp~GCC5=1140#6b050c0^1#6b050e0:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp)simple_type_specifier
|   |  )trailing_type_specifier#6b050e0
|   | )decl_specifier#6b04fe0
|   |)basic_decl_specifier_seq#6b05160
|   |(ptr_declarator@Cpp~GCC5=1417#6b053e0^1#6b05420:2 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
|   | (noptr_declarator@Cpp~GCC5=1421#6b053c0^1#6b053e0:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
|   |  (declarator_id@Cpp~GCC5=1487#6b05360^1#6b053c0:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
|   |   (id_expression@Cpp~GCC5=317#6b05280^1#6b05360:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
|   |   |(unqualified_id@Cpp~GCC5=319#6b051a0^1#6b05280:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
|   |   | (IDENTIFIER@Cpp~GCC5=3368#6b046a0^1#6b051a0:1[`p'] Line 3 Column 40 File C:/temp/prime_with_templates.cpp)IDENTIFIER
|   |   |)unqualified_id#6b051a0
|   |   )id_expression#6b05280
|   |  )declarator_id#6b05360
|   | )noptr_declarator#6b053c0
|   |)ptr_declarator#6b053e0
|   )parameter_declaration#6b05420
|  )template_parameter#6b05440
| )template_parameter_list#6b05460
小开

这里的一个大问题是术语“上下文无关”和“上下文敏感”在计算机科学中有点不直观。对于c++，上下文敏感性看起来很像歧义，但在一般情况下不一定是这样。

在C/ c++中，if语句只允许在函数体中使用。这似乎是上下文敏感的，对吧?嗯,没有。与上下文无关的语法实际上不需要这样的属性，即您可以提取某一行代码并确定它是否有效。这实际上并不是context-free的意思。它实际上只是一个标签，模糊地暗示了一些与它的发音相关的东西。

现在，如果函数体中的语句根据直接语法祖先之外的定义而被不同地解析(例如，标识符是描述类型还是变量)，如a * b;情况，那么它实际上是上下文敏感的。这里没有实际的歧义;如果a是类型，它将被解析为指针的声明，否则将被解析为乘法。

上下文敏感并不一定意味着“难以解析”。C语言实际上并不难，因为臭名昭著的a * b;“歧义”可以通过包含前面遇到的__abc1的符号表来解决。它不需要任何任意模板实例化(已被证明是图灵完备的)来解决这种情况，就像c++偶尔做的那样。实际上，即使C程序具有与c++相同的上下文敏感性，也不可能编写出在有限时间内无法编译的C程序。

Python(以及其他对空白敏感的语言)也依赖于上下文，因为它需要lexer中的状态来生成缩进和缩进标记，但这并不会使它比典型的LL-1语法更难解析。它实际上使用了一个解析器-生成器，这就是为什么Python会有这样没有信息的语法错误消息的部分原因。同样重要的是要注意，这里没有像Python中的a * b;问题那样的“歧义”，这给出了一个没有“歧义”语法的上下文敏感语言的很好的具体例子(如第一段所述)。


提交答案