c - 是C 上下文无关或者上下文相关?

  显示原文与译文双语对照的内容

我经常听说 C++ 是一种context-sensitive语言。 接受以下示例:

 
a b(c);

 

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

如果你查找context-free语言的定义,它将基本上告诉你所有语法规则都必须有left-hand边,它包含一个non-terminal符号。 Context-sensitive文法,另一方面,允许任意字符串在left-hand端终端和non-terminal的符号。

在它的left-hand side,"C++ 编程语言"翻阅附录A 中,我没有找到一个单一的语法规则,该规则有其他任何东西除了单个 non-terminal symbol. 这意味着 C++ 是 context-free 。 ( 当然,每一种context-free语言都是context-sensitive的,因为context-free语言构成了context-sensitive语言的子集,但这不是重点。)

C++ context-free或者 context-sensitive?

时间:

下面就是我( 当前) 喜欢的演示为什么解析 C++ 是( 可能可能) Turing-complete,因为它显示了一个程序,它在语法上是正确的当且仅当一个给定的整数是素数。

所以我都断言 C++ 既不是context-free也不是 context-sensitive

如果你在任何生产的两边允许任意的符号序列,你会在乔姆斯基层次结构中生成一个Type-0语法("无限制"),它比context-sensitive语法更强大;无限制语法是 Turing-complete 。 context-sensitive ( Type-1 ) 语法允许在生产的左边有多个上下文符号,但是在生产( 因此名称"context-sensitive")的右边必须出现相同的上下文。 [1] Context-sensitive文法等价于 linear-bounded图灵机。

在示例程序中,素数计算可以由linear-bounded灵机执行,因此它不完全证明图灵等价,但是重要的部分是解析器需要执行计算来执行句法分析。 它可能是任何可以表示为模板实例化的计算,并且有理由相信 C++ 模板实例化是 Turing-complete 。 例如 Todd L 。 2003 veldhuizen纸张 。

无论如何,C++ 可以由一个计算机解析,所以它可以由一个图灵机来解析。 因此,一个不受限制的语法可以识别它。 实际上编写这样的语法是不切实际的,这就是为什么标准不尝试这么做的原因。 ( 见下面。)

某些表达式"二义性"的问题大多是红色的。 首先,歧义是特定语法的特征,而不是语言。 即使一个语言可以被证明没有明确的语法,如果它可以被context-free语法识别,它是 context-free 。 类似地,如果context-free语法不能识别它,但它可以被context-sensitive语法识别,它是 context-sensitive 。 歧义不是相关的。

但在任何情况下,如第 21行( 例如 。 auto b = foo<IsPrime<234799>>::typen<1>(); ) 在下面的程序中,表达式根本不明确;它们只是根据上下文进行了不同的分析。 在这个问题的最简单表达式中,某些标识符的句法类别依赖于它们声明为( 类型和函数,例如)的方式,这意味着正式语言必须识别相同程序中两个arbitrary-length字符串是否相同。 这可以用"副本"语法建模,语法是识别同一个单词的两个连续副本的语法。 用抽取引理很容易证明这种语言不是 context-free 。 可以使用这里语言的context-sensitive语法,并且在这里问题的答案中提供了Type-0语法: http://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language

如果要尝试编写一个 context-sensitive ( 或者无限制) 语法来解析 C++,它很可能会充满涂鸦。 编写一个图灵机来解析 C++ 是一个相当不可能的任务。 甚至编写一个 C++ 程序都是很困难的,据我所知没有一个是正确的。 这就是为什么标准不尝试提供完整的语法,为什么它选择在技术英语中编写一些解析规则。

C++ 标准中的正式语法不是 C++ 语言语法的完整形式定义。 在预处理之后,它甚至不是语言的完整形式定义,这可能更容易形式化。 ( 但这不是语言: 由标准定义的C++ 语言包括预处理器,并且预处理器的操作在算法中被描述,因为在任何语法形式中都很难描述。 在这个标准部分,词汇分解被描述,包括必须多次应用的规则。

在附录A 中收集了各种语法( 用于词法分析的两个重叠语法,一个发生在预处理前,另一个在必要时,如有必要加上"语法"语法),这个重要音符( 添加的强调):

C++ 语法摘要旨在帮助理解。 不是语言的准确语句。 特别是,这里描述的语法接受 有效 C++ 构造的超集 注释规则( 6.8,7.1,10.2 ) 必须用于区分表达式和声明。 此外,访问控制,歧义和类型规则必须用来剔除语法有效但毫无意义的构造。

最后,这是承诺的程序。 第 21行在语法上正确,只有当 IsPrime<N> 中的N 为素数时。 否则,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;
}


[1] 要更严格地讲,context-sensitive语法中的每个生产都必须是:

αAβ &rightarrow; αγβ

其中 A 是non-terminal和 αβ 可能是语法符号的序列,而 γ 是一个non-empty序列。 ( 语法符号可以是终端或者 non-terminals ) 。

在上下文这个能否读取 A &rightarrow; γ 盘算。 在 context-free ( 类型 2 ) 语法中,αβ 必须为空。

事实证明,你还可以使用"单调"限制限制语法,其中每个生产必须是以下形式:

α &rightarrow; β|α| ≥ |β|> 0 ( |α| 表示" α的长度")

