Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #562 > unrolled thread

Good practical language and OS agnostic text?

Back to article view | Back to comp.compilers

Contents

  Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-17 21:28 +0000
    Re: Good practical language and OS agnostic text? Philip Herron <redbrain@gcc.gnu.org> - 2012-04-18 14:25 +0100
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-19 16:32 +0000
        Re: Good practical language and OS agnostic text? arnold@skeeve.com (Aharon Robbins) - 2012-04-20 03:58 +0000
          Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-22 10:10 +0000
        Re: Good practical language and OS agnostic text? "BartC" <bc@freeuk.com> - 2012-04-20 09:45 +0100
          Re: Good practical language and OS agnostic text? "Jonathan Thornburg" <jthorn@astro.indiana.edu> - 2012-04-21 15:04 +0000
    Re: Good practical language and OS agnostic text? BGB <cr88192@hotmail.com> - 2012-04-18 08:39 -0700
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-19 17:32 +0000
    Re: Good practical language and OS agnostic text? Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2012-04-18 18:24 +0200
      Re: Good practical language and OS agnostic text? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2012-04-19 13:53 +0200
        Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-21 03:07 +0000
        Re: Good practical language and OS agnostic text? "BartC" <bc@freeuk.com> - 2012-04-21 12:01 +0100
          Re: code quality, was Good practical language and OS agnostic text? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2012-04-22 12:41 +0200
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-19 11:31 +0000
        Re: Good practical language and OS agnostic text? "Jonathan Thornburg" <jthorn@astro.indiana.edu> - 2012-04-20 16:19 +0000
    Re: Good practical language and OS agnostic text? "Derek M. Jones" <derek@knosof.co.uk> - 2012-04-18 18:16 +0100
      Re: Good practical language and OS agnostic text? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-04-18 22:43 +0000
        Re: Good practical language and OS agnostic text? BGB <cr88192@hotmail.com> - 2012-04-19 00:05 -0700
        Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-19 11:31 +0000
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-19 16:32 +0000
    Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-18 19:30 +0000
      Re: Good practical language and OS agnostic text? "BartC" <bc@freeuk.com> - 2012-04-19 18:43 +0100
    Re: Good practical language and OS agnostic text? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-04-18 20:29 +0000
      Re: Good practical language and OS agnostic text? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2012-04-19 14:20 +0200
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-19 19:05 +0000
        Re: Good practical language and OS agnostic text? Uli Kusterer <ulimakesacompiler@googlemail.com> - 2012-04-21 11:30 +0200
    Re: Good practical language and OS agnostic text? Roberto Waltman <usenet@rwaltman.com> - 2012-04-18 22:00 -0400
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-19 11:31 +0000
        Re: Good practical language and OS agnostic text? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-04-20 07:02 +0000
          Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-22 11:10 +0000
            Re: Good practical language and OS agnostic text? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-04-22 23:56 +0000
          Re: PL/360, was Good practical language and OS agnostic text? ArarghMail204@Arargh.com - 2012-04-24 19:13 -0500
    Re: Good practical language and OS agnostic text? Bakul Shah <usenet@bitblocks.com> - 2012-04-18 21:15 -0700
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-20 16:06 +0000
    Re: Good practical language and OS agnostic text? torbenm@diku.dk (Torben Ægidius Mogensen) - 2012-04-19 14:58 +0200
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-20 16:06 +0000
    Re: Good practical language and OS agnostic text? "Joe Schmo" <askmeforit@myisp.com> - 2012-04-21 02:53 -0600
      Re: Writing parsers, was Good practical language and OS agnostic text? Uli Kusterer <ulimakesacompiler@googlemail.com> - 2012-04-22 16:18 +0200
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-23 19:12 +0000
    Re: Good practical language and OS agnostic text? Uli Kusterer <ulimakesacompiler@googlemail.com> - 2012-04-21 11:22 +0200
      Re: Good practical language and OS agnostic text? BGB <cr88192@hotmail.com> - 2012-04-21 18:58 -0700
        Re: writing interpreters, was Good practical language and OS agnostic text? Uli Kusterer <ulimakesacompiler@googlemail.com> - 2012-04-22 12:53 +0200
          Re: writing interpreters, was Good practical language and OS agnostic text? BGB <cr88192@hotmail.com> - 2012-04-22 12:29 -0700
        Re: generating bytecode, was Good practical language and OS agnostic text? Uli Kusterer <ulimakesacompiler@googlemail.com> - 2012-04-22 13:12 +0200
        Re: Recursive descent parsing and optimization, was Good practical language and OS agnostic text? "BartC" <bc@freeuk.com> - 2012-04-22 12:51 +0100
          Re: Recursive descent parsing and optimization, was Good practical language and OS agnostic text? "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2012-04-22 18:18 +0200
            Re: Recursive descent parsing and optimization, was Good practical language and OS agnostic text? "Bartc" <bartc@freeuk.com> - 2012-04-23 10:59 +0100
          Re: Recursive descent parsing and optimization, was Good practical language and OS agnostic text? BGB <cr88192@hotmail.com> - 2012-04-22 13:45 -0700
      Re: Good practical language and OS agnostic text? compilers@is-not-my.name - 2012-04-22 22:11 +0000
        Re: Good practical language and OS agnostic text? "BartC" <bc@freeuk.com> - 2012-04-23 18:41 +0100
    Re: Good practical language and OS agnostic text? basile@starynkevitch.net - 2012-05-02 22:16 -0700
      Re: Good practical language and OS agnostic text? Johann 'Myrkraverk' Oskarsson <johann@2ndquadrant.com> - 2012-06-06 16:52 +0000

