Pratt-parser
in [General Programming]
|
From: Rod Pemberton on 5 Nov 2009 02:50 Is anyone here familiar with Vaughn Pratt's concept of "Top Down Operator Precedence" (1973) or Pratt-parsers? I'd like to know more about the technique. Unfortunately, the articles below are programming language heavy. Apparently, Pratt-parsers are recursive descent parsers modified by top down operator precedence. It seems that this dramatically reduces the code size. AFAICT, Pratt-parsers are used with CGOL, LISP, and Scheme. Otherwise, the concept was obscure until recently. However, it has been rediscovered apparently by Crockford: for Javascript, by Douglas Crockford http://javascript.crockford.com/tdop/tdop.html for Python, by Fredrik Lundh http://effbot.org/zone/simple-top-down-parsing.htm Rod Pemberton
From: Dmitry A. Kazakov on 5 Nov 2009 04:04 On Thu, 5 Nov 2009 02:50:02 -0500, Rod Pemberton wrote: > Is anyone here familiar with Vaughn Pratt's concept of "Top Down Operator > Precedence" (1973) or Pratt-parsers? I don't have the paper, but I remember a Pratt's book (1975) where the parsing technique was described. > I'd like to know more about the technique. Unfortunately, the articles > below are programming language heavy. > > Apparently, Pratt-parsers are recursive descent parsers modified by top down > operator precedence. It seems that this dramatically reduces the code size. > > AFAICT, Pratt-parsers are used with CGOL, LISP, and Scheme. Otherwise, the > concept was obscure until recently. However, it has been rediscovered > apparently by Crockford: > > for Javascript, by Douglas Crockford > http://javascript.crockford.com/tdop/tdop.html > > for Python, by Fredrik Lundh > http://effbot.org/zone/simple-top-down-parsing.htm I am using Pratt's method for decades. I am not sure if he invented it, he didn't say it in the book, maybe he was. I have built several compilers on it. In my view it is simple and efficient. One of the compilers I built was in Assembler for a 32K machine, which illustrates how simple the method is. I also extended the methods towards two asymmetric priorities. You can find a description and implementation here http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc The section 11.2 contains an explanation how the techinique works for most complex expressions one can find in programming languages and mathematics notation: http://www.dmitry-kazakov.de/ada/components.htm#11.2 One of the crucial advantages of the technique is that it does not require grammar, and as a consequence nothing need to be precompiled/generated. The parser can be made 100% table-driven. It perfectly suitable for OO design. I am glad to see that the method finally gains attention it certainly deserves. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Rod Pemberton on 5 Nov 2009 05:17 "Dmitry A. Kazakov" <mailbox(a)dmitry-kazakov.de> wrote in message news:1jgp7sm64eejy$.1tz85slyasyb7$.dlg(a)40tude.net... > On Thu, 5 Nov 2009 02:50:02 -0500, Rod Pemberton wrote: > > > Is anyone here familiar with Vaughn Pratt's concept of "Top Down Operator > > Precedence" (1973) or Pratt-parsers? > > I don't have the paper, but I remember a Pratt's book (1975) where the > parsing technique was described. > > > I'd like to know more about the technique. Unfortunately, the articles > > below are programming language heavy. > > > > Apparently, Pratt-parsers are recursive descent parsers modified by top down > > operator precedence. It seems that this dramatically reduces the code size. > > > > AFAICT, Pratt-parsers are used with CGOL, LISP, and Scheme. Otherwise, the > > concept was obscure until recently. However, it has been rediscovered > > apparently by Crockford: > > > > for Javascript, by Douglas Crockford > > http://javascript.crockford.com/tdop/tdop.html > > > > for Python, by Fredrik Lundh > > http://effbot.org/zone/simple-top-down-parsing.htm > > I am using Pratt's method for decades. I am not sure if he invented it, he > didn't say it in the book, maybe he was. I have built several compilers on > it. > > In my view it is simple and efficient. One of the compilers I built was in > Assembler for a 32K machine, which illustrates how simple the method is. > > I also extended the methods towards two asymmetric priorities. You can find > a description and implementation here > > http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc > > The section 11.2 contains an explanation how the techinique works for most > complex expressions one can find in programming languages and mathematics > notation: > > http://www.dmitry-kazakov.de/ada/components.htm#11.2 > > One of the crucial advantages of the technique is that it does not require > grammar, and as a consequence nothing need to be precompiled/generated. The > parser can be made 100% table-driven. It perfectly suitable for OO design. > > I am glad to see that the method finally gains attention it certainly > deserves. > Thank you! Hmm, your page lists "T. Pratt" and it seems Terrence Pratt wrote the book you mentioned. But, from the descriptions, it sounds like they do same thing... or very similar. RP
From: Dmitry A. Kazakov on 5 Nov 2009 05:44 On Thu, 5 Nov 2009 05:17:46 -0500, Rod Pemberton wrote: > Hmm, your page lists "T. Pratt" and it seems Terrence Pratt wrote the book > you mentioned. But, from the descriptions, it sounds like they do same > thing... or very similar. Once I asked in comp.compilers if anybody knew the author of the method, nobody was certain about it. Grammar-based approaches have been dominating compiler construction for many years being in my eyes inferior. History of software is full of such examples. For example, regular expressions is a quite weak class of languages incapable to recognize simple bracket constructs, very difficult and uncomfortable to use. Nevertheless it is basically the only pattern language known, except for wild-cards patterns. Far better and simpler SNOBOL patterns are forgotten. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Ben Pfaff on 5 Nov 2009 12:07
"Dmitry A. Kazakov" <mailbox(a)dmitry-kazakov.de> writes: > For example, regular expressions is a quite weak class of > languages incapable to recognize simple bracket constructs, > very difficult and uncomfortable to use. Nevertheless it is > basically the only pattern language known, except for > wild-cards patterns. Far better and simpler SNOBOL patterns are > forgotten. That's very interesting. I have never heard of SNOBOL patterns before. Wikipedia says: A SNOBOL pattern can be very simple or extremely complex. A simple pattern is just a text string (e.g. "ABCD"), but a complex pattern may be a large structure describing, for example, the complete grammar of a computer language. It is possible to implement a language interpreter in SNOBOL almost directly from a Backus-Naur form expression of it, with few changes. I see that there is a SNOBOL pattern extension for Python: http://snopy.sourceforge.net/user-guide.html -- "Writing is easy. All you do is sit in front of a typewriter and open a vein." --Walter Smith |