PEG pour l'indentation de style Python

StackOverflow https://stackoverflow.com/questions/4205442

Question

Comment écririez-vous un Parsing grammaire d'expression dans l'un des générateurs de Parser suivants ( PEG.js , arboricole ) qui peut gérer indentation de style Python / Haskell / coffeescript:

Exemples d'un langage de programmation non encore existant: 

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: Ne pas essayer d'écrire un interprète pour les exemples ci-dessus. Je suis seulement intéressé par le problème de retrait. Un autre exemple pourrait être l'analyse du suivant: 

foo
  bar = 1
  baz = 2
tap
  zap = 3

# should yield (ruby style hashmap):
# {:foo => { :bar => 1, :baz => 2}, :tap => { :zap => 3 } }
Était-ce utile?

La solution

pur PEG ne peut pas analyser indentation.

Mais peg.js peut.

Je l'ai fait une expérience rapide et sale (étant inspirée par le commentaire de Ira Baxter au sujet de la tricherie) et écrit simple tokenizer.

Pour une solution plus complète (un analyseur complet) s'il vous plaît voir cette question: niveau de retrait Parse avec 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 est une pile de indentations. tiret () rend un tableau de jetons d'indentation et commencer () déballe le tableau pour rendre l'analyseur se comporte un peu comme un flux.

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

Cette tokenizer attrape même tirets mauvais.

Autres conseils

Je pense un langage sensible indentation comme qui est sensible au contexte. Je crois que le PEG ne peut faire langauges sans contexte.

Notez que, alors que la réponse de nalply est certainement exact que PEG.js peut le faire via l'état externe (les variables globales redoutés), il peut être un chemin dangereux de marcher (pire que les problèmes habituels avec les variables globales). Certaines règles peuvent d'abord correspondre (puis exécutez leurs actions), mais les règles parents peuvent échouer causant ainsi la course d'action invalide. Si l'état externe est modifié dans 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. Quelques problèmes et solutions à ce sont dans les commentaires ici: https://github.com/dmajda/pegjs / questions / 45

Alors ce que nous faisons vraiment ici avec indentation crée quelque chose comme un des blocs de type C qui ont souvent leur propre champ lexical. Si je devais écrire un compilateur pour un langage comme ça, je pense que je voudrais essayer et d'avoir le lexer garder une trace de l'empreinte. Chaque fois que l'empreinte augmente, il pourrait insérer un jeton « { ». De même chaque fois qu'il diminue, il pourrait un encart « } » jeton. écrit alors une grammaire d'expression avec des accolades explicites pour représenter la portée lexicale devient plus avant droit.

Vous pouvez le faire en arboricole en utilisant des prédicats sémantiques. Dans ce cas, vous avez besoin d'un prédicat sémantique qui détecte la fermeture d'un bloc indenté espace blanc en raison de l'apparition d'une autre ligne qui a la même ou moins en retrait. Le prédicat doit compter le renfoncement à partir de la ligne d'ouverture, et retourner true (bloc fermé) si l'indentation de la ligne courante est terminée à la même longueur ou plus courte. Parce que la condition de fermeture est reliée au contexte, il ne faut pas memoized. Voici le code exemple, je suis sur le point d'ajouter à la documentation arboricole. Notez que j'ai surchargé le SyntaxNode de arboricole méthode inspect pour le rendre plus facile à visualiser le résultat. 

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

Voici un petit programme pilote de test afin que vous puissiez l'essayer facilement: 

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

Je sais que c'est un vieux fil, mais je voulais juste ajouter un code PEGjs aux réponses. Ce code va analyser un morceau de texte et « nid » dans une sorte de structure « AST-ish ». Il va seulement une profonde et il semble laid, de plus, il n'a pas vraiment utiliser les valeurs de retour pour créer la bonne structure, mais garde un arbre en mémoire de votre syntaxe et il retournera à la fin. Cela pourrait bien devenir difficile à manier et causer des problèmes de performances, mais au moins il fait ce qu'il est censé.

Remarque: Assurez-vous d'avoir des onglets au lieu des espaces 

{ 
    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"
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top