C++ 是上下文无关的还是上下文敏感的？

真正的:)

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

C++ 使用 GLR 解析器进行解析。这意味着在解析源代码期间，解析器可能会遇到歧义，但它应该继续并决定以后使用哪个语法规则。

也看，

为什么 C++ 不能用 LR（1） 解析器解析？

---

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

int x;
x = 9 + 1.0;

你不能用上下文无关的语法来描述以下规则：作业的右侧应与左侧的类型相同。

C++ 不是上下文无关的。我前段时间在编译器讲座中学到了它。快速搜索提供了此链接，其中“语法或语义”部分解释了为什么 C 和 C++ 不是上下文无关的：

维基百科讲座：上下文无关的语法

问候，
奥瓦内斯

是的。以下表达式具有不同的操作顺序，具体取决于类型解析的上下文：

编辑：当实际操作顺序发生变化时，使用“常规”编译器非常困难，该编译器在修饰 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);

是强制转换 if 是类型名称，function 调用 if 是函数名称。另一种情况是所谓的“最令人烦恼的解析”，其中无法区分变量定义和函数声明（有一条规则说它是函数声明）。namename

这种困难导致了对从属名称和从属名称的需求。据我所知，C++ 的其余部分对上下文不敏感（即可以为其编写上下文无关语法）。typenametemplate

Meta-S“是 Quinn Tyler Jackson 的上下文相关解析引擎。我没有用过它，但他讲了一个令人印象深刻的故事。查看他在 comp.compilers 中的评论，并查看 rnaparse.com/MetaS%20defined.htm – Ira Baxter Jul 25 at 10：42发表

正确的链接是解析 enigines

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

C++模板已被证明是图灵强大的。虽然不是正式的参考资料，但这里有一个可以在这方面查看的地方：

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

我将大胆猜测（与民间和简洁的CACM证明一样古老，表明60年代的ALGOL不能被CFG引用），并说C++因此不能仅由CFG正确解析。CFGs，在树上或减少事件中与各种TP机制相结合--这是另一回事了。从一般意义上讲，由于停止问题，存在一些 C++ 程序，这些程序不能被证明是正确/不正确的，但仍然是正确的/不正确的。