Page 1 of 3  [1] 2 3  Next page →

#562 — Good practical language and OS agnostic text?

Guys, I'm having a bear of a time finding a good practical language
and OS agnostic text on writing a compiler. I'm weak in math and not
interested in the theoretical details. I want to understand the hows
and whys of compiler writing. Everything I've found is either
gobbledygook equations or "let's use C/C++/Java on UNIX" or things
that are so trivial and focused they don't explain general cases and
can't be extended to anything useful.

I think of all the compilers were written in the DOS days and there
were normal guys writing them, not Nobel math prizewinners. Shirley
there must be at least one book that explains how compilers work
without depending on intimate knowledge of a specific target or
implementation language?  Whatever happened to pseudocode? It doesn't
have to be modern, just something that covers all the practical
aspects of compiler writing. Not exhaustive coverage of every possible
angle mind you, but at least so I can understand the basics and get
started without having to go back to uni and get an advanced maths
degree. I'm a good practical programmer and have experience with
writing my own libraries for all sorts of data structures and
functions and am not a cut and paste sort of fellow at all. I hope to
find a text or two for a guy like me who isn't a professor! Thanks for
your suggestions.

[Sorry to burst your bubble, but I knew people writing compilers for
DOS, and they understood parsing theory just fine.  Although I agree
that some compiler texts are more readable than others, the math isn't
there to be obscure, it's there because understanding how state
machines and LL and LR work makes writing fast and reliable scanners
and parsers vastly easier. As far as the language they use for
examples, you have to use something.  If you can find a copy of
Holub's "Compiler Design in C", and the errata list which is essential
due to the incredible number of errors in the published edition, you
might be able to work your way through that. -John]

[toc] | [next] | [standalone]

#564

On 17 April 2012 22:28,  <compilers@is-not-my.name> wrote:
> .... I'm a good practical programmer and have experience with
> writing my own libraries for all sorts of data structures and
> functions and am not a cut and paste sort of fellow at all. I hope to
> find a text or two for a guy like me who isn't a professor! Thanks for
> your suggestions.

I understand your squabbles with wanting a very straight forward text
to work from. I had similar annoyances although I have a degree in
Math and Computer science maybe that made it a little easier but I
personally think understanding the ideas behind grammar and state
machines etc all that theory is actually very straight forward it just
can look obscure but it is kind of essential to know otherwise you can
end up making a lot of mistakes without really understanding why. But
that's not to say just taking your time to understand from first
principles you wont get there it just would take more time.

I personally found the Lex and Yacc o'reilly book extremely insightful
because if you work though the bison manual the examples they give can
really make you see how things work to a very basic level and its very
easy to see how it can be extended very quickly. Another is the dragon
book i still think although there is a lot of obscurity in it, but Its
a classic book for a reason its actually really really good. There are
a few other online pdf manuals i don't have the links for but a very
quick search though this mailing list will turn them up. Some of them
a very much to the point. The biggest point of all is compiler and os
work isn't very rewarding for a very long time when you start working
at it. As in you can go for ages and ages and not feel like your
getting anywhere then all of a sudden it can click. Well that's how i
feel sometimes.

I hope this gives you some hope because its not the easiest subject to
tackle. There is no substitution to just working at something just
starting your own small basic compiler project to understand
expressions will give you very much of what you want to know for the
basics in my opinion and just work at that in your own time.

--Phil
[Thanks for the suggestion of lex & yacc.  I revised it a couple
of years ago, the new edition is called flex & bison. -John]

[toc] | [prev] | [next] | [standalone]

#583

From: Philip Herron <redbrain@nospam.gcc.gnu.org>

> I understand your squabbles with wanting a very straight forward text
> to work from. I had similar annoyances although i have a degree in
> Math and Computer science maybe that made it a little easier but i
> personally think understanding the ideas behind grammar and state
> machines etc all that theory is actually very straight forward it just
> can look obscure but it is kind of essential to know otherwise you can
> end up making a lot of mistakes without really understanding why. But
> that's not to say just taking your time to understand from first
> principles you wont get there it just would take more time.

I have an undergraduate degree in computer science as well but we didn't get
into much theoretical stuff. I went into development from there and didn't
get an advanced degree. Obviously I lack the higher academic knowledge that
many of you have. Your comments seem to confirm what I thought about this
specific issue. It's just I haven't found the right presentation and not
having anyone to discuss things with is also difficult. I don't think the
theory is silly or not relevant that's not my point at all. Given I lack the
background to understand it I'm trying for a more practical angle, that's
all.

> I personally found the Lex and Yacc o'reilly book extremely insightful
> because if you work though the bison manual the examples they give can
> really make you see how things work to a very basic level and its very
> easy to see how it can be extended very quickly.

I've looked over the archives here and John obviously knows his stuff! I'm
sure the book is very good. That sort of approach doesn't help me though
because I don't have Lex or Yacc or Bison in my development environment and
I really want to understand the parts well enough to write my own pieces and
not use something other people have written. That method has always been a
good idea in the past because I was forced to understand how the code
works. If you use other people's code you can miss things.

> Another is the dragon book i still think although there is a lot of
> obscurity in it, but Its a classic book for a reason its actually really
> really good.

