Python 风格缩进的 PEG

Question

您如何在以下任何解析器生成器中编写解析表达式语法（PEG.js, 柑橘, Treetop) 可以处理 Python/Haskell/CoffeScript 风格的缩进：

not 的示例- 现有的编程语言：

square x =
    x * x

---

cube x =
    x * square x

---

fib n =
  if n <= 1
    0
  else
    fib(n - 2) + fib(n - 1) # some cheating allowed here with brackets

更新： 不要尝试为上面的示例编写解释器。我只对缩进问题感兴趣。另一个例子可能是解析以下内容：

foo
  bar = 1
  baz = 2
tap
  zap = 3

# should yield (ruby style hashmap):
# {:foo => { :bar => 1, :baz => 2}, :tap => { :zap => 3 } }

Answer 1

纯 PEG 无法解析缩进。

但 peg.js 可以。

我做了一个快速而肮脏的实验（受到 Ira Baxter 关于作弊的评论的启发）并编写了一个简单的标记器。

如需更完整的解决方案（完整的解析器），请参阅此问题：使用 PEG.js 解析缩进级别

/* Initializations */
{
  function start(first, tail) {
    var done = [first[1]];
    for (var i = 0; i < tail.length; i++) {
      done = done.concat(tail[i][1][0])
      done.push(tail[i][1][1]);
    }
    return done;
  }

  var depths = [0];

  function indent(s) {
    var depth = s.length;

    if (depth == depths[0]) return [];

    if (depth > depths[0]) {
      depths.unshift(depth);
      return ["INDENT"];
    }

    var dents = [];
    while (depth < depths[0]) {
      depths.shift();
      dents.push("DEDENT");
    }

    if (depth != depths[0]) dents.push("BADDENT");

    return dents;
  }
}

/* The real grammar */
start   = first:line tail:(newline line)* newline? { return start(first, tail) }
line    = depth:indent s:text                      { return [depth, s] }
indent  = s:" "*                                   { return indent(s) }
text    = c:[^\n]*                                 { return c.join("") }
newline = "\n"                                     {}

深度 是一堆缩进。 indent() 返回一个缩进标记数组，start() 解包该数组以使解析器的行为有点像流。

peg.js 为文本生成：

alpha
  beta
  gamma
    delta
epsilon
    zeta
  eta
theta
  iota

这些结果：

[
   "alpha",
   "INDENT",
   "beta",
   "gamma",
   "INDENT",
   "delta",
   "DEDENT",
   "DEDENT",
   "epsilon",
   "INDENT",
   "zeta",
   "DEDENT",
   "BADDENT",
   "eta",
   "theta",
   "INDENT",
   "iota",
   "DEDENT",
   "",
   ""
]

此标记生成器甚至可以捕获错误的缩进。

Answer 2

我认为像这样的缩进敏感语言是上下文敏感的。我相信 PEG 只能处理上下文无关的语言。

请注意，虽然 nalply 的答案肯定是正确的，即 PEG.js 可以通过外部状态（即可怕的全局变量）来做到这一点，但它可能是一条危险的道路（比全局变量的常见问题更糟糕）。某些规则最初可以匹配（然后运行其操作），但父规则可能会失败，从而导致操作运行无效。如果在此类操作中外部状态发生更改，您可能会得到无效状态。这是非常可怕的，可能会导致颤抖、呕吐和死亡。一些问题和解决方案位于此处的评论中： https://github.com/dmajda/pegjs /问题/45

Answer 3

因此，我们在这里使用缩进真正做的是创建类似 C 风格块的东西，这些块通常有自己的词法范围。如果我正在为这样的语言编写编译器，我想我会尝试让词法分析器跟踪缩进。每次缩进增加时，它都可以插入一个“{”标记。同样，每次减少时，它都可以插入一个“}”标记。然后编写带有显式花括号的表达式语法来表示词法范围变得更加直接。

Answer 4

您可以在 Treetop 中使用语义谓词来执行此操作。在这种情况下，您需要一个语义谓词来检测由于出现具有相同或更少缩进的另一行而关闭空白缩进块。谓词必须计算从起始行开始的缩进，如果当前行的缩进已完成相同或更短的长度，则返回 true（块已关闭）。因为结束条件是依赖于上下文的，所以不能记住它。
这是我要添加到 Treetop 文档中的示例代码。请注意，我已经重写了 Treetop 的 SyntaxNode 检查方法，以便更轻松地可视化结果。

