你的词汇有点奇怪。大多数解析器都设计为识别语言的语法。通常,语言定义会定义一些终结符,并明确排除“空格”,由终结符文本之间的无趣序列组成,通常包括空格、制表符和各种独立的注释。因此,在解析中使用的“终止符”一词通常意味着“不是空格”的那些语言原子。你隐含地将其定义为包含空格,我认为这会导致问题。
从这个角度来看,避免使用空格来混淆解析器使用的语法定义最简单的方法是让词法分析器不将空格传递给解析器。然后,您的语法不需要指示如何处理它们(是的,做这样的语法真的很凌乱),解析器不必担心它们,它们也不会出现在树中。
如果您正在构建编译器或解释器,则忽略空格最容易。
如果您正在构建一个重构解析器(请参见我们的
DMS软件重构工具包),那么至少在AST中捕获注释非常重要,因为最终希望从构建的AST重新生成文本,并且如果重新生成的文本包含注释,则会很有帮助。[您可以用其他方法做到这一点,但它们不如这种方法简单]。
DMS词法分析器内部产生“微”标记,这些标记是您语言标记、空格和注释的概念。它丢弃空格微标记,因为它们根本没有添加任何内容(请参见上述讨论)。它将传统标记传递给解析器,就像您所期望的那样。它将注释标记粘合到前面或后面的语言标记上,具体取决于标记类型和遇到位置; 对于C语言,/* ... */在标记之前出现时附加到标记上,// ...注释附加到前面的标记上(还有一些更微妙的细节在此未讨论)。然后,解析仍然只看到语言标记,因此语法不会不必要地复杂化,如果所有附加到标记的信息都放在树中,则注释也会随之而来。
现在,人们经常需要“抽象”语法树;他们想要省略像“(”和“)”这样的东西。我上面描述的方案将注释附加到甚至是这些具体标记的地方。现在有一个复杂的问题:如果你从树中剔除( .. )标记,那么附加的注释也会消失。糟糕了。
所以DMS解析器做了一件复杂的事情:附加到具有逻辑位置但实际上不存在的标记(“消除终端”)的注释被提升到父树节点,并带有一个注释,表示它们属于缺失的子标记。是的,实施这确实很麻烦。
好消息是,在DMS的通用解析机制中,我们只需要这样做一次,它可以适用于许多语言。但这意味着你必须愿意构建一个不寻常的(“再造”)解析器,而我们也有商业动机去这样做。
编辑:不清楚 OP 为什么想要这个,但他坚持在树中捕获空格。由于他没有告诉我们原因,我猜测:他想要标记/树节点的精确列信息。这并不难做到:教 lexer 跟踪位置(行/列),并为每个 token(包括注释等微型 token)打上起始/结束位置,并让解析器将该信息存储在树中。这样也避免了在树中保留空格。(DMS 也是这样做的,因为在报告问题时,精确信息很有用,在重新生成代码时,将代码放回其原始位置(至少相同的列)通常是可取的)。
编辑2:如果 OP 坚持捕获空格,他可以考虑探索 scannerless GLR parsing。这会保留输入流中的每个字符,包括空格。