I received some scans a few years ago and the book is daunting. If everyone
agrees it's good I suppose I should buy a real copy I always find reading
actual books is better than switching back and forth between screens. The
prospect of needing to understand a 1,000+ page book to do a small project
such as think I have in mind seems a bit much.

> There are a few other online pdf manuals i don't have the links for but a
> very quick search though this mailing list will turn them up. Some of them
> a very much to the point.

That's the biggest problem is how many there are and since I can't tell
which are good and which are bad I'm asking for help selecting the right one
for me. So far I haven't come across it.

> The biggest point of all is compiler and os work isn't very rewarding for
> a very long time when you start working at it. As in you can go for ages
> and ages and not feel like your getting anywhere then all of a sudden it
> can click. Well that's how i feel sometimes.

Thanks that's an important piece of information to keep handy on a project
like this. I've worked on many large products that may take years before
they go to production so I'm aware of this general idea. Writing big
software projects is not for the immediate gratification crowd!

> I hope this gives you some hope because its not the easiest subject to
> tackle. There is no substitution to just working at something just
> starting your own small basic compiler project to understand
> expressions will give you very much of what you want to know for the
> basics in my opinion and just work at that in your own time.

Thanks that's exactly what I'm after. I don't have any plans to rock
the compilation world or write books on the subject. I'd be very excited to
be able to understand the basics enough to produce something I can use and
to use that as a path to additional learning on the topic.

[toc] | [prev] | [next] | [standalone]

#588

It may be showing its age, but I think that "Crafting A Compiler in C"
by Fischer and LeBlanc is worth looking at.  The original "Crafting
A Compiler" was written in the late 80s when Ada was going to conquer the
world and was also pushing compiler technology. Circa 1991 I translated
the Ada code and pseudo-code into C for the C version of the book. Once
I did that I finally understood how LR parsers work. :-)

(How did I get to do the work? I did my MS work under Rich LeBlanc at
Georgia Tech and had stayed in touch. :-)
--
Aharon (Arnold) Robbins 			arnold AT skeeve DOT com
P.O. Box 354		Home Phone: +972  8 979-0381
Nof Ayalon		Cell Phone: +972 50 729-7545
D.N. Shimshon 99785	ISRAEL

[toc] | [prev] | [next] | [standalone]

#605

> Aharon (Arnold) Robbins wrote:
>
> It may be showing its age, but I think that "Crafting A Compiler in C"
> by Fischer and LeBlanc is worth looking at.  The original "Crafting
> A Compiler" was written in the late 80s when Ada was going to conquer the
> world and was also pushing compiler technology. Circa 1991 I translated
> the Ada code and pseudo-code into C for the C version of the book. Once
> I did that I finally understood how LR parsers work. :-)

The Ada version sounds intriguing. Thanks for mentioning it. I've done
similar things with non-compiler projects (translate something from one
language to another very different one). It helps greatly with understanding
as you said.

[toc] | [prev] | [next] | [standalone]

#591

<compilers@is-not-my.name> wrote in message news:12-04-040@comp.compilers...

> I have an undergraduate degree in computer science as well but we didn't
> get into much theoretical stuff.

Same here. I started writing my own compilers out of necessity (to make it
easier to program the microprocessor circuits I was building; it was just
not practical to run someone else's compiler).

But I also created my very simple languages which could do just what I
needed.

I'd heard of the 'proper' parsing methods in my compiler course, but ignored
all that and just did whatever was necessary to tokenise source code, parse
the few statements I had in the language, and write whatever code was
required to run the results. And it worked! I think those first attempts
might even have been single pass compilers, so ultra-simple if that was the
case.

> I really want to understand the parts well enough to write my own pieces
> and not use something other people have written. That method has always been a
> good idea in the past because I was forced to understand how the code
> works. If you use other people's code you can miss things.

(Again, same here. Thirty years on and I still don't think I've ever used
someone else's actual source code (or language). (However I do use some
libraries, and someone else's OS.))

>> I hope this gives you some hope because its not the easiest subject to
>> tackle. There is no substitution to just working at something just
>> starting your own small basic compiler project to understand
>> expressions will give you very much of what you want to know for the
>> basics in my opinion and just work at that in your own time.
>
> Thanks that's exactly what I'm after. I don't have any plans to rock
> the compilation world or write books on the subject. I'd be very excited
> to be able to understand the basics enough to produce something I can use and
> to use that as a path to additional learning on the topic.

Start with a very simple language. Perhaps even a version of  Basic (as a
useful language consisting of Let, If, Goto, Print (and perhaps Input) can
be created without any structured statements; only expressions need
recursive methods to deal with). You might consider also interpreting the
language rather than translating to a target language. And use an easy,
dynamic language to implement it all in. Stay away from C, C++, or anything
else with curly braces.

(Sorry, I can't recommend any books because I haven't read any...)

--
Bartc

[toc] | [prev] | [next] | [standalone]

#602

BartC <bc@freeuk.com> wrote:
> Start with a very simple language. Perhaps even a version of  Basic (as a
> useful language consisting of Let, If, Goto, Print (and perhaps Input) can
> be created without any structured statements; only expressions need
> recursive methods to deal with). You might consider also interpreting the
> language rather than translating to a target language. And use an easy,
> dynamic language to implement it all in. Stay away from C, C++, or anything
> else with curly braces.
>
> (Sorry, I can't recommend any books because I haven't read any...)

Another book of interest is

   P. J. Brown
   "Writing Interactive Compilers and Interpreters"
   (Wiley, 1981)

It's a completely non-mathematical (& pretty "basic", i.e., assuming
very little prior knowledge) tour through what's needed to write a
Basic interpreter.

--
-- "Jonathan Thornburg [remove -animal to reply]" <jthorn@astro.indiana-zebra.edu>
   Dept of Astronomy & IUCSS, Indiana University, Bloomington, Indiana, USA
[It's not a bad book.  It's quite old, but you can usually find a copy in the
usual online used bookstores. -John]

[toc] | [prev] | [next] | [standalone]

#565

On 4/17/2012 2:28 PM, compilers@is-not-my.name wrote:
> Guys, I'm having a bear of a time finding a good practical language
> and OS agnostic text on writing a compiler. I'm weak in math and not
> interested in the theoretical details. I want to understand the hows
> and whys of compiler writing. Everything I've found is either
> gobbledygook equations or "let's use C/C++/Java on UNIX" or things
> that are so trivial and focused they don't explain general cases and
> can't be extended to anything useful.

<snip>

this is a hard thing to ask.

There is a lot of possible variation between languages, all of which may
have notable impact on the "best" compiler design.

I have not as of yet seen much of anything which tries to address all
this, and most focus more narrowly on "a C or Java like language
compiling directly to native code and using a C-style calling
convention". if designing a dynamic language, or having a "VM layer", or
a language with notably different requirements, then it may make sense
to vary the compiler design as well.

OS and CPU architecture can impact a fair amount as well, so it could be
similarly hard to address all of this without making at least some
assumptions on these fronts.

for example, do they use x86 or ARM as the example? ...


Otherwise, I guess, the book would probably be more of a "survey of the
field and lists of assorted design trade-offs" (or like a topic-focused
encyclopedia or similar), which although likely still useful, is
probably not likely to seem as "refined" or sell nearly as well.

