Wie würden Sie die Offside-Regel implementieren?

Question

Ich habe bereits einen Generator geschrieben, der den Trick macht, aber ich würde gerne den bestmöglichen Weg kennen, die Offside-Regel zu implementieren.

Kurz: Off-side rule bedeutet in diesem Zusammenhang, dass Einbuchtung als syntaktisches Element erkannt zu werden.

Hier ist die Abseitsregel in Pseudo-Code für Tokenizer zu machen, dass in verwertbarer Form capture Vertiefung, ich möchte nach Sprache keine Antworten beschränken:

token NEWLINE 
    matches r"\n\ *" 
    increase line count 
    pick up and store the indentation level 
    remember to also record the current level of parenthesis 

procedure layout tokens 
    level = stack of indentation levels 
    push 0 to level 
    last_newline = none 
    per each token 
     if it is NEWLINE put it to last_newline and get next token 
     if last_newline contains something 
      extract new_level and parenthesis_count from last_newline 
      - if newline was inside parentheses, do nothing 
      - if new_level > level.top 
       push new_level to level 
       emit last_newline as INDENT token and clear last_newline 
      - if new_level == level.top 
       emit last_newline and clear last_newline 
      - otherwise 
       while new_level < level.top 
        pop from level 
        if new_level > level.top 
         freak out, indentation is broken. 
        emit last_newline as DEDENT token 
       clear last_newline 
     emit token 
    while level.top != 0 
     emit token as DEDENT token 
     pop from level 

comments are ignored before they are getting into the layouter 
layouter lies between a lexer and a parser 

Diese Layouter bei nicht mehr als ein NEWLINE erzeugen Zeit und erzeugt NEWLINE nicht, wenn ein Einzug entsteht. Daher bleiben Parsing-Regeln recht einfach. Es ist ziemlich gut, denke ich, aber informiere, wenn es einen besseren Weg gibt, es zu erreichen.

Während der Verwendung für eine Weile, habe ich bemerkt, dass es nach DEDENTs nett sein kann, Newline trotzdem auszugeben, auf diese Weise können Sie die Ausdrücke mit NEWLINE trennen, während Sie den INDENT DEDENT als Anhänger für Ausdruck behalten.

Answer 1

Ich habe in den letzten paar Jahren Tokenizer und Parser für ein paar kleine indentationszentrische domänenspezifische Sprachen geschrieben, und was Sie dort haben, sieht für mich ziemlich vernünftig aus, egal was es wert ist. Wenn ich mich nicht irre, ist deine Methode zum Beispiel ziemlich ähnlich zu dem, was Python tut, was so aussieht, als ob es ein gewisses Gewicht haben sollte.

Die Umwandlung von NEWLINE NEWLINE INDENT in nur INDENT, bevor es den Parser erreicht, scheint definitiv der richtige Weg zu sein - es ist ein Schmerz (IME), dafür im Parser immer vorauszuschauen! Ich habe diesen Schritt tatsächlich als separate Ebene in einem dreistufigen Prozess gemacht: der erste kombiniert was dein Lexer und Layouter macht, minus alle NEWLINE-Lookahead-Sachen (was es sehr einfach machte), die zweite (auch sehr einfach)) gefaltet und aufeinanderfolgende neue Zeilen umgewandelt NEWLINE SPIEGELSTRICH Schicht nur SPIEGELSTRICH (oder, Kolon NEWLINE SPIEGELSTRICH einrücken eigentlich immer in diesem Fall alle seit eingekerbten Blöcke von Doppelpunkten voran wurden), dann wird der Parser die dritte Stufe auf der Oberseite das war. Aber es macht auch sehr viel Sinn, die Dinge so zu machen, wie Sie sie beschrieben haben, besonders wenn Sie den Lexer vom Layouter trennen wollen, was Sie vermutlich tun würden, wenn Sie ein Code-Generierungs-Tool verwenden würden zum Beispiel, um Ihren Lexer zu machen, wie es allgemein üblich ist.

Ich habe eine Anwendung, die etwas flexibler über Einbuchtung Regeln sein musste, im Wesentlichen den Parser so dass sie erzwingen, wenn erforderlich - das gilt in bestimmten Kontexten zu sein, benötigt folgende, zum Beispiel:

this line introduces an indented block of literal text: 
    this line of the block is indented four spaces 
    but this line is only indented two spaces 

, die mit SPIEGELSTRICH/Dedent Token nicht sehr gut funktioniert, da Sie eine SPIEGELSTRICH für jede Spalte von Vertiefung zu erzeugen, am Ende benötigen und eine gleiche Anzahl von DEDENTs auf dem Weg zurück, es sei denn, Sie Weg in der Zukunft schauen, um herauszufinden, wo die Einzugsebenen werden am Ende sein, und es scheint nicht, als ob Sie einen Tokenizer benötigen würden. In diesem Fall habe ich ein paar verschiedene Dinge ausprobiert und am Ende nur einen Zähler in jedem NEWLINE-Token gespeichert, der die Änderung in der Einrückung (positiv oder negativ) für die folgende logische Zeile ergab. (Jeder Token auch alle nachfolgenden Leerzeichen gespeichert, falls es die Erhaltung benötigt, z. NEWLINE, die gespeicherte Leerzeichen enthielten die EOL selbst irgendwelche intervenierenden Leerzeilen, und die Einkerbung auf der folgenden logische Zeile) keinen separaten SPIEGELSTRICH oder Dedent Tokens überhaupt. Erste die Parser damit umgehen war ein bisschen mehr Arbeit als nur Verschachtelung Einzüge und DEDENTs und könnte gut ist die Hölle mit einer komplizierten Grammatik, die einen ausgefallenen Parser-Generator benötigt, aber es war nicht annähernd so schlimm, wie ich befürchtet hatte, entweder. Auch hier ist es für den Parser nicht nötig, von NEWLINE aus nach vorne zu schauen, um zu sehen, ob in diesem Schema ein INDENT auftaucht.

