Comment analyser le code informatique, Advent of Code ay 3

Après avoir relevé certains des défis ultérieurs de l'Avent of Code, j'ai voulu revenir sur le jour 3, qui présentait un problème d'analyse intéressant. La tâche impliquait d'extraire du code valide à partir d'une entrée bruyante, un excellent exercice de développement d'analyseurs et de lexeurs. Rejoignez-moi pour explorer mon approche de ce défi.

Une image générée montrant mon amour pour le puzzle (?) par Microsoft Copilot

Quand j'ai écrit pour la première fois sur la règle DSL, je me suis appuyé sur Hy pour l'analyse. Cependant, ma récente exploration de l'IA générative a introduit une nouvelle méthode d'analyse : le code généré à l'aide de la bibliothèque funcparserlib. Ce défi Advent of Code m'a permis de plonger dans les subtilités de funcparserlib et de développer une compréhension beaucoup plus solide des fonctionnalités du code généré.

Implémentation du Lexer (analyse lexicale)

La première étape du traitement de notre entrée corrompue est le lexing (ou tokénisation). Le lexer (ou tokenizer) analyse la chaîne d'entrée et la divise en jetons individuels, qui sont les éléments de base pour un traitement ultérieur. Un jeton représente une unité significative dans l'entrée, classée par son type. Pour ce puzzle, nous nous intéressons à ces types de jetons :

• Opérateurs (OP) : Ceux-ci représentent des noms de fonctions, tels que mul, do et don't. Par exemple, l'entrée mul(2, 3) contient le jeton d'opérateur mul.
• Nombres : Ce sont des valeurs numériques. Par exemple, dans l'entrée mul(2, 3), 2 et 3 seraient reconnus comme des jetons numériques.
• Virgules : Le caractère virgule (,) fait office de séparateur entre les arguments.
• Parenthèses : Les parenthèses ouvrantes (et fermantes) définissent la structure des appels de fonction.
• Charabia : Cette catégorie englobe tous les caractères ou séquences de caractères qui ne correspondent pas aux autres types de jetons. C'est là qu'intervient la partie « corrompue » de l'entrée. Par exemple, %$#@ ou toute lettre aléatoire serait considérée comme du charabia.

Bien que funcparserlib utilise souvent des chaînes magiques dans ses tutoriels, je préfère une approche plus structurée. Les chaînes magiques peuvent conduire à des fautes de frappe et rendre difficile la refactorisation du code. L'utilisation d'un Enum pour définir les types de jetons offre plusieurs avantages : une meilleure lisibilité, une maintenabilité améliorée et une sécurité de type améliorée. Voici comment j'ai défini les types de jetons à l'aide d'un Enum :

from enum import Enum, auto

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

En utilisant Spec.OP, Spec.NUMBER, etc., nous évitons l'ambiguïté et les erreurs potentielles associées à l'utilisation de chaînes simples.

Pour intégrer de manière transparente Enum à funcparserlib, j'ai créé un décorateur personnalisé nommé TokenSpec_. Ce décorateur agit comme un wrapper autour de la fonction TokenSpec originale de funcparserlib. Il simplifie la définition du jeton en acceptant une valeur de notre Spec Enum comme argument de spécification. En interne, il extrait la représentation sous forme de chaîne de l'énumération (spec.name) et la transmet avec tous les autres arguments à la fonction TokenSpec d'origine.

from enum import Enum, auto

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

Avec la fonction décorée TokenSpec_, cela nous permet de définir le tokenizer. Nous utilisons make_tokenizer de funcparserlib pour créer un tokenizer qui prend une liste de définitions TokenSpec_. Chaque définition spécifie un type de jeton (de notre Spec ENUM) et une expression régulière pour y correspondre.

from funcparserlib.lexer import TokenSpec

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

L'expression régulière OP utilise l'alternance (|) pour correspondre aux différents formats de fonctions. Plus précisément :

