programming-languages - 您将如何实现越位规则？

Question

我已经编写了一个可以解决这个问题的生成器，但我想知道实现越位规则的最佳方法。

很快:Off-side rule意味着在这种情况下，缩进被认为是一个句法元素。

这是伪代码中的越位规则，用于制作以可用形式捕获缩进的标记器，我不想按语言限制答案:

token NEWLINE
    matches r"\n\ *"
    increase line count
    pick up and store the indentation level
    remember to also record the current level of parenthesis

procedure layout tokens
    level = stack of indentation levels
    push 0 to level
    last_newline = none
    per each token
        if it is NEWLINE put it to last_newline and get next token
        if last_newline contains something
            extract new_level and parenthesis_count from last_newline
            - if newline was inside parentheses, do nothing
            - if new_level > level.top
                push new_level to level
                emit last_newline as INDENT token and clear last_newline
            - if new_level == level.top
                emit last_newline and clear last_newline
            - otherwise
                while new_level < level.top
                    pop from level
                    if new_level > level.top
                        freak out, indentation is broken.
                    emit last_newline as DEDENT token
                clear last_newline
        emit token
    while level.top != 0
        emit token as DEDENT token
        pop from level

comments are ignored before they are getting into the layouter
layouter lies between a lexer and a parser

此布局器一次不会生成多个 NEWLINE，并且在出现缩进时不会生成 NEWLINE。因此解析规则仍然非常简单。我认为这很好，但请告知是否有更好的方法来完成它。

在使用它一段时间后，我注意到在 DEDENT 之后发出换行符可能很好，这样您就可以用 NEWLINE 分隔表达式，同时将 INDENT DEDENT 作为表达式的预告片。

Answer 1

在过去的几年里，我为一些以缩进为中心的特定领域语言编写了标记器和解析器，并且你所拥有的东西对我来说看起来很合理，无论它值多少钱。如果我没记错的话，您的方法与 Python 所做的非常相似，例如，它似乎应该具有一定的分量。

在遇到解析器之前将 NEWLINE NEWLINE INDENT 转换为仅 INDENT 似乎是正确的做事方式——总是在解析器中窥视它是一种痛苦(IME)!我实际上已经将这一步作为一个单独的层完成，最终是一个三步过程:第一个组合你的词法分析器和布局器所做的减去所有 NEWLINE 前瞻的东西(这使它变得非常简单)，第二个(也非常简单) ) 层折叠连续的换行符并将 NEWLINE INDENT 转换为仅 INDENT(或者，实际上，将 COLON NEWLINE INDENT 转换为 INDENT，因为在这种情况下，所有缩进的块总是以冒号开头)，然后解析器是第三阶段。但对我来说，按照你描述的方式做事情也很有意义，特别是如果你想将词法分析器与布局器分开，如果你使用代码生成工具，你可能会想要这样做例如，按照惯例制作您的词法分析器。

我确实有一个应用程序需要在缩进规则方面更加灵活，基本上让解析器在需要时强制执行它们——以下需要在某些上下文中有效，例如:

this line introduces an indented block of literal text:
    this line of the block is indented four spaces
  but this line is only indented two spaces

这对 INDENT/DEDENT 标记的工作效果不佳，因为您最终需要为每一列缩进生成一个 INDENT，并在返回的路上生成相同数量的 DEDENT，除非您提前确定缩进级别最终会成为，这似乎不是你想要一个标记器来做的。在那种情况下，我尝试了一些不同的事情，最终只在每个 NEWLINE 标记中存储了一个计数器，该计数器给出了以下逻辑行的缩进(正或负)的变化。 (每个标记还存储所有尾随空格，以防它需要保留；对于 NEWLINE，存储的空格包括 EOL 本身、任何中间空行以及以下逻辑行上的缩进。)根本没有单独的 INDENT 或 DEDENT 标记。让解析器处理这个问题比嵌套 INDENT 和 DEDENT 需要更多的工作，而且很可能会遇到需要花哨的解析器生成器的复杂语法，但它并没有我担心的那么糟糕，任何一个。同样，解析器不需要从 NEWLINE 提前查看此方案中是否有 INDENT。

尽管如此，我认为您会同意在标记器/布局器中允许和保留各种看起来很疯狂的空白并让解析器决定什么是文字和什么是代码是一个不寻常的要求!例如，如果您只是希望能够解析 Python 代码，您当然不希望您的解析器背负着缩进计数器。您做事的方式几乎可以肯定是您的应用程序和许多其他应用程序的正确方法。虽然如果其他人对如何最好地做这种事情有想法，我显然很想听听他们......