On 08/20/08 11:43, Derek Elkins wrote:
On Wed, 2008-08-20 at 16:03 +0200, Johannes Waldmann wrote:
Hello.
I plan to give a course in compiler construction, using Haskell as the implementation language (not as source or target language).
Something along these lines: 1. combinator parsers (Parsec), 2. simple interpreter (arithmetical expressions) 3. add algebraic data types, functions 4. type checker 5. code generator. Ideally, 2..5 would be using the very same tree traversal code and just change the monad for evaluation.
Any comments appreciated. Have you given such a course? Taken?
[I've replied to Haskell-Cafe which is a better list for this discussion.]
2 & 3 are going to have different trees so using the same tree traversal code would require some finesse, though the code for 2 should only need extension not change.
One thing you may want to look at is attribute grammars which can be cast into a monadic framework and gives a natural example of using the backward state monad and allows you to connect to other formalisms used for compiler construction.
Could you give some examples or links or references?
Another possibility is abstract interpretation. Both code generation and type checking can be viewed as examples of abstract interpretation (as well as, of course, actual interpretation.) Also many analyses fit into the model of abstract interpretation.
Links or references? [snip] I'd also would like to see First and Follow sets: http://www.jambe.co.nz/UNI/FirstAndFollowSets.html calculated in haskell. I'd think it would be natural since, AFAICT, the calculation of the First sets is a homomorphism on the algebra of grammar expressions. IOW FIRST( x <|> y ) = set_union(FIRST(x),FIRST(y)) and I *think* maybe a similar definition can be made for the sequencing operator. Since I've seen haskell associated with algebras and expecially monads, I guess haskell would be especially adept at this. WARNING: I've not written a line of haskell code. -regards Larry