如何使C语言上下文无关?
How to make C language context-free?
我知道C不是上下文无关语言,一个著名的例子是:
int foo;
typedef int foo;
foo x;
在这种情况下,词法分析器不知道第 3 行中的 foo
是标识符,还是 typedef
.
我的问题是,这是使 C 成为 上下文敏感语言 的唯一原因吗?
我的意思是,如果我们去掉 typedef
,它会变成上下文无关语言吗?还是有其他原因(例子)阻止了它?
是的。 C 可以用经典的 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 不能是严格的上下文独立语言。为此,您应该描述一种不允许以与您在问题中描述的方式类似的方式使用未声明变量(这是上下文)的语法。语言作者总是使用某种上下文无关文法来描述语法,但只是为了描述语言的主要句法结构。您描述的情况(使类型标识符适合不同的令牌 class 以便能够进入不应进入的地方)只是一个示例。例如,如果您查看 static unsigned long long int variable
之类的顺序的自由度,简化了程序员的语法记忆,但对编译器作者来说却使事情复杂化。
根据我的知识和研究,有两个基本原因使 C 成为上下文敏感语言。它们是:
- 变量在使用前声明。
- 匹配函数或子程序的形参和实参。
下推自动机 (PDA) 无法完成这两项,但线性有界自动机 (LBA) 可以完成这两项。
我知道C不是上下文无关语言,一个著名的例子是:
int foo;
typedef int foo;
foo x;
在这种情况下,词法分析器不知道第 3 行中的 foo
是标识符,还是 typedef
.
我的问题是,这是使 C 成为 上下文敏感语言 的唯一原因吗?
我的意思是,如果我们去掉 typedef
,它会变成上下文无关语言吗?还是有其他原因(例子)阻止了它?
是的。 C 可以用经典的 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 不能是严格的上下文独立语言。为此,您应该描述一种不允许以与您在问题中描述的方式类似的方式使用未声明变量(这是上下文)的语法。语言作者总是使用某种上下文无关文法来描述语法,但只是为了描述语言的主要句法结构。您描述的情况(使类型标识符适合不同的令牌 class 以便能够进入不应进入的地方)只是一个示例。例如,如果您查看 static unsigned long long int variable
之类的顺序的自由度,简化了程序员的语法记忆,但对编译器作者来说却使事情复杂化。
根据我的知识和研究,有两个基本原因使 C 成为上下文敏感语言。它们是:
- 变量在使用前声明。
- 匹配函数或子程序的形参和实参。
下推自动机 (PDA) 无法完成这两项,但线性有界自动机 (LBA) 可以完成这两项。