大多数解析器生成器不会处理上下文无关语法。他们处理一些子集(LL(1),LL(k),LL(*),LALR(1),LR(k),...)。如果您选择其中之一,您几乎肯定必须修改您的语法以匹配解析器生成器的限制(没有左递归,有限的前瞻,......)。如果你想要一个真正的无上下文解析器生成器,你需要一个早期解析器生成器(低效)、一个 GLR 解析器生成器(最实用的)或 PEG 解析器生成器(最后一个不是无上下文的;它需要要排序的规则以确定哪些规则优先)。
您似乎担心混合用于构建树的语法和解析器操作。
如果您构建的树不是语法的直接功能,则必须有某种方法将树构建机器与语法产生联系起来。将它“靠近”语法产生是一种方法,但会导致您的“混合”符号反对。
另一种方法是给每个规则一个名称(或一些唯一标识符),并将树构建机制设置为由名称索引的一侧。这样你的语法就不会被“其他东西”污染,这似乎是你的反对意见。我所知道的解析器生成器系统都没有这样做。一个尴尬的问题是你现在必须发明很多规则名称,而任何时候你有几百个名称本身就很不方便,而且很难让它们助记。
第三种方法是使语法成为函数,并自动生成树构建步骤。这根本不需要额外的东西来生成 AST。我知道的唯一工具(可能还有其他工具,但我一直在寻找 20 多年但没有见过)是我公司的产品DMS Software Reengineering Toolkit。[DMS 不仅仅是一个解析器生成器;它是一个完整的生态系统,用于为任意语言构建程序分析和转换工具,使用 GLR 解析引擎;是的,它处理 Python 样式的缩进]。
一个反对意见是,这种树是具体的、臃肿的和令人困惑的。如果做得对,那是不对的。我对这个问题的回答是:
抽象语法树和具体语法树有什么区别?讨论我们如何从自动生成的压缩 CST 中获得 AST 的好处。
关于 DMS 方案的好消息是基本语法并没有因解析支持而臃肿。不太好的消息是你会发现很多其他的东西你想与语法规则相关联(漂亮的打印规则、属性计算、树合成……),然后你又回到了相同的选择。DMS 拥有所有这些“其他东西”,并通过多种方式解决关联问题:
通过在语法规则旁边放置其他相关的描述性形式(产生您抱怨的混合)。对于漂亮打印规则,我们可以容忍这一点,因为事实上,语法(解析)规则与漂亮打印(反解析)规则相邻是很好的。我们还允许将属性计算放在语法规则附近以提供关联。
虽然 DMS 允许规则有名称,但这只是为了方便程序代码访问,而不是将其他机制与规则相关联。
DMS 提供了第三种方式来关联这些机制(尤其是属性语法计算),方法是将规则本身用作一种巨大的名称。因此,您在一个地方编写语法和漂亮打印规则,而在其他地方您可以使用关联的属性计算再次编写语法规则。原则上,这就像给每个规则一个名称(好吧,一个签名)并将计算与名称相关联。但它也允许我们定义许多不同的属性计算(用于不同的目的)并将它们与它们的规则相关联,而不会弄乱基本语法。我们的工具检查(规则,关联计算)在基本语法中是否具有有效规则,因此当基本语法发生变化时,它可以相对地跟踪需要修复的内容。
这是我的工具(我是架构师),您不应该将此作为建议,而只是一种偏见。这种偏见得到了 DMS 解析(无需抱怨)C、C++、Java、C#、IBM Enterprise COBOL、Python、F77/F90/F95 以及 column6 continue/F90 continue 和嵌入式 C 预处理器指令在大多数情况下启动的能力的支持), Mumps、PHP4/5 和许多其他语言。