Subject: An interesting article on parser generation languages

From: omer mussaev <[email-masked]>
Date: Sat, 29 Jan 2005 00:36:04 -0800 (PST)

It seems that area of parsing algorithms was not dead
in last 15 years, just dormant. 

An article 
http://www.acm.org/crossroads/xrds7-5/bison.html
explains why there's a place for new parsing
algorithms, and introduces two of these.

In addition, horrors of maintaining Yacc grammar files
are depicted in funny statecharts. 

I loved the article much, and recommend it heartly.

=====
--
o.m.

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com

---

From: "Elad Efrat" <[email-masked]>
Date: Sat, 29 Jan 2005 12:41:15 +0200

hello omer and list

[before anything, yacc *is* weak and probably
the main reason why we don't have a worthy C++
parser. if you're really interested in parsers and
compilers, take a look at http://www.ten15.org,
especially TDF.]

i've been writing parsers for several years now, both
for very 'busy' configuration files, small languages,
and even a 'subset' of C to create a smaller language
when i practiced sparc64 code generation. i'd like to
comment on this article and i hope you take what i
say seriously because this chaoticly-titled article is
not more than your usual end-of-the-world last-
newspaper-page prophecy...

the author of the article makes no distinction between
parsing of human-generated and computer-generated
data. you'll agree with me that writing 'parsers' for
network protocols -- often a cast of a structure on
packet payload (or similar, you get the drift) -- is
much easier than attempting to parse fully loaded
expressions that languages like C, C++, or Perl
offer. this is both shown very early in the article,
and in "Beyond Yacc", where he says "I've used
a similar idea to decompile Python byte-codes
back into source code. I wouldn't have even
attempted it with Yacc."

..of course not. that's NOT what yacc was meant
to do, nor what you should use it for. byte-code
'languages' are very different than human-readable
languages; they require different parsing, they do
not have a clear structure, and they can not be
tokenized. in other words, your yylex() becomes
getchar(). :)

next, the author of the article shows an example
for a grammar that is supposed to work, but
generates a shift/reduce error. unfortunately, if
figure 3 wasn't flawed, i would take it more
seriously.. can you spot why it's flawed or do
i have to point it out aswell? yacc forces you
to write logical parsers.

"To help answer this question, let's imagine a
tool that places no restrictions on the grammar
we give it. What things can be done with such
a tool?"

horrifying things. i can promise you that if you
convince the gcc project to move to such a
grammar, you open a pandora box of people
who'll finally implement what ken thompson
was talking about in another acm article...
http://www.acm.org/classics/sep95/. (do i
need to explain why?)

and what do we get as our "next parsing tool"?
we have ACCENT, which is *exactly* like
yacc -- except that it allows you to 'easily' select
the way an ambiguity is handled. i never seen
this become a problem in yacc grammars.

we also have SPARK; which is 100% python.
need i say more?

and finally we have ASF+SDF. i suggest everyone
to go there and see what it is for yourselves. :)

all in all, this is, to me, just another article of a Ph.D
student attempting to come out with chaotic titles
just to get his degree, similar to the java session-id
lecture some of us heard in TAUSEC of this month.

as far as i can see, yacc and bison are not becoming
extinct. for the past 30 years we've all used the
yacc grammars that specify so simply the way our
code is structured. pointing out the problems is one
thing, but you're not taken into account unless you
also provide solutions... and from the article, the
solutions the author presents are far from being
used in reality.

i'd like to, again, point everyone to TDF, if you're
looking for *active* development of a compiler
and parser for ambigious languages in the 21st
century; one that is NOT an attempt for a Ph.D
of some clueless kid. :)

> Yahoo! Groups Links

---

From: guy keren <[email-masked]>
Date: Sat, 29 Jan 2005 20:02:27 +0200 (IST)

now, can you send this post again, and this time, without the patronizing
accent? (please take this request seriously).

thanks,

--guy

On Sat, 29 Jan 2005, Elad Efrat wrote:

> comment on this article and i hope you take whati
> > Tired of spam?Yahoo! Mail has the best spam protection around
> > http://mail.yahoo.com
> >
> >
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
> >
> >
> >
> >
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>

-- 
guy

"For world domination - press 1,
 or dial 0, and please hold, for the creator." -- nob o. dy

---

From: Arik Baratz <[email-masked]>
Date: Wed, 2 Feb 2005 00:26:50 +0200

> accent? (please take this request seriously).

Oh oh, yes, and with links to all the parser-generators you are
mentioning, to save us google-time.

-- Arik