可以用 yacc 解析哪一类语言？

Question

我最近了解到C 没有上下文无关语法。我最近还了解到gcc 曾经使用 yacc 来解析 C。yacc 实用程序的手册指出“[yacc] 接受的规范类别是非常通用的：具有消歧规则的 LALR(1) 语法”，而维基百科指出LALR 语法是确定性上下文无关语法的子集，它们是上下文无关语法的子集。如果 C 甚至不是上下文无关的（更不用说确定性上下文无关语言），但 yacc 可以解析 C，那么 yacc 可以解析什么类语言（如果不是具有 LALR(1) 的上下文无关语言的子集）语法？

Answer 1

Yacc 生成的计算机程序非常图灵完备。yacc 框架使用 LALR(1) 框架来触发操作，但操作是任意代码。

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

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

简而言之，现实世界的解析器是实用编写的程序，而不是理论学术练习。bison/yacc 解析的语言通常“大部分”是 LALR(1)，它们的词法分析通常“大部分”是正则的，但是当计算机程序充分利用其能力来超越这些限制时，请不要感到惊讶。

这就是使编程成为一项有趣的活动的原因。

这些都不会降低学术理论的用处。Bison/yacc 和其他解析器生成器消除了构建解析器的大量繁琐工作，因为它们可以处理“大部分”分析。语言越接近可分析的上下文无关模型，就越容易生成（“大部分”）其他有用的工具：linter、语法突出显示、重新格式化、索引器、静态分析器、文档提取器等。更不用说充当语言本身语法的文档了。