Dennoch, ich denke, Sie würden zustimmen, dass alle Arten von verrückt aussehenden Whitespace im Tokenizer/Layouter und lassen Sie den Parser entscheiden, was ein Literal ist und was Code ist ein bisschen eine ungewöhnliche Anforderung! Sie möchten sicherlich nicht, dass Ihr Parser mit diesem Einrückungszähler versehen wird, wenn Sie beispielsweise nur Python-Code analysieren möchten. Die Art, wie Sie Dinge tun, ist mit ziemlicher Sicherheit der richtige Ansatz für Ihre Anwendung und viele andere. Obwohl, wenn jemand anderes Gedanken darüber hat, wie man das am besten macht, würde ich es lieben, sie zu hören ...

Answer 2

Ich experimentiere schon seit kurzem damit, und ich kam zu dem Schluss, dass für meine Bedürfnisse zumindest wollte ich, dass die NEWLINES das Ende jeder "Anweisung" markieren, egal ob es die letzte Anweisung in einem eingerückten Block war oder nicht, dh ich brauche die Zeilenumbrüche schon vor DEDENT.

Meine Lösung war, es auf den Kopf zu stellen, und anstatt NEWLINES das Ende der Zeilen zu markieren, verwende ich einen LINE-Token, um den Anfang einer Zeile zu markieren.

Ich habe einen Lexer, der leere Zeilen (einschließlich Kommentarzeilen) zusammenfasst und ein einzelnes LINE-Token mit Informationen über den Einzug der letzten Zeile ausgibt. Dann nimmt meine Vorverarbeitungsfunktion diesen Token-Stream und fügt INDENT oder DEDENT "dazwischen" irgendwelche Zeilen hinzu, an denen sich der Einzug ändert. So

line1 
    line2 
    line3 
line4 

würde der Token-Strom

LINE "line1" INDENT LINE "line2" LINE "line3" DEDENT LINE "line4" EOF 

Diese mir klar, Grammatik Produktionen für Erklärungen schreiben können, ohne sich Gedanken über das Ende der Aussagen Erkennung, auch wenn sie am Ende mit verschachtelten, eingekerbte, Subblöcke, etwas das kann schwierig sein, wenn Sie stattdessen NEWLINES (und DEDENTS) zusammenbringen. Hier

ist der Kern des Vorprozessors, in O'Caml geschrieben:

match next_token() with 
     LINE indentation -> 
     if indentation > !current_indentation then 
      (
      Stack.push !current_indentation indentation_stack; 
      current_indentation := indentation; 
      INDENT 
     ) 
     else if indentation < !current_indentation then 
      (
      let prev = Stack.pop indentation_stack in 
       if indentation > prev then 
       (
        current_indentation := indentation; 
        BAD_DEDENT 
       ) 
       else 
       (
        current_indentation := prev; 
        DEDENT 
       ) 
     ) 
     else (* indentation = !current_indentation *) 
      let token = remove_next_token() in 
      if next_token() = EOF then 
       remove_next_token() 
      else 
       token 
    | _ -> 
     remove_next_token() 

Ich habe nicht zusätzliche Unterstützung für Klammern noch, aber das sollte eine einfache Erweiterung sein. Es wird jedoch vermieden, eine streunende LINE am Ende der Datei auszugeben.

Answer 3

Tokenizer in Ruby für Spaß:

def tokenize(input) 
    result, prev_indent, curr_indent, line = [""], 0, 0, "" 
    line_started = false 

    input.each_char do |char| 

    case char 
    when ' ' 
     if line_started 
     # Content already started, add it. 
     line << char 
     else 
     # No content yet, just count. 
     curr_indent += 1 
     end 
    when "\n" 
     result.last << line + "\n" 
     curr_indent, line = 0, "" 
     line_started = false 
    else 
     # Check if we are at the first non-space character. 
     unless line_started 
     # Insert indent and dedent tokens if indentation changed. 
     if prev_indent > curr_indent 
      # 2 spaces dedentation 
      ((prev_indent - curr_indent)/2).times do 
      result << :DEDENT 
      end 
      result << "" 
     elsif prev_indent < curr_indent 
      result << :INDENT 
      result << "" 
     end 

     prev_indent = curr_indent 
     end 

     # Mark line as started and add char to line. 
     line_started = true; line << char 
    end 

    end 

    result 
end 

funktioniert nur für Zweiraum-Einzug. Ergebnis ist etwas wie ["Hello there from level 0\n", :INDENT, "This\nis level\ntwo\n", :DEDENT, "This is level0 again\n"].