C语言中非上下文语言的示例



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

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

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

这个问题是笨拙的,所以我在这条线之间阅读。尽管如此,这是一个常见的家庭作业/学习问题。

通常呈现的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解决,以使程序有效。)

对于另一种类型的上下文敏感性,函数调用需要在参数的 number 中匹配函数声明;这种要求由L2 = {a^n b^m c^n d^m| n,m >=1}建模,其中ac表示某些功能的定义和使用,bd表示不同功能的定义和使用。(同样,以高度简化的形式。)

这第二个要求可能不太清楚句法要求。其他语言(例如,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)
};

这些事物在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?

最新更新