Compiler Construction in Ada

Compiler Construction in Ada

[agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!zaphod.mps.ohio-state]

I'm looking at teaching Construction in the Spring semester.  The course
includes writing a compiler (all the way through code generation for a
SPARC machine) for a language I specify.  In the past, we have had a
Pascal compiler, and the class has used Pascal to write their projects.

Now the Pascal compiler is gone.  And I'm looking for the appropriate
language in which to write the compiler for the project.  The language and
the project require the student to write a top-down, recursive descent
parsing compiler.  Therefore, a language allowing nested subprogram
definition would be very preferrable.

We have what looks like a good Ada compiler (from Meridian) for the Sun
workstations.  So I'd like to use Ada to write the compiler.  

My question(s): is there any pitfalls to look out for here?  has any one
done this?  what special disadvantages are there here?

Thanks in advance.

      Mike Jipping
      Hope College Department of Computer Science
      jipping@cs.hope.edu  (BITNET: JIPPING@HOPE)
[I'd use whatever language had the best debugging support.  I've written
recursive descent code in C and (a while ago) in Fortran without any
trouble. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[enterpoop.mit.edu!usc!wupost!uwm.edu!ogicse!das-news.harvard.edu!spdcc!ie]

jipping@cs.hope.edu (Mike Jipping) writes:
>I'm looking at teaching Construction in the Spring semester.  [Our old
>Pascal compiler has gone away.  How about using Ada?]

Others are commenting on the Sun compilers. I just hope you are using the
Fischer/LeBlanc book, "Crafting a Compiler" (the Ada version).  The
language being compiled is a decent Ada subset; the language of discourse
of the book is Ada. That will get your students started very nicely!

Mike Feldman
--
Michael B. Feldman, co-chair, SIGAda Education Committee
Professor, Dept. of Electrical Engineering and Computer Science
School of Engineering and Applied Science, The George Washington University
Washington, DC 20052 USA
(202) 994-5253 (voice), (202) 994-5296 (fax), mfeldman@seas.gwu.edu (Internet)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[James Crigler]

jipping@cs.hope.edu (Mike Jipping) writes:
>I'm looking at teaching Construction in the Spring semester.  [Our old
>Pascal compiler has gone away.  How about using Ada?]

mfeldman@seas.gwu.edu (Michael Feldman) writes:
>Others are commenting on the Sun compilers. I just hope you are using the
>Fischer/LeBlanc book, "Crafting a Compiler" (the Ada version).  ...

If you can stand the book.  When I took the compiler course here, we used
the book Prof. Mike mentions and I didn't like it.  Caveat: We were using
lex/yacc to create a compiler, which is, of course (:-) the opposite
approach to parsing.  (Since I had the class they've gone back to using
the Dragon book :-) but I can't afford a copy :-(

Jim Crigler
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[swrinde!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!pacific.mps.ohio-sta]

Here's a vote _for_ Fischer/LeBlanc. It's the text for the undergrad
compiler course at Georgia Tech, and the class project usually revolves
around building a compiler, using a Pascal-ized lex/yacc suite for the
parser and Pascal for the remainder.

IMHO the discussion and description in the Ada version of LeBlanc is more
clear and more appropriate for undergrad courses than the dragon book.
YMMV.

-Paul
-- 
Paul Robichaux, KD4JZG
Mission Software Development Div.
New Technology, Inc.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[Michael Feldman]

mfeldman@seas.gwu.edu (Michael Feldman) writes:
>Others are commenting on the Sun compilers. I just hope you are using the
>Fischer/LeBlanc book, "Crafting a Compiler" (the Ada version).  ...

robichau@lambda.msfc.nasa.gov writes:
>Here's a vote _for_ Fischer/LeBlanc. It's the text for the undergrad
>compiler course at Georgia Tech, and the class project usually revolves
>around building a compiler, using a Pascal-ized lex/yacc suite for the
>parser and Pascal for the remainder.
>
>IMHO the discussion and description in the Ada version of LeBlanc is more
>clear and more appropriate for undergrad courses than the dragon book.

I assume that LeBlanc either taught the course or had something to do with
its structure. Undoubtedly the course and the book were better coordinated
than the one described in a previous post. It's easy when the book author
and the teacher (or course designer, anyway) are the same person :-)

But I agree with you about the clarity of the book, especially if one is
using Ada for the course, which is what Prof. Jipping had in mind.
Fischer/LeBlanc is the only compiler book acknowledging Ada as a suitable
language in which to write a compiler.

As an aside, Rational, TeleSoft, Alsys, and RR (Janus and relatives) have
all written their compilers in Ada. People I have spoken to in all these
companies confirm their satisfying experiences in using Ada for this kind
of software project. Naturally (no surprise!) I agree :-)

