PEG pour l'indentation de style Python

Question

Comment écririez-vous une Analyse de l'Expression de la Grammaire et de la Parser (Générateurs dePEG.js, Agrumes, Arbres) qui peut gérer Python/Haskell/CoffeScript style d'indentation:

Des exemples d'un pas-encore-existant langage de programmation:

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

Mise à jour: N'essayez pas d'écrire un interprète pour les exemples ci-dessus. Je suis seulement intéressé par l'indentation problème. Un autre exemple pourrait être l'analyse de la suivante:

foo
  bar = 1
  baz = 2
tap
  zap = 3

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

Answer 1

Pure PEG ne peut pas analyser l'indentation.

Mais peg.js pouvez.

J'ai fait une rapide et sale expérience (inspirée par l'Ira de Baxter commentaire à propos de la tricherie).

/* 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 est une pile de indentations. tiret() renvoie une matrice de mise en retrait des jetons et start() déballe le tableau pour faire de l'analyseur se comporter un peu comme un ruisseau.

peg.js produit pour le texte:

alpha
  beta
  gamma
    delta
epsilon
    zeta
  eta
theta
  iota

ces résultats:

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

Cet analyseur même captures mauvais tirets.

Answer 2

Je pense à une mise en retrait sensible à la langue qui est sensible au contexte. Je crois que le PEG ne peut le faire le contexte-gratuit langues.

Notez que, bien que nalply la réponse est certainement exact que PEG.js pouvez le faire par l'intermédiaire extérieure de l'état (c'est à dire le redouté des variables globales), il peut être dangereux de chemin à pied vers le bas (pire que les problèmes habituels avec des variables globales). Certaines règles peuvent initialement match (et puis exécutez leurs actions) mais parent règles peut échouer ainsi à l'origine de l'action à exécuter pour être valide. Si extérieure de l'état est changé en une telle action, vous pouvez vous retrouver avec un état non valide. C'est super terrible, et pourrait conduire à des tremblements, des vomissements, et la mort. Certaines de ces questions et des solutions à ce sont dans les commentaires ici: https://github.com/dmajda/pegjs/issues/45

Answer 3

Donc, ce que nous sommes vraiment en train de faire ici avec l'indentation est de créer quelque chose comme un C-style blocs qui ont souvent leur propre portée lexicale. Si j'avais écrit un compilateur pour un langage comme ça, je crois que je vais essayer de l'avoir le lexer garder une trace de l'indentation. Chaque fois que l'indentation augmente, il pourrait insérer un '{' token. De la même manière à chaque fois qu'il diminue, il pourrait en médaillon un '}' token. Puis l'écriture d'une grammaire des expressions explicites des accolades pour représenter portée lexicale devient plus simple.