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

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


--
Quinn


http://members.shaw.ca/qtj/


[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.
2002.


[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 comp.compilers page.
Search the comp.compilers archives again.