So analysieren Sie Computercode, Advent of Code ab 3

Nachdem ich einige der späteren Advent of Code-Herausforderungen in Angriff genommen hatte, wollte ich Tag 3 noch einmal Revue passieren lassen, der ein interessantes Parsing-Problem aufwies. Die Aufgabe bestand darin, gültigen Code aus einer verrauschten Eingabe zu extrahieren, eine großartige Übung in der Parser- und Lexer-Entwicklung. Begleiten Sie mich, wenn ich meine Herangehensweise an diese Herausforderung erforsche.

Ein generiertes Bild, das meine Liebe zum Puzzle (?) von Microsoft Copilot zeigt

Als ich zum ersten Mal über das Lineal DSL schrieb, verließ ich mich beim Parsen auf Hy. Bei meiner jüngsten Erkundung der generativen KI wurde jedoch eine neue Parsing-Methode eingeführt: generierter Code mithilfe der funcparserlib-Bibliothek. Diese Advent of Code-Herausforderung ermöglichte es mir, in die Feinheiten von funcparserlib einzutauchen und ein viel besseres Verständnis für die Funktionalität des generierten Codes zu entwickeln.

Implementierung des Lexers (lexikalische Analyse)

Der erste Schritt bei der Verarbeitung unserer beschädigten Eingaben ist die Lexing (oder Tokenisierung). Der Lexer (oder Tokenizer) scannt den Eingabestring und teilt ihn in einzelne Tokens auf, die die Grundbausteine ​​für die weitere Verarbeitung darstellen. Ein Token stellt eine sinnvolle Einheit in der Eingabe dar, kategorisiert nach ihrem Typ. Für dieses Rätsel interessieren uns diese Token-Typen:

• Operatoren (OP): Diese repräsentieren Funktionsnamen wie mul, do und don't. Beispielsweise enthält die Eingabe mul(2, 3) den Operator-Token mul.
• Zahlen: Dies sind numerische Werte. Beispielsweise würden in der Eingabe mul(2, 3) 2 und 3 als Zahlentoken erkannt.
• Kommas: Das Kommazeichen (,) fungiert als Trennzeichen zwischen Argumenten.
• Klammern: Öffnende (und schließende) Klammern definieren die Struktur der Funktionsaufrufe.
• Kauderwelsch: Diese Kategorie umfasst alle Zeichen oder Zeichenfolgen, die nicht mit den anderen Token-Typen übereinstimmen. Hier kommt der „korrupte“ Teil der Eingabe ins Spiel. Beispielsweise würden %$#@ oder beliebige beliebige Buchstaben als Kauderwelsch betrachtet.

Während funcparserlib in seinen Tutorials häufig magische Zeichenfolgen verwendet, bevorzuge ich einen strukturierteren Ansatz. Magic Strings können zu Tippfehlern führen und die Umgestaltung von Code erschweren. Die Verwendung einer Enum zum Definieren von Tokentypen bietet mehrere Vorteile: bessere Lesbarkeit, verbesserte Wartbarkeit und verbesserte Typsicherheit. So habe ich die Token-Typen mithilfe einer Aufzählung definiert:

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Durch die Verwendung von Spec.OP, Spec.NUMBER usw. vermeiden wir die Mehrdeutigkeit und potenziellen Fehler, die mit der Verwendung einfacher Zeichenfolgen verbunden sind.

Um Enum nahtlos in funcparserlib zu integrieren, habe ich einen benutzerdefinierten Dekorator namens TokenSpec_ erstellt. Dieser Dekorator fungiert als Wrapper um die ursprüngliche TokenSpec-Funktion von funcparserlib. Es vereinfacht die Token-Definition, indem es einen Wert aus unserem Spec Enum als Spec-Argument akzeptiert. Intern extrahiert es die Zeichenfolgendarstellung der Aufzählung (spec.name) und übergibt diese zusammen mit allen anderen Argumenten an die ursprüngliche TokenSpec-Funktion.

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Mit der dekorierten Funktion TokenSpec_ können wir den Tokenizer definieren. Wir verwenden make_tokenizer von funcparserlib, um einen Tokenizer zu erstellen, der eine Liste von TokenSpec_-Definitionen akzeptiert. Jede Definition gibt einen Token-Typ (aus unserem Spec ENUM) und einen dazu passenden regulären Ausdruck an.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

Der reguläre OP-Ausdruck verwendet Alternation (|), um den verschiedenen Funktionsformaten zu entsprechen. Konkret:

• mul(?=(d{1,3},d{1,3})): Entspricht mul nur, wenn darauf Klammern folgen, die zwei durch Komma getrennte Zahlen enthalten. Die positive Lookahead-Behauptung (?=...) stellt sicher, dass die Klammern und Zahlen vorhanden sind, aber nicht von der Übereinstimmung verbraucht werden.
• do(?=()): Übereinstimmungen funktionieren nur, wenn leere Klammern folgen.
• nicht(?=()): Übereinstimmungen nicht nur, wenn leere Klammern folgen.