grammar IndentedBlocks
  rule top
    # Initialise the indent stack with a sentinel:
    &{|s| @indents = [-1] }
    nested_blocks
    {
      def inspect
        nested_blocks.inspect
      end
    }
  end

  rule nested_blocks
    (
      # Do not try to extract this semantic predicate into a new rule.
      # It will be memo-ized incorrectly because @indents.last will change.
      !{|s|
        # Peek at the following indentation:
        save = index; i = _nt_indentation; index = save
        # We're closing if the indentation is less or the same as our enclosing block's:
        closing = i.text_value.length <= @indents.last
      }
      block
    )*
    {
      def inspect
        elements.map{|e| e.block.inspect}*"\n"
      end
    }
  end

 rule block
    indented_line       # The block's opening line
    &{|s|               # Push the indent level to the stack
      level = s[0].indentation.text_value.length
      @indents << level
      true
    }
    nested_blocks       # Parse any nested blocks
    &{|s|               # Pop the indent stack
      # Note that under no circumstances should "nested_blocks" fail, or the stack will be mis-aligned
      @indents.pop
      true
    }
    {
      def inspect
        indented_line.inspect +
          (nested_blocks.elements.size > 0 ? (
            "\n{\n" +
            nested_blocks.elements.map { |content|
              content.block.inspect+"\n"
            }*'' +
            "}"
          )
          : "")
      end
    }
  end

  rule indented_line
    indentation text:((!"\n" .)*) "\n"
    {
      def inspect
        text.text_value
      end
    }
  end

  rule indentation
    ' '*
  end
end

这是一个小测试驱动程序，您可以轻松尝试：

require 'polyglot'
require 'treetop'
require 'indented_blocks'

parser = IndentedBlocksParser.new

input = <<END
def foo
  here is some indented text
    here it's further indented
    and here the same
      but here it's further again
      and some more like that
    before going back to here
      down again
  back twice
and start from the beginning again
  with only a small block this time
END 

parse_tree = parser.parse input

p parse_tree

Answer 5

我知道这是一个旧线程，但我只是想在答案中添加一些 PEGjs 代码。这段代码将解析一段文本并将其“嵌套”到一种“AST-ish”结构中。它只深入一层，看起来很丑，而且它并没有真正使用返回值来创建正确的结构，而是在内存中保留语法树，并在最后返回该树。这很可能变得笨拙并导致一些性能问题，但至少它做了它应该做的事情。

注意：确保使用制表符而不是空格！

{ 
    var indentStack = [], 
        rootScope = { 
            value: "PROGRAM",
            values: [], 
            scopes: [] 
        };

    function addToRootScope(text) {
        // Here we wiggle with the form and append the new
        // scope to the rootScope.

        if (!text) return;

        if (indentStack.length === 0) {
            rootScope.scopes.unshift({
                text: text,
                statements: []
            });
        }
        else {
            rootScope.scopes[0].statements.push(text);
        }
    }
}

/* Add some grammar */

start
  = lines: (line EOL+)*
    { 
        return rootScope;
    }


line
  = line: (samedent t:text { addToRootScope(t); }) &EOL
  / line: (indent t:text { addToRootScope(t); }) &EOL
  / line: (dedent t:text { addToRootScope(t); }) &EOL
  / line: [ \t]* &EOL
  / EOF

samedent
  = i:[\t]* &{ return i.length === indentStack.length; }
    {
        console.log("s:", i.length, " level:", indentStack.length);
    }

indent
  = i:[\t]+ &{ return i.length > indentStack.length; }
    {
        indentStack.push(""); 
        console.log("i:", i.length, " level:", indentStack.length);
    }

dedent
    = i:[\t]* &{ return i.length < indentStack.length; }
      {
          for (var j = 0; j < i.length + 1; j++) {
              indentStack.pop();
          } 
          console.log("d:", i.length + 1, " level:", indentStack.length);  
      }

text
    = numbers: number+  { return numbers.join(""); } 
    / txt: character+   { return txt.join(""); }


number
    = $[0-9] 

character 
    = $[ a-zA-Z->+]  
__
    = [ ]+

_ 
    = [ ]*

EOF 
    = !.

EOL
    = "\r\n" 
    / "\n" 
    / "\r"