4

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

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

谢谢

4

1 回答 1

3

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

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

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

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

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

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

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

    如果matched_indentation > expected_indentation，则匹配失败，则此处没有 a dedent。

您期望缩进增加的那些终端和非终端应该增加expected_indentation一。

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

indented_statement : indent statement newline;    

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

现在让我们看一下以下代码，并假设 anif_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规则中的一个，因为它是 a statement，并且indented_statement已经需要缩进。

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

于 2013-11-24T15:47:07.723 回答