Subject: Re: yacc for Scheme?
From: (Rob Warnock)
Date: 1997/10/02
Newsgroups: comp.lang.scheme
Message-ID: <60v63f$>

Richard Silverman  <> wrote:
| Does anyone know of yacc/lex (flex/bison) type tools for Scheme? 

Do you *really* want to port existing ".y" files [warping the embedded C
code into Scheme?], or are you just looking for similar capabilities and

I don't know of "yacc/lex" clones per se for Lisp/Scheme, but on the other
hand small ad hoc parsers are usually fairly easy to write in Lisp or Scheme.
(In fact, some wags might say that you're not a "real" Lisp programmer until
you've written several application-specific languages and the parsers for
them [usually as Lisp macros].)

Personally, though I've used "yacc" on occasion, I've never bothered
with "lex". Writing an ad hoc "yylex()" in C always seemed easier.
When I began coding in Scheme, the translation into Scheme of a few
of those "yylex()" routines was an interesting(!) exercise, especially
since my brute-force straightforward transliterations always resulted
in particularly ugly-looking Scheme!  ;-}

I've since gotten better at it [let me know if you want to see an example
of a simple yylex()-equivalent in Scheme], but still wouldn't claim to
be using the anything close to the best Scheme "style" in my lexers...

Such low-level character-tweaking is one of the areas that *every* Lisp
or Scheme text I've seen so far tends to gloss over or simply ignore --
mainly because the existence of the Scheme/Lisp reader usually *allows*
you to ignore the topic, but also probably because discussing it to the
same extent as other topics would take up disproprtionate time/space in
the book. Still, it's been hard to find good examples to learn from...

On the other hand, if the token-level grammar you're try to parse is at all
straightforward [by which I mean is either LL(1) or can be coaxed into it
with a few pragmatic disambiguations], writing a top-down recursive-descent
parser in Scheme is practically trivial. And if you're familiar with the
trick[*] of mixing simple operator-precedence parsing with recursive-descent
parsing, why, it can even be fairly efficient!


[*] Which I learned from the internals of the BLISS-10 and BLISS-11
compilers. See "The Design of an Optimizing Compiler", Wulf, et al.
You mix the two styles by using operator-precedence for expressions
and recursive-descent for control structures. The "trick" is simply
that all of the "statement keywords" are treated as "operators" of
very high priority. (And also that auxiliary keywords like "then"
and "else" are not treated as operators at all, but as "stoppers"
like the semicolon in C or right brackets, forcing a end to the
current sub-expression.)

Rob Warnock, 7L-551
Silicon Graphics, Inc.		Phone: 650-933-1673 [New area code!]
2011 N. Shoreline Blvd.		FAX: 650-933-4392
Mountain View, CA  94043	PP-ASEL-IA