Since many people seem to more like being told "this is how it is and
this is how you do it" than being handed something which more resembles
an encyclopedia.

like with "authority": many people play "follow the leader", others play
"oppose the leader", but both are likely pointless.

a person actively "doing their own thing" will not likely play that
game, and may not really care what the leader thinks, but will in turn
seem to at times be "following the leader" and "opposing the leader",
not because they actually are, but because not everything "the leader"
does is necessarily either right or wrong.


> [Sorry to burst your bubble, but I knew people writing compilers for
> DOS, and they understood parsing theory just fine.  Although I agree
> that some compiler texts are more readable than others, the math isn't
> there to be obscure, it's there because understanding how state
> machines and LL and LR work makes writing fast and reliable scanners
> and parsers vastly easier. As far as the language they use for
> examples, you have to use something.  If you can find a copy of
> Holub's "Compiler Design in C", and the errata list which is essential
> due to the incredible number of errors in the published edition, you
> might be able to work your way through that. -John]


I don't entirely agree (not being as much of a fan of math either).
the problem isn't so much about "understanding the topic", so much as
people often trying to throw mathematical notation at pretty much
everything.

often it could be explained easily enough using either natural-language,
some kind of pseudo-code, or some other specialized (presumably
non-esoteric) notation.

it is kind of defeats the point if a person needs a math degree to even
figure out what exactly this glob of notation is supposed to be (or even
what sort of math this is even supposed to be, as it becomes more the
"find a match the greek letters and other symbols" game).


it is much like people throwing set notation at everything.
yes, the concept of sets can be used.

but people throw it at nearly everything, often in cases where:
there is another notation and/or formalism which can express the topic
better (such as predicate logic, or even good old algebraic notation);
it has little to do with the topic (such as statistics or newtonian
mechanics, and more obscures the topic than it helps);
...


the end result is the same, the actual topic is buried under a pile of
mathematical gobbledygook.

[toc] | [prev] | [next] | [standalone]

#584

BGB <cr88192@nospam.hotmail.com> wrote:

> this is a hard thing to ask.
>
> There is a lot of possible variation between languages, all of which may
> have notable impact on the "best" compiler design.

I'm not dreaming about "best" just getting a small project going would be
enough to make my day or month etc.

> I have not as of yet seen much of anything which tries to address all
> this, and most focus more narrowly on "a C or Java like language
> compiling directly to native code and using a C-style calling
> convention".

I guess that would be ok, do you have any suggestions on a book like that?

> OS and CPU architecture can impact a fair amount as well, so it could be
> similarly hard to address all of this without making at least some
> assumptions on these fronts.

Fair enough. I didn't think so but everybody seems to be saying that so I
guess that is the way these books are written. I would have thought there is
a lot that has nothing to do with code generation and that code generation
itself aside from optimization obviously would be a pluggable component.

> for example, do they use x86 or ARM as the example? ...

My target would be z/OS and I may want to do it so it can generate code for
MVS and XA and ESA targets as well. If I can get to the code generation part
I'll have no trouble with this actual detail. It's all the stuff before that
and maybe after it, I have no idea how to do.

> like with "authority": many people play "follow the leader", others play
> "oppose the leader", but both are likely pointless.

I have no agenda and I know my limits. I'm not opposed to a book that picks
one way and pretends it's the only way, we've all been around to know that
can't be true. I'm willing to go along for the ride, but I am trying to find
a writer you guys says is trustworthy.

> a person actively "doing their own thing" will not likely play that
> game, and may not really care what the leader thinks, but will in turn
> seem to at times be "following the leader" and "opposing the leader",
> not because they actually are, but because not everything "the leader"
> does is necessarily either right or wrong.

I'm happy to follow the leader on this sort of project because I've never
done it before. I don't pretend to know how to do it and I'd be silly to
pretend that. But I do need something that explains the practical issues and
I don't need to understand the theory to be able to prove anything. If I
can understand /what/ to do I'll eventually understand /why/ it works well
enough for what I need. At some level everything is a black box. Some people
just drill down further than others until they get to that point.

> I don't entirely agree (not being as much of a fan of math either).
> the problem isn't so much about "understanding the topic", so much as
> people often trying to throw mathematical notation at pretty much
> everything.

This issue comes up a lot and it's partly people have worked pretty hard to
amass deep knowledge of a topic and they don't like to see people coming in
and trivializing or disrespecting that and saying you're all silly and I can
do it without all that. Nothing of the kind, I have a lot of respect for
people with the theoretical understanding who've actually written a real,
disciplined compiler according to proper rigorous methods.

My approach is not to dismiss that or say it has no value, quite the
opposite. I don't know what you guys know and I can't learn it quickly
enough so I need some distillation of the theory and a presentation in
a practical way a good programmer who is a very bad mathematician can
understand and actually use.

> often it could be explained easily enough using either natural-language,
> some kind of pseudo-code, or some other specialized (presumably
> non-esoteric) notation.

That is what I thought but everybody else seems to say that isn't true.

> it is kind of defeats the point if a person needs a math degree to even
> figure out what exactly this glob of notation is supposed to be (or even
> what sort of math this is even supposed to be, as it becomes more the
> "find a match the greek letters and other symbols" game).

Yeah that's how I feel.

[toc] | [prev] | [next] | [standalone]

#566

compilers@is-not-my.name writes:

> Guys, I'm having a bear of a time finding a good practical language
> and OS agnostic text on writing a compiler. I'm weak in math and not
> interested in the theoretical details. I want to understand the hows
> and whys of compiler writing. [...]

First, don't expect to understand much of compilation without at least
some background in discrete maths (some basic language theory, but
also graph theory if you go down later stages), and of course
algorithmics and programming.

Second, don't think compilation is all about language theory. For
instance, control-flow analysis is heavy on graph traversals, code
generation may use subtle algorithmics (e.g., dynamic programming), etc.
And optimization techniques may use whatever will provide a suitable
model (some loop optimizations make heavy use of linear algebra).

Of course, if you're interested in compilers you'll become interested
into all the theories/topics they use. And I think it's a very nice way
to learn a lot about computer science.

OK, now my suggestion: "Modern Compiler Implementation", by Andrew
Appel, which imho has the perfect balance between theory and
implementation. You are allowed to choose the implementation language:
the book exists in C, Java, and ML versions.

-- Alain.

[toc] | [prev] | [next] | [standalone]

#576

Alain Ketterlin schrieb:
> compilers@is-not-my.name writes:
>
>> Guys, I'm having a bear of a time finding a good practical language
>> and OS agnostic text on writing a compiler. I'm weak in math and not
>> interested in the theoretical details. I want to understand the hows
>> and whys of compiler writing. [...]
>
> First, don't expect to understand much of compilation without at least
> some background in discrete maths (some basic language theory, but
> also graph theory if you go down later stages), and of course
> algorithmics and programming.

I dare to disagree. For writing an parser it's sufficient to understand
a formal language definition (BNF...), from which a LL(1) parser can be
even hand-coded. When tools are used to create a compiler skeleton
(lex/yacc, Coco/R, Antlr...), the related math is encapsulated in these
tools, no need that their users bother with it.

IMO the OP will be comfortable with Wirth's books, languages and
compilers, which are understandable even without a big theoretical
background. Even if Wirth is concerned with *teaching* compiler
principles, his languages and compilers are not the toys as many people
believe. E.g. Oberon implements a complete OS, with the compiler being
an integrated part of the entire system. From there it's only a small
step to understanding and implementing e.g. JIT compilers, which require
an different approach from stand-alone compilers.


> Second, don't think compilation is all about language theory. For
> instance, control-flow analysis is heavy on graph traversals, code
> generation may use subtle algorithmics (e.g., dynamic programming), etc.
> And optimization techniques may use whatever will provide a suitable
> model (some loop optimizations make heavy use of linear algebra).
>
> Of course, if you're interested in compilers you'll become interested
> into all the theories/topics they use. And I think it's a very nice way
> to learn a lot about computer science.

Again I suggest the OP to dig into the various (optional) parts of an
compiler later, when he discoverd a *practical* need/motivation for code
flow analysis, register allocation etc. Many people (like me ;-) are
much more open to the theory, when they have practical examples for
their application *before*.

Life is too short for writing an full-blown heavily-optimizing
production compiler from scratch, including its whole RTL. A beginner
IMO is better off with a small language and compiler, where he can study
the related problems, and can find out the areas of his personal interest.

DoDi

[toc] | [prev] | [next] | [standalone]

#596

Hans-Peter Diettrich <DrDiettrich1@nospam.aol.com> wrote