• mul(?=(d{1,3},d{1,3})) : correspond à mul uniquement s'il est suivi de parenthèses contenant deux nombres séparés par une virgule. L'assertion d'anticipation positive (?=...) garantit que les parenthèses et les nombres sont présents mais ne sont pas consommés par la correspondance.
• do(?=()) : les correspondances ne sont effectuées que si elles sont suivies de parenthèses vides.
• ne pas faire(?=()) : les correspondances ne fonctionnent pas uniquement si elles sont suivies de parenthèses vides.

Une représentation graphique de l'expression régulière

Enfin, la fonction tokenize filtre tous les jetons GIBBERISH pendant la tokenisation pour se concentrer sur les parties pertinentes de l'entrée pour un traitement ultérieur.

Le processus d'interprétation du code comporte généralement deux étapes principales : l'analyse lexicale (ou lexing) et l'analyse syntaxique. Nous avons déjà implémenté la première étape : notre fonction tokenize agit comme un lexer, prenant la chaîne d'entrée et la convertissant en une séquence de jetons. Ces jetons sont les éléments fondamentaux que l’analyseur utilisera pour comprendre la structure et la signification du code. Voyons maintenant comment l'analyseur utilise ces jetons.

Implémentation de l'analyseur

Les jetons analysés renvoyés par la fonction tokenize sont ensuite envoyés à un analyseur pour un traitement ultérieur. Pour combler le fossé entre notre Spec Enum et la fonction tok, nous introduisons un décorateur nommé tok_.

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
    )

Par exemple, si nous avons un jeton Spec.NUMBER, l'analyseur renvoyé acceptera le jeton et renverra une valeur comme suit :

from funcparserlib.parser import tok

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

La valeur renvoyée peut ensuite être transformée dans le type de données souhaité à l'aide du bouton >> opérateur, comme indiqué ci-dessous :

from enum import Enum, auto

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

En règle générale, il est recommandé d'utiliser ast.literal_eval lors de l'analyse d'une entrée inconnue afin d'éviter d'éventuelles vulnérabilités de sécurité. Cependant, les contraintes de ce casse-tête particulier de l'Avent du Code (en particulier, le fait que tous les nombres sont des entiers valides) nous permettent d'utiliser la fonction int la plus directe et la plus efficace pour convertir les représentations sous forme de chaîne en nombres entiers.

from funcparserlib.lexer import TokenSpec

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

Nous pouvons définir des règles d'analyse pour appliquer des séquences de jetons spécifiques et les transformer en objets significatifs. Par exemple, pour analyser un appel de fonction mul, nous avons besoin de la séquence suivante : parenthèse gauche, chiffre, virgule, un autre chiffre, parenthèse droite. On transforme ensuite cette séquence en objet Mul :

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
    )

Cette règle combine les analyseurs tok_ pour les jetons requis (OP, LPAREN, COMMA, RPAREN) avec l'analyseur numérique. Le >> L'opérateur transforme ensuite la séquence correspondante en un objet Mul, extrayant les deux nombres de l'élément tuple aux indices 2 et 4.

Nous pouvons appliquer le même principe pour définir des règles d'analyse pour les opérations do et don't. Ces opérations ne prennent aucun argument (représenté par des parenthèses vides) et sont transformées en objets Condition :

from funcparserlib.parser import tok

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

La règle do crée un objet Condition avec can_proceed = True, tandis que la règle don't en crée un avec can_proceed = False.

Enfin, nous combinons ces règles d'analyse individuelles (do, don't et mul) en un seul analyseur expr à l'aide de | (ou) opérateur :

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

Cet analyseur expr tentera de faire correspondre l'entrée à chacune des règles tour à tour, renvoyant le résultat de la première correspondance réussie.

Notre analyseur expr gère des expressions complètes comme mul(2,3), do() et don't(). Toutefois, l'entrée peut également contenir des jetons individuels qui ne font pas partie de ces expressions structurées. Pour les gérer, nous définissons un analyseur fourre-tout appelé 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

