PEG für Python-Stil Einzug

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

Frage

Wie würden Sie einen Parsing Expression Grammatik in einem der folgenden Parser-Generatoren ( PEG.js , Treetop ), die Python / Haskell / Coffeescript Stil Einzug verarbeiten kann:

Beispiele für einen noch nicht vorhandenen Programmiersprache: 

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

Update: Versuchen Sie nicht, einen Interpreter für die obigen Beispiele zu schreiben. Ich bin nur in der Vertiefung Problem interessiert. Ein weiteres Beispiel könnte die folgende sein Parsen: 

foo
  bar = 1
  baz = 2
tap
  zap = 3

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

Lösung

Reines PEG kann nicht Parse-Einzug.

Aber peg.js können.

Ich habe ein schnelles und unsauberes Experiment (von Ira Baxter Kommentar inspiriert über Betrug) und schrieb ein einfaches tokenizer.

Für eine vollständigere Lösung (ein vollständiger Parser) bitte diese Frage finden Sie unter: Parst Einrückungsebene mit 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 ist ein Stapel von Vertiefungen. indent () gibt ein Array von Einbuchtung Token zurück und starten () das Array auspackt den Parser verhalten sich etwas wie ein Strom zu machen.

peg.js produziert für den Text: 

alpha
  beta
  gamma
    delta
epsilon
    zeta
  eta
theta
  iota

diese Ergebnisse: 

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

Dieser tokenizer sogar fängt schlecht Einzüge.

Andere Tipps

Ich denke, eine Vertiefung sensible Sprache wie das ist kontextsensitiv. Ich glaube, PEG kann nur kontextfreien langauges tun.

Beachten Sie, dass, während nalply Antwort der ist sicher richtig, dass PEG.js es über externen Staat tun kann (dh die gefürchteten globalen Variablen), kann es ein gefährlicher Weg zu gehen nach unten (schlechter als die üblichen Problemen mit globalen Variablen). Einige Regeln können zunächst übereinstimmen (und dann ihre Aktionen ausgeführt werden), aber Eltern Regeln können somit nicht die Aktion Lauf verursacht ungültig. Wenn externe Zustand in eine solche Aktion geändert wird, können Sie sich mit ungültigen Zustand beenden. Das ist super schrecklich, und könnte zu Zittern, Erbrechen und Tod führen. Einige Probleme und Lösungen dafür sind in den Kommentaren hier: https://github.com/dmajda/pegjs / issues / 45

Also, was wir wirklich hier tun mit Vertiefung ist so etwas wie ein C-Stil Blöcke zu schaffen, die oft ihren eigenen lexikalischen Gültigkeitsbereich haben. Wenn ich einen Compiler für eine Sprache schrieben, dass ich glaube, ich würde versuchen, die Lexer verfolgen die Vertiefung haben. Jedes Mal, erhöht sich die Einbuchtung es einfügen könnte ‚{‘ token. Ebenso jedes Mal, wenn es abnimmt könnte ein ‚}‘ token nach innen versetzt. Dann einen Ausdruck Grammatik mit expliziten geschweiften Klammern schreiben lexikalischer darstellen Umfang mehr geradlinig wird.

Sie können diese mithilfe von semantischen Prädikaten in Treetop tun. In diesem Fall müssen Sie ein semantisches Prädikat, das erkennt einen weißen Raum eingerückt Block aufgrund des Auftretens einer anderen Leitung zu schließen, die die gleichen oder geringere Vertiefung hat. Das Prädikat muss die Vertiefung von der Öffnung Linie zählen, und return true (Block geschlossen), wenn die Einrückung der Stromleitung von der gleichen oder kürzerer Länge fertig gestellt. Da der Schließzustand kontextabhängig ist, darf es nicht memoized werden. Hier ist der Beispielcode ich bin zu Treetop Dokumentation hinzuzufügen. Beachten Sie, dass ich habe Treetop die SyntaxNode inspizieren Methode außer Kraft gesetzt, um es einfacher das Ergebnis sichtbar zu machen. 

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

Hier ist ein kleines Test-Treiberprogramm, so dass Sie es leicht ausprobieren können: 

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

Ich weiß, das ist ein alter Thread, aber ich wollte nur etwas PEGjs Code auf die Antworten hinzuzufügen. Dieser Code wird ein Stück Text und „Nest“ in eine Art „AST-ish“ Struktur analysiert. Es geht nur eine tief und es sieht hässlich aus, außerdem ist es nicht wirklich die Rückgabewerte verwenden, um die richtige Struktur zu schaffen, sondern hält einen speicherinternen Baum Ihrer Syntax und es wird wieder, dass am Ende. Dies könnte auch unhandlich und einige Performance-Probleme verursachen, aber zumindest tut es das, was es soll.

Hinweis: Kontrollieren Sie, ob Tabs statt Leerzeichen 

{ 
    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"
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top