Informatik Lehrbuch Art und Weise text / xml / was auch immer das Parsen zu tun

Question

Es ist schon in meinem Gehirn für eine Weile ratling.

Ich habe einige Untersuchungen auf Compilers / Flex / Byson und Sachen hatte, aber ich fand nie eine gute Referenz, die ausführlich über die „Parsing Stack“ gesprochen, oder wie über die Implementierung einer gehen.

Kennt jemand gute Referenzen, wo ich aufholen könnte?

Bearbeiten : Ich weiß schätzen, die all Compiler Referenzen, und ich werde einige der Bücher bekommen aufgelistet, aber mein Hauptaugenmerk lag auf dem Parsing selbst und nicht das, was Sie damit machen nach .

Answer 1

Dies ist als Reaktion auf Dima Antwort, die Sie als die richtige Antwort akzeptiert. Obwohl es keine schlechte Antwort ist zu sagen, dass das Parsen Theorie Automaten beziehen, fühle ich, dass es ein Missverständnis ist hier.

• Zuerst endliche Automaten ist nur in der Lage reguläre Sprachen (zum Beispiel reguläre Ausdrücke) zu erkennen. Um kontextfreie Sprachen zu erkennen, müssen Sie Kellerautomaten , die mächtiger ist. Siehe http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata für mehr Automaten und ihre Beziehung zu verschiedenen Klassen von Sprachen.

• Zweitens Parsen unterscheidet sich von Erkennen . nur einen String Erkennen sagt Ihnen, ob diese Zeichenfolge in der Sprache, die von der Grammatik erzeugt wird. Der Zweck eines Parser ist einen konkreten Syntaxbaum zu erzeugen, die sowohl härter ist und in der Regel mehr nützlich.

Es gibt eine Vielzahl von Analyseverfahren gibt, so ist es schwer, Sie einen bestimmten Bezug zu geben, die Ihnen sagen, was Sie ... In der Regel wissen müssen, sollten Sie den Unterschied zwischen verstehen top-down-Parsing und bottom-up-Parsing . Aber hier ist ein Überblick über ein paar gemeinsamen von Parser-Generatoren für den Fall verwendet Techniken, die Sie interessiert sind:

• Der Wikipedia-Artikel für LR Parsing , LL Parsing , SLR Parsing LALR Parsing , GLR Parsing
• LL (*) Parsing
• Monadic Parsing in Haskell (für Gebäude-Parser in der funktionalen Programmierung Sprachen)
• Und die exotischere Packrat Parser

EDIT: Es tut mir leid wieder diese Frage stoßen, ich über zwei ausgezeichnete Beiträge gerade passiert ist, die die Beziehung zwischen reguläre Sprachen und endliche Automaten , kontextfreie Sprachen und Push-down-Automaten . Könnte für Leute interessant sein, die diese Frage zu finden.

Answer 2

Das Drachen Buch ! Ich habe es erst vor kurzem einen Compiler (in PHP!) Für eine Verarbeitungssprache für Template-Dateien in RTF geschrieben zu schreiben ...

Answer 3

Ein Parser ist im Grunde eine Finite State Machine, auch bekannt als ein endlicher Automat. Sie sollten ein Buch über Theorie der Berechnung finden, die endlichen Automaten diskutiert, und Dinge wie reguläre Sprachen, kontextfreie Sprachen, etc.

Answer 4

amazon

Compiler Construction ist nur ein gutes Beispiel

Answer 5

Check out „Brinch Hansen auf Pascal Compiler“ .. es im Jahr 1985 geschrieben wurde, aber ich habe es im vergangenen Jahr für einen Kurs auf Compiler (von Per Brinch Hansen ofcourse.) Und fand es sehr präzise und hilfreich für die Compiler-Design.