c - 如何使C语言无上下文？

Question

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

int foo;
typedef int foo;
foo x;

在这种情况下，词法分析器不知道第三行中的 foo 是标识符还是 typedef 。

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

我的意思是，如果我们去掉 typedef ，它会成为上下文无关语言吗？或者还有其他原因(示例)阻止它发生？

Answer 1

是的。可以使用经典的 lex + yacc 组合来解析 C。词法分析器定义和 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 将是一种完美的上下文无关语言。