Computer Science text book way to do text/xml/whatever parsing

Question

It's been ratling in my brain for a while.

I've had some investigation on Compilers/Flex/Byson and stuff but I never found a good reference that talked in detail about the "parsing stack", or how to go about implementing one.

Does anyone know of good references where I could catch up?

Edit: I do appreciate all the compiler references, and I'm going to get some of the books listed, but my main focus was on the Parsing itself and not what you do with it after.

Answer 1

This is in response to Dima's answer that you accepted as the correct answer. Although it is not a bad answer to state that parsing is related to automata theory, I feel that there is some misunderstanding here.

• Firstly, finite state automata are only able to recognize regular languages (e.g. regular expressions). In order to recognize context-free languages you need pushdown automata, which is more powerful. See http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata for more automata and their relation to different classes of languages.

• Secondly, parsing is different from recognizing. Recognizing a string only tells you whether that string is in the language generated by your grammar. The purpose of a parser is to produce a concrete syntax tree which is both harder and generally more useful.

There's a wide variety of parsing methods out there, so it's hard to give you one specific reference that will tell you what you need to know... In general, you should understand the difference between top-down parsing and bottom-up parsing. But here's an overview of a few common techniques employed by parser generators in case you're interested:

• The wikipedia articles for LR Parsing, LL Parsing, SLR Parsing, LALR Parsing, GLR Parsing
• ANTLR's LL(*) parsing
• Monadic Parsing in Haskell (for building parsers in functional programming languages)
• And the more exotic Parsing Expression Grammars

EDIT: I'm sorry for bumping this question again, I just happened across two excellent posts describing the relationship between regular languages and finite automata, context-free languages and push-down automata. Might be interesting for people who find this question.

Answer 2

The Dragon book! I used it quite recently to write a compiler (in PHP!) for a processing language for template files written in RTF...

Answer 3

A parser is basically a finite state machine, aka a finite automaton. You should find a book on theory of computation, which discusses finite automata, and things like regular languages, context free languages, etc.

Answer 4

try amazon

Compiler Construction is just one good example

Answer 5

Check out "Brinch Hansen on Pascal Compilers".. it was written in 1985, but I used it last year for a course on compilers (by Per Brinch Hansen ofcourse.) and found it very concise and helpful for compiler design.