将不应存在的节点放入解析树中

7
我正在编写一种语言的解析器,扫描器被设计成根据一个布尔标记来

  1. 返回不必要的终端(例如空格)或者
  2. 不返回。

现在,在解析器中,我不想用所有这些终端来混淆语法,它们应该以某种方式被解析树“自动地”吞噬掉。

为了做到这一点,“神奇”的方法是,我想把终端链接起来(简单的环形链表),这样我就可以迭代它们,并在规约发生时“填补空白”。

这听起来像一个合理的想法,但有一个问题。你还记得我说过“返回...或不返回”吗?在情况(2)下,我会释放终端,因为谁知道接下来会发生什么?而且我不想有任何内存泄漏。

但在情况(1)下,我不能释放终端,因为基于它们,我将在进一步的规约中决定那个“填补空白”的过程应该停止。

我也不能有条件地释放它,因为出于同样的原因:我不知道接下来会发生什么。如果不会触发任何“填补空白”的过程怎么办?如果根本没有进一步的规约怎么办?

你是否遇到过类似的问题?你是如何解决它的?

:这都是我心中的想法,我可能没有解释清楚,请问一下,我会编辑我的问题。情景实际上更加复杂,我不是从头开始编写,我正在将其集成到其他东西中,所以很可能我会回答“由于环境限制,我不能这样做”。


附言

我想到的唯一真正好的主意是分叉并改进解析器生成器,在某些小地方我已经这样做了,以克服我上面提到的一些限制。

1个回答

3
你的词汇有点奇怪。大多数解析器都设计为识别语言的语法。通常,语言定义会定义一些终结符,并明确排除“空格”,由终结符文本之间的无趣序列组成,通常包括空格、制表符和各种独立的注释。因此,在解析中使用的“终止符”一词通常意味着“不是空格”的那些语言原子。你隐含地将其定义为包含空格,我认为这会导致问题。

从这个角度来看,避免使用空格来混淆解析器使用的语法定义最简单的方法是让词法分析器不将空格传递给解析器。然后,您的语法不需要指示如何处理它们(是的,做这样的语法真的很凌乱),解析器不必担心它们,它们也不会出现在树中。

如果您正在构建编译器或解释器,则忽略空格最容易。

如果您正在构建一个重构解析器(请参见我们的DMS软件重构工具包),那么至少在AST中捕获注释非常重要,因为最终希望从构建的AST重新生成文本,并且如果重新生成的文本包含注释,则会很有帮助。[您可以用其他方法做到这一点,但它们不如这种方法简单]。
DMS词法分析器内部产生“微”标记,这些标记是您语言标记、空格和注释的概念。它丢弃空格微标记,因为它们根本没有添加任何内容(请参见上述讨论)。它将传统标记传递给解析器,就像您所期望的那样。它将注释标记粘合到前面或后面的语言标记上,具体取决于标记类型和遇到位置; 对于C语言,/* ... */在标记之前出现时附加到标记上,// ...注释附加到前面的标记上(还有一些更微妙的细节在此未讨论)。然后,解析仍然只看到语言标记,因此语法不会不必要地复杂化,如果所有附加到标记的信息都放在树中,则注释也会随之而来。
现在,人们经常需要“抽象”语法树;他们想要省略像“(”和“)”这样的东西。我上面描述的方案将注释附加到甚至是这些具体标记的地方。现在有一个复杂的问题:如果你从树中剔除( .. )标记,那么附加的注释也会消失。糟糕了。
所以DMS解析器做了一件复杂的事情:附加到具有逻辑位置但实际上不存在的标记(“消除终端”)的注释被提升到父树节点,并带有一个注释,表示它们属于缺失的子标记。是的,实施这确实很麻烦。
好消息是,在DMS的通用解析机制中,我们只需要这样做一次,它可以适用于许多语言。但这意味着你必须愿意构建一个不寻常的(“再造”)解析器,而我们也有商业动机去这样做。

编辑:不清楚 OP 为什么想要这个,但他坚持在树中捕获空格。由于他没有告诉我们原因,我猜测:他想要标记/树节点的精确列信息。这并不难做到:教 lexer 跟踪位置(行/列),并为每个 token(包括注释等微型 token)打上起始/结束位置,并让解析器将该信息存储在树中。这样也避免了在树中保留空格。(DMS 也是这样做的,因为在报告问题时,精确信息很有用,在重新生成代码时,将代码放回其原始位置(至少相同的列)通常是可取的)。

编辑2:如果 OP 坚持捕获空格,他可以考虑探索 scannerless GLR parsing。这会保留输入流中的每个字符,包括空格。


我知道我想要什么,我想要树中的空格。真的。只是我想要的不是人们通常想要的东西。而且我有很好的理由将这些标记放在树中。非常好的理由。如果没有这些理由,我一开始就不会这样做。但还是谢谢你提醒我。 - Flavius
是的,很明显你知道你想要什么。如果你没有解释清楚你有非常好的理由,或者特别告诉我们你希望实现的最终效果,那么你会得到“传统答案说...”。如果你想走非传统路线,你可以将我们在DMS中所做的事情概括一下:将你的微型标记(包括空格和注释)作为序列附加到语言标记上。 - Ira Baxter
是的,就像我在问题中提到的那样,我使用了链表,不过最终我使用了双向链表。不过内存占用仍然困扰着我,因为为标记添加两个额外的指针成员相当多,不是吗?我不知道,我想我会完成这个原型并看看它的效果如何。 - Flavius
这可能很多,也可能不多;这取决于您正在处理的语言的统计属性。如果您要处理单个程序的10,000行,并且您的解析器在PC上运行,则包括您在内的任何人都不会关心其空间消耗。如果您要处理18,000个编译单元(我们有时使用DMS进行此操作),则空间确实非常宝贵,我会非常努力地不保留空格,因为在我看来,它对您不能通过其他我建议的技术获得的任何贡献都是无用的。 - Ira Baxter

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接