[Erledigt] Suche Parser - Tutorial

[mytar]

Hallo! :)

Bin garade auf der suche nach einem guten Parser - Tutorial?

Hier in der DP gibts jedemenge Code, aber ich möchte als Newbie vom Anfang starten.

Könnt ihr mir weiterhelfen?

greetz
mytar :-D

[edit=MrSpock]Auf Wunsch als erledigt markiert. Mfg, MrSpock[/edit]

[mytar]

* push *

greetz
mytar :)

[xineohp]

moin,

von einem Parser - Tutorial hab ich noch nie was gehört ... geschweigedenn von einem guten :wink:

es wird dir wohl nix anderes übrigbleiben, als den hier gefundenden Code nachzuvollziehen ...

bei Fragen kannst du ja fragen :mrgreen:

[mytar]

Dann hab ich mich warscheinlich falsch ausgedrückt.

Gibt es sonst eigentlich irgengwelche Beschreibungen oder Text wie man einen
vernünftigen Parser baut?

greetz
mytar :)

[Tubos]

Falls du HTML parsen willst, würde ich den DiHTMLParser verwenden.
Der ist sehr einfach zu verwenden, schnell und funktioniert gut.
Achja, und Freeware :)

[torud]

Hallo!

Und noch eine Antwort. Also vielleicht solltest Du hier mal posten, was Du parsen willst und was Du dann mit dem geparsten anstellen willst? Parsen ansich ist ja nicht nur, wie gern immer angenommen wird nur das Syntaxhighlighting einer Programmiersprache.

Gib mehr Infos und Du bekommst, falls denn noch noetig, mehr Hilfe!

[Luckie]

Beim Stichwort "paresen" fällt mir zu erst "Compilerbau" ein.

[mytar]

Danke, für die Antworten!

Mir geht es in erster Linie um das Parsen von mathematischen Ausdrücken bzw. Termen.

greetz
mytar :-D

[torud]

Parser (von englisch to parse - analysieren) ist ein Programm, das entscheidet, ob eine Eingabe zur Sprache einer bestimmten Grammatik gehört. Er benutzt dabei in der Regel einen separaten Scanner, um eine zeichenweise vorliegende Eingabe vorher in Token (zusammengehörende Einheiten, z. B. Schlüsselwörter, Bezeichner usw.) zu konvertieren.

Während des Parsens erfolgt eine syntaktische Überprüfung der Eingangsdaten. Bei der Überprüfung wird in der Regel aus den Daten ein Baum aufgebaut, um die Daten anschließend weiterverarbeiten zu können (z. B. semantische Analyse und Codegenerierung in einem Compiler).

Hinweis: Der Begriff parsen sollte nicht mit dem Begriff kompilieren verwechselt werden. Letzteres erzeugt einen Zielcode aufgrund eines Quellcodes, dabei wird unter anderem auch geparst, darüberhinaus finden aber weitere Aktionen statt. Siehe hierzu auch Compilerbau, Parser-Generator.

Das Parsen wohldefinierter künstlicher Sprachen (siehe formale Sprachen, Programmiersprachen) ist weniger komplex als das Parsen frei gewachsener natürlicher Sprachen wie Englisch oder Deutsch, die durch eine Vielzahl von Mehrdeutigkeiten, Irregularitäten und Inkonsistenzen geprägt sind. Siehe hierzu auch Computerlinguistik.

[Niels]

Hi!

Bin zur Zeit dabei ne Scriptsprache zu entwickeln. Hab aber erst vor Kurzem angefangen (bin noch beim Parser). Du willst bestimmt, dass man beispielsweise in ein Edit-Feld einen mathematischen Ausdruck eingibt und dieser dann berechnet wird. Zuerst brauchst du einen Lexer, der wie der Name schon sagt, Den "Text" auseinandernimmt, also in sogenannte Token unterteilt. Dieser Tokenstrom wird dann an den Parser weitergegeben. Dieser führt nun eine Analyse der Grammatik durch und ordnet die Token in einen Baum ein (wie torud schon gesagt hat). Der Inhalt dieses Baums wird dann durch Funktionen berechnet.

Hier mal ein Beispiel (so habe ich meine Parser-Funktionen aufgebaut):

Ein arithmetischer Ausdruck enthält eine Summe. Eine Summe besteht aus einem Produkt und einer weiteren Summe.
Der erste Faktor eines Produktes ist eine Zahl/Variable oder ein arithmetischer Ausdruck, der zweite Faktor wieder ein Produkt.

Falls du dich jetzt fragst was mit Subtraktion und Division ist, Summe und Differenz, sowie Produkt und Quotient kann man aufgrund ihrer Ähnlichkeit gemeinsam behandeln.


mfg Niels :thumb:

[edit] Damit das Beispiel funktioniert, muss der arithmetische Ausdruck in Klammern stehen [/edit]

[mytar]

Ja ich verstehe.

@torud: Bei wikipedia hab ich schon geschaut.

Wie erzeuge ich aus so einem Ausdruck einen Termbaum?

greetz
mytar :)

[xineohp]

moin,

du suchst den rangniedrigsten Operator in deinem Term (und zwar nur in der äußersten Klammerebene, d.h. Ausdrücke in Klammern werden ignoriert):
also zB: 1-2*(3+4) --> niedrigster Operator: "-"

Diesen trägst du dann als Wurzel in deinen Baum ein. Anschließend rufst du deine Funktion rekursiv wieder auf, und zwar einmal mit dem linken und einmal mit dem rechten Teilausdruck:
also nachdem obigen Beispiel:

linker Teil: 5 --> kein Operator vorhanden, 5 wird als linker Nachfolger der Baumwurzel("-") eingetragen.

rechter Teil: 2*(3+4) --> liefert "*" als niedrigsten Operator, dieser wird als rechter Nachfolger der Baumwurzel("-") eingetragen.
Anschließend: erneute Rekursion mit 2 und (3+4):

linker Teil: 2 -->kein Operator vorhanden, 2 wird als linker Nachfolger des Knotens("*") eingetragen.

rechter Teil: (3+4) --> kein Operator (außerhalb der Klammern; s.o.) vorhanden UND 1.Zeichen = "(" es folgt: der gesamte Ausdruck ist von Klammern umschlossen. daher: erstes und letztes Zeichen löschen --> 3+4 und wieder Rekursion :wink: --> niedrigster (und einzigster Operator) = "+" ... als Knoten eintragen ... Rekursion linker Teil: 3 ; Rekursion rechter Teil: 4

so, Baum fertig :mrgreen:

Code:

  1-2*(3+4) -->

     -
    / \
   1   *
      / \
     2   +
        / \
       3   4

[mytar]

Ich verstehe jetzt langsam.

Die Rekursionsaufrufe sind genau wie bei Quicksort.

greetz
mytar :-D