可以证明由单调文法识别的一组语言与context-sensitive文法识别的一组语言完全一样,而且很容易在单调语法中进行基本的证明。 因此,很常见的是看到"context-sensitive",就好像它是"单调"。

首先,你这是正确的观察结束时的语法里没有上下文相关规则标准,这样语法是 C++ context-free 。

但是,语法并没有精确描述 C++ 语言,因为它产生了non-C++程序,比如


int m() { m++; }

或者


typedef static int int;

C++ 语言定义为"well-formed C++ 程序集"不是 context-free ( 可以证明只需要声明要求的变量就可以) 。 假设你可以在模板中编写Turing-complete程序并根据它的结果生成程序 ill-formed,这甚至不是 context-sensitive 。

现在,( ignorant ) 人员( 通常不是语言理论家,但解析器设计者) 通常使用以下一些含义

  • 二义性
  • 无法用Bison解析
  • 不是 LL(k), LR(k), LALR(k) 或者他们选择的任何parser-defined语言类

标准后面的语法不满足这些类别( IE 。 它不明确,不是 LL(k). 。) 所以 C++ 语法是"不是 context-free"。 在某种意义上,它们是正确的,很难生成一个工作的C++ 解析器。

注意这里所使用的属性只与context-free语言弱连接- 模糊与 context-sensitivity ( 事实上,context-sensitive规则通常帮助消除歧义) 无关,另外两个仅仅是context-free语言的子集。 解析context-free语言不是一个线性过程( 尽管解析确定性的是) 。

, 类型上解析上下文是的下面的表达式都有不同运算顺序 depending:

编辑:当实际的操作顺序不同时,在修饰它之前,使用"常规"编译器解析到未修饰的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 );

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

  1. 几乎所有编程语言的语法都是 context-free 。 通常,它是作为扩展的Backus-Naur表单或者 context-free gramar给出的。

  2. 但是,即使程序与编程语言定义的context-free gramar一致,它也不一定是一个有效的程序。 为了成为一个有效的程序,程序必须满足许多 non-context-free poperties 。 比如,最简单的这种属性是变量的作用域。

最后,C++ 是否为context-free取决于你所问的问题。

C++ 用GLR解析器解析。 这意味着在解析过程中,解析器可能 遇到歧义但它应该继续并决定哪些语法规则的源代码以使用以后 。

还有,

为什么 C++ 不能用 LR(1) 解析器解析


请记住,context-free语法就不能描述 所有规则的一种编程语言的语法。 例如属性语法用于检查表达式类型的有效性。


int x;
x = 9 + 1.0;

context-free grammar,你不能描述以下 rule: 赋值右边的右边应该是左边的相同类型。

你可能想看看的设计&的C++,由 Bjarne Stroustrup 。 在其中他描述了他试图使用 yacc ( 或者类似或者相似) 解析早期版本的问题,并希望他使用递归下降。

是的C++ 是上下文敏感的,非常敏感的上下文。 在以前的知识判断( 不能自动生成的语法树通过简单地解析整个文件使用一个上下文无关的解析器,因为在某些情况下你需要知道 symbol. 在分析时构建一个符号表。

第一个示例:

 
A*B;

 

这是乘法表达式?

或者

这是 B 变量的声明,它是 A 类型的指针?

如果是变量,则它是表达式,如果是类型,则是指针声明。

第二个示例:

 
A B(bar);

 

这是一个函数 Prototype,它接受 bar 类型的参数?

或者

这个声明变量 B 是类型 A,并调用 bar 常量的构造函数作为初始值设定项?

你需要再次了解 bar 是一个变量还是来自符号表的类型。

第三个示例:


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

当这个功能definition,是这种情况,则生成符号表在解析时将不起作用,因为x 和y的声明 comes. 所以你需要先粗略看一下类的定义,并在第二阶段中,要告诉x*y看看这个方法定义是一个表达式,而不是一个指针声明或者任何东西。

我觉得"context-sensitive"的正式定义和"context-sensitive"的非正式用法有一些混淆。 前者具有定义明确的含义。 后者用于表示"你需要上下文来解析输入"。

这里还要求: Context-sensitivity vs 歧义列表。

以下是context-free语法:


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

这是不明确的,所以为了分析输入"x",你需要一些上下文( 或者使用模糊,或者发出"警告: E8271 - 第 115行的输入不明确。 但它肯定不是context-sensitive语法。

没有Algol-like语言是context-free的,因为它们具有约束标识符的规则,这些表达式和语句可以基于它的类型,因为声明和使用之间的语句数量没有限制。

通常的解决方案是编写一个context-free分析器,实际上接受的超集有效的程序和动作中把context-sensitive部分即席"语义"代码附加到规则。

C++ 远不止于这里,这要归功于它的Turing-complete模板系统。 参见堆栈溢出问题 794015

它是 context-sensitive,因为 a b(c); 有两个有效的parses-声明和变量。 当你说"如果 c 是一种类型",那就是上下文,就在那里,你已经准确描述了 C++ 对它是如何敏感的。 如果你没有"什么是 c"的上下文,你就无法明确解析。

在这里,上下文是用tokens-的选择表示解析器读取一个标识符作为类型名令牌如果它命名一个类型。 这是最简单的解决方法,避免了 context-sensitive ( 在本例中)的复杂性。

编辑:当然,有更多的上下文敏感性问题,我只关注你所展示的那个。 模板对于这种情况尤其讨厌。

...