CS444 Exams

    5 April 2004, mid-afternoon

Patrick wanted me to post the CS 444 exams I found, incase they got taken down. Here they are: 1986, 1987, 1993, 1994, 2001.

On a scale of 1 to hard, I’d say these exams are hard. I hope the one we have to write tomorrow is easy, but I have my doubts.

Useful information about the SPARC architecture and the assembly language can be found here.

Comment |  

Compilers

    5 April 2004, the wee hours

I am amazed at how much of this term I have spent working on, or thinking about, compilers. I have one last thing to worry about in that class, the final exam, which I will write this tuesday. Since handing in the last assignment I have done absolutely nothing useful with my time. I wish I had at least spent some of it reading. The old exams I’ve read over look hard. God damn, when will it end.

Comment |  

And in the End.

   30 March 2004, early morning

And that is that. We’re done. In a half hour I will have been up for twenty-four hours. I’m tired, but it is raining outside, so i’ve decided to stay in the C&D with patrick.

What can I say? If I had to do it all over again, I probably would have taken Networks. No, I suppose I am joking — a little bit anyway.

Compilers has definitely been an experience.

update: I woke up at 8:30 yesterday, so I could make it to my Marxist Theory class. I got home today at 11:15, just before lunch. (My plan is to take a shower and sleep.) I’ve missed all my classes for today. My last class as an undergraduate should have been STAT 231, instead it will be PSCI 321. I kind of like it that way. I didn’t think about it at all till I started walking home, listening to no surprises by Radiohead.

Comment [3] |  

A3.

   30 March 2004, the wee hours

CS 444 / 644 Assignment Part 3 Due March 30, 2004 Complete your Ada/CS compiler by implementing a code generator and run-time environment for the SUN.
Fuck you too, Cormack.

Comment [1] |  

Closer.

   29 March 2004, the wee hours


        .file "test/code/simple_assignment.ada"
        .global main
main:
        save    %sp, -96, %sp
        sub     %sp, 4, %sp
        mov     10, %r16
        sub     %fp, 0, %r17
        st      %r16, [%r17]
        mov     20, %r16    
        sub     %fp, 0, %r17
        st      %r16, [%r17]
        nop
        ret
        restore

Assembly has never looked so good.

Comment [2] |  

Another Long Night.

   28 March 2004, late at night

(11:30 pm) I’ve basically spent the entire day at my desk. I woke up late, at 1:00 or so, and started programming again. 10 hours later, I’m still at my desk, and I’m still programming. I wish there was more progress. It seems like things are moving so slowly.

(1:00 am) I am feeling stressed.

(1:40 am) Here is some useful information for those of you who aren’t in CS. A lot of the times when you program in C/C++, you will encounter one of the following two runtime errors:

  • Segmentation fault: You are breaking the permissions of the memory pages. Common reasons are: You are writing to read-only memory, including the read-only data or the text (code), You are reading or writing the first page of memory, typically because you are dereferencing the NULL pointer, Your data and stack segments have overlapped, typically because you have recurred too much.
  • Bus error: You are breaking the expected memory alignment, typically trying to read or write a word at a non-word-aligned address. 1

Our compiler currently has neither error.

Comment [1] |  

A Long Day.

   27 March 2004, terribly early in the morning

It’s four in the morning, and I’m just about to go to bed. This is going to be a horrid weekend I think. The compiler does a little bit more then it did yesterday, but we still have so much to do.

Comment |  

The Long and Winding Road.

   25 March 2004, mid-morning

I slept through my Compilers class today. Cormack has gotten better at lecturing in the past few lectures I’ve been to, but he’s still a bit too rambling for my liking. Nevertheless, I still think he is a very nice professor.

Our compiler is doing a lot more stuff now. I think we have pretty much completed A2 now. We do analysis for almost every part of Ada/CS. There are holes here and there, I think the most obvious two are subtypes and function overloading. Regardless, it’s quite impressive watching it determine that A(1,1)(1).B(1)(1) is a function that returns an array of records that contain an array of arrays. Well impressive for me anyway.

