什么是可以使用yacc解析的语言类？

Question

什么是可以使用yacc解析的语言类？

4

我最近了解到C语言没有上下文无关文法。我也最近了解到gcc曾经使用yacc来解析C语言。yacc实用程序的手册说明{{link3：“被yacc接受的规范类是非常普遍的：带有消歧规则的LALR（1）文法”}}，而维基百科指出，LALR文法是确定性上下文无关文法的子集，是上下文无关文法的子集。如果C甚至不是上下文无关的（更不用说是确定性上下文无关语言），但yacc可以解析C，那么yacc可以解析哪些语言类别，而不是具有LALR（1）文法的上下文无关语言子集？

- user9889635

4

通常使用Yacc将C语言编译，并在词法分析器和语法分析器之间提供上下文感知的反馈，以便正确处理typedef等内容。 - Jonathan Leffler

3

正如 @JonathanLeffler 所说的那样，它使用解析器和词法分析器之间的反馈。我的猜测是：当定义一个名称时，它会被添加到词法分析器使用的令牌表中，以便后续对该名称的使用可以被正确分类。这使得它具有上下文敏感性，即使语法不是。 - Barmar

1

我并没有说这是来自man手册，我说的是来自manual手册，而我给出的引用文字直接链接到了yacc手册，在那里它说yacc接受LALR(1)语法作为输入。维基百科页面说LALR语法是上下文无关语法的子集。因此，yacc接受上下文无关语法的一个子集作为输入规范。 - user9889635

2

@user207421 带有消歧规则的LALR(1)语法仍然没有比上下文无关文法更强大。消歧规则是处理具有二义性上下文无关文法的方法，它们不允许YACC突然接受上下文有关文法。正如其他人所说，YACC可以通过使解析器向词法分析器反馈信息来解析C语言 - 这与消歧规则无关。 - sepp2k

1

@user207421，但它并没有解决问题。问题是如何使用YACC解析上下文敏感的语言（如C语言），因为它只接受LALR语法，而您建议这是由于消除歧义规则（至少这是我从您之前的评论中看到的唯一方式）。我指出这与消除歧义规则（或yacc接受的语法类的普遍性）无关，而是与词法分析器和语法分析器之间的交互有关，而引用的段落并未涉及此问题。因此，不，它没有回答OP的问题。 - sepp2k

显示剩余8条评论

2个回答

1

C语言没有上下文无关文法，这只是因为标识符记号（其词法类别）的语义分类有时需要理解它是如何声明的。C语言被设计为单遍编译，所以在解析的任何时刻，从之前的声明中已知与解析相关的所有内容。范围内的声明可以用来为令牌分配词法类别。

例如，如果解析器在语句块中间面对(A)(B)，这可能是：

- 将表达式(B)强制转换为类型A。 - 将参数列表(B)应用于函数表达式(A)。

但是，这种歧义不必在解析器中出现，因为词法分析器可以窥视范围，并根据A是typedef名称还是其他内容来不同地分类，然后这些不同分类的标识符可以被单独的语法规则所针对。这就像拥有一个魔法神谕，可以为标记添加语义信息，因此可以应用上下文无关技术。

另一个问题，在C语言中首先存在的是预处理器。 C语言的语法被指定为单独的部分：有一个预处理器语法，还有一个针对预处理后的标记流的语法。不能有一个完全捕捉其短语结构细微差别的C语言上下文无关文法，因为预处理可以重新定义语法，并且宏可以在任何地方调用，除了注释和字符串文字中。

- Kaz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

Yacc生成计算机程序，这些程序相当完整的图灵完备。Yacc框架使用LALR（1）框架来触发操作，但这些操作是任意代码。

此外，yacc的输入是令牌流，而不是直接输入。令牌流是由另一个用图灵完备语言编写的计算机程序产生的，该程序也可以以不受上下文限制的方式操纵其输入。

最后，没有什么能阻止yacc生成的解析器最初接受所需语言的超集，然后稍后分析上下文无关的解析树并基于任意计算拒绝某些结构，例如坚持在使用之前声明变量（上下文敏感计算）。

简而言之，实际应用中的解析器是实用主义编写的程序，而不是理论学术习题。被bison/yacc解析的语言通常是“大多数”LALR（1），它们的词法分析通常是“大多数”正则的，但当计算机程序利用它们的全部功能超越这些限制时，不要感到惊讶。

这就是使编程成为有趣活动的原因。这一切都不会使学术理论变得不那么有用。Bison/yacc和其他解析器生成器减轻了构建解析器的许多繁琐工作，因为它们可以处理“大多数”分析。语言越接近可分析的上下文无关模型，生成其他有用工具（例如，linters、语法高亮器、重新格式化程序、索引器、静态分析器、文档提取器等等）就越容易。更不用说作为语言本身语法的文档。