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

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.

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.

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.

"Dmitry A. Kazakov" <mailbox at (no spam) 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.

Ben Pfaff <blp at (no spam) cs.stanford.edu> writes:

"Dmitry A. Kazakov" <mailbox at (no spam) 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.

They are very powerful but a little "operational" in that some of the
time you feel you are telling the matcher what to _do_ rather than
what to match. None the less, SNOBOL left a deep impression on me. I
recall an implementation of Russel's paradox in SNOBOL: a pattern, R,
that matches only those patterns that don't match themselves. You
then ask if R matches R!

Have you come across Icon[1]? Designed, at least in part, by Griswold
of SNOBOL fame. It have some very elegant ideas. It is a shame it is
not more widely know.

[1] http://www.cs.arizona.edu/icon/

Have you come across Icon[1]? Designed, at least in part, by Griswold
of SNOBOL fame. It have some very elegant ideas. It is a shame it is
not more widely know.

[1] http://www.cs.arizona.edu/icon/

Ben Bacarisse <ben.usenet at (no spam) bsb.me.uk> writes:

Ben Pfaff <blp at (no spam) cs.stanford.edu> writes:

"Dmitry A. Kazakov" <mailbox at (no spam) 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.

They are very powerful but a little "operational" in that some of the
time you feel you are telling the matcher what to _do_ rather than
what to match. None the less, SNOBOL left a deep impression on me. I
recall an implementation of Russel's paradox in SNOBOL: a pattern, R,
that matches only those patterns that don't match themselves. You
then ask if R matches R!

I looked around the web for a while and found a few superficial
descriptions of SNOBOL patterns. I also found a few SNOBOL
reference manuals, but again their descriptions of patterns were
very brief and I found it difficult to figure out how they were
used and why exactly they were so powerful.

Can you give a few examples?

I looked around the web for a while and found a few superficial
descriptions of SNOBOL patterns....

Can you give a few examples?

On Nov 6, 1:36 am, Ben Pfaff <b... at (no spam) cs.stanford.edu> wrote:
I looked around the web for a while and found a few superficial
descriptions of SNOBOL patterns....

Can you give a few examples?

Another nice feature of the SNOBOL programming language
is that the string matching a subpattern can be saved in
a variable. IIRC,
A B.X C

is the same as
A B C
but the string matching the subpattern B is saved in X.

I've often wanted to use this feature when sed'ing, e.g.
sed "sqhas [0-9]* wivesqwill have N happy widowsq"
where "N" is the matching [0-9]* remembered.

I've often wanted to use this feature when sed'ing, e.g.
sed "sqhas [0-9]* wivesqwill have N happy widowsq"
where "N" is the matching [0-9]* remembered.

Ben Pfaff <blp at (no spam) cs.stanford.edu> writes:
I looked around the web for a while and found a few superficial
descriptions of SNOBOL patterns. I also found a few SNOBOL
reference manuals, but again their descriptions of patterns were
very brief and I found it difficult to figure out how they were
used and why exactly they were so powerful.

Can you give a few examples?

The main feature is that patterns are built from pattern primitives
using operators. Patterns are named so you can write:

James Dow Allen schrieb:

I've often wanted to use this feature when sed'ing, e.g.
   sed "sqhas [0-9]* wivesqwill have N happy widowsq"
where "N" is the matching [0-9]* remembered.

Use backreferences:

$ sed 'sqhas \([0-9]*\) wivesqwill have \1 happy widowsq'
has 9 wives
will have 9 happy widows
has 4 wives
will have 4 happy widows

        Christian