Was ist Parsing in Begriffen, die ein neuer Programmierer verstehen würde?

Question

Ich bin Studentin und mache meinen Abschluss in Informatik. Viele meiner Kommilitonen haben noch nicht wirklich viel programmiert. Sie haben ihre Klassenarbeiten gemacht, aber seien wir mal ehrlich, diese Fragen bringen einem nicht wirklich bei, wie man programmiert.

Mehrere andere Schüler haben mir Fragen dazu gestellt, wie man Dinge analysiert, und ich bin mir nie ganz sicher, wie ich es ihnen erklären soll. Ist es am besten, einfach Zeile für Zeile nach Teilstrings zu suchen, oder ihnen die kompliziertere Vorlesung über die richtige lexikalische Analyse usw. zu halten, um Token zu erstellen, BNF zu verwenden und all das andere Zeug? Sie verstehen es nie ganz, wenn ich versuche, es zu erklären.

Wie erkläre ich das am besten, ohne sie zu verwirren oder sie davon abzuhalten, es tatsächlich zu versuchen?

Answer 1

Ich würde Parsing als den Prozess der Umwandlung einer Art von Daten in eine andere Art von Daten erklären.

In der Praxis bedeutet das für mich fast immer, dass ich eine Zeichenkette oder binäre Daten in eine Datenstruktur innerhalb meines Programms umwandle.

Zum Beispiel das Drehen

":Nick!User@Host PRIVMSG #channel :Hello!"

in (C)

struct irc_line {
    char *nick;
    char *user;
    char *host;
    char *command;
    char **arguments;
    char *message;
} sample = { "Nick", "User", "Host", "PRIVMSG", { "#channel" }, "Hello!" }

Answer 2

Parsing ist der Prozess der Analyse eines Textes, der aus einer Abfolge von Token besteht, um seine grammatikalische Struktur im Hinblick auf eine gegebene (mehr oder weniger) formale Grammatik zu bestimmen.

Der Parser baut dann eine Datenstruktur auf der Grundlage der Token auf. Diese Datenstruktur kann dann von einem Compiler, Interpreter oder Übersetzer verwendet werden, um ein ausführbares Programm oder eine Bibliothek zu erstellen.

_{(Quelle: <a href="http://upload.wikimedia.org/wikipedia/en/a/a9/Parser_Flow.gif" rel="noreferrer">wikimedia.org </a>)}

Wenn ich Ihnen einen englischen Satz gebe und Sie auffordere, den Satz in seine Bestandteile (Substantive, Verben usw.) zu zerlegen, würden Sie den Satz parsen.

Das ist die einfachste Erklärung für das Parsing, die mir einfällt.

Allerdings ist das Parsing ein nicht triviales Rechenproblem. Man muss mit einfachen Beispielen beginnen und sich zu den komplexeren hocharbeiten.

Answer 3

Was ist Parsing?

In der Informatik ist Parsing der Prozess der Analyse von Text, um festzustellen, ob er zu einer bestimmten Sprache gehört oder nicht (d. h. ob er syntaktisch gültig für die Grammatik der betreffenden Sprache ). Es ist eine informelle Bezeichnung für die syntaktische Analyse Prozess.

Nehmen wir zum Beispiel an, die Sprache a^n b^n (d.h. gleiche Anzahl von Zeichen A gefolgt von gleicher Anzahl von Zeichen B). Ein Parser für diese Sprache würde akzeptieren AABB Eingabe und verwerfen die AAAB Eingabe. Das ist die Aufgabe eines Parsers.

Außerdem könnte während dieses Prozesses eine Datenstruktur für die weitere Verarbeitung erstellt werden. In meinem vorangegangenen Beispiel könnte es zum Beispiel darum gehen, die AA et BB in zwei getrennten Stapeln.

Alles, was danach passiert, wie z. B. der Sinngebung von AA ou BB oder in etwas anderes umwandeln, ist kein Parsing. Das Verleihen von Bedeutung an Teile einer Eingabesequenz von Token wird als semantische Analyse .

Was wird nicht geparst?

• Parsing bedeutet nicht, eine Sache in eine andere umzuwandeln. Die Umwandlung von A in B ist im Wesentlichen das, was ein Compiler tut. Das Kompilieren umfasst mehrere Schritte, das Parsen ist nur einer davon.
• Parsing bedeutet nicht, einem Text eine Bedeutung zu entnehmen. Das heißt semantische Analyse ein Schritt des Kompilierungsprozesses.

