10
$\begingroup$

One of my Java projects is a fork of parboiled, and unlike, say, Antlr or JavaCC, parsers are generated at runtime. Grammars generated are Parsing Expression Grammars, or PEGs (I hear another term for them is "packrat").

While the runtime generation adds complexity (bytecode generation involved), another aspect relates to parser theory itself. As I have, unfortunately, no solid background in computer science, I lack theoretical knowledge to map existing code to existing concepts -- in this case, parsers.

Is there a good reference book on parsers which I can purchase and read, or even links on the Internet, which can help me build such a "mapping", accounting for my poor theoretical knowledge?

Improve this question
$\endgroup$
0

4 Answers 4

Reset to default
13
$\begingroup$

One book that I can recommend is D. Grune, C. J. H. Jacobs, Parsing Techniques: a Practical Guide.

Improve this answer
$\endgroup$
0
3
$\begingroup$

If you want to learn about the theory of parsers, I recommend volume 1 of this classic book:

Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling, Prentice-Hall (1972).

Improve this answer
$\endgroup$
1
  • $\begingroup$ This was an encyclopedia on the topic at the time of publication. But there has been research work done since then. $\endgroup$
    – babou
    Commented Dec 3, 2014 at 0:09
2
$\begingroup$

If you don't mind the language difference, Chapter 8 of Higher Order Perl is all about parsing, and in particular builds up a recursive descent parser using parser combinators. It's accessible (if you're not afraid of Perl) and available to read for free if you like. It helped spark my interest in parsing techniques a number of years back.

Improve this answer
$\endgroup$
2
$\begingroup$

While the Parsing Techniques is a great book and I have read some parts several time, it has its focus on LR parsing which won't be interesting for you. In your particular case, you are looking at PEGs which are sort of top-down recursive descent parsing with backtracking based on the order of alternatives.

I would like to suggest you to look at parser combinators, which use the same strategy. You can for example check this paper http://research.microsoft.com/pubs/65201/parsec-paper-letter.pdf which uses Haskell to build parser combinators. Check the section with try where they incorporate backtracking (Section 3.4).

In any case, what you need to learn is:

  • recursive-descent parsing and LL grammars
  • fixed lookahead vs. infinite lookahead (done via backtracking)
  • backtracking strategies
  • how to deal with Left-recursive rules
  • Memoization of the partial results to avoid exponential behavior
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.