Eine grafische Darstellung des regulären Ausdrucks

Schließlich filtert die Tokenize-Funktion während der Tokenisierung alle GIBBERISH-Tokens heraus, um sich für die weitere Verarbeitung auf die relevanten Teile der Eingabe zu konzentrieren.

Der Prozess der Codeinterpretation umfasst typischerweise zwei Hauptphasen: lexikalische Analyse (oder Lexing) und Parsing. Die erste Stufe haben wir bereits implementiert: Unsere Tokenize-Funktion fungiert als Lexer, nimmt die Eingabezeichenfolge und wandelt sie in eine Folge von Tokens um. Diese Token sind die grundlegenden Bausteine, die der Parser verwendet, um die Struktur und Bedeutung des Codes zu verstehen. Lassen Sie uns nun untersuchen, wie der Parser diese Token verwendet.

Implementierung des Parsers

Die von der Tokenize-Funktion zurückgegebenen geparsten Token werden dann zur weiteren Verarbeitung an einen Parser gesendet. Um die Lücke zwischen unserem Spec Enum und der tok-Funktion zu schließen, führen wir einen Dekorator namens tok_.
ein

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

Wenn wir beispielsweise ein Spec.NUMBER-Token haben, akzeptiert der zurückgegebene Parser das Token und gibt einen Wert wie folgt zurück:

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

Der zurückgegebene Wert kann dann mit der Funktion >> in den gewünschten Datentyp umgewandelt werden. Operator, wie unten gezeigt:

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Normalerweise empfiehlt es sich, beim Parsen unbekannter Eingaben ast.literal_eval zu verwenden, um potenzielle Sicherheitslücken zu vermeiden. Die Einschränkungen dieses speziellen Advent of Code-Rätsels – insbesondere die Tatsache, dass alle Zahlen gültige Ganzzahlen sind – ermöglichen es uns jedoch, die direktere und effizientere int-Funktion zum Konvertieren von Zeichenfolgendarstellungen in Ganzzahlen zu verwenden.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

Wir können Parsing-Regeln definieren, um bestimmte Token-Sequenzen zu erzwingen und sie in sinnvolle Objekte umzuwandeln. Um beispielsweise einen Mul-Funktionsaufruf zu analysieren, benötigen wir die folgende Sequenz: linke Klammer, Zahl, Komma, eine andere Zahl, rechte Klammer. Anschließend transformieren wir diese Sequenz in ein Mul-Objekt:

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

Diese Regel kombiniert die tok_-Parser für die erforderlichen Token (OP, LPAREN, COMMA, RPAREN) mit dem Zahlenparser. Das >> Der Operator wandelt dann die übereinstimmende Sequenz in ein Mul-Objekt um und extrahiert die beiden Zahlen aus dem Tupelelem an den Indizes 2 und 4.

Wir können das gleiche Prinzip anwenden, um Parsing-Regeln für die Do- und Don't-Operationen zu definieren. Diese Operationen benötigen keine Argumente (dargestellt durch leere Klammern) und werden in Bedingungsobjekte umgewandelt:

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

Die Do-Regel erstellt ein Bedingungsobjekt mit can_proceed = True, während die Don't-Regel eines mit can_proceed = False erstellt.

