Le langage d'expression d'une heure

Il est préférable de consulter cet article de blog dans son format original.

Cet article récapitule une présentation intitulée Le langage d'expression d'une heure, passant en revue à la fois les concepts et le code.¹

Un langage d'expression², dans ce contexte, évalue une expression : une séquence d'octets, très probablement des caractères UTF-8.³ Les exemples incluent :

• 1 1
• //article[@title="foobar"]//image
• .items[].foo|select(.bar = "foo")
• a.comments > 1 and a.category not in ["misc"]

Des exemples de langages d'expression (ou DSL⁴) sont :

• JQ
• Langage de requête Kibana
• Langage XPath
• Langage d'expression Symfony

Pourquoi construire votre propre langage d'expression ? Pourquoi pas? Trop occupé ? Ne t'inquiète pas! Cela ne nécessite pas de mois, de semaines ou même de jours. Créez-en un en une heure avec le One Hour Expression Language !⁵

ProCalc2000

Nous allons créer le langage d'expression ProCalc2000, une calculatrice arithmétique non scientifique de nouvelle génération pour l'an 2000 et au-delà.

Il évalue des expressions comme 1 1 ou 1 2 et peut gérer des problèmes de division tels que 1 3 2 / 2.

Godzilla

Godzilla n'aime pas la division à cause des nombres à virgule flottante.

Le langage comprend des nombres (par exemple, 1, 2) et des opérateurs ( , -, ). Il ne prendra pas* en charge la priorité des opérateurs (voir Annexe I) ou la division.

Malgré sa simplicité, il fournit une base pour l'ajout de fonctionnalités : variables, fonctions, opérateurs de canal, suffixes, concaténation de chaînes et même (contre la volonté de Godzilla) division.

Qu'y a-t-il dans un, s'il vous plaît ?

Il existe de nombreuses façons d'évaluer une séquence d'octets, mais nous utiliserons un tokenizer, un analyseur et un évaluateur :

<code>              +-----------+  tokens  +--------+  ast  +-----------+ 
EXPRESSION ==>| Tokenizer |--------->| Parser |------>| Evaluator | => VALUE
              +-----------+          +--------+       +-----------+</code>

Tokeniseur

Également connu sous le nom de lexer ou scanner. Cette classe divise la chaîne en morceaux catégorisés appelés jetons.

<code class="language-php">class Tokenizer
{
    public function tokenize(string $expression): Tokens
    {
        // ...
    }
}</code>

Par exemple, 1 2 3 génère cinq jetons :

<code>Token(Integer, 1)
Token(Plus)
Token(Integer, 2)
Token(Plus)
Token(Integer, 3)</code>

Le tokenizer scanne de gauche à droite, identifiant les morceaux intéressants : les entiers positifs et les opérateurs , - et *. Les espaces sont ignorés ; d'autres caractères provoquent des erreurs. Les types de jetons sont Integer, Plus, Minus et Multiply.

Godzilla

Godzilla suggère un tokenizer et une machine à empiler, mais nous utiliserons un analyseur et un évaluateur parce que Godzilla s'en soucie.

Le tokenizer ne vérifie pas la validité de l'expression ; il ne catégorise que les morceaux.⁶ Les jetons sont transmis à l'analyseur.

Analyseur

L'analyseur interprète les jetons et les transforme en un arbre de syntaxe abstraite (AST).

<code>              +-----------+  tokens  +--------+  ast  +-----------+ 
EXPRESSION ==>| Tokenizer |--------->| Parser |------>| Evaluator | => VALUE
              +-----------+          +--------+       +-----------+</code>

Étant donné une liste de jetons, l'analyseur renvoie un AST, un nœud racine d'un arbre. Chaque nœud est une expression évaluable ; les types de nœuds sont BinaryOp et Integer.

Une opération binaire a deux opérandes (par exemple, foo or bar pourrait être BinaryOp(Variable('foo'), 'or', Variable('bar'))).

Les opérations unaires ont un opérande (par exemple, -1).

Les opérations ternaires ont trois opérandes (par exemple, foo ? bar : baz).

L'expression 1 1 / 5 est un BinaryOp avec comme opérateur, un opérande étant 1 et l'autre étant un autre BinaryOp (1 / 5).

<code class="language-php">class Tokenizer
{
    public function tokenize(string $expression): Tokens
    {
        // ...
    }
}</code>

Évaluateur

