Home > Archive > Scheme > October 2006 > Resources for a Compilers course.....
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Resources for a Compilers course.....
|
|
|
| .....of course the Compiler project is to be written in Java, but I am
old stubborn and foolish so I am here asking for pointers to Schemeish
resources and any other useful pointers.
| |
|
|
wooks wrote:
> ....of course the Compiler project is to be written in Java, but I am
> old stubborn and foolish so I am here asking for pointers to Schemeish
> resources and any other useful pointers.
I should clarify I am looking more for study materials to learn the
principles - of course I shall have to submit the project written in
Java.
| |
|
|
|
|
| Wolfram Fenske 2006-10-18, 7:04 pm |
| "wooks" <wookiz@hotmail.com> writes:
> wooks wrote:
>
> I should clarify I am looking more for study materials to learn the
> principles - of course I shall have to submit the project written in
> Java.
Compiler design is a rather large field, so you need to be a bit more
specific. If you are a complete newbie, Compilers: Principles,
Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi,
Jeffrey D. Ullman is probably the best place to start. Otherwise I
have some question:
What is it in specific that you want to know more about? Is it lexing
& parsing, i. e. converting the source code into an abstract syntax
tree (AST), optimizing (probably not), or code generation, i. e.
converting the AST into the target language, e. g. assembler or C.
What kind of language do you want to compile? Imperative, functional,
logical? Compilation strategies for these different paradigms are
very different, knowing how to compile a language like C doesn't help
you very much when you try to write a compiler for Scheme and the
other way around.
What syntax does your language have? Is it more lispy, i. e. hardly
any syntax at all or a more complex kind?
If you aren't allowed to use Scheme for the implementation, why are
you asking for Schemeish resources? How does that help you?
Wolfram
| |
|
|
Wolfram Fenske wrote:
> "wooks" <wookiz@hotmail.com> writes:
>
>
> Compiler design is a rather large field, so you need to be a bit more
> specific. If you are a complete newbie, Compilers: Principles,
> Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi,
> Jeffrey D. Ullman is probably the best place to start. Otherwise I
> have some question:
>
I am a compiler virgin but from all that I have heard about that book,
I probably don't have the math background to read it.
> What is it in specific that you want to know more about? Is it lexing
> & parsing, i. e. converting the source code into an abstract syntax
> tree (AST), optimizing (probably not), or code generation, i. e.
> converting the AST into the target language, e. g. assembler or C.
>
Here is the course syllabus.
Anatomy of a compiler The importance of compilers
Structure of a compiler
Analysis (lexical, syntax and semantic analysis)
Synthesis (intermediate code generation, optimisation and code
generation)
Compilers vs. interpreters
Lexical analysis (scanning) Tokens
Regular expressions
Finite state automata (deterministic and non-deterministic)
Translating regular expressions into finite state automata
Automatic lexer generators (JLex/JFlex)
Syntax analysis (parsing) Context-free grammars
Derivations and (concrete/abstract) syntax trees
Handling ambiguous grammars
Bottom-up parsing (LR(k) grammars, shift-reduce parsers)
Automatic parser generators (CUP)
Syntactic error recovery
Syntax-directed translation Syntax-directed definitions
Abstract syntax tree construction
Semantic analysis Symbol table management
Scoping and type checking
Basic implementation techniques (Visitor methodology)
Intermediate code generation Three address code
IR instructions
Translation methodologies
Code generation and optimisation Run-time storage organisation
A simple code generation algorithm
Optimisation of intermediate code
Optimisation of target code (Peephole optimisation)
> What kind of language do you want to compile? Imperative, functional,
> logical? Compilation strategies for these different paradigms are
> very different, knowing how to compile a language like C doesn't help
> you very much when you try to write a compiler for Scheme and the
> other way around.
>
Ok thats interesting to know that the techniques are not generic. We've
not yet been told what nature of language we will be writing a compiler
for. In all probability we will be asked to compile an imperative
language.
> What syntax does your language have? Is it more lispy, i. e. hardly
> any syntax at all or a more complex kind?
>
See above.
> If you aren't allowed to use Scheme for the implementation, why are
> you asking for Schemeish resources? How does that help you?
>
Because
1. I thought the principles involved were language agnostic.
2. I am willing to risk compromising my grade to get a more enjoyable
learning experience. Because we are I'm ashamed to admit a "Java
school" there is no flexibility in implementation language so I am
going to have to translate my work.
| |
| Wolfram Fenske 2006-10-19, 7:01 pm |
| "wooks" <wookiz@hotmail.com> writes:
> Wolfram Fenske wrote:
sh[color=darkred]
>
> I am a compiler virgin but from all that I have heard about that book,
> I probably don't have the math background to read it.
It's not heavy on math heavy. I guess what people mean by math is in
fact formal languages theory, in particular regular languages and
context free languages, and ways how to parse these classes of
languages. This is only important for the front-end of the compiler,
but depending on the instructor, this may be large part of the course.
Looking at the course syllabus you gave below, your course is no
exception.
The Dragon Book may focus more on theoretical aspects than other
books, but still, AFAIK it's the reference, and it covers most if not
all of what is mentioned in your course outline.
[=2E..]
> Here is the course syllabus.
>
> Anatomy of a compiler The importance of compilers
> Structure of a compiler
> Analysis (lexical, syntax and semantic analysis)
> Synthesis (intermediate code generation, optimisation and code
> generation)
> Compilers vs. interpreters
> Lexical analysis (scanning) Tokens
> Regular expressions
> Finite state automata (deterministic and non-deterministic)
> Translating regular expressions into finite state automata
> Automatic lexer generators (JLex/JFlex)
> Syntax analysis (parsing) Context-free grammars
> Derivations and (concrete/abstract) syntax trees
> Handling ambiguous grammars
> Bottom-up parsing (LR(k) grammars, shift-reduce parsers)
> Automatic parser generators (CUP)
> Syntactic error recovery
> Syntax-directed translation Syntax-directed definitions
> Abstract syntax tree construction
> Semantic analysis Symbol table management
> Scoping and type checking
> Basic implementation techniques (Visitor methodology)
> Intermediate code generation Three address code
> IR instructions
> Translation methodologies
> Code generation and optimisation Run-time storage organisation
> A simple code generation algorithm
> Optimisation of intermediate code
> Optimisation of target code (Peephole optimisation)
>
>
> Ok thats interesting to know that the techniques are not generic.
What I meant was that depending on the features of your language,
certain topics may never come up. Some expamples:
1. In a language with lazy evaluation, you have to work very hard to
make lazy evaluation fast. If your language doesn't have lazy
evaluation these techniques are not very useful.
2. If your language has closures (like Scheme or Common Lisp), you
need to know how to translate nested functions into a set of
non-nested functions and how to treat variables that the closure
has "captured" from its definition environment. In a language
like C, which doesn't have nested functions, you don't need to
worry about that.
3. In a language without automatic memory management, the whole
field of garbage collection doesn't concern you.
There is come common ground though. Lexing and parsing of course work
the same for all languages. Also, code generation for function calls
or access to local variables are pretty much the same in, say, C and
Lisp.
> We've not yet been told what nature of language we will be writing a
> compiler for. In all probability we will be asked to compile an
> imperative language.
There's a lot of literature about that because this is what most books
focus on. If you wated to compile a Lisp dialect, I would have
recommended =BBLisp in Small Pieces=AB [1]. Since Lisp is also what I'm
interested in, I could have given you some pointers about garbage
collectors and so on, too. I'm afraid I can't be of much help when it
comes to imperative languages, though.
>
> See above.
Then you need to know a lot about parsers etc.. But your course
covers all that, and so does the Dragon Book. Lisp is much easier in
that regard. You could easily write a parser by hand because the
syntax is about as simple as possible.
>
> Because
>
> 1. I thought the principles involved were language agnostic.
No, see above.
> 2. I am willing to risk compromising my grade to get a more enjoyable
> learning experience. Because we are I'm ashamed to admit a "Java
> school" there is no flexibility in implementation language so I am
> going to have to translate my work.
I think you should wait and see what the actual assigment is. Writing
a complete compiler for a useful language is a lot of work, so you'll
probably just have to extend an existing compiler with a new statement
or so.
Wolfram
Footnotes:=20
[1] <http://www-spi.lip6.fr/~queinnec/WWW/LiSP.html>
| |
| Emilio Lopes 2006-10-30, 7:31 pm |
| wooks writes:
> Wolfram Fenske wrote:
[color=darkred]
> I am a compiler virgin but from all that I have heard about that book,
> I probably don't have the math background to read it.
On the field of parsing there is also "Parsing Techniques - A Practical
Guide". The first edition is freely available on-line from:
http://www.cs.vu.nl/~dick/PTAPG.html
--
Emílio C. Lopes
Munich, Germany
|
|
|
|
|