{PS- 作为 Meta-S 的作者（上面的几个人提到过）——我可以肯定地说，Thothic 既没有倒闭，也没有免费提供软件。也许我已经用这个版本的措辞来表达我的回复，这样我就不会被删除或投票到 -3。

是的，C++ 是上下文敏感的，非常上下文敏感。您不能通过简单地使用上下文无关解析器解析文件来构建语法树，因为在某些情况下，您需要从以前的知识中知道符号才能决定（即在解析时构建符号表）。

第一个例子：

A*B;

这是乘法表达式吗？

或

这是变量的声明是类型的指针吗？BA

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

第二个例子：

A B(bar);

这是一个采用类型参数的函数原型吗？bar

或

这个声明变量是类型，并使用常量作为初始值设定项调用 A 的构造函数吗？BAbar

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

第三个例子：

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

当在解析时构建符号表无济于事时，就是这种情况，因为 x 和 y 的声明位于函数定义之后。因此，您需要先浏览类定义，然后在第二遍中查看方法定义，以判断 x*y 是一个表达式，而不是指针声明或其他什么。

它是上下文相关的，就像两个有效的解析一样 - 声明和变量。当你说“If 是一个类型”时，这就是上下文，就在那里，你已经准确地描述了 C++ 对它的敏感程度。如果你没有“什么是？”的上下文，你就无法明确地解析它。a b(c);cc

在这里，上下文以标记的选择来表示 - 如果解析器命名类型，则解析器会将标识符读取为 typename 标记。这是最简单的解决方案，并且避免了上下文敏感（在本例中）的复杂性。

编辑：当然，还有更多的上下文敏感性问题，我只关注你展示的问题。为此，模板尤其令人讨厌。

下面是我（当前）最喜欢的演示，说明为什么解析 C++ 是（可能）图灵完备的，因为它显示了一个程序，当且仅当给定整数是素数时，该程序在语法上是正确的。

所以我断言 C++ 既不是上下文无关的，也不是上下文敏感的。

如果允许任何作品的两端都使用任意符号序列，则会在 Chomsky 层次结构中生成 Type-0 语法（“无限制”），这比上下文相关语法更强大;不受限制的语法是图灵完备的。上下文相关（类型 1）语法允许在作品的左侧使用多个上下文符号，但相同的上下文必须出现在作品的右侧（因此称为“上下文相关”）。[1] 上下文相关语法等同于线性有界图灵机。

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

无论如何，C++可以被计算机解析，所以它当然可以被图灵机解析。因此，不受限制的语法可以识别它。实际上，编写这样的语法是不切实际的，这就是为什么标准不尝试这样做的原因。（见下文。

某些表达的“歧义”问题主要是一条红鲱鱼。首先，歧义是特定语法的特征，而不是语言的特征。即使一种语言可以被证明没有明确的语法，但如果它可以被无上下文的语法识别，它就是无上下文的。同样，如果它不能被上下文无关的语法识别，但可以被上下文敏感的语法识别，则它是上下文敏感的。模棱两可无关紧要。

但无论如何，就像下面程序中的第 21 行（即 ）一样，表达式一点也不模棱两可;它们只是根据上下文以不同的方式解析。在问题的最简单表达中，某些标识符的语法类别取决于它们的声明方式（例如类型和函数），这意味着形式语言必须识别同一程序中两个任意长度字符串相同的事实（声明和使用）。这可以通过“复制”语法来建模，该语法可以识别同一单词的两个连续精确副本。用抽水引理很容易证明这种语言不是与上下文无关的。这种语言的上下文相关语法是可能的，并且在这个问题的答案中提供了 Type-0 语法：https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language 。auto b = foo<IsPrime<234799>>::typen<1>();

如果有人试图编写一个上下文相关（或不受限制）的语法来解析 C++，它很可能会用涂鸦填满整个宇宙。编写图灵机来解析C++同样是一项不可能完成的任务。即使编写 C++ 程序也很困难，据我所知，没有一个被证明是正确的。这就是为什么该标准没有试图提供完整的形式语法，以及为什么它选择用技术英语编写一些解析规则。

在 C++ 标准中看起来像形式语法的东西并不是 C++ 语言语法的完整形式定义。它甚至不是预处理后语言的完整形式定义，这可能更容易形式化。（不过，那不是语言：标准定义的 C++ 语言包括预处理器，并且预处理器的操作是用算法描述的，因为在任何语法形式中都很难描述。正是在标准的那部分中描述了词法分解，包括必须多次应用它的规则。

各种语法（用于词汇分析的两种重叠语法，一种在预处理之前进行，另一种在必要时在预处理之后进行，加上“句法”语法）收集在附录 A 中，并附有以下重要注释（强调后加）：

本 C++ 语法摘要旨在帮助理解。它不是语言的确切陈述。特别是，此处描述的语法接受有效 C++ 构造的超集。必须应用消除歧义规则（6.8、7.1、10.2）来区分表达式和声明。此外，必须使用访问控制、歧义和类型规则来清除语法上有效但无意义的构造。

最后，这是承诺的程序。第 21 行在语法上是正确的，当且仅当 N in 是素数时。否则，是一个整数，而不是一个模板，所以被解析为在语法上不正确，因为这不是一个语法上有效的表达式。IsPrime<N>typentypen<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;
}

---

[1] 更严格地说，上下文相关语法中的每个作品都必须具有以下形式：

αAβ → αγβ

其中 是非终端 和 ，可能是语法符号的空序列，并且是非空序列。（语法符号可以是终端，也可以是非终端）。Aαβγ

