Eine weitere Nacherzählung des “Tutorials” von Jack Crenshaw / Sudo Null IT News

Manchmal ist es angenehm, eine mehr oder weniger nicht triviale Aufgabe mit dem Gefühl einer leichten Basis unter den Füßen zu lösen. Die Basis ist sozusagen bereits vorhanden, und wir, als etwas zwischen einem Künstler und einem Architekten, ertappen uns (zu einem bestimmten Zeitpunkt) dabei, das Leere ins Leere zu verschieben, etwas Helles und Starkes vorzubereiten (fast wie ein halbtrockenes rot 🙂. Hell – denn ohne ein Jota Schönheit kommt man leicht halbwegs davon, und stark – der Beruf verpflichtet

compilers.iecc.com/crenshaw

(nichttechnische Einführung in den Compilerbau) und beginnen wir damit, einen kleinen, aber recht anständigen Linter zu bauen

en.wikipedia.org/wiki/Lint_

(Software) (Ehrlich gesagt, da die Analyse des Javascript-Codes unten implementiert wird, ist es durchaus akzeptabel, aber nur vorübergehend, den Linter in Parser umzubenennen und neu zu denken)

Zuerst wollte ich die Basis so erklären, wie sie ist, aber nach einigem Nachdenken kann man zu dem enttäuschenden Schluss kommen, dass eine gut definierte Basis keinen Sinn machen wird, da sie sich an einem bestimmten Punkt im Raum befindet, zu einem bestimmten Zeitpunkt Mit der Zeit ist die Zukunft wie die Vergangenheit sehr vage.

Teil 1

compilers.iecc.com/crenshaw/tutor1.txt
Einführung…
zur Theorie und Praxis der Entwicklung von Sprachparsern und Compilern.
Einfach sehr lesenswert 🙂

Teil 2

compilers.iecc.com/crenshaw/tutor2.txt
Ausdrucksanalyse

Als Ergebnis müssen Sie in der Lage sein, den folgenden Ausdruck zu analysieren (1+2)/((3+4)+(5-6))

Nun, fangen wir vielleicht an

std::string_view s{“(1+2)/((3+4)+(5-6))”}; const m = matcher{std::begin(s), std::end(s)}; lint(ausdruck_t{}, m);

Das heißt, wir gehen davon aus, dass das Ausdruckstoken der Ausdruck in Klammern ist. Hier ist es theoretisch notwendig, eine Art Beziehung zwischen drei Token (warum genau drei, um ehrlich zu sein xs, nehmen wir an, sie haben es zufällig genommen) festzustellen: Ausdruck, Begriff und Operator.

Ausdruck <-> Begriff <-> Operator

… gibt es 5+5
… gibt es 5+5+5
… gibt es 5+5+5+5

Das heißt, die erste Option kann beschrieben werden als: Begriff, Operator, Begriff
Der zweite ist Term, Operator, Term, Operator, Term
Nachfolgend – Begriff, {Operator, Begriff}*
Das heißt, Ausdruck = Begriff, {Operator, Begriff}*

Ferner ist Begriff entweder eine Zahl oder Klammern. Was ist so großartig an der Rekursion, dass Sie hier und jetzt denken können, ohne über den vorherigen Kontext nachzudenken:
Begriff=Zahl | ‘(‘, Ausdruck, ‘)’ ist entweder eine Zahl oder “Ausdruck” in Klammern, aber was für ein “Ausdruck” ist das? Das heißt, es war möglich, die Definition mit Begriff zu beginnen, ohne einen Unterschied im Allgemeinen.

Nochmal was passiert:

Ausdruck = Begriff, {Operator, Begriff}*
Begriff=Zahl | ‘(‘, Ausdruck, ‘)’

Wir übersetzen in Code:

template result_t lint(const expression_t&, matcher& m) { auto x = and_t { term_t{}, optional_t{ iff_t{ operator_t{}, expression_t{}, } } }; return lint(std::move(x), m); } struct term_t {}; template result_t lint(const term_t&, matcher& m) { auto x = or_t { iff_t{ char_t{context::Chars::LeftBracket}, and_t{ expression_t{}, char_t{context::Chars: :RightBracket} } }, number_t{}, }; return lint(std::move(x), m); }

Teil 3

compilers.iecc.com/crenshaw/tutor3.txt
mehr Ausdruck

Hier lernen wir, Variablen und Zuweisungen zu parsen.

Ziemlich einfach, aber es funktioniert:

Strukturzuweisung_t {}; template result_t lint(const Assignment_t&, matcher& m) { auto x = std::vector { // modelliert ‘foreach’-Relation identifier_t{}, char_t{context::Chars::EqualSign }, expression_t{}, optional_t{ char_t{context::Chars::Semikolon} }, }; return lint(std::move(x), m); }

Teil 4

compilers.iecc.com/crenshaw/tutor4.txt
Dolmetscher
Nicht für Linterzwecke, aber interessanter und informativer Text

Teil 6

compilers.iecc.com/crenshaw/tutor6.txt
Boolescher Ausdruck
Interessante Lektüre, aber in unserer Version des Linters vergessen wir die Operatorpriorität

Teil 5, Teil 7

compilers.iecc.com/crenshaw/tutor7.txt
Schlüsselwörter und Lexikonscanner

Es scheint, als ob der Scanner nur wegen der Schlüsselwörter benötigt wird. Die Leute haben einmal gemerkt, dass das Beschreiben der Regeln für “reinen Text” etwas kompliziert oder langweilig ist. Warum den Text nicht in Token parsen und erst dann die Parsing-Regeln der Programmiersprache anwenden? Das ist es, was Erwachsene tun (einschließlich Jack Crenshaw), und für unseren bescheidenen Linter wird das Parsen in Token überflüssig oder langweilig sein. Aber die Frage blieb offen: Wie kann man zwischen einem Schlüsselwort und einer Variablen unterscheiden?

while (true) {…} willing = true

Das heißt, wir finden den Unterschied zwischen den beiden Zeilen am fünften Zeichen – einerseits ist es irgendwie zu spät, andererseits sind dies Informationen, mit denen Sie arbeiten können. Das heißt, wir haben eine _Auswahl_, die auf Informationen zum Parsen eines Blocks mit einem Schlüsselwort basiert: Schlüsselwort -> Übereinstimmung | Nichtübereinstimmung | Nichtübereinstimmung nach n Symbolen mit n > 0

Oder in Code übersetzen:

template result_t lint(const while_statement_t&, matcher& m) { auto x = choice_t { keyword_t{context::Keywords::While}, // if we match keyword must_t {/* parse body of while expression */}, // prüfen wir das nächste Schlüsselwort, wenn wir an der ersten Position fehlen if_statement_t{}, // wenn es an anderen Positionen nicht übereinstimmt, prüfen wir einfach // auf Variable oder Funktionsaufruf mismatch_keyword_t{}, }; return lint(std::move(x), m); } struct choice_t { linter a; linterb; Linter c; linter d; }; template constexpr result_t lint(const choice_t& x, matcher& m) { auto r = lint(xa, m); if (!r) return lint(xb, m); return lint(*r == 0 ? xc : xd, m); }

Teil 8

compilers.iecc.com/crenshaw/tutor8.txt
philosophisch

Tatsächlich stellt sich nach sieben schicken, aber sehr großen Teilen eine Sättigung ein. Kapitel Nummer acht liest sich lebhaft, aber mit der Absicht, danach eine Pause einzulegen. Acht Kapitel hinter und acht werden voraus sein, als würden sie auf einen Stopp hinweisen. Wir werden nach einem weiteren Block aufhören. Jetzt können wir ein solches sehr bedeutungsloses, aber möglicherweise gängiges Skript in der Produktion bereits analysieren:

const co = 4; konstante Geschwindigkeit = 42*co + 4/5; for (const x of xs) { log(x) } for (let x of xs) { x = x + 1 notification(x+x) } if (!shouldShow) {let i = 100; sei j = 1000; Aufnahme starten (); while (i != (ij)) { while((j+1 >= 100) && (i <= 50)) { if (i**j === 5) { log(i) } } i = i - eines; j = j - ich; nächste(); } if (!!gutesWetter) { i = 6**32 done(); } else { if (!willBeWorse) { i = -2; justSomeFunc(); } ich = (1+2)/((3+4)+(5-6)) + ich; benachrichtigen (i); } }

Der fehlende Block ist eine Funktion. Eine Funktion ist eine sehr notwendige Sache; ohne sie kann nicht einmal eine funktionale Programmierung erstellt werden, ganz zu schweigen von anderen. Gebäude:

(a, b) => {…} // unser Lambda
(a + 5) * 42

Hier gibt es ein Parsing-Problem: Unsere Funktion und der Ausdruck in Klammern haben einen gemeinsamen Teil. Tatsächlich ist es sogar noch etwas komplizierter, da das gemeinsame Präfix sozusagen aus zwei Zeichen besteht: einer Klammer und einer Variablen, und erst nach dem dritten Zeichen erscheint die Antwort auf die Frage „eine Funktion oder nicht“. .

Hier gibt es tatsächlich ein paar Richtungen. Der erste ist wie die Erwachsenen, gehen Sie zwei Token zurück, wenn “keine Funktion” ist, und führen Sie dann den Parser für den Ausdruck aus. Wir haben einen InputIterator, und leider können wir nicht zurückgehen. Es gab eine Idee, wie man das System austrickst und der Parsing-Zeile ein Präfix hinzufügt:

“(a – 5) * 42” -> Anfangsstring
“- 5) * 42” -> Zeile nach Fehler
“(and” `concat` “- 5) * 42” -> Versuchen Sie nun, den Ausdruck zu finden

Hier konnte ich nichts Einfaches finden, um zwei Iteratoren zu kombinieren, obwohl es so aussieht, als ob es nicht schwierig sein sollte, weil der letzte für InputIterator immer gleich ist.

Die zweite Variante ist etwas exotisch, funktioniert aber auch: Jeder Linter hat ein Schema (auto x =… in den obigen Beispielen), was ist, wenn dieses Schema in nur einem Schritt ausgeführt wird, zum Beispiel:

auto x = and_t{ number_t{}, operator_t{}, number_t{}};
auto x2 = make(x, ‘5’); // füttere ‘5’
x2 // -> and_t{ noop_t{}, operator_t{}, number_t{}};

Jetzt ist x2 ein gültiges Schema für die Zeile „+7“. Der Algorithmus stellt sich als etwas zu kompliziert heraus, und wir suchen nach einfachen und einfachen Wegen, also werden wir uns daran erinnern und es beiseite legen.

Varik ist eine Priorität – um gültige Schemata für einen Ausdruck ohne die erste Klammer und eine Variable mit Stiften zu sammeln. Die Schemata sehen etwas ungewöhnlich aus, sind aber recht einfach.

Code für Lambda:

struct lambda_t{}; template result_t lint(const lambda_t&, matcher& m) { // (x, …) => {…} // vs (x + 55) * 6 auto r = lint( char_t{context::Chars::LeftBracket}, m); auto p = lint(identifier_t{}, m); auto q = lint(char_t{context::Chars::Comma}, m); // basierend auf den Ergebnissen von r, p und q haben wir 2**3 = 8 Optionen // die Hälfte davon wird von unserem Parser nicht unterstützt // eine folgt direkt dem Hauptteil unseres Lambdas // andere dem Ausdruck oder Teilausdrücken (zB ohne erste Klammer)

Jetzt können wir parsen

const bar = (a,b) => { foo(); Bar(); }

und die Welt erobern, naja, vielleicht klappt es beim nächsten Mal 🙂

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *