Re: Designing Lisp from scratch

On Fri, Mar 23, 2007 at 03:38:09AM -0400, [email protected] wrote:
>  
> I fully agree with you that jamming the lexing, parsing, and other code all  
> into one large mess of a file is less desirable than separating them the way  
> it's done with Lex / Yacc.

Well, I never really stated that that's the way I'd prefer to do it. In 
fact, I've never really understood the rationale of separating the lexer 
from the parser.

Of all the parser generators I've worked with, the one I found nicest 
was one I wrote in Scheme, which was a pretty much literal port of the 
parser combinators described by Hutton and Meijer in "Monadic Parsing in 
Haskell".

> 2.  Grammar for languages like Scheme might use symbols that are  invalid in 
> C, thus causing it not to work with Yacc (conventional C  implementations of 
> it).  I'm not 100 percent sure of this.

And you're wrong. It doesn't matter to lex what your tokens look like. 
It certainly doesn't return C symbols (symbols don't even exist as 
values in C). Yacc cares even less about what tokens look like (it only 
cares about magic numbers), and as soon as you're past yacc, tokens 
might as well not exist.

>  However, in an earlier message I asked if anyone could supply Lex / 
> Yacc code for Lisp, and I've also searched on my own, and still 
> haven't found any.

I'm sure such code is out there. I've written a Lisp parser in ANTLR, 
myself. ANTLR is pretty close to lex and yacc. If you want, I can send 
that code to you.

> In my search, I have found hints that people will 
> not, cannot, need not, or would simply prefer not to do a conventional 
> C-based Lex / Yacc implementation of Scheme or other Lisp.  I would be 
> interested in more of a definitive answer on whether it can be done or 
> if it is too hard to do, or whether creating a Lisp parser by hand is 
> too easy for one to bother with Lex / Yacc.

I guess the main reason you may have a hard time finding lex/yacc 
parsers for Lisp is that Lisp parsers are built into every Lisp system. 
Thus, if you want to parse Lisp code, you just use Lisp and say (read). 
So, as you say, it may be the "need not". I can also imagine Lisp 
programmers not liking C, so it could be the "will not". It could also 
be that Lisp syntax is too simple to bother with lex and yacc, and it 
could be the "cannot", if you take into account Common Lisp's read 
macros (which is your next point).

> 3.  If a language has a mutable or extendible syntax (or semantics),  then 
> you can forget about using Lex / Yacc .

Right.

> 4.  I've seen it said that grammars for some languages (like Perl)  simply 
> cannot be expressed effectively in BNF form.  Though I haven't  tackled Perl 
> yet, uCalc does not deal with BNF grammars.  I don't foresee  any obstacles to 
> reducing Perl-like syntax like I've done for other  languages.

Yacc is actually pretty powerful. I wouldn't bet on it being able to 
parse Perl or C, but I wouldn't be surprised if it could.

Regards,

Bob

-- 
Two atoms are talking to each other, and one says,
"I think I've just lost an electron!"
"Are you certain?" the other replies.
"Yes! I'm positive!"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFGA6J/fb9wcmD+WN4RAh27AJwLmcr4iZQJ8vytpxST5FuaQf2k5wCdGW+1
br1zYb4Fkwa6a2NS8uJl5XM=
=5FcK
-----END PGP SIGNATURE-----