这只能在上下文中理解为。在上下文无关（类型 2）语法中，并且必须为空。A → γ[α, β]αβ

事实证明，您还可以使用“单调”限制来限制语法，其中每个产品都必须具有以下形式：

α → β其中 （ 表示“长度|α| ≥ |β| > 0|α|α")

可以证明单调语法识别的语言集与上下文敏感语法识别的语言集完全相同，并且通常更容易基于单调语法进行证明。因此，将“上下文相关”用作“单调”是很常见的。

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

这里也提出了这个问题：上下文敏感性与歧义。

下面是一个与上下文无关的语法：

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

它是模棱两可的，所以为了解析输入“x”，你需要一些上下文（或者忍受歧义，或者发出“警告：E8271 - 输入在第 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. 但是，即使程序符合编程语言定义的上下文无关语法，它也不一定是有效的程序。程序必须满足许多非上下文无关的属性才能成为有效的程序。例如，最简单的此类属性是变量的作用域。

总而言之，C++ 是否与上下文无关取决于你提出的问题。

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

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

C++ 远远不止于此，这要归功于其图灵完备的模板系统。请参阅 Stack Overflow 问题 794015。

C++ 标准中的 productions 是与上下文无关的，但众所周知，并没有真正精确地定义语言。大多数人认为当前语言中的一些歧义问题（我相信）可以通过上下文敏感的语法明确解决。

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

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

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”是模板，则为前者，如果不是，则为后者。

这个答案说 C++ 不是上下文无关的......这意味着（不是答案者）它无法解析，并且答案提供了一个困难的代码示例，如果某个常量不是质数，则会产生无效的 C++ 程序。

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

为了解决关于可解析性的问题，我提供了经验证据，证明 C++ 有上下文无关的语法，可以使用 为源文本的上下文无关解析生成 AST 事实上，通过使用由显式语法驱动的基于 GLR 解析器的现有工具来解析它。

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

如果你的意思是，确定源程序是否是成员 的一组有效的 C++ 源代码程序，那么我会同意 问题要困难得多。但问题不在于解析。

该工具通过将分析与类型检查隔离开来解决此问题 已解析的程序。（有多种解释 在没有上下文的情况下，它记录了一个歧义节点 在解析树中，有几个可能的解析;类型 检查决定哪一个是正确的，并消除无效的 子树）。在下面的示例中，您可以看到一个（部分）解析树;整棵树太大，无法放入 SO 答案。请注意，无论使用值 234797 还是 234799，您都会得到一个分析树。

使用原始值 234799 在 AST 上运行工具的名称/类型解析程序会成功。如果值为 234797，则名称解析器将失败（如预期的那样），并显示错误消息“typen is not a type.”，因此该版本不是有效的 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/++ 中，if 语句只允许在函数体内使用。这似乎使它对上下文敏感，对吧？嗯，不。上下文无关语法实际上并不需要可以提取一些代码行并确定它是否有效的属性。这实际上并不是上下文无关的意思。它实际上只是一个标签，隐约暗示着与它听起来的东西有关的东西。

现在，如果函数体中的语句根据直接语法祖先之外定义的内容（例如，标识符是否描述类型或变量）以不同的方式解析，那么它实际上是上下文相关的。这里没有实际的歧义;如果是类型，它将被解析为指针的声明，否则将被解析为乘法。a * b;a

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

Python（和其他对空格敏感的语言）也是上下文相关的，因为它需要词法分析器中的状态来生成缩进和缩进标记，但这并不比典型的 LL（1） 语法更难解析。在 3.9 版本之前，Python 实际上使用了 LL（1） 解析器生成器，这也是为什么它有/有这种无信息的语法错误消息的部分原因（其中许多在切换到 PEG 解析器后已得到修复）。这里还需要注意的是，这里没有像 Python 中那样的“歧义”问题，它给出了一个很好的上下文相关语言的例子，没有“模棱两可”的语法（如第一段所述）。a * b;