3

我认为这个问题是自给自足的。C 语言的语法是完全通过上下文无关语法定义的，还是我们有在解析过程中可能需要非上下文无关定义的语言结构？

我认为非 CFL 构造的一个例子是变量在使用之前的声明。但是在 Compilers (Aho Ullman Sethi) 中，声明 C 语言不会根据名称来区分标识符。词法分析器将所有标识符标记为“id”。如果 CFG 没有完全定义 C，请任何人都可以举一个 C 中非 CFL 构造的例子吗？

4

5 回答 5

3

问题是您还没有定义“C 的语法”。

如果您将其定义为 CS 意义上的 C 语言，即所有有效 C 程序的集合，那么 C——以及除了 turing tarpits 和 Lisp 之外的几乎所有其他语言——都不是上下文无关的。原因与解释C 程序的问题无关（例如，决定是乘法还是声明）。相反，这仅仅是因为上下文无关文法无法帮助您确定给定字符串是否是有效的 C 程序。即使是简单的事情也需要比上下文无关文法更强大的机制，因为您必须 (1) 记住返回类型和 (2) 检查匹配返回类型之后发生的任何事情。a * b;int main() { return 0; }returna * b;面临一个类似的问题——你不需要知道它是否是一个乘法，但如果它是一个乘法，那必须是aand类型的有效运算b。我实际上不确定上下文相关语法是否足以满足所有 C 的需求，因为对有效 C 程序的一些限制非常微妙，即使您排除了未定义的行为（其中一些甚至可能无法确定）。

当然，上述概念几乎没有用处。通常，在谈论语法时，我们只对有效程序的一个非常好的近似感兴趣：我们想要一个语法，它可以排除尽可能多的非 C 字符串，而不会使语法过度复杂（例如，1 a或(-)） . 其他一切都留给编译器的后期阶段，称为语义错误或类似的东西，以将其与第一类错误区分开来。这些“近似”语法几乎总是上下文无关语法（包括在 C 的情况下），因此如果您想将有效程序集的这种近似称为“语法”，C 确实是由上下文无关语法定义的。很多人都这样做，所以你会在好公司。

于 2013-10-25T17:34:58.827 回答
1

C 语言的语法是否完全通过上下文无关语法定义？

是的。这是BNF中C的语法：

http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf

如果您在任何规则的左侧只看到一个符号，则该语法是上下文无关的。这就是上下文无关语法（维基百科）的定义：

在形式语言理论中，上下文无关文法 (CFG) 是一种形式文法，其中每个生产规则都具有以下形式

V → w

其中 V 是单个非终结符，w 是一串终结符和/或非终结符（w 可以为空）。

由于其他人提到了歧义，我想澄清一下。想象一下以下语法：

A -> B x | C x
B -> y
C -> y

这是一个模棱两可的语法。但是，它仍然是上下文无关的语法。这两个是完全不同的概念。

显然，C 的语义分析器是上下文敏感的。这个来自重复问题的答案有进一步的解释。

于 2013-10-25T17:26:44.667 回答
1

由C语言标准定义的语言包括预处理器。下面是一个语法正确的 C 程序：

#define START int main(
#define MIDDLE ){

START int argc, char** argv MIDDLE return 0; }

似乎真的很想回答这个问题（出现很多）“当然，C 有一个 CFG”，基于在标准中提取语法的一个子集，该语法本身是模棱两可的并且可以识别一个超集语言。CFG 很有趣，甚至很有用，但它不是 C。

事实上，标准中的产生式甚至没有尝试描述语法正确的源文件是什么。他们描述：

  1. 源文件的词法结构（连同预处理后的有效标记的词法结构）。

  2. 单个预处理器指令的语法

  3. 后处理语言语法的超集，它依赖于某种其他机制来区分 的typedef-name和其他用途identifier，以及区分 的constant-expression和其他用途的机制conditional-expression。

许多人认为第 3 点中的问题是“语义的”，而不是“句法的”。然而，C（以及它的表亲 C++）的本质是不可能将“语义”与程序的解析分开。例如，下面是一个语法正确的 C 程序：

#define base 7
#if base * 2 < 10
  &one ?= two*}}
#endif

int main(void){ return 0; }

所以如果你真的是说“是一个CFG定义的C语言的语法”，那么答案一定是否定的。如果你的意思是，“是否有一个 CFG 定义了某种语言的语法，它表示字符串是 C 语言程序翻译的中间产物”，答案可能是肯定的，尽管有些人会争辩说有必要明确什么是 aconstant-expression和 atypedef-name使语法必然是上下文敏感的，而其他语言则不然。

于 2013-10-25T21:13:53.277 回答
0

如果您的意思是“C 的语法”所有 C 编译器接受的有效 C 字符串，并且在运行预处理器之后，但忽略输入错误，那么这就是答案：是但不是明确的。

首先，您可以假设输入程序是根据 C 标准进行标记化的。语法将描述这些标记之间的关系，而不是裸字符。这种上下文无关文法可以在有关 C 的书籍和使用解析器生成器的实现中找到。这种标记化是一个很大的假设，因为相当多的工作涉及“词法分析”C。所以，我认为我们还没有使用上下文无关语法来描述 C，如果我们还没有使用上下文无关语法来描述词汇级别的话. 标记器和解析器之间的分期结合扫描仪生成器的排序（首选关键字、最长匹配等）是计算能力的主要增加，这在无上下文语法中不容易模拟。

因此，如果您不假设分词器可以使用符号表将类型名称与变量名称区分开来，那么上下文无关语法将变得更加困难。然而：这里的诀窍是接受歧义。我们可以用上下文无关文法完整地描述 C 的语法，包括它的记号。只有语法会模棱两可，并且对同一字符串产生不同的解释。例如，A *a;它将具有乘法和指针声明的派生。没问题，语法仍然按照您的要求描述 C 语法，只是不是很明确。

请注意，我们假设也首先运行了预处理器，我相信您的问题与预处理之前的代码无关。描述使用上下文无关文法将是疯狂的，因为句法正确性取决于扩展用户定义的宏的语义。基本上，每次定义宏时，程序员都会扩展 C 语言的语法。在 CWI，我们确实为 C 编写了上下文无关文法，给出了一组已知的宏定义来扩展 C 语言并且效果很好，但这不是一个通用的解决方案。

于 2013-10-26T10:20:49.243 回答
0

这里有两件事：

  1. 语言的结构（语法）：这是上下文无关的，因为你不需要知道周围的环境来弄清楚什么是标识符和什么是函数。
  2. 程序的含义（语义）：这不是上下文无关的，因为您需要知道是否已声明标识符以及引用它时的类型。
于 2013-10-25T17:04:18.047 回答