We have 5 days to get the compiler to make code. I’m hoping we can get it all done. I have faith. We’ll have to wait and see.

Comment [3] |  

IGU

    2 March 2004, the wee hours

There comes a point when you just have to say, “fuck it.” I am at that point. It isn’t that late just yet, a little past 1:00 in the morning, but a week of this is too much. Hopefully we can make up all the marks we’ll lose on this assignment when we do the next one. The last assignment is worth half of our mark.

I now know that writing a compiler is a lot of hard work.

For those who want to know, this assignment we were asked to do the semantic analysis needed to process a Ada source file. That means we have to make sure the file makes sense. Examples of things needed to be done are ensuring variables are given unique names, that the scoping rules for Ada are followed, that types are created properly, that expressions are valid, that statements are used properly, etc., etc. We also had to implement a better error-recovery strategy in our parser, as we were just terminating when we encountered our first error.

I’d say we did about half the stuff we were supposed to do. Right now our compiler is 36000 lines of code. I think 25000 of that was generated by programs we wrote.

Comment [4] |  

Quasi Works?

    1 March 2004, lunch time

The compiler does some things, and doesn’t do others. We have a day to get it to do everything except spit out code. Whether it’ll happen we’ll have to wait an see. There is still some much to do. Patrick, the recent addition to our compiler group, has the acronym IGU next to his MSN name all the time. I asked him what it meant, since I was curious why it was always there next to his name. He told me I would reach a point where I would know what it meant. Kumar told me late last night that it meant “I Give Up”. That made me chuckle.

Comment |  

A Night at the Lab.

   29 February 2004, terribly early in the morning

I left for school at 11:30 at night. Patrick was working on his networks assignment in one of the second floor computer labs, so I thought i’d join him. It is a little depressing, walking to school so late at night and watching people pass you by as they walk in the other direction, heading home. I am reminded of when I was in second year, working at school late at night with Ju-Lian and Annie on CS 241 (the baby compilers course). We used to spend the whole day in the stankest lab the school had. I’m not sure why we liked that lab the best. A year or so ago, the school renovated the lab and turned it into another PC lab. Such a shame. I digress. This second assignment is still a bitch and a half. It’s due tuesday.

Comment |  

Bottom-Up? Top-Down?

   28 February 2004, terribly early in the morning

A parser will take an input source file and produce a parse tree. The parse tree can then be used to do some context-sensitive analysis of the language, i.e. making sure that variables are declared before they are used, or that break statements occur within loops.

Usually this type of analysis is done by attaching attributes to each of the nodes in the parse tree, and calculating the values of these attributes using information from the lexer, and the structure of the tree.

You can compute some attributes in a bottom-up fashion. That is, the attribute at a particular node is computed using information from its children. Such attributes are said to be synthesized attributes. We can do a bottom-up walk through the tree using a depth-first search type traversal. You can compute some attributes in a top-down fashion. The attribute at a particular node inherits its value from its parent. These attributes are referred to as inherited attributes. We can do a top-down talk through the tree with a breadth-first search type traversal.

Sometimes things get more complicated then that. Sometimes things get much more complicated then that.

Comment |  

Compilers and Macs.

   26 February 2004, early morning

My compilers class is currently filled with at most 20 people. Of those, 4 of us are typing away on our Macs as the prof speaks. Pretty high ratio considering Macs are supposed to have a 3% market share or something like that.

Comment [10] |  

God Damn, Compilers is Hard.

   26 February 2004, the wee hours

I don’t know if hard is the right word, but compilers is definitely not easy. CS 444 is slowly consuming more and more of my time. The worse part is that it seems like I have so little to show for all my effort. Thankfully Patrick, who joined Kumar and I, seems to be infinitely more productive then the both of us.