> IMO the OP will be comfortable with Wirth's books, languages and
> compilers, which are understandable even without a big theoretical
> background. Even if Wirth is concerned with *teaching* compiler
> principles, his languages and compilers are not the toys as many people
> believe. E.g. Oberon implements a complete OS, with the compiler being
> an integrated part of the entire system. From there it's only a small
> step to understanding and implementing e.g. JIT compilers, which require
> an different approach from stand-alone compilers.

I've always found Wirth's terse descriptions tough. I know he was
revolutionary so I will have to go over these again and try harder.
Thanks for your comments.

> Again I suggest the OP to dig into the various (optional) parts of an
> compiler later, when he discoverd a *practical* need/motivation for code
> flow analysis, register allocation etc. Many people (like me ;-) are
> much more open to the theory, when they have practical examples for
> their application *before*.

Very perceptive observations. Thanks for posting them.

> Life is too short for writing an full-blown heavily-optimizing
> production compiler from scratch, including its whole RTL. A beginner
> IMO is better off with a small language and compiler, where he can study
> the related problems, and can find out the areas of his personal interest.

Thank you for your comments. I found them very helpful.

[toc] | [prev] | [next] | [standalone]

#601

"Hans-Peter Diettrich" <DrDiettrich1@aol.com> wrote in message
> Life is too short for writing an full-blown heavily-optimizing
> production compiler from scratch, including its whole RTL.

Especially when there might only be difference of 2 or 3 times between
performance of the best and worst code.

My own compiler for x86-32 generates pretty awful code, and on a small
handful of mostly numeric benchmarks, it averages out about 2.5 x as
slow as gcc on it's highest optimisation setting. But, gcc often
recognises these benchmarks as doing nothing useful, so removes whole
sections of code!

The true factor is probably between 1 and 2, and for critical code, I just
use inline assembly code, so it's not real problem. I'm rewriting that
compiler at the moment, and will probably achieve somewhat better
performance, but don't worry about it too much.

--
Bartc

[toc] | [prev] | [next] | [standalone]

#604 — Re: code quality, was Good practical language and OS agnostic text?

BartC schrieb:
> "Hans-Peter Diettrich" <DrDiettrich1@aol.com> wrote in message
>> Life is too short for writing an full-blown heavily-optimizing
>> production compiler from scratch, including its whole RTL.
>
> Especially when there might only be difference of 2 or 3 times between
> performance of the best and worst code.
>
> My own compiler for x86-32 generates pretty awful code, and on a small
> handful of mostly numeric benchmarks, it averages out about 2.5 x as
> slow as gcc on it's highest optimisation setting. But, gcc often
> recognises these benchmarks as doing nothing useful, so removes whole
> sections of code!

I never trust benchmarks, in detail when supplied by compiler vendors :-]

When we had several workstations for evaluation, the AIX workstation
came with a benchmark program executing in about 3 seconds on that
machine. On other machines the time ranged from 8 minutes to more than
an hour.

When I added a printf after the loop in the benchmark code, it also took
about 8 minutes! The benchmark turned out to test the compiler *default*
optimization settings, where the HP station was so incredibly slow
because it had turned off *any* optimization by default.

 From that experience I also learned what optimization means in
practice. A dumb compiler, or with all optimizations disabled, may fetch
every expression operand from memory, and write back every intermediate
result (SSA?), which is nice when debugging some code. Thus *register
allocation* turned out to be a basic optimization of high value - I
wonder how somebody could ever design a CPU (with more than 8 bit
registers) with as few registers as available on most Intel processors.
Dead code elimination and moving loop-invariant computations out of
loops are the next optimizations to consider. And CSE...

Another compiler, for an M68000, turned out to be a very quick&dirty
port of an M6800 compiler. According to "an int is a pointer, a pointer
is an int" it kept all operands in the M68K *address* registers, so that
every logical or arithmetic operation had to be done in a subroutine,
which moved the operands from A0 and A1 into *data* registers, evaluated
and stored back the result into A0. The caller had to move the operands
into A0 and A1 before, of course. In my test programs every single C
statement resulted in about 3 pages of assembler code! [1]

But despite that horrible code generation, this compiler came with a
very powerful graphics and window software, with amazing runtime
behaviour. This observation again relativates the need for optimization,
at least in GUI applications.


[1] This compiler, and my rudimentary knowledge of C and compilers and
runtime libraries, made me write my first C decompiler in the late 80's.
Of course in Basic, which was the language I had used on all my
homecomputers before. Hereby I learned more and more about bad and good
practices in compiler writing, encountering any number of workarounds
for adopting old 8-bit compilers to 16/32 bit code and memory layouts.

DoDi

[toc] | [prev] | [next] | [standalone]

#579

Alain Ketterlin <alain@nospam.dpt-info.u-strasbg.fr> wrote

> compilers@is-not-my.name writes:
>
> > Guys, I'm having a bear of a time finding a good practical language
> > and OS agnostic text on writing a compiler. I'm weak in math and not
> > interested in the theoretical details. I want to understand the hows
> > and whys of compiler writing. [...]
>
> First, don't expect to understand much of compilation without at least
> some background in discrete maths (some basic language theory, but
> also graph theory if you go down later stages), and of course
> algorithmics and programming.

Discrete maths!? I don't even know what that is.

> Second, don't think compilation is all about language theory. For
> instance, control-flow analysis is heavy on graph traversals, code
> generation may use subtle algorithmics (e.g., dynamic programming), etc.
> And optimization techniques may use whatever will provide a suitable
> model (some loop optimizations make heavy use of linear algebra).

