|Re: An "open" letter to Karsten Nyblad (and other compiler compiler im cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-23)|
|RE: An "open" letter to Karsten Nyblad (and other compiler compiler im firstname.lastname@example.org (Quinn Tyler Jackson) (2005-06-30)|
|From:||Quinn Tyler Jackson <email@example.com>|
|Date:||30 Jun 2005 09:58:46 -0400|
|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.
Return to the
Search the comp.compilers archives again.