parsing - 用于 Python 样式缩进的 PEG

Question

你会怎么写Parsing Expression Grammar在以下任何可以处理 Python/Haskell/CoffeScript 样式缩进的解析器生成器( PEG.js 、 Citrus 、 Treetop )中:

尚不存在的编程语言的示例:

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 关于作弊的评论的启发)并编写了一个简单的标记器。

有关更完整的解决方案(完整的解析器)，请参阅此问题:Parse indentation level with 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"                                     {}

depths是一堆缩进。 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",
   "",
   ""
]

这个标记器甚至可以捕获错误的缩进。