Yeah but like anything else now that you smart mathematicians have worked
all that out, can't we use what you know without fully understanding it? Is
it unreasonable to explain what to do in an algorithmic way without needing
for the reader to understand the theoretical background? Otherwise it smacks
of having to reinvent the research wheel to do a project like this.

> OK, now my suggestion: "Modern Compiler Implementation", by Andrew
> Appel, which imho has the perfect balance between theory and
> implementation. You are allowed to choose the implementation language:
> the book exists in C, Java, and ML versions.

I don't know or use any of those languages so I suppose it won't help me
very much but I'll see if I can look over the book anyway. Thank you.

[toc] | [prev] | [next] | [standalone]

#595

compilers@is-not-my.name wrote:
> Is it unreasonable to explain what to do in an algorithmic way without needing
> for the reader to understand the theoretical background?

You might consider

  Patricia Anklam, David Cutler, Roger Heinen, Jr., and M. Donald MacLaren,
  "Engineering a Compiler: VAX-11 Code Generation and Optimization"
  Digital Press, 1982, ISBN 0-932376-19-3

It's a high-level description of the backend (code generation) of the
DEC Vax/VMS PL/1 and C compilers.  The book gives a clear presentation
of the somewhat ad-hoc, but successful, design and implementation of
these compilers backend, using very little mathematics.

Once you understand the ideas, translating them to your choice of
target & implementation environment is a much smaller problem...

Having said that, I'll echo others in this thread: learning enough math
to read the Dragon book would be *very* valuable.  In fact, even if you
don't grok the math, the Dragon book is still a great read!

ciao,

--
-- "Jonathan Thornburg [remove -animal to reply]" <jthorn@astro.indiana-zebra.edu>
   Dept of Astronomy & IUCSS, Indiana University, Bloomington, Indiana, USA
[That's not a bad book, but it's 100% about the code generator, since they bought
the PL/I front end from someone else. -John]

[toc] | [prev] | [next] | [standalone]

#567

On 17/04/2012 22:28, compilers@is-not-my.name wrote:
> Guys, I'm having a bear of a time finding a good practical language
> and OS agnostic text on writing a compiler. I'm weak in math and not
> interested in the theoretical details. I want to understand the hows
> and whys of compiler writing.

I always recommend:
A Retargetable C Compiler: Design and Implementation
by David R. Hanson and Christopher W. Fraser

If you are weak on math you might have a problem getting your head
around recursion.  If you cannot understand recursion your compiler
writing days are finished.

> I think of all the compilers were written in the DOS days and there
> were normal guys writing them, not Nobel math prizewinners. Shirley

In my experience compiler writers are not normal guys, but then I
am a vested interest.

> [Sorry to burst your bubble, but I knew people writing compilers for
> DOS, and they understood parsing theory just fine.  Although I agree
> that some compiler texts are more readable than others, the math isn't
> there to be obscure, it's there because understanding how state
> machines and LL and LR work makes writing fast and reliable scanners
> and parsers vastly easier. As far as the language they use for  ...]

I would question whether it is necessary to have any deep knowledge
of parsing theory.  Some knowledge of state machines is useful for any
kind of software development.

I would add my voice to the previous posters who suggested our
moderator's book, flex & bison.

[toc] | [prev] | [next] | [standalone]

#571

Derek M. Jones <derek@knosof.co.uk> wrote:
> On 17/04/2012 22:28, compilers@is-not-my.name wrote:
>> Guys, I'm having a bear of a time finding a good practical language
>> and OS agnostic text on writing a compiler. I'm weak in math and not
>> interested in the theoretical details. I want to understand the hows
>> and whys of compiler writing.

> I always recommend:
> A Retargetable C Compiler: Design and Implementation
> by David R. Hanson and Christopher W. Fraser

So, that makes two (out of about five) of us. (My post comes later.)

Much of the book is about code generation, which, it seems to me,
is not described in as much detail in many other compiler books.

Parsing theory is where much of the theory, and hard to understand
mathematical descriptions, appear, but in the end (back end, in the
case of compilers) it is about code generations.

As far as languages to write compilers in, it is now usual (though
maybe not 50 years ago) to describe parts of the compiler in a
special purpose language. As previously noted, there are flex and
bison to write the front end, though you usually need to know some
C to use them.

For compilers that generate code for more than one target,
(at least gcc and lcc), the back end is usually described through
a language easier for humans to understand. To me, the lcc code
generator is much easier to understand than that of gcc.
You should be able to write a description for a new target
without knowing C, or much of parsing theory. You do need a
good understanding of the instruction set for the target, though.

-- glen

[toc] | [prev] | [next] | [standalone]

#574

On 4/18/2012 3:43 PM, glen herrmannsfeldt wrote:
> Derek M. Jones<derek@knosof.co.uk>  wrote:
>> On 17/04/2012 22:28, compilers@is-not-my.name wrote:
>>> Guys, I'm having a bear of a time finding a good practical language
>>> and OS agnostic text on writing a compiler. I'm weak in math and not
>>> interested in the theoretical details. I want to understand the hows
>>> and whys of compiler writing.
>
>> I always recommend:
>> A Retargetable C Compiler: Design and Implementation
>> by David R. Hanson and Christopher W. Fraser
>
> So, that makes two (out of about five) of us. (My post comes later.)

sadly, in my case, I can't really currently get (or afford) books which
aren't freely available online.


