Hi all,
I've read in several places (and it appears often in this group) that
Lisp is good for writing compilers/interpreters. I'm now thinking of
undertaking a project to prove that (at least to myself).
I want to write a C compiler, in Lisp. Another C compiler, you might
ask ? Yes, I want to compile C to Parrot - the new VM for dynamic
languages (developed for Perl6, but will also run Python, Scheme, Ruby,
TCL and others). I think that a good C compiler to Parrot will be
useful to people, it will allow to easily link old C code with other
languages on that platform.
Functional languages already have a touch in this area, the prototypal
Perl6 compiler is being now built in Haskell.
So, I gather, if Haskell can compile Perl, Lisp can surely compile C
:-)
For now, I'm thinking about the front-end of this compiler. I know that
compiling Lisp-like languages (like Norvig did in PAIP) is easy in
Lisp, but C's syntax isn't Lisp like.
Lex & Yacc grammars exist for C, so one route of action (A) would be:
1) Use a C program (compiled from Lex&Yacc) to tokenize/parse C and
translate it to a syntax tree in a format that Lisp would understand.
2) Write a Lisp program to read the tree, and do the rest of the
compiling.
This looks like the simplest way, because as I said, Lex & Yacc
grammars for C exist. It's not pure Lisp, however, and that's pity...
Another route of action (B) would be to replace (1) with some
Lisp-based compiler-generator. Is there a program to read in Lex & Yacc
and to generate Lisp code from that ? I didn't find any, which is weird
because I *did* hear that Lisp is good for compilers. (I wonder how
hard it is, maybe it's an idea for another project...)
Finally, I can try to directly parse C with Lisp code, without using a
compiler-generator.
I hope to undertake this project as an effort to finally fortify my
Lisp knowledge, a language I *love* but haven't written anything
serious in (for now mostly reading books and working through them, PAIP
being the most challenging). I'm sure Lisp can do it, I'm just not sure
I can do it in Lisp. Moreover, this can show that Lisp is good and
useful to the huge future community of Parrot (Perl, Python, Ruby...)
This remains to be seen.
So, any comments/thoughts are welcome.
Kind regards,
Eli
Eli Bendersky wrote:
> Another route of action (B) would be to replace (1) with some
> Lisp-based compiler-generator. Is there a program to read in Lex & Yacc
> and to generate Lisp code from that ? I didn't find any, which is weird
> because I *did* hear that Lisp is good for compilers. (I wonder how
> hard it is, maybe it's an idea for another project...)
The problem with yacc-parsers is that they include C code, and
part of the parser usually consists of work-arounds around C or
yacc (at least the ones I've written). A yacc-parser isn't half
as elegant as, say, a parser in SML-yacc. I haven't tried the
Lisp ones, yet.
So I think it would be really hard to auto-translate a yacc
program into a Lisp program. Your best bet is to hand-translate
the yacc grammar into CL-yacc (or what other tools there are).
That's still *far* easier than hard-coding the parser and saves
lots of errors.
> Finally, I can try to directly parse C with Lisp code, without using a
> compiler-generator.
Don't (unless you want to spend weeks just debugging your
parser...)! I think C would be far too complex (and weird)
grammar-wise to allow nice hand-written parsers.
smitty_one_each wrote:
> What about the Semantic Bovinator? Is Emacs Lisp inappropriate
> somehow? It's already doing a plethora of languages.
Thanks for this tip - I never heard of the Bovinator before.
I looked at it and it doesn't seem to fit.
First, it's not a full parser - the author explicitly states that it's
good for source analysis, not full-expression parsing for compilation.
Second, it's rather heavy - lots of .el files. I want something
lighter, like CL-YACC (started looking at it too, looks good so far).
> Second, it's rather heavy - lots of .el files. I want something
> lighter, like CL-YACC (started looking at it too, looks good so far).
Well, I wrote CL-Yacc exactly for that reason -- I needed to parse C.
I've ripped out the lexer, parser and pretty-printer from my current
development sources and put them on
http://www.pps.jussieu.fr/~jch/software/files/cpc-parser-20050411.tar.gz
You are welcome to use this code in any way you see fit. I would
appreciate it, however, if you could make sure to credit me as the
original author in the documentation of any software that uses these
sources.
And Steven H. is right -- parsing C is a pain.
This is most definitely work in progress; while a variant of this code
has successfully parsed a few thousands lines of C, it is known to be
incomplete and buggy. Of course, I'm interested in any fixes you may
want to send me.
Enjoy,
Juliusz Chroboczek
Ulrich Hobelmann wrote:
> The problem with yacc-parsers is that they include C code, and part of
> the parser usually consists of work-arounds around C or yacc (at least
> the ones I've written). A yacc-parser isn't half as elegant as, say, a
> parser in SML-yacc. I haven't tried the Lisp ones, yet.
There is already in Allegro CL a full YACC workalike. (It is used by
the regexp package to parse PERL's boiled-frog string syntax into a
reasonable parse tree that can be processed by the FSM generator.)
Unfortunately, it isn't documented so it isn't yet really usable for
other purposes. The documentation and some tutorial material is on
my to-do list.
However, it is widely acknowledged that parsing C is a rather ugly
problem, more work than it is worth. The _interesting_ reasons for
using Lisp to write a C compiler concern code analysis and possible
optimization analysis. I would suggest you duct tape some existing
parser onto your front end and see how Lisp works for the interesting
stuff. If your compiler works really well and you want to make it
independently portable, that would be the time to deal with the
unpleasant task of parsing.
On 2005-04-09 11:28:51 +0200, "Eli Bendersky" <······@gmail.com> said:
> Is there a program to read in Lex & Yacc
> and to generate Lisp code from that ?
Maybe this interests you
http://www.pps.jussieu.fr/~jch/software/cl-yacc/
From: Björn Lindberg
Subject: Re: writing a C compiler in Common Lisp
Date:
Message-ID: <425a3a0c$1@news.cadence.com>
Eli Bendersky wrote:
> For now, I'm thinking about the front-end of this compiler. I know that
> compiling Lisp-like languages (like Norvig did in PAIP) is easy in
> Lisp, but C's syntax isn't Lisp like.
> Lex & Yacc grammars exist for C, so one route of action (A) would be:
>
> 1) Use a C program (compiled from Lex&Yacc) to tokenize/parse C and
> translate it to a syntax tree in a format that Lisp would understand.
>
> 2) Write a Lisp program to read the tree, and do the rest of the
> compiling.
>
> This looks like the simplest way, because as I said, Lex & Yacc
> grammars for C exist. It's not pure Lisp, however, and that's pity...
>
> Another route of action (B) would be to replace (1) with some
> Lisp-based compiler-generator. Is there a program to read in Lex & Yacc
> and to generate Lisp code from that ? I didn't find any, which is weird
> because I *did* hear that Lisp is good for compilers. (I wonder how
> hard it is, maybe it's an idea for another project...)
>
> Finally, I can try to directly parse C with Lisp code, without using a
> compiler-generator.
Two more ideas:
C) Use Zebu (http://www.cliki.net/Zebu). Zebu is a CL parser generator
for CL. You could find BNF or yacc code for C and translate it to
Zebu.
D) There are sources available for a C compiler written in Zetalisp
(http://www.cliki.net/Zeta-C). Cliki says it is not trivially
portable, but perhaps ripping out the parser and porting it to CL is
not as difficult. I have no idea though, since I've only briefly
looked at the sources.
I agree with Steven that the parsing is probably the least interesting
part of your project, so just find something that works and move on to
the interesting things. You can always replace it later.
Bj�rn
Some more ideas:
a) Browse through "A Retargetable C Compiler: Design and Implemenation" by
Fraser and Hanson which describes the lcc compiler. You can get the full
source (C) and there's a newsgroup comp.compilers.lcc. As far as I know,
they simply ad-hoc'ed the grammar and got great performance. Fraser and
Hanson (and Davidson) invented some blazing compiler-compiler technologies,
including the ideas used by GCC. Lcc uses a newer technology called lburg.
I've been thinking that on some lazy weekend, I would simply sight-read the
C code for lcc and translate it to Lisp, so that I could have an lburg to
play with... (I've learned a lot by doing things that way - when you
sight-read and transliterate existing code, you know that you're starting
with something that already works. You invariably insert bugs as you do
this, but the extent of the bugs is never too daunting (since you know the
orignal worked). The process of debugging your own bugs makes you
intimately familiar with the workings of the code. By the time you finish,
you're an expert in the design of the system. And the whole process takes
much, much less time than inventing all of the code from scratch).
b) Lispworks comes with a yacc-like parser generator.
c) When I write compilers (about once every year), I most often use the
simplest compiler-compiler language that I know of - S/SL (syntax /
semantic language). It has 13 operators and does better at managing the
hard stuff - like semantics and code generation - than yacc and friends. I
cobbled up an S/SL-in-lisp in about a weekend - it converts S/SL (+ lisp)
to lisp (mainly macros - one for each operator). As it parses, it
auto-magically generates a tree. It also contains experimental
functionality for changing parsers on-the-fly and producing a unity
transform of the source (Why? Because a lot of things I do involve
source-to-source translation. Too complicated for Perl - needs parser
technology. But, (almost) no existing parser technology preserves comments
and leaves the formatting alone (I think Antlr might have some painful
extentensions for this feature)). My version of S/SL is also
self-compiling, so S/SL-in-lisp is written in and maintained in itself. If
you're interested, and don't expect too much documenation, etc, ask me for
a copy.
d) Look at TXL (www.txl.com). It is a (purely) functional language
originally built for source-to-source transformation and language-design
experimentation. It uses a backtracking parser. Look at how clean the
syntax for C is, when you're allowed to backtrack. Admire. With some
thought, you too could do this using only lisp.
Paul Tarvydas
Paul Tarvydas wrote:
> c) When I write compilers (about once every year), I most often use the
> simplest compiler-compiler language that I know of - S/SL (syntax /
> semantic language).
Any links on S/SL? Google finds a paper on the ACM website, but I
don't do business with the devil.
Is there any open spec or documentation/tutorials?
Ulrich Hobelmann wrote:
> Paul Tarvydas wrote:
>
>> c) When I write compilers (about once every year), I most often use the
>> simplest compiler-compiler language that I know of - S/SL (syntax /
>> semantic language).
>
>
> Any links on S/SL? Google finds a paper on the ACM website, but I
> don't do business with the devil.
>
> Is there any open spec or documentation/tutorials?
May I ask, why is the ACM the devil?
--
Barry Jones
Barry Jones wrote:
> May I ask, why is the ACM the devil?
Well, I'm used to freely reading research from professors
worldwide (from their websites), and after all most of them are
(at least partly) tax-funded, too. Science is called
"collaboration" for a reason. The ACM is on obsolete middleman.
I just think an organization that wants to have entrance fees to
show you papers *they* didn't write, is bad. Professors write
papers, not the ACM, and I see no reason why they shouldn't
publish their stuff on the web (I guess these articles don't
appear anywhere else for free, because the ACM also holds all
right, even though they didn't write the articles). I for one
won't pay $5+ for articles, and most articles aren't that useful
to me usually, anyway. Judging from the ACM's abstracts, I don't
miss out on *that* much.
Some other reasons, partly overlapping with mine, are IIRC on Kent
Pitman's website.
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
Ulrich Hobelmann <···········@web.de> writes:
> I just think an organization that wants to have entrance fees to show
> you papers *they* didn't write, is bad. Professors write papers, not
> the ACM, and I see no reason why they shouldn't publish their stuff on
> the web (I guess these articles don't appear anywhere else for free,
> because the ACM also holds all right, even though they didn't write
> the articles).
You are clearly ignorant of the ACM's publication policies. It's
unclear to me why you would want to speculate on this matter when all
of the information you need to make an informed decision is on-line.
Carl Shapiro wrote:
> Ulrich Hobelmann <···········@web.de> writes:
>
> > I just think an organization that wants to have entrance fees to
show
> > you papers *they* didn't write, is bad. Professors write papers,
not
> > the ACM, and I see no reason why they shouldn't publish their stuff
on
> > the web (I guess these articles don't appear anywhere else for
free,
> > because the ACM also holds all right, even though they didn't write
> > the articles).
>
> You are clearly ignorant of the ACM's publication policies. It's
> unclear to me why you would want to speculate on this matter when all
> of the information you need to make an informed decision is on-line.
Perhaps, but you're not addressing the real issue here. Aside from his
value judgements, what does he have wrong about the ACM's modus
operandi?
I recently became perplexed while searching for a number of ACM
articles on the WWW. Apparently to read those papers one must:
- pay a (rather hefty) fee to ACM for each paper,
- become a paying member of the ACM, or
- have access to computers in a university library(which subscribes to
ACM).
In all cases, the authors had not posted those articles on their own
websites, although non-ACM papers were posted.
On 12 Apr 2005 16:17:31 -0700, <··················@yahoo.com> wrote:
> Carl Shapiro wrote:
>> Ulrich Hobelmann <···········@web.de> writes:
>>
>> > I just think an organization that wants to have entrance fees to
> show
>> > you papers *they* didn't write, is bad. Professors write papers,
> not
>> > the ACM, and I see no reason why they shouldn't publish their stuff
> on
>> > the web (I guess these articles don't appear anywhere else for
> free,
>> > because the ACM also holds all right, even though they didn't write
>> > the articles).
>>
>> You are clearly ignorant of the ACM's publication policies. It's
>> unclear to me why you would want to speculate on this matter when all
>> of the information you need to make an informed decision is on-line.
>
> Perhaps, but you're not addressing the real issue here. Aside from his
> value judgements, what does he have wrong about the ACM's modus
> operandi?
>
> I recently became perplexed while searching for a number of ACM
> articles on the WWW. Apparently to read those papers one must:
> - pay a (rather hefty) fee to ACM for each paper,
> - become a paying member of the ACM, or
> - have access to computers in a university library(which subscribes to
> ACM).
>
> In all cases, the authors had not posted those articles on their own
> websites, although non-ACM papers were posted.
That's been my experience for years now. To the naysayers, 'put up or
shut up'. Mere repetition that "you have it wrong" is insufficient to
convince the majority of the non-ACM world. Perhaps your claim is
that the ACM has a terribly designed website that misleads the average
visitor into unnecessarily paying a fee. Pray tell (in detail this
time) where did we go wrong??
--
Everyman has three hearts;
one to show the world, one to show friends, and one only he knows.
GP lisper wrote:
> That's been my experience for years now. To the naysayers, 'put up or
> shut up'.
Sure, I just ignore the ACM pretty much. Well, and I don't see
why some researchers publish their stuff there instead of, say,
LNCS, whose papers usually appear on the "free" web, too. Doesn't
exactly make me admire them (or even read).
I simply stated my opinion because I was asked ;)
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
Ulrich Hobelmann wrote:
> GP lisper wrote:
>
>> That's been my experience for years now. To the naysayers, 'put up or
>> shut up'.
>
> Sure, I just ignore the ACM pretty much. Well, and I don't see why some
> researchers publish their stuff there instead of, say, LNCS, whose
> papers usually appear on the "free" web, too. Doesn't exactly make me
> admire them (or even read).
I like the ACM digital library because it offers a very good interface.
I think it's acceptable to pay for it. I am not a firm believer that
everything should be available for free, there are good arguments
against this notion.
Having said that, in the academic world it's usually the authors'
responsibility to decide whether their papers should be available for
free additionally to the download options of publishers. In the case of
LNCS/Springer, there's no difference there. They also charge you for papers.
Whenever you find a paper that you find interesting, you have the
following additional options:
- check out citeseer
- check out Google scholar
- ask the authors per email
Especially the last option works pretty well. Authors are usually proud
of their work and happy that someone is interested. I usually also
suggest to authors that they should make their papers available for
download at their websites, which several have responded to in a very
positive way.
The usual wisdom applies: You can either complain about the state of the
world, or you can start to do something about it.
Pascal
--
2nd European Lisp and Scheme Workshop
July 26 - Glasgow, Scotland - co-located with ECOOP 2005
http://lisp-ecoop05.bknr.net/
Pascal Costanza wrote:
> Having said that, in the academic world it's usually the authors'
> responsibility to decide whether their papers should be available for
> free additionally to the download options of publishers. In the case of
> LNCS/Springer, there's no difference there. They also charge you for
> papers.
Seems to be the case. I remember a couple years back I often
followed links to the LNCS website and I could swear it said that
after two years of publication the papers are available from the
website. Anyway, I downloaded a couple ones back then. Maybe it
was just a teaser. Recently when I visited their website there
was no trace of anything free.
Actually a (book-format) LNCS subscription was the best thing my
first university had to offer. I kind of miss that, since those
had *really* interesting papers in it. (most ACM abstracts don't
really tease me enough)
You're right that the authors should choose what to publish. I
just think in the case of tax-supported universities their
contributions to science should be free.
> Whenever you find a paper that you find interesting, you have the
> following additional options:
>
> - check out citeseer
No. 1 source since the beginning of time :)
> - check out Google scholar
just the same in inferior the one time I tried it.
> The usual wisdom applies: You can either complain about the state of the
> world, or you can start to do something about it.
True. I just read what I can find access to and otherwise I
pretty much don't care. I have too little time anyways and don't
work as a researcher, so I guess it doesn't matter.
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
Ulrich Hobelmann wrote:
> Pascal Costanza wrote:
>
>> Having said that, in the academic world it's usually the authors'
>> responsibility to decide whether their papers should be available for
>> free additionally to the download options of publishers. In the case
>> of LNCS/Springer, there's no difference there. They also charge you
>> for papers.
>
> Seems to be the case. I remember a couple years back I often followed
> links to the LNCS website and I could swear it said that after two years
> of publication the papers are available from the website. Anyway, I
> downloaded a couple ones back then. Maybe it was just a teaser.
> Recently when I visited their website there was no trace of anything free.
Their policy is that authors are allowed to publish their work one year
after they have appeared in their print publications. (These issues are
somewhat tricky because such publishers ask you to transfer your
copyrights to them. In Germany, for example, it's not possible to do that.)
> I just read what I can find access to and otherwise I pretty much
> don't care. I have too little time anyways and don't work as a
> researcher, so I guess it doesn't matter.
That's a pity because of lots of interesting and important stuff appears
to be forgotten just because it's not online. I hope this will gradually
change somehow.
Pascal
--
2nd European Lisp and Scheme Workshop
July 26 - Glasgow, Scotland - co-located with ECOOP 2005
http://lisp-ecoop05.bknr.net/
Pascal Costanza wrote:
> Their policy is that authors are allowed to publish their work one year
> after they have appeared in their print publications. (These issues are
> somewhat tricky because such publishers ask you to transfer your
> copyrights to them. In Germany, for example, it's not possible to do that.)
Maybe they all just forget after a year :)
Anyway, that seems like a reasonably fair policy.
>> I just read what I can find access to and otherwise I pretty much
>> don't care. I have too little time anyways and don't work as a
>> researcher, so I guess it doesn't matter.
>
>
> That's a pity because of lots of interesting and important stuff appears
> to be forgotten just because it's not online. I hope this will gradually
> change somehow.
The more important it is to put old stuff online. The Dijkstra
archives for instance are really nice.
It's just much more efficient to google/citesee instead of having
to browse through microfiche catalogs ;)
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
GP lisper <········@CloudDancer.com> writes:
> That's been my experience for years now. To the naysayers, 'put up or
> shut up'. Mere repetition that "you have it wrong" is insufficient to
> convince the majority of the non-ACM world. Perhaps your claim is
> that the ACM has a terribly designed website that misleads the average
> visitor into unnecessarily paying a fee. Pray tell (in detail this
> time) where did we go wrong??
Are you suggesting that it's possible to fetch papers from acm web
site freely? Because I too have learned to ignore ACM links...
--
__Pascal Bourguignon__ http://www.informatimago.com/
The mighty hunter
Returns with gifts of plump birds,
Your foot just squashed one.
Carl Shapiro wrote:
> Ulrich Hobelmann <···········@web.de> writes:
>
>
>>I just think an organization that wants to have entrance fees to show
>>you papers *they* didn't write, is bad. Professors write papers, not
>>the ACM, and I see no reason why they shouldn't publish their stuff on
>>the web (I guess these articles don't appear anywhere else for free,
>>because the ACM also holds all right, even though they didn't write
>>the articles).
>
>
> You are clearly ignorant of the ACM's publication policies. It's
> unclear to me why you would want to speculate on this matter when all
> of the information you need to make an informed decision is on-line.
I don't care honestly. It's about free (beer) research. It's
about open collaboration. It's about the fact that probably most
leading CS people worldwide publish their research in an open way.
I see no reason to pay an organization that does nothing lock
papers up on their servers and make me pay for them.
Anyway, that's what I see when I see an ACM link. I don't care
about their publication policies, I just refuse to pay $5+ for an
article that doesn't really change my life anyway.
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
Ulrich Hobelmann <···········@web.de> writes:
> I don't care honestly. It's about free (beer) research. It's about
> open collaboration. It's about the fact that probably most leading CS
> people worldwide publish their research in an open way. I see no
> reason to pay an organization that does nothing lock papers up on
> their servers and make me pay for them.
Obviously you do care enough to spread misinformation.
Carl Shapiro wrote:
> Ulrich Hobelmann <···········@web.de> writes:
>
>
>>I don't care honestly. It's about free (beer) research. It's about
>>open collaboration. It's about the fact that probably most leading CS
>>people worldwide publish their research in an open way. I see no
>>reason to pay an organization that does nothing lock papers up on
>>their servers and make me pay for them.
>
>
> Obviously you do care enough to spread misinformation.
I'm sorry, but that's just my opinion that I stated. I don't like
the ACM, so what?
If I have any wrong perceptions of how to obtain ACM papers, or of
the publication rules of the ACM, then please enlighten me.
I highly second the post of Xeo at Thermopylae btw.
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
Ulrich Hobelmann <···········@web.de> writes:
> Carl Shapiro wrote:
> > Ulrich Hobelmann <···········@web.de> writes:
> >
> >>I just think an organization that wants to have entrance fees to show
> >>you papers *they* didn't write, is bad. Professors write papers, not
> >>the ACM, and I see no reason why they shouldn't publish their stuff on
> >>the web (I guess these articles don't appear anywhere else for free,
> >>because the ACM also holds all right, even though they didn't write
> >> the articles).
> > You are clearly ignorant of the ACM's publication
> > policies. It's
> > unclear to me why you would want to speculate on this matter when all
> > of the information you need to make an informed decision is on-line.
>
> I don't care honestly.
Making misleading claims and then not caring is not a good combination.
ACM allows authors to link their own papers on their homepages. So
your argument disappears.
Matthias wrote:
>>I don't care honestly.
>
>
> Making misleading claims and then not caring is not a good combination.
I don't think I claimed anything. Sorry if this came across
wrongly. I only stated my perception. Almost no papers on the
web => I *guessed* there must be some policy.
> ACM allows authors to link their own papers on their homepages. So
> your argument disappears.
>
Ok, so they do. I just stated that almost every single ACM paper
I tried to find, was *not* available on the web. (maybe one or two
I encountered, were)
If it's allowed, the authors don't care. Maybe they think that
everybody (relevant) has (or should have) a subscription. I don't
know. I don't care.
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
I found an old version of S/SL here:
http://burks.brighton.ac.uk/burks/foldoc/30/114.htm
It appears to contain a troff'ed version of one of the original tech reports
(TR118). Anyone remember how to use troff? :-)
The tar file appears to contain S/SL written in itself (file.ssl). You
might even get the hang of it by browsing the syntax and comments.
Ulrich Hobelmann wrote:
> Any links on S/SL? Google finds a paper on the ACM website, but I
> don't do business with the devil.
If you've got access to a decent comp sci library, you could find the
hardcopy of that TOPLAS issue and photocopy it.
On Mon, 11 Apr 2005 17:10:49 -0400, Paul Tarvydas wrote:
> Some more ideas:
> d) Look at TXL (www.txl.com). It is a (purely) functional language
> originally built for source-to-source transformation and language-design
> experimentation. It uses a backtracking parser. Look at how clean the
> syntax for C is, when you're allowed to backtrack. Admire. With some
> thought, you too could do this using only lisp.
The site appears to be http://www.txl.ca the .com does not respond to me
and the way back machine shows nothing of interest.
Paul Tarvydas wrote:
> c) When I write compilers (about once every year), I most often use the
> simplest compiler-compiler language that I know of - S/SL (syntax /
> semantic language). It has 13 operators and does better at managing the
> hard stuff - like semantics and code generation - than yacc and friends. I
> cobbled up an S/SL-in-lisp in about a weekend - it converts S/SL (+ lisp)
> to lisp (mainly macros - one for each operator). As it parses, it
> auto-magically generates a tree. It also contains experimental
> functionality for changing parsers on-the-fly and producing a unity
> transform of the source (Why? Because a lot of things I do involve
> source-to-source translation. Too complicated for Perl - needs parser
> technology. But, (almost) no existing parser technology preserves comments
> and leaves the formatting alone (I think Antlr might have some painful
> extentensions for this feature)). My version of S/SL is also
> self-compiling, so S/SL-in-lisp is written in and maintained in itself. If
> you're interested, and don't expect too much documenation, etc, ask me for
> a copy.
Thanks a lot for the pointer! The S/SL introduction in the tar.gz
available from the Foldoc link you posted is quite interesting.
Since the language seems to mix so many programming/developing
ideas (as mentioned at the of the paper), it seems like a good
tool for a wide range of programming problems. The cycle ({})
construct is much nicer than having to specify an extra rule in
yacc dialects (probably equivalent to having loops in a language
compared to having to declare a new tail-recursive function for
every loop).
I especially liked the mention of the Euclid compiler consisting
of five consecutive stages of S/SL :D
I'd very much like to see your S/SL in Lisp, maybe also some
examples (if you are willing to share them). What I don't really
get is how an S/SL *stream* of tokens (compared to a yacc syntax
*tree*) is processed by the rest of the program. Does one insert
begin and end markers (e.g. to create a nested lisp etc. from the
linear stream)? It almost seems that S/SL output needs another
parser to process it ;)
--
No man is good enough to govern another man without that other's
consent. -- Abraham Lincoln
Other papers that would interest you, if S/SL compiler-writing interests
you:
A complete compiler written in S/Sl:
Rosselet J.A. PT: A Pascal subset. Rep. CSRG-119, Computer Science
Research Group, Univ. of Toronto, Canada, Sept. 1980.
A simple, brilliant way to describe and track location of data / variables /
constants inside a compiler, along with the algorithms to manipulate them
(e.g. derefencing, etc):
Data Descriptors: A Compile-Time Model of Data and Addressing, ACM
Transactions on Programming Languages and Systems, Vol. 9, No. 3, July
1987, pp. 387-389 (R.C. Holt):
A simple, understandable, portable code generator technology / language. So
simple, you'll wonder why you didn't think of it yourself:
Code Generation using an Orthogonal Model, Software Practice and Experience,
Vol 20 (3), pp 301-320, March 1990 (J.R. Cordy and R.C. Holt).
Ulrich Hobelmann wrote:
When it comes to compiler literature, I have two favourite camps that I'm a
fan of - Holt, Cordy, et al, and Fraser, Davidson, Hanson, et al.
Both "groups" seem to put a high value on simplicity. They work very hard
to find the simplest solutions (which is, in fact, a very hard thing to
do!).
> Since the language seems to mix so many programming/developing
> ideas (as mentioned at the of the paper), it seems like a good
> tool for a wide range of programming problems.
If you browse for some of my previous postings here (something to the effect
'architecting by the seat of your pants'), you'll see that I advocate this
very idea.
The strength of S/SL is that it doesn't have any variables. (!). You are
forced to think and describe "architecture" (high-level design) only. For
complicated problems (e.g. compilers) it is a wonderful discipline to learn
and to use.
> The cycle ({})
> construct is much nicer than having to specify an extra rule in
> yacc dialects (probably equivalent to having loops in a language
> compared to having to declare a new tail-recursive function for
> every loop).
I agree. Some people don't agree. Cycle is a lower-level concept. Yacc
rules are more auto-magic. S/SL cannot warn you, like YACC can, if you've
written an ambiguous grammar (e.g. within the contraints of LALR). S/SL,
though, can parse a wider range of languages (since it is lower-level).
The easiest part of building a compiler is the scanning and parsing. I'd
rather use tools that make the hard parts more manageable.
> I especially liked the mention of the Euclid compiler consisting
> of five consecutive stages of S/SL :D
> What I don't really
> get is how an S/SL *stream* of tokens (compared to a yacc syntax
> *tree*) is processed by the rest of the program. Does one insert
> begin and end markers (e.g. to create a nested lisp etc. from the
> linear stream)? It almost seems that S/SL output needs another
> parser to process it ;)
You're wrong :-). You do get it :-).
A typical compiler built in this paradigm consists of a scanner, a parser, a
semantic analysis pass, an allocator pass and a coder.
The latter 4 passes each parse the grammar of the language (give or take -
the parser throws away any noise, so that the grammar in the subsequent
passes is noiseless and slightly less human-oriented).
The result is a compiler which is very well organized and is easy to
understand, to implement and to maintain.
It has a pattern-matching-functional-language "feel" - 'when you see this
construct, do the following'.
Is it less efficient than building a tree, then operating on the tree? Not
noticably (which was a surprise to me, originally). You still have to
expend energy to walk a tree. With this method, you expend (more?) energy
re-parsing, but you can spend less memory, since the whole tree doesn't
need to be kept in memory. On top of this, you find that you don't need to
keep a global symbol table lying around - the semantic pass creates a
symbol table, resolves all symbols to unique id's and data-descriptors,
then tosses the symbol table away. You lose some, but you win some.
Couldn't you fold all of the passes into one (like YACC promotes)? Yes, but
then the result becomes less and less "organized" and more ad-hoc -> more
bugs, more future confusion because the "architecture" gets schmooed into a
tightly-wound hair-ball.
The secret of useful reuse is to make the architecture (design) blazingly
obvious.
> I'd very much like to see your S/SL in Lisp, maybe also some
> examples (if you are willing to share them).
Sure. Please send me an email to prod me, and I'll email it to you.
pt
"Eli Bendersky" <······@gmail.com> wrote :
>
> 1) Use a C program (compiled from Lex&Yacc) to tokenize/parse C and
> translate it to a syntax tree in a format that Lisp would understand.
I would try Juliusz Chroboczek's parser or maybe gcc-xml:
http://www.gccxml.org/HTML/Index.html
Then you can either read the xml with a Lisp xml parser or better tweak
gcc-xml to output an sexpr directly.
Marc