c - C语言中的非上下文无关语言的例子？

Question

C 语言中的非上下文无关语言的例子有哪些？ C语言中如何存在以下非CFL？

a) L1 = {wcw|w is {a,b}*}

b) L2 = {a^n b^m c^n d^m| n,m >=1}

Answer 1

这个问题措辞笨拙，所以我在字里行间阅读，在这里。尽管如此，这是一个常见的家庭作业/学习问题。

通常呈现的 C 语法中的各种歧义 [1] 不会使该语言成为非上下文无关的。 (实际上，它们甚至没有使语法成为非上下文无关的。)一般规则“如果它看起来像一个声明，那么它就是一个声明，而不管其他可能的解析”可能可以编码为一个非常复杂的上下文无关语法(尽管这不是 100% 明显的，因为 CFG 不会在交集或差异下关闭)，但是使用更简单的 CFG 解析然后根据声明规则消除歧义会更容易。

现在，关于 C(和大多数编程语言)的重要一点是，该语言的语法比用于解释目的的 BNF 复杂得多。例如，如果使用 undefined variable ，则 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 并非如此。必须解析为 typedef-name如果它恰好是一个；这只发生在可以减少的地方。即使在相同的范围内，对类型和变量使用相同的标识符也不是语法错误。 (这不是一个好主意，但它是有效的。)以下示例改编自标准第 6.7.8 节中的示例，显示了 t 的使用。作为字段名称和类型定义:

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