Schließlich kombinieren wir diese einzelnen Parsing-Regeln (do, don't und mul) mithilfe des | zu einem einzigen expr-Parser (oder) Operator:

>>> from funcparserlib.lexer import Token
>>> number_parser = tok_(Spec.NUMBER)
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
'123'

Dieser Ausdrucksparser versucht, die Eingabe nacheinander mit jeder der Regeln abzugleichen und gibt das Ergebnis des ersten erfolgreichen Abgleichs zurück.

Unser expr-Parser verarbeitet vollständige Ausdrücke wie mul(2,3), do() und don't(). Die Eingabe kann jedoch auch einzelne Token enthalten, die nicht Teil dieser strukturierten Ausdrücke sind. Um damit umzugehen, definieren wir einen Catch-All-Parser namens everything:

>>> from funcparserlib.lexer import Token
>>> from ast import literal_eval
>>> number_parser = tok_(Spec.NUMBER) >> literal_eval
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
123

Dieser Parser verwendet das | (oder)-Operator zur Übereinstimmung mit einem einzelnen Token vom Typ NUMBER, LPAREN, RPAREN oder COMMA. Es handelt sich im Wesentlichen um eine Möglichkeit, alle verstreuten Token zu erfassen, die nicht Teil eines größeren Ausdrucks sind.

Nachdem alle Komponenten definiert sind, können wir nun definieren, was ein vollständiges Programm ausmacht. Ein Programm besteht aus einem oder mehreren „Aufrufen“, wobei ein „Aufruf“ ein Ausdruck ist, der möglicherweise von Streutokens umgeben ist.

Der Aufrufparser verarbeitet diese Struktur: Er entspricht einer beliebigen Anzahl verstreuter Token (viele(alles)), gefolgt von einem einzelnen Ausdruck (expr), gefolgt von einer beliebigen Anzahl zusätzlicher verstreuter Token. Die Funktion „operator.itemgetter(1)“ extrahiert dann den passenden Ausdruck aus der resultierenden Sequenz.

number = tok_(Spec.NUMBER) >> int

Ein vollständiges Programm, dargestellt durch den Programmparser, besteht aus null oder mehr Aufrufen, wodurch sichergestellt wird, dass die gesamte Eingabe durch die Verwendung des fertigen Parsers verbraucht wird. Das analysierte Ergebnis wird dann in ein Tupel von Ausdrücken umgewandelt.

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Abschließend gruppieren wir alle diese Definitionen in einer Parse-Funktion. Diese Funktion verwendet ein Tupel von Tokens als Eingabe und gibt ein Tupel geparster Ausdrücke zurück. Alle Parser werden innerhalb des Funktionskörpers definiert, um eine Verschmutzung des globalen Namespace zu verhindern und weil der Zahlenparser von der tok_-Funktion abhängt.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

Das Rätsel lösen

Mit unserem Parser ist die Lösung von Teil 1 unkompliziert. Wir müssen alle Mul-Operationen finden, die Multiplikationen durchführen und die Ergebnisse summieren. Wir beginnen mit der Definition einer Auswertungsfunktion, die Mul-Ausdrücke verarbeitet

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

Um Teil 1 zu lösen, tokenisieren und analysieren wir die Eingabe und verwenden dann die Funktion „evaluate_skip_condition“, die wir gerade definiert haben, um das Endergebnis zu erhalten:

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

Für Teil 2 müssen wir die Auswertung von Mul-Operationen überspringen, wenn eine Don't-Bedingung aufgetreten ist. Wir definieren eine neue Bewertungsfunktion, „evalu_with_condition“, um dies zu handhaben:

>>> from funcparserlib.lexer import Token
>>> number_parser = tok_(Spec.NUMBER)
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
'123'

Diese Funktion verwendet Reduzieren mit einer benutzerdefinierten Reduzierfunktion, um eine laufende Summe und ein boolesches Flag (Bedingung) beizubehalten. Das Bedingungsflag wird aktualisiert, wenn ein Bedingungsausdruck (do oder don't) auftritt. Mul-Ausdrücke werden nur ausgewertet und zur Summe addiert, wenn die Bedingung wahr ist.

Vorherige Iteration

Anfangs umfasste mein Parsing-Ansatz zwei unterschiedliche Durchgänge. Zuerst würde ich die gesamte Eingabezeichenfolge tokenisieren und alle Token unabhängig von ihrem Typ sammeln. Dann würde ich in einem separaten Schritt eine zweite Tokenisierung und Analyse durchführen, speziell um Mul-Operationen zu identifizieren und zu verarbeiten.

>>> from funcparserlib.lexer import Token
>>> from ast import literal_eval
>>> number_parser = tok_(Spec.NUMBER) >> literal_eval
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
123

Der verbesserte Ansatz beseitigt diese Redundanz, indem die Tokenisierung und Analyse in einem einzigen Durchgang durchgeführt werden. Wir haben jetzt einen einzigen Parser, der alle Token-Typen verarbeitet, einschließlich derer, die sich auf Mul-, Do-, Don't- und andere einzelne Token beziehen.

number = tok_(Spec.NUMBER) >> int

Anstatt die Eingabe erneut zu tokenisieren, um Mul-Operationen zu finden, nutzen wir die Token-Typen, die bei der anfänglichen Tokenisierung identifiziert wurden. Die Parse-Funktion verwendet nun diese Token-Typen, um direkt die entsprechenden Ausdrucksobjekte (Mul, Condition usw.) zu erstellen. Dadurch wird das redundante Scannen der Eingabe vermieden und die Effizienz deutlich verbessert.

Damit ist unser Parsing-Abenteuer für den Advent of Code dieser Woche abgeschlossen. Obwohl dieser Beitrag einen erheblichen Zeitaufwand erforderte, war es ein lohnendes Unterfangen, meine Kenntnisse im Lexing und Parsen noch einmal durchzugehen und zu festigen. Das war ein lustiges und aufschlussreiches Rätsel, und ich bin gespannt darauf, in den kommenden Wochen komplexere Herausforderungen anzugehen und meine Erkenntnisse zu teilen.

Wie immer vielen Dank fürs Lesen, und ich werde nächste Woche wieder schreiben.

Das obige ist der detaillierte Inhalt vonSo analysieren Sie Computercode, Advent of Code ab 3. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!