crigler@osceola.cs.ucf.edu (James Crigler) writes:
>If you can stand the book.  When I took the compiler course here, we used
>the book Prof. Mike mentions and I didn't like it.  Caveat: We were using
>lex/yacc to create a compiler, which is, of course (:-) the opposite
>approach to parsing.  (Since I had the class they've gone back to using
>the Dragon book :-) but I can't afford a copy :-(

Well, since you did not say what you didn't like about Fischer/LeBlanc, I
can only assume that the poor fit between the book and the tools you were
using had something to do with it. Fischer/LeBlanc provides a lot of very
useful code segments, procedures, packages, etc., for "Crafting a
Compiler" in Ada. The C version of their book does the same with C, though
the language being compiled is _still_ an Ada subset.

In my opinion, your professor did you a disservice by requiring a book
that (1) used Ada as the language of discourse and (b) focused on
hand-coding a compiler, then gave you a project in which you used
lex/yacc/C to do the actual work. That caused too much "dissonance" and,
naturally, you had an unpleasant experience. Probably soured you on Ada,
too.

Different books are written with different viewpoints and biases; books
should be selected carefully to match the intent of the course.  The
original poster, Prof. Jipping, prefers the hand-coding approach, on the
grounds (I suppose) that using tools is great once you have some
understanding of how they work. Students who have hand-coded parts of
parsers and lexers really come to appreciate what yex/yacc/aflex/ayacc buy
you, and that's just the right education for undergraduates (IMHO). 

Michael B. Feldman, co-chair, SIGAda Education Committee

Professor, Dept. of Electrical Engineering and Computer Science
School of Engineering and Applied Science
The George Washington University
Washington, DC 20052 USA
(202) 994-5253 (voice) (202) 994-5296 (fax) mfeldman@seas.gwu.edu (Internet)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[Brent Burton]

mfeldman@seas.gwu.edu (Michael Feldman) writes:
|The original poster, Prof. Jipping, prefers the hand-coding approach, on the
|grounds (I suppose) that using tools is great once you have some
|understanding of how they work. Students who have hand-coded parts of
|parsers and lexers really come to appreciate what yex/yacc/aflex/ayacc buy
|you, and that's just the right education for undergraduates (IMHO). 

I couldn't agree more.

Last spring I took the compiler design class here and I found it to be an
excellent class.  We used the Dragon book and a hand-coded approach while
the language to compile was a subset of Pascal.

This format proved to be quite effective and educational.  Through
previous work at IBM, I had experience with lex and yacc already and a
good understanding of the parsing process.  However, the hand-coding
approach was, I feel, mandatory to learn the important underlying
algorithms and to better understand the roles lex and yacc play.  After
the the discussion about LL and LALR parsers, I could finally understand
the shift/reduce and reduce/reduce errors. ;-)

In short, I'd suggest the hand-coding approach.  Learning definitely comes
from doing, and the lex and yacc-based course doesn't provide that extra
depth of knowledge.

-Brent, waiting anxiously for the graduate compiler design this spring
-- 
Brent Burton    N5VMG, bpb9204@tamsun.tamu.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[agate!spool.mu.edu!uwm.edu!ogicse!das-news.harvard.edu!spdcc!iecc!compile]

bpb9204@tamsun.tamu.edu (Brent Burton) writes:
>This format [hand-coded lexer/parser in Pascal, using the Dragon book]
>proved to be quite effective and educational.  Through
>previous work at IBM, I had experience with lex and yacc already and a
>good understanding of the parsing process.  However, the hand-coding
>approach was, I feel, mandatory to learn the important underlying
>algorithms and to better understand the roles lex and yacc play.  After
>the the discussion about LL and LALR parsers, I could finally understand
>the shift/reduce and reduce/reduce errors. ;-)

	Having been involved in teaching the compiler design course here
at Hopkins for the last two years, I thought I'd put my two cents in.
(For the record, the first two years used the Dragon book, with a bunch of
hand-written supplements, while the last year used Fischer/LeBlanc (C
version)).

	Basically, I'd agree with Brent's motives: it's very important to
understand the theory of shift/reduce parsing and backing-up DFA lexing
before one can use the lex/yacc family of tools effectively.  However, I
don't think that necessarily means writing lexers/parsers by hand.

	Here at Hopkins we structure the course around the semester
