如何让C语言上下文无关？

Question

我知道C不是上下文无关语言，一个著名的例子是：

int foo;
typedef int foo;
foo x;

在这种情况下，词法分析器不知道第三行中的

foo

是标识符，还是

typedef

。

我的问题是，这是使C成为上下文敏感语言的唯一原因吗？

我的意思是，如果我们去掉

typedef

，它会变成上下文无关语言吗？或者还有其他原因（例子）阻止它发生？

Answer 1

后处理器 C syntax 可以使用经典的 lex + yacc 组合进行解析。词法分析器定义和 yacc 语法可在

免费获得

http://www.quut.com/c/ANSI-C-grammar-l-2011.html 和 http://www.quut.com/c/ANSI-C-grammar-y-2011.html

正如您从 lex 文件中看到的那样，它很简单，除了上下文敏感的

check_type()

（和

comment()

，但评论处理在技术上属于预处理器），这使得

typedef

成为上下文敏感的唯一来源.由于 yacc 文件也不包含任何引入上下文敏感的技巧，因此

typedef

-less C 将是一个完美的上下文无关语法。

C 的后续类型检查（匹配声明与使用站点）是上下文敏感的，所以你可以说总体而言，C 是上下文敏感的。

Answer 2

没有。 C 不能是严格的上下文独立语言。为此，您应该描述一种不允许以与您在问题中描述的方式类似的方式使用未声明变量（这是上下文）的语法。语言作者总是使用某种上下文无关文法来描述语法，但只是为了描述语言的主要句法结构。您描述的情况（制作一个类型标识符以适应不同的令牌类以便能够进入它不应该进入的地方）只是一个例子。例如，如果您看一下，像

static unsigned long long int variable

这样的顺序的自由度简化了程序员的语法记忆，但对编译器作者来说却使事情复杂化。

Answer 3

根据我的知识和研究，有两个基本原因使 C 语言成为上下文敏感的语言。它们是：

1. 变量在使用前声明。
2. 匹配函数或子程序的形参和实参

下推自动机（PDA）无法完成这两项，但线性有界自动机（LBA）可以完成这两项。