did find a site though (which I guess is a personal site for the author?):
http://www.well.com/~cwf/pro/vita.htm

which has maybe a few interesting looking papers.


saw one about employing LZ77 in an ISA, which is a fairly nifty seeming
feature, but is sadly not really directly applicable in my case.


> Much of the book is about code generation, which, it seems to me,
> is not described in as much detail in many other compiler books.
>
> Parsing theory is where much of the theory, and hard to understand
> mathematical descriptions, appear, but in the end (back end, in the
> case of compilers) it is about code generations.


then there is the irony being that it is considerably more effort IME to
write the back-end than it is to write a parser, or at least this has
been my experience in these matters (logic for things like register
allocation, allocating space in the stack-frame, logic for dealing with
types and spitting out various ASM fragments, ... is all a bit painful).


granted, I tend not to use any fancy parsing algorithms, as pretty much
all of my parsers have been hand-written recursive descent parsers.


although, I guess it is always possible that maybe I have just been
approaching the back-end in ways more complex or painful than necessary,
but it is not clear how it could all be considerably easier.

granted, maybe it is also that modern CPU architectures (such as x86 and
x86-64) and type-towers (integer types, FPU, and SIMD) are more complex
than many older architectures.

if so, maybe the parser preoccupation is at least partly a hold-over
from the times where the parser was more complex relative to the
code-generator?

I guess the other major option is that it is because the parser is often
the part of the problem that most people run into first (and thus where
more people are more likely to give up and walk away?).


> As far as languages to write compilers in, it is now usual (though
> maybe not 50 years ago) to describe parts of the compiler in a
> special purpose language. As previously noted, there are flex and
> bison to write the front end, though you usually need to know some
> C to use them.

I have not personally used them.

to me, depending on an external tool to spit out code for something that
is maybe a few thousand lines seems a bit overkill IMHO.


granted, maybe it is that I haven't been writing "maximally efficient"
parsers, but more just sort of "straightforward but naive" parsers:
read in a few tokens;
match against possible constructions;
...

I had not usually actually introduced a separate lexer and parser stage
either, but instead typically just read tokens directly from a string
buffer during parsing (or a "reader stream object").

I have sometimes used a small hash-table to partly optimize re-reading
the same tokens (as my parsers tend to often end up re-reading the same
tokens multiple times, and hashing the string-pointer allows skipping
much of the logic). this was done in my C parser as it ends up dealing
with considerably more code during parsing (and thus tends to bog down
more readily with reading tokens).

a lot of this then ends up with a lot of if/else logic and "strcmp()"
and similar (although in a few places I have used "indexed tokens",
where an index number is used for keywords in place of string comparisons).


maybe it is all a bit lazy, but it works.


> For compilers that generate code for more than one target,
> (at least gcc and lcc), the back end is usually described through
> a language easier for humans to understand. To me, the lcc code
> generator is much easier to understand than that of gcc.
> You should be able to write a description for a new target
> without knowing C, or much of parsing theory. You do need a
> good understanding of the instruction set for the target, though.


in my case, most of my stuff tends to be plain C.


some of the code in my prior code-generator did use a special
preprocessor which allowed for more powerful macros.

my assembler uses a special notation for the ASM listings, where
basically a notation similar to that used in the Intel docs is used to
describe most of the opcodes.

later changes to support AVX and XOP, and ARM and Thumb, were a little
less clean (nasty notational cruft).

more notation had to be devised as these docs had (for some reason)
mostly using either bit-based notations or "bit-box" diagrams.


actually, when I started out trying to write the assembler, I started
out writing explicit logic for the various instructions, but quickly
became frustrated, and then wrote a tool to convert the Intel-docs
notation into C (changing all this mostly into a task of transcribing
the docs into a text file).

but, pretty much everything else is plain C.


I am not terribly sure why "needing to knowing C" would be something to
be avoided for a compiler backend, when presumably someone who "doesn't
know C" (and can't be asked to learn about it) should presumably be
somewhere far away from a compiler's back-end?

a better goal I think is using a specialized format more as an aide to
reduce the amount of code which needs to be written to support a new target.

[toc] | [prev] | [next] | [standalone]

#577

gah@nospam.ugcs.caltech.edu wrote

> Much of the book is about code generation, which, it seems to me,
> is not described in as much detail in many other compiler books.

I wonder how useful that will be for me given my non-UNIX target but I'll
try to look at that book since it got two thumbs up here.

> Parsing theory is where much of the theory, and hard to understand
> mathematical descriptions, appear, but in the end (back end, in the
> case of compilers) it is about code generations.

I looked over Let's Build a Compiler and the code generation part wasn't
difficult for me. I worked out the first few examples cross-compiling to
z/OS. But after that it started to look like it wasn't a serious article as
far as producing something useful goes. Anyone care to comment on it?

> As far as languages to write compilers in, it is now usual (though
> maybe not 50 years ago) to describe parts of the compiler in a
> special purpose language. As previously noted, there are flex and
> bison to write the front end, though you usually need to know some
> C to use them.

Not only don't I know C and am not interested in knowing it, but the tools
for the front end aren't available to me and I don't plan on using anything
I don't write. I've gotten this far without ever cutting and pasting and I
don't intend to start now.

> You should be able to write a description for a new target
> without knowing C, or much of parsing theory. You do need a
> good understanding of the instruction set for the target, though.

And that I have in spades. Thanks for your post.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.compilers

csiph-web