具有缩进和回溯的递归下降解析器

Question

我一直在尝试找到一种也适合回溯缩进的递归下降解析器算法。但我一直让自己为此寻找麻烦的解决方案。

是否有任何资源也可以处理缩进？

谢谢

Answer 1

根据您的问题，我假设您正在为缩进敏感语言编写自己的递归下降解析器。

我之前尝试过基于缩进的语言，并通过设置一个跟踪当前缩进级别的状态和两个匹配缩进的不同终端来解决这个问题。它们都匹配缩进单位（例如两个空格或制表符）并对它们进行计数。我们将匹配的缩进级别matched_indentation和当前缩进级别称为expected_indentation。

对于第一个，我们称其为indent：

• 如果matched_indentation < expected_indentation，则这是 a dedent，并且匹配失败。
• 如果matched_indentation == expected_indentation，则匹配成功。匹配器消耗缩进。
• if matched_indentation > expected_indentation，你有一个语法错误（无缘无故的缩进）并且应该这样处理它（抛出异常或其他东西）。

对于第二个，我们称之为dedent：

• 如果matched_indentation < expected_indentation，则匹配成功。你减expected_indentation一，但不消耗输入。这样您就可以链接多个dedent终端来关闭多个范围。

• 如果matched_indentation == expected_indentation，则匹配成功，这次您确实消耗了输入（这是最后一个dedent终端，所有范围都已关闭）。

  如果matched_indentation > expected_indentation，则匹配失败，则此处不存在dedent。

您预计缩进量会增加的那些终端和非终端应增加expected_indentation1。

假设您想要实现一个类似 python 的 if 语句（我将使用类似 EBNF 的表示法），它看起来像这样：

indented_statement : indent statement newline;    

if_statement : 'if' condition ':' newline indented_statement+ dedent ;

现在让我们看一下下面的代码，并假设 an是您的规则if_statement的一部分：statement

1|if cond1:                 <- expected_indentation = 0, matched_indentation = 0
2|  if cond2:               <- expected_indentation = 1, matched_indentation = 1
3|    statement1            <- expected_indentation = 2, matched_indentation = 2
4|    statement2            <- expected_indentation = 2, matched_indentation = 2
5|                          <- expected_indentation = 2, matched_indentation = 0

• 在前四行，您将成功匹配indent终端
• 在最后一行，您将匹配两个dedent终端，关闭两个范围，并得到结果expected_indentation = 0

您应该注意的一件事是放置indent终端的位置dedent。在本例中，我们不需要if_statement规则中的 1，因为它是statement, 并且indented_statement已经需要缩进。

还要注意如何对待换行符。一种选择是将它们用作一种语句终止符，另一种选择是将它们放在缩进之前，因此选择最适合您的选项。