1

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

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

b) L2 = {a^nb^mc^nd^m| n,m >=1}

4

2 回答 2

5

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

通常呈现的 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必须将 an 解析为 atypedef-name才能使程序有效。）

对于另一种类型的上下文敏感，函数调用需要在参数数量上匹配函数声明；这类需求由L2 = {a^n b^m c^n d^m| n,m >=1}where建模a，c代表某个功能的定义和使用，b以及d代表不同功能的定义和使用。（再次，以高度简化的形式。）

这第二个要求可能不太清楚是句法要求。其他语言（例如 Python）允许使用任意数量的参数调用函数，并将参数/参数计数匹配检测为仅在运行时检测到的语义错误。然而，在 C 的情况下，不匹配显然是语法错误。

简而言之，构成 C 语言的语法有效字符串集是 C 语言定义中呈现的 CFG 识别的字符串集的真子集；有效解析集是 CFG 生成的推导集的真子集，并且语言本身是 (a) 明确的，并且 (b) 不是上下文无关的。

注 1：其中大多数并不是真正的歧义，因为它们取决于如何identifier解析给定的（typedef 名称、函数标识符、声明的变量……）。

注2：不是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)
};
于 2012-10-23T07:15:35.017 回答
3

这些东西在 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?
于 2012-10-22T14:10:39.517 回答