Wie kann man es am einfachsten verstehen?

Ich denke, der beste Weg zum Verständnis des Parsing-Konzepts ist, mit den einfacheren Konzepten zu beginnen. Das einfachste Konzept im Bereich der Sprachverarbeitung ist der endliche Automat. Es handelt sich um einen Formalismus zum Parsen regulärer Sprachen, wie z. B. reguläre Ausdrücke.

Es ist sehr einfach: Sie haben eine Eingabe, eine Reihe von Zuständen und eine Reihe von Übergängen. Betrachten Sie die folgende Sprache, die aus dem Alphabet aufgebaut ist { A, B } , L = { w | w starts with 'AA' or 'BB' as substring } . Der nachstehende Automat stellt einen möglichen Parser für diese Sprache dar, bei dem alle gültigen Wörter mit "AA" oder "BB" beginnen.

    A-->(q1)--A-->(qf)
   /  
 (q0)    
   \          
    B-->(q2)--B-->(qf)

Es ist ein sehr einfacher Parser für diese Sprache. Sie beginnen bei (q0) den Ausgangszustand, dann liest man ein Symbol von der Eingabe, wenn es A dann gehen Sie zu (q1) Zustand, ansonsten (es ist ein B erinnern Sie sich daran, dass das Alphabet nur A et B ) ziehen Sie um nach (q2) Staat und so weiter. Wenn Sie erreichen (qf) Zustand, dann wurde die Eingabe akzeptiert.

Da er visuell ist, brauchen Sie nur einen Stift und ein Blatt Papier, um jedem, auch einem Kind, zu erklären, was ein Parser ist. Ich denke, die Einfachheit ist es, die Automaten zum geeignetsten Mittel macht, um Sprachverarbeitungskonzepte wie Parsing zu lehren.

Als Informatikstudent schließlich werden Sie solche Konzepte in theoretischen Informatikkursen wie Formale Sprachen und Rechentheorie eingehend studieren.

Answer 4

Lassen Sie sie versuchen, ein Programm zu schreiben, das beliebige einfache arithmetische Ausdrücke auswerten kann. Das Problem ist einfach zu verstehen, aber wenn man tiefer in die Materie einsteigt, ergibt eine Menge grundlegender Parsing-Funktionen einen Sinn.

Answer 5

Parsing bedeutet für mich, etwas in sinnvolle Teile zu zerlegen... unter Verwendung eines definierbaren oder vordefinierten, bekannten, gemeinsamen Satzes von Teil-"Definitionen".

Für Programmiersprachen gäbe es Schlüsselwortteile, brauchbare Interpunktionsfolgen...

Bei einem Kürbiskuchen könnten das etwa die Kruste, die Füllung und der Belag sein.

Bei den Schriftsprachen könnte es darum gehen, was ein Wort ist, ein Satz, was ein Verb ist...

Bei gesprochenen Sprachen könnten dies Tonfall, Lautstärke, Stimmung, Implikation, Emotion, Kontext sein.

Die Syntaxanalyse (und auch der gesunde Menschenverstand) würde zeigen, ob es sich bei dem, was Sie parsen, um einen Kürbis oder um eine Programmiersprache handelt. Hat es eine Kruste? Nun, vielleicht ist es Kürbispudding oder vielleicht eine gesprochene Sprache!

Eine Sache, die man beim Parsing beachten sollte, ist, dass es normalerweise viele Möglichkeiten gibt, Dinge in Teile zu zerlegen.

Man kann zum Beispiel einen Kürbiskuchen aufbrechen, indem man ihn von der Mitte zum Rand oder von unten nach oben durchschneidet oder mit einem Löffel die Füllung herausholt oder ihn mit einem Vorschlaghammer zerschlägt oder isst.

Und die Art und Weise, wie man die Dinge analysiert, entscheidet darüber, ob etwas mit diesen Teilen leicht oder schwer zu machen ist.

In der Welt der "Computersprachen" gibt es gängige Methoden zum Parsen von Textquellcode. Diese gängigen Methoden (Algorithmen) haben Titel oder Namen. Suchen Sie im Internet nach gängigen Methoden/Namen für das Parsen von Sprachen. Wikipedia kann in dieser Hinsicht helfen.