Die einstündige Ausdruckssprache

Dieser Blogbeitrag lässt sich am besten im Originalformat ansehen.

Dieser Beitrag fasst eine Präsentation mit dem Titel The One Hour Expression Language zusammen, in der sowohl die Konzepte als auch der Code besprochen werden.¹

Eine Ausdruckssprache² wertet in diesem Zusammenhang einen Ausdruck aus – eine Folge von Bytes, höchstwahrscheinlich UTF-8-Zeichen.³ Beispiele sind:

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

Beispiele für Ausdruckssprachen (oder DSLs⁴) sind:

• JQ
• Kibana-Abfragesprache
• XPath-Sprache
• Symfony Expression Language

Warum eine eigene Ausdruckssprache aufbauen? Warum nicht? Zu beschäftigt? Mach dir keine Sorge! Es sind keine Monate, Wochen oder gar Tage erforderlich. Erstellen Sie eines in einer Stunde mit der One Hour Expression Language!⁵

ProCalc2000

Wir werden die Ausdruckssprache ProCalc2000 entwickeln – einen nichtwissenschaftlichen Rechenrechner der nächsten Generation für das Jahr 2000 und darüber hinaus.

Es wertet Ausdrücke wie 1 1 oder 1 2 aus und kann Divisionsprobleme wie 1 3 2 / 2 verarbeiten.

Godzilla

Godzilla mag Divisionen aufgrund von Gleitkommazahlen nicht.

Die Sprache besteht aus Zahlen (z. B. 1, 2) und Operatoren ( , -, ). Es wird keine Operatorpriorität (siehe Anhang I) oder Division unterstützen.

Trotz seiner Einfachheit bietet es eine Grundlage für das Hinzufügen von Funktionen: Variablen, Funktionen, Pipe-Operatoren, Suffixe, String-Verkettung und sogar (gegen Godzillas Willen) Division.

Was ist bitte in einem?

Es gibt viele Möglichkeiten, eine Bytesequenz auszuwerten, aber wir verwenden einen Tokenizer, Parser und Evaluator:

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

Tokenizer

Auch als Lexer oder Scanner bekannt. Diese Klasse teilt die Zeichenfolge in kategorisierte Blöcke, sogenannte Token, auf.

class Tokenizer
{
    public function tokenize(string $expression): Tokens
    {
        // ...
    }
}

Zum Beispiel ergibt 1 2 3 fünf Token:

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

Der Tokenizer scannt von links nach rechts und identifiziert interessante Blöcke: positive ganze Zahlen und die Operatoren , - und *. Leerzeichen werden ignoriert; andere Zeichen verursachen Fehler. Token-Typen sind Ganzzahl, Plus, Minus und Multiplizieren.

Godzilla

Godzilla schlägt einen Tokenizer und eine Stack-Maschine vor, aber wir werden einen Parser und einen Evaluator verwenden, weil Godzilla sich darum kümmert.

Der Tokenizer überprüft die Gültigkeit des Ausdrucks nicht. es kategorisiert nur Chunks.⁶ Die Token werden an den Parser übergeben.

Parser

Der Parser interpretiert die Token und wandelt sie in einen Abstract Syntax Tree (AST) um.

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

Anhand einer Token-Liste gibt der Parser einen AST zurück – einen Wurzelknoten eines Baums. Jeder Knoten ist ein auswertbarer Ausdruck; Knotentypen sind BinaryOp und Integer.

Eine binäre Operation hat zwei Operanden (z. B. könnte foo or bar BinaryOp(Variable('foo'), 'or', Variable('bar')) sein).

Unäre Operationen haben einen Operanden (z. B. -1).

Ternäre Operationen haben drei Operanden (z. B. foo ? bar : baz).

Der Ausdruck 1 1 / 5 ist ein BinaryOp mit als Operator, wobei ein Operand 1 und der andere ein anderer BinaryOp (1 / 5) ist.

class Tokenizer
{
    public function tokenize(string $expression): Tokens
    {
        // ...
    }
}

Gutachter

Der Evaluator akzeptiert einen Knoten und gibt einen Wert zurück (hier eine Ganzzahl). Es ist ein baumwandelnder Dolmetscher.

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

Zeigen Sie mir bitte Ihren Code?

Dieser Code entstand bei einem PHPSW-Treffen, basierend auf Unit-Tests (hier weggelassen). Siehe das Repository.

Godzilla

Godzilla wäre über diesen Code verärgert und schlägt eine Umgestaltung vor.

Tokenizer

Zuerst eine Token-Klasse mit einer TokenType-Aufzählung und einem optionalen Wert:

class Parser
{
    public function parse(Tokens $tokens): Node
    {
        // ...
    }
}

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

Token sehen so aus:

class Evaluator
{
    public function evaluate(Node $node): int
    {
        // ...
    }
}

Die Tokenizer Klasse erledigt die Arbeit:⁷

class Token
{
    public function __construct(
        public TokenType $type,
        public ?string $value = null
    ) {}
}

Die Tokens Kollektion:

enum TokenType
{
    case Plus;
    case Minus;
    case Multiply;
    case Integer;
}

Godzilla

Godzilla bevorzugt ein Array und „array_shift“ oder einen Generator für die gleichzeitige Tokenisierung und Analyse.

Parser

[
    new Token(TokenType::Integer, 50),
    new Token(TokenType::Plus),
    // ...
]

Hier würden Operatorpriorität, Suffix-Parsing und Pipe-Operatoren hinzugefügt. Suffix-Parsing würde beispielsweise Ausdrücke wie „5 Meilen“ verarbeiten.

Gutachter

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);
    }
}

Das ist es

Dieser Code wurde live codiert, einschließlich Tests. Der vollständige Code ist im Repository verfügbar.

Bedienerpriorität

Der Ausdruck 1 * 3 4 sollte (1 * 3) 4 = 7 sein, aber unsere Sprache wertet ihn aufgrund der Parsing-Methode als 1 * (3 4) = 7 aus.⁸ Ein Pratt-Parser korrigiert dies:

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

Godzilla

Godzilla versteht Rekursion.

Weiterführende Literatur

• Crafting Interpreters: Buch (mit kostenloser Web-Ausgabe) von Robert Nystrom
• Ausdrucksanalyse leicht gemacht: Blogbeitrag von Robert Nystrom
• Stack Machine RPN-Rechner: Beitrag 2014 von Igor Wiedler
• Doktrin Lexer
• PHPStan Phpdoc Parser⁹

---

1. Der Code ändert sich mit jeder Iteration.
2. Oder genauer gesagt, ein Ausdruckssprachendolmetscher.
3. Wird in PHP oft als String bezeichnet.
4. Domänenspezifische Sprache.
5. Es existiert kein Patent.
6. Ein Tokenizer ist nützlich für die Syntaxhervorhebung.
7. preg_Methoden sind möglicherweise leistungsfähiger.
8. Nur ​​falsch, wenn eine andere Antwort erwartet wurde.
9. Tree Traversal wurde durch die Abfrageersteller von Doctrine entdeckt.

Das obige ist der detaillierte Inhalt vonDie einstündige Ausdruckssprache. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!