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

正确的环节是解析谜题

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

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，至少从通常使用的术语来看是这样的。

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

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

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.

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

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

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

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: https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language .

如果有人试图编写上下文敏感的(或不受限制的)语法来解析c++，那么很可能会到处乱写乱写。编写图灵机来解析c++同样是不可能完成的任务。即使是编写c++程序也是困难的，而且据我所知，没有一个被证明是正确的。这就是为什么标准没有尝试提供完整的正式语法，以及为什么它选择用技术英语编写一些解析规则。

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.)

各种语法(两个用于词法分析的重叠语法，一个发生在预处理之前，另一个，如果有必要，发生在预处理之后，再加上“句法”语法)收集在附录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;
}

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

aB → AGB

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

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

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

α→β,|α|≥|β| > 0(|α|意味着“α”的长度)

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

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

这里也有一个问题: 上下文敏感性vs模糊性。

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

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

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

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

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

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

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

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

x = (name)(expression);

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

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