What’s new with our compiler? Well the one that is working right now is the new and improved error handling. (We use the Burke-Fisher algorithm to catch errors.) You can also perform some very basic analysis of the program.

We have so much left to do it seems. The next few days should be long.

Comment |  

Assignment One Done

    3 February 2004, early morning

I arrive at school to be told the compilers class has been cancelled. Normally I wouldn’t care, but at 8:30 in the morning that is some cold shit. I emailed Kumar telling him not to come to class, printed out our documenatation, gave it to the angry CS secretary, and am now sitting in the computer lab. I’m apparently supposed to read four papers on error recovery and detection when you are parsing. What a dis.

Comment |  

Done?

    3 February 2004, the wee hours

Kumar is putting the final touches on the document we need to submit for compilers. The afternoon was spent hacking together a symbol table that we hope works well enough for the assignment. I’m hoping everything works! For the next assignment we have to do the serious semantic analysis, and the symbol table stuff we did for this assignment will probably be scrapped.

Comment |  

Two More Days

    2 February 2004, late evening

Our assignment is due in two days. We are quite close to completion, though there are still two components we need to get working. First, we need to make a symbol table. This shouldn’t be too difficult, and I think Kumar is almost finished implementing one. The second task, which will be trickier to do, is error recovery. Right now, when an error occurs, the program prints an error message and terminates. Ideally, the behaviour our compiler should exhibit is some sort of recovery strategy that allows it to keep parsing, looking for more errors. I hope we can get everything done in time.

Comment |  

Spoke Too Soon

   27 January 2004, lunch time

Damn it, I spoke too soon. The parser is a little bit on the broken side. Hopefully I can figure out what’s wrong and fix it quickly. Kumar is working on the symbol table now, though apparently another problem is that the huge parse table won’t compile for him.

Comment |  

Parsing, Baby!

   27 January 2004, late at night

Our compiler seems to be parsing stuff now. We need to do some serious testing to make sure this is indeed the case, but I am hoping that there are no problems. Kumar is supposed to be working on a testing document now.

I used a program called ilalr to determine the states of a DFA that we could use to parse the context-free grammar. I had to write a program that would convert the output of the program into code I could use to make a parse table. The parser implemented is an LR-parser, which people usually refer to as a bottom up parser because of the way the parse tree gets built.

Kumar and I still have to write the code needed to produce a basic symbol table, and I think we need to improve our error handling. Hopefully that isn’t too much work.

Comment |  

Grammars

   21 January 2004, the wee hours

You specify the syntax of a context free language with a context free grammar. Most programming languages correspond to a special class of context-free languages known as LALR languages. I have spent the past few days trying to write a working Ada/CS grammar, only to discover one laying around on the internet that works just fine. After getting rid of all the Yacc-isms I was left with something useful. I can’t believe I wasted so much time these past few days.

I am now trying to parse the output of this program called ilalr, which takes as input a LALR grammar and returns information that can be used to build a program that parses the grammar

Compilers is probably going to be a very hard course.

Comment |  

Scanners

   14 January 2004, mid-afternoon

I met with Kumar today to work on our compilers project. We think we have sketched out what we need to implement in order to recognize the tokens in our language.

For those who don’t know, when you write a computer program, the first part of compilation involves a program called a scanner breaking your program up into individual tokens, which are then fed to a parser and processed further. For example, a C code fragment like “x = x + 1” would become something like “ID ASSIGN ID PLUS INT_LITERAL”. Additional information like the name of the identifier and the value of the integer literal would also be stored in the token, to be used later when compiling. So now you know a little bit more about compilers.

It is so cold outside. I am in no mood to walk back home, but will probably do so shortly.

Comment [5] |  

Compilers

   13 January 2004, late evening

I have started reading the definition of the language we are supposed to write a compiler for, Ada/CS. Ada/CS is a subset of the language Ada, which was developed for use by US department of the defense. Compilers looks like it will be a bitch of a course.

Comment [1] |