project, which traditionally has been writing a Toy-to-C translator, where
Toy is a Pascal-like language with integer and function types, ref and
array constructors, and first-class functions.  (Function closures are
what make the translation non-trivial).  The first half of the
semester-long course's lectures are all on parsing theory, using Gough's
excellent "Syntax Analysis and Software Tools" as a supplemental text.
However, the students build their lexers and parsers using C, lex, and
yacc.  I really don't see that subjecting students to the torture of
cranking out lexers for a grammar with something like thirty keywords
accomplishes much other than convincing them one is a sadist.  Don't even
think about LR parsers with non-trivial action functions; debugging even
the machine- generated ones is a horror show.

	I think that it's much better to get the student's up and running
with a useable parser in a short amount of time.  This lets them
concentrate on the more interesting parts of the compiler, like the
type-checker, and experiment with different run-time strategies.  Yes, the
theory of LR parsing is very important to learn, but I don't believe that
can only be done by "rolling your own."
--
Jack Eifrig (eifrig@cs.jhu.edu)       The Johns Hopkins University, C.S. Dept.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[Eliot Moss]

I have taught a compiler course four times, and much prefer having the
students learn to use an off the shelf parser generator (yacc/bison
style). I do have them write a lexer themselves -- it's actually easier
for many languages, since lex is a bit tricky to use and get comments,
etc., right.

Reacting to previous postings, I don't think deep understanding of the
syntactic aspects is quite the important thing. It is much more important
to gain understanding of type checking, semantic processing in general,
code generation, and the role of optimization, in my opinion. Many people
concentrate on the syntactic stuff because it's clean and theoretical, but
the tools make it by the far the easiest part of compiling, so to me it
does not seem the smart place to spend limited classroom time.

Just one professor's view, but it seems to work.
--
J. Eliot B. Moss, Associate Professor	Visiting Associate Professor
Department of Computer Science		School of Computer Science
Lederle Graduate Research Center	Carnegie Mellon University
University of Massachusetts		5000 Forbes Avenue
Amherst, MA  01003			Pittsburgh, PA  15213-3891
(413) 545-4206, 545-1249 (fax)		(412) 268-6767, 681-5739 (fax)
Moss@cs.umass.edu			Moss@cs.cmu.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!zaphod.mps.ohio-state]

moss@cs.cmu.edu (Eliot Moss) writes:
>Reacting to previous postings, I don't think deep understanding of the
>syntactic aspects is quite the important thing. It is much more important
>to gain understanding of type checking, semantic processing in general,
>code generation, and the role of optimization, in my opinion. Many people
>concentrate on the syntactic stuff because it's clean and theoretical, but
>the tools make it by the far the easiest part of compiling, so to me it
>does not seem the smart place to spend limited classroom time.

  I have to agree with this point of view.  I took a class in programming
languages that involved writing a nearly-full front end for a Unity
compiler, and the lexical analyzer was the EASIEST part of the project by
far, both to understand and to code.  The shift-reduce parser was
difficult but not impossible, but coding it contributed little to the
fundamental understanding, and table-based interpretations that led to the
introduction of yacc helped the students to grasp the concept much better
than coding did.  The semantic analyzer was by far the hardest part of the
project, and unfortunately, after coding the parser and syntactic analyzer
etc., there was little enthusiasm left for it.  Again unfortunate is that
the semantic analyzer is probably the most important and helpful part of
the compiler.  It's usually easy to find a simple syntactic mistake in a
program like missing a semicolon or failing to include spaces, even if the
error is generic and cryptic.  It's harder to keep track of things like
type compatibilities and proper code use that the semantic analyzer
manages.  So I'm all for using yacc.  That's how the professor constructed
his assignment solutions anyway!  BNF grammars are a little easier to
handle, even when disambiguating them is taken into account.

Doug Lamb
University of Virginia
dtl8v@Virginia.EDU
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[Robert Firth]

In article <93-01-090@comp.compilers> moss@cs.cmu.edu (Eliot Moss) writes:

>Reacting to previous postings, I don't think deep understanding of the
>syntactic aspects is quite the important thing. It is much more important
>to gain understanding of type checking, semantic processing in general,
>code generation, and the role of optimization, in my opinion.

That's my view too, based on the days when I taught compiler writing.
Lexis and syntax is much the easiest part, and there's no need to make
a meal of it.  The least easy part is error detection, reporting and
recovery, and I think however much time you allocate to lexis and
syntax, at least half should be spent on that aspect.

Re: Compiler Construction in Ada

[agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!zaphod.mps.ohio-state]

moss@cs.cmu.edu (Eliot Moss) writes:
>Reacting to previous postings, I don't think deep understanding of the
>syntactic aspects is quite the important thing. It is much more important
>to gain understanding of type checking, semantic processing in general,
>code generation, and the role of optimization, in my opinion. Many people
>concentrate on the syntactic stuff because it's clean and theoretical, but
>the tools make it by the far the easiest part of compiling, so to me it
>does not seem the smart place to spend limited classroom time.

