RE: An "open" letter to Karsten Nyblad (and other compiler compiler implementors)

Quinn Tyler Jackson <>
30 Jun 2005 09:58:46 -0400

          From comp.compilers

Related articles
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im (Chris F Clark) (2005-06-23)
RE: An "open" letter to Karsten Nyblad (and other compiler compiler im (Quinn Tyler Jackson) (2005-06-30)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 30 Jun 2005 09:58:46 -0400
Organization: Compilers Central
References: 05-06-111
Keywords: LR(1), parse, bibliography
Posted-Date: 30 Jun 2005 09:58:46 EDT

Chris F. Clark said:

> Brian Ford's innovation of packrat parsing is an interesting twist
> on the backtracking theme that linearizes the resulting performance.

Memoization of parsing results dates at least back to [Norvig] in 1991, and
then to [Johnson] in 1995. The term itself dates back to [Michie] in 1968 --
so it's not an entirely new technique. This is not to disparage [Ford]'s
2002 work -- which seems to be a very good implementation of it in
combination with [Birman]'s top-down parser.

I attempted to get some gains with memoization of adaptive parsers. The
results of this will be included in the second half of the chapter I am in
the middle of putting together (which explains the specific references).


[Birman] Alexander Birman, _The TMG Recognition Schema_, Ph.D. dissertation,
Princeton University, Dept. of Electrical Engineering, Feb. 1970.

[Ford] Bryan Ford, _Packrat Parsing: a Practical Linear-Time Algorithm with
Backtracking_, Masterís thesis, Massachusetts Institute of Technology, Sept.

[Johnson] Mark Johnson, "Memoization of Top-Down Parsing," Computational
Linguistics, Vol. 21 No. 3, pp. 405-417, Sept. 1995.

[Michie] Donald Michie, "Memo Functions and Machine Learning," Nature, No.
218, pp. 19-22, 1968.

[Norvig] Peter Norvig, "Techniques for Automatic Memoization with
Applications to Context-Free Parsing," Computational Linguistics, Vol. 17
No. 1, pp. 91-98, March 1991.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.