L'évaluateur accepte un Node et renvoie une valeur (ici, un entier). C'est un interprète qui marche dans les arbres.

<code>Token(Integer, 1)
Token(Plus)
Token(Integer, 2)
Token(Plus)
Token(Integer, 3)</code>

Montrez-moi votre code, s'il vous plaît ?

Ce code provient d'une rencontre PHPSW, pilotée par des tests unitaires (omis ici). Voir le référentiel.

Godzilla

Godzilla serait en colère contre ce code et suggère une refactorisation.

Tokeniseur

Tout d'abord, une classe Token avec une énumération TokenType et une valeur facultative :

<code class="language-php">class Parser
{
    public function parse(Tokens $tokens): Node
    {
        // ...
    }
}</code>

<code>                        +-------------+
                        | Binary Op + | 



<p>In PHP:</p>

```php
$ast = new BinaryOp(
    left:     new Integer(1),
    operator: '+',
    right:    new BinaryOp(
        left:     new Integer(1),
        operator: '/',
        right:    new Integer(5),
    )
);</code>

Les jetons ressemblent à :

<code class="language-php">class Evaluator
{
    public function evaluate(Node $node): int
    {
        // ...
    }
}</code>

La classe Tokenizer fait le travail :⁷

<code class="language-php">class Token
{
    public function __construct(
        public TokenType $type,
        public ?string $value = null
    ) {}
}</code>

La Tokenscollection :

<code class="language-php">enum TokenType
{
    case Plus;
    case Minus;
    case Multiply;
    case Integer;
}</code>

Godzilla

Godzilla préfère un tableau et `array_shift` ou un générateur pour la tokenisation et l'analyse simultanément.

Analyseur

<code class="language-php">[
    new Token(TokenType::Integer, 50),
    new Token(TokenType::Plus),
    // ...
]</code>

C'est ici que la priorité des opérateurs, l'analyse des suffixes et les opérateurs de tuyaux seraient ajoutés. L'analyse des suffixes, par exemple, gérerait des expressions telles que « 5 miles ».

Évaluateur

<code class="language-php">class Tokenizer
{
    public function tokenize(string $expression): Tokens 
    {
        $offset = 0;
        $tokens = [];
        while (isset($expression[$offset])) {
            $char = $expression[$offset++];
            if (is_numeric($char)) {
                while (is_numeric($expression[$offset] ?? null)) {
                    $char .= $expression[$offset++];
                }
                $tokens[] = new Token(TokenType::Integer, $char);
                continue;
            }
            $token = match ($char) {
                '+' => new Token(TokenType::Plus),
                '-' => new Token(TokenType::Minus),
                '*' => new Token(TokenType::Multiply),
                ' ' => null,
                default => throw new RuntimeException(sprintf(
                    'Invalid operator: "%s"', $char
                )),
            };
            if ($token === null) {
                continue;
            }
            $tokens[] = $token;
        }
        return new Tokens($tokens);
    }
}</code>

C'est tout

Ce code a été codé en direct, y compris les tests. Le code complet est disponible dans le référentiel.

Priorité des opérateurs

L'expression 1 * 3 4 devrait être (1 * 3) 4 = 7, mais notre langage l'évalue comme 1 * (3 4) = 7 en raison de la méthode d'analyse.⁸ Un analyseur Pratt corrige ceci :

<code>              +-----------+  tokens  +--------+  ast  +-----------+ 
EXPRESSION ==>| Tokenizer |--------->| Parser |------>| Evaluator | => VALUE
              +-----------+          +--------+       +-----------+</code>

Godzilla

Godzilla comprend la récursion.

Lectures complémentaires

• Crafting Interpreters : Livre (avec édition web gratuite) de Robert Nystrom
• L'analyse des expressions simplifiée : article de blog de Robert Nystrom
• Calculateur RPN Stack Machine : article 2014 d'Igor Wiedler
• Doctrine Lexer
• PHPStan Phpdoc Parser⁹

---

1. Le code change à chaque itération.
2. Ou plus précisément, un interprète de langage d'expression.
3. Souvent appelée chaîne en PHP.
4. Langage spécifique au domaine.
5. Aucun brevet n'existe.
6. Un tokenizer est utile pour la coloration syntaxique.
7. preg_ les méthodes pourraient être plus performantes.
8. Faux seulement si une réponse différente était attendue.
9. La traversée d'arbres a été découverte grâce aux générateurs de requêtes de Doctrine.

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!