dtl8v@holmes.acc.Virginia.EDU (Heracleitus) writes:
>  I have to agree with this point of view.  I took a class in programming
>languages that involved writing a nearly-full front end for a Unity

Just another student's point of view:

I took a compilers class where we wrote a simple lexical analyzer, then a
simple parser from scratch.  We then took a skeleton tiny-c lex/yacc
definition and expanded on it to the point of having a working compiler
(including peephole optimizations, not including the assembler). 

This seemed to give a proper perspective on how important tools (lex/yacc)
can be, while at the same time not wasting too much time implementing
something which could better by done by the tools.
-- 
Adam G.
adamg@microware.com, or ...!uunet!mcrware!adamg
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[Robert I. Eachus]

     I used to say that there are three parts to a compiler: parsing,
semantic analysis, and code generation and that I never met anyone who
enjoyed (or was expert) in all three areas.  Looking at the comments
on teaching compiler writing, I see exactly the same categories.  Has
anyone ever tried a (one-year, I hope) course where the various parts
were taught by different people?  I'd love to see a profile of how the
grades came out.

     Having said all that, I'll throw my two cents in.  Anyone who
says lex and yacc are wonderful doesn't understand parser theory very
well.  (They are hacks, actually, they are hacks on top of hacks.)  I
was fortunate when I taught compiler construction to have access to
LALR on Multics, which accepted all LALR(k) grammars and some grammars
that were not even in LR(k).  This allowed me to teach parser theory
with toy langauges then hand out a reasonably sized grammar for
students to build a translator on.  (Since I don't do code generation,
I usually assigned a Pascal to C translator or some such.)
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Compiler Construction in Ada

[agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!zaphod.mps.ohio-state]

dtl8v@holmes.acc.Virginia.EDU (Heracleitus) writes:
>...  The shift-reduce parser was
>difficult but not impossible, but coding it contributed little to the
>fundamental understanding, and table-based interpretations that led to the
>introduction of yacc helped the students to grasp the concept much better
>than coding did.  The semantic analyzer was by far the hardest part of the
>project, and unfortunately, after coding the parser and syntactic analyzer
>etc., there was little enthusiasm left for it.

I had a class experience which gave me a different perspective.  In this
class (at UMass, but not taught by Eliot :-), we implemented a subset of
ADA using Pascal; the underlying machine was a simulator that executed the
tuple form, so we could learn about machine- independent optimizations.
We wrote our own lexical analyzers, and a parser generator tool was
available, but I wrote my own instead.  I followed Chapter 6 of the
(first) Dragon Book, going from an LR(0) to an LALR(1) generator.  This
gave me a thorough understanding of LR parsing.  Since then, I have
noticed that people who use LEX and YACC and have *not* been exposed to
the gory theory tend to write bad grammars (e.g., so ambiguous that they
are hard to modify).  I have forgotten many of the details of LR parsing,
but my exposure gave me intuition about what makes a grammar good; I'm
very glad of it, since my current work is compiler-related.

Now, I still agree with Eliot and Doug.  The point of a first compiler
course is to expose CS majors to that aspect of computing, and types and
so on are very important.  But I think that anyone who wants to do real
compiler work would benefit from the experience of digging into parsers
and parser generation.

- John
--
hagerman@ece.cmu.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

Re: Compiler Construction in Ada

[enterpoop.mit.edu!world!iecc!compilers-sender]

Hmm. We've had several rounds of language wars in this newsgroup. Perhaps
its time to have a round of parser wars :-)

Creating a shift-reduce parser for as non-trivial language is a pain in
the neck.  If you insist on doing it this way, then I agree, by all means
use a parser generator - in this group I hope that means using ayacc.

For Compiler Construction courses, it seems to me that there is a benefit
in teaching students how to make a parser from scratch, in just the same
way that we teach kids to do arithmetic manually before letting them loose
on calculators - so that they get an understanding of how it works. Given
the above, this seems to indicate using top-down methods - typically
recursive descent. Interestingly, the GNAT compiler will be using
hand-coded recursive descent, and very impressive performance stats have
been reported in this group. So this technique is of more than simple
academic interest.

I agree with previous posters that too much emphasis in compiler
construction courses can be placed on syntax processing. However, there is
one related topic that is frequently given insufficient attention, as far
as I can gather - syntax error recovery. It is perhaps a matter of taste,
and error recovery is certainly an art rather than a science :-) but I
believe that top-down parsing methods have a distinct edge here.
--
Andrew Dunstan
Department of Computer Science
University of Adelaide
South Australia
net: andrewd@cs.adelaide.edu.au
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.