parsing之用于 Python 样式缩进的 PEG

你会怎么写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 } } 

请您参考如下方法:

纯 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", 
   "", 
   "" 
] 

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