C语言中的非上下文自由语言示例？

Question

什么是C语言中非上下文无关语言的示例？ C语言中如何存在以下非CFL？

一个）L1 = {WCW | w是{A，B} *}

B）L2 = {A^N b^M C^N d^M | N，M> = 1}

Answer 1

这些东西不是上下文中C：

foo * bar; // foo multiplied by bar or declaration of bar pointing to foo? 
foo(*bar); // foo called with *bar as param or declaration of bar pointing to foo? 
foo bar[2] // is bar an array of foo or a pointer to foo? 
foo (bar baz) // is foo a function or a pointer to a function? 

Answer 2

问题是笨拙措辞，所以我字里行间，在这里。不过，这是一个常见的家庭作业/学习问题。

C语法中的各种歧义[1]通常不会呈现语言非上下文无关。 （事实上​​，它们甚至不提供语法无关的语法。）一般规则“如果它看起来像一个声明，它是一个声明，而不管其他可能的解析”可能被编入一个非常复杂的上下文无关语法（尽管这不是100％显而易见的，因为CFG在相交或差异之下没有关闭），但用简单的CFG解析并根据声明规则消除歧义更容易。

现在，关于C语言（以及大多数编程语言）的重要一点是语言的语法比用于解释目的的BNF复杂得多。例如，如果一个变量在未被定义的情况下使用，则C程序的格式不正确。这是一个语法错误，但它没有被CFG解析器检测到。由于语言的复杂语法，定义这些情况所需的语法产品非常复杂，但它们将归结为要求id在有效程序中出现两次。因此L1 = {wcw|w is {a,b}+}（这里w是标识符，并且c太复杂了）。在实践中，检查这个要求通常是用符号表来完成的，而正式的语言规则虽然精确，但并不是用逻辑形式来编写的。由于L1不是上下文无关的语言，所以形式不能没有上下文，但是上下文敏感的语法可以识别L1，所以它不是不可能的。 （例如，请参见Algol 68。）

符号表也用于决定特定的identifier是否要减少到typedef-name [2]。这是解决语法中的一些模糊问题所必需的。 （它还会进一步限制语言中的字符串集合，因为有些情况下identifier必须解析为typedef-name才能使程序有效。）

对于另一种类型的上下文敏感性函数调用需要匹配参数号码中的函数声明;这种要求通过L2 = {a^n b^m c^n d^m| n,m >=1}来模拟，其中a和c分别代表一些函数的定义和使用，b和d代表不同函数的定义和使用。 （同样，以高度简化的形式）。

这第二个要求可能不太清楚语法要求。其他语言（例如Python）允许使用任意数量的参数进行函数调用，并将参数/参数计数匹配检测为仅在运行时检测到的语义错误。然而，在C的情况下，不匹配显然是语法错误。简而言之，构成C语言的语法有效字符串集合是由C语言定义中呈现的CFG所识别的字符串集合的适当子集;有效解析集合是CFG生成的派生集合的真子集，而且语言本身是（a）明确的，（b）没有上下文。注1：其中大部分并不真正含糊不清，因为它们取决于如何解析给定的identifier（typedef名称，函数标识符，声明变量，...）。

注意2：如果identifier碰巧是一个，那么identifier必须解析为typedef-name;只有在可能减少的地方才会发生。即使在相同的范围内，对类型和变量使用相同的标识符也不是语法错误。 （这不是一个好主意，但它是有效的），下面的例子，适合于标准的第6.7.8从一个例子，说明了如何使用t既是一个字段名和一个typedef：

typedef signed int t; 
struct tag { 
    unsigned t:4; // field named 't' of type unsigned int 
    const t:5;  // unnamed field of type 't' (signed int) 
};