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

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

CC BY-SA 3.0
2014-12-03T00:09:55.933Z
This was an encyclopedia on the topic at the time of publication. But there has been research work done since then.
babou
CC BY-SA 3.0
2014-12-02T14:11:26.043Z
2014-12-02T14:11:26.043Z
Zsbán Ambrus
<p>If you don't mind the language difference, Chapter 8 of <a href="http://hop.perl.plover.com/" rel="nofollow">Higher Order Perl</a> 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 <em>my</em> interest in parsing techniques a number of years back.</p>

CC BY-SA 3.0
2014-12-02T20:56:43.233Z
2014-12-02T20:56:43.233Z
hobbs
<p>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. </p>

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

<p>In any case, what you need to learn is:</p>

<ul>
<li>recursive-descent parsing and LL grammars</li>
<li>fixed lookahead vs. infinite lookahead (done via backtracking)</li>
<li>backtracking strategies</li>
<li>how to deal with Left-recursive rules</li>
<li>Memoization of the partial results to avoid exponential behavior</li>
</ul>

CC BY-SA 3.0
2015-01-02T01:39:40.787Z
2015-01-02T01:39:40.787Z
Wickoo
<p>One book that I can recommend is D. Grune, C. J. H. Jacobs, <a href="http://dickgrune.com/Books/PTAPG_2nd_Edition/">Parsing Techniques: a Practical Guide</a>. </p>

CC BY-SA 3.0
2014-12-02T15:17:30.200Z
2014-12-02T15:17:30.200Z
Martin Berger
<p>One of my Java projects is a <a href="https://github.com/parboiled1/grappa">fork of parboiled</a>, 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").</p>

<p>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.</p>

<p>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?</p>

<research-practice><books><parsing>
Good books on parser theory?
fge
# Good books on parser theory?

(Asked by: username_0 on 2014-12-02)

One of my Java projects is a [fork of parboiled](https://github.com/parboiled1/grappa), 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?

**Tags:** research-practice, books, parsing


---

## 4 answers

### Answer by username_5 on 2014-12-02. Score: 13 | Accepted answer

One book that I can recommend is D. Grune, C. J. H. Jacobs, [Parsing Techniques: a Practical Guide](http://dickgrune.com/Books/PTAPG_2nd_Edition/).


---

### Answer by username_1 on 2014-12-02. Score: 3

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).

> **Comments:**
> **username_2**: This was an encyclopedia on the topic at the time of publication. But there has been research work done since then.  

---

### Answer by username_3 on 2014-12-02. Score: 2

If you don't mind the language difference, Chapter 8 of [Higher Order Perl](http://hop.perl.plover.com/) 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.


---

### Answer by username_4 on 2015-01-02. Score: 2

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


---

