用于Python样式缩进的PEG

Question

您将如何在以下任何可以处理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可以.

我做了一个快速而肮脏的实验(受到艾拉巴克斯特关于作弊的评论的启发).

/* 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",
   "",
   ""
]

这个解析器甚至可以捕获坏的缩进.

Answer 2

我认为像这样的缩进敏感语言是上下文敏感的.我相信PEG只能做无背景的语言.

请注意,虽然nalply的答案肯定是正确的,PEG.js可以通过外部状态(即可怕的全局变量)来做到,但它可能是一条走路的危险路径(比全局变量的常见问题更糟).某些规则最初可以匹配(然后运行其操作),但父规则可能会失败,从而导致操作运行无效.如果在此类操作中更改了外部状态,则最终可能会出现无效状态.这太可怕了,可能导致震颤,呕吐和死亡.一些问题和解决方案在这里的评论:https://github.com/dmajda/pegjs/issues/45

Answer 3

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