Cet analyseur utilise le | (ou) opérateur pour correspondre à n’importe quel jeton unique de type NUMBER, LPAREN, RPAREN ou COMMA. C'est essentiellement un moyen de capturer tous les jetons parasites qui ne font pas partie d'une expression plus large.

Avec tous les composants définis, nous pouvons désormais définir ce qui constitue un programme complet. Un programme se compose d'un ou plusieurs « appels », où un « appel » est une expression potentiellement entourée de jetons parasites.

L'analyseur d'appel gère cette structure : il correspond à n'importe quel nombre de jetons parasites (many(everything)), suivi d'une seule expression (expr), suivi d'un nombre quelconque de jetons parasites supplémentaires. La fonction Operator.itemgetter(1) extrait ensuite l'expression correspondante de la séquence résultante.

number = tok_(Spec.NUMBER) >> int

Un programme complet, représenté par l'analyseur de programme, se compose de zéro ou plusieurs appels, garantissant que la totalité de l'entrée est consommée en utilisant l'analyseur terminé. Le résultat analysé est ensuite converti en un tuple d'expressions.

from enum import Enum, auto

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

Enfin, nous regroupons toutes ces définitions dans une fonction d'analyse. Cette fonction prend un tuple de jetons en entrée et renvoie un tuple d'expressions analysées. Tous les analyseurs sont définis dans le corps de la fonction pour éviter de polluer l'espace de noms global et parce que l'analyseur numérique dépend de la fonction tok_.

from funcparserlib.lexer import TokenSpec

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

Résoudre l'énigme

Avec notre analyseur en place, résoudre la partie 1 est simple. Nous devons trouver toutes les opérations mul, effectuer les multiplications et additionner les résultats. Nous commençons par définir une fonction d'évaluation qui gère les expressions Mul

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
    )

Pour résoudre la partie 1, nous tokenisons et analysons l'entrée, puis utilisons la fonction évaluer_skip_condition que nous venons de définir pour obtenir le résultat final :

from funcparserlib.parser import tok

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

Pour la partie 2, nous devons ignorer l'évaluation des opérations mul si une condition "ne pas faire" a été rencontrée. Nous définissons une nouvelle fonction d'évaluation,estimate_with_condition, pour gérer cela :

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

Cette fonction utilise réduire avec une fonction de réduction personnalisée pour maintenir une somme cumulée et un indicateur booléen (condition). L'indicateur de condition est mis à jour lorsqu'une expression de condition (faire ou ne pas) est rencontrée. Les expressions Mul ne sont évaluées et ajoutées à la somme que si la condition est vraie.

Itération précédente

Au départ, mon approche de l'analyse impliquait deux passes distinctes. Tout d’abord, je tokeniserais la chaîne d’entrée entière, en collectant tous les jetons quel que soit leur type. Ensuite, dans une étape distincte, j'effectuerais une deuxième tokenisation et analyse spécifiquement pour identifier et traiter les opérations mul.

>>> 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

L'approche améliorée élimine cette redondance en effectuant la tokenisation et l'analyse en un seul passage. Nous disposons désormais d'un seul analyseur qui gère tous les types de jetons, y compris ceux liés à mul, do, don't et autres jetons individuels.

number = tok_(Spec.NUMBER) >> int

Au lieu de re-tokeniser l'entrée pour rechercher les opérations mul, nous exploitons les types de jetons identifiés lors de la tokenisation initiale. La fonction d'analyse utilise désormais ces types de jetons pour construire directement les objets d'expression appropriés (Mul, Condition, etc.). Cela évite l'analyse redondante de l'entrée et améliore considérablement l'efficacité.

Cela conclut notre aventure d'analyse pour l'Avent of Code de cette semaine. Bien que ce poste ait nécessité beaucoup de temps, le processus de révision et de consolidation de mes connaissances en lexing et en analyse syntaxique en a valu la peine. C’était un casse-tête amusant et perspicace, et j’ai hâte de relever des défis plus complexes dans les semaines à venir et de partager mes apprentissages.

Comme toujours, merci d'avoir lu, et j'écrirai à nouveau la semaine prochaine.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!