Quizzes

During the course of the semester, there will be a number of short quizzes. You are expected to do these completely on your own with no help from anyone. Further, you are expected to not show your work to anyone else besides the grader or me until the quizzes have been graded and returned.

The quizzes will be available online and will generally have a set period of time to complete. Normally the quizzes will be available online and you will have approximately a day to complete a quiz. Details will be in the instructions for each quiz.

Notification of a pending quiz will be done through the class web page and mailing list. You are responsible for checking both on a daily basis. If you miss a quiz, you get a zero on it. Right now, the schedule is as follows:

Availbility Date Link Points Comments
Thursday, 9/5/2002 Quiz 1 50 Solution
Tuesday, 9/24/2002 Quiz 2 50 Solution
Tuesday, 10/8/2002 Quiz 3 50 Solution
Thursday, 10/24/2002 Quiz 4 50 Solution
Tuesday, 11/19/2002 Quiz 5 50 Solution

Class will not meet on days that a quiz is available. You should use the class time to do the quiz. Each quiz will be short and you should be able to do it in about 75 minutes.

Quiz 1 (9/5/2002)

This is to be done by yourself without external help. Please spend no more than 75 minutes working on this quiz. Please email me your solution with the subject CS 441 Quiz 1 no later than 2pm on Friday, September 6. Remember to send a copy to your own email address. Send a plain text file.

Complete the state example from pages 11-12 in the lecture notes. Use the style in the notes. The notes are online at

http://www.mgnet.org/~douglas/Classes/compilers/2002f-notes.html.

Do not use a computer program to complete the code.

Solution

You needed to work out all of the possibilities that a single code code run into. For the diagram in question, this is small. Realistic languages can have 10,000+ states unless special processing is used. My solution is a C code: q1-soln.c

Amazingly, it seems to work for simple cases, but can be broken without too much trouble, e.g., use a variable name of length 1025 characters): .

The production of the transition table and basic code took a few minutes. However, getting a working, commented program took hours. Lex would have been a lot quicker. I did not expect to receive any working codes, just pseudo code in the spirit of the lecture on 9/3 and a description of the transition table.

Grading

Since this was the first quiz of the course, I was fairly lenient on certain parts of the quiz. I would appreciate it if you would read the instructions and follow them. For example, use the specified subject (in this case, CS 441 Quiz 1), not something creative or missing entirely. I get over 100 messages a day. Using a uniform system helps me find your message and give you credit. Also, having the date and time correct on your computer makes a big difference. A message from the year 2000 shows up in a different folder and I just might not find it before the cutoff time.

So, the way to lose points on Quiz 1 included the following:

Points

For what

10

No transition table
10 Actions make too little sense
20 No significant actions
30 Just copied all or part of class notes with no real additions

The scores were 50 (5), 40 (11), 30 (4), and 20 (3).

Quiz 2 (9/24/2002)

This is to be done by yourself without external help. Please spend no more than 75 minutes working on this quiz. Please email me your solution with the subject CS 441 Quiz 2 no later than 2pm on Wednesday, September 25. Remember to send a copy to your own email address.

Please refer to page 23 of the class notes. You are going to write a lex program (call it lex1.l, lex one dot ell) and then modify it twice. Your program should begin with the lines

letter                   [a-zA-Z_]
digit                     [0-9]
letter_or_digit     [a-zA-Z_0-9]
white_space        [ \t\n]
blank                   [ \t]
other                   [^a-zA-Z_0-9 \t\n]
 
%%

Now define 10 keywords. They can be anything, but should be 2-10 characters long each. (You do not have to use words from a programming language, so be creative.)  For my solution, I used the same action of

{ return process_keyword(); }

Next define all of the following operators:

(, ), ++, <=, >=, !=, =, <, >, +, -, *, /, %, |, &, ||, and &&

I used the same action for each operator:

{ return process_operator(); }

Then use the definitions at the end of page 23 to define name, number, white space, and other. Do not write any C code to actually implement the rest of the lexer. Run lex and determine how many table entries are needed.

Now copy lex1.l (call the new one lex2.l). Eliminate the explicit definitions for keywords and process them as part of the name definition. Run lex and determine how many table entries are needed. It should be quite a bit lower.

Now copy lex2.l (call the new one lex3.l). Eliminate the explicit definitions for operators and process them as part of the other definition. Run lex and determine how many table entries are needed. It should less yet.

Turn in the the three lex programs and how many table entries were needed for each.

Solution

The actual lex code with my 10 keywords is contained in q2a-soln.l. There are three variants of the lex program:

PNG type file Out of curiosity, I tried 20 (839 table entries), 30 (1048 table entries), and 40 (1250 table entries) keywords. The ratios of the number of table entries when there are operators or not operators is summarized in the graphs (click the thumbnail for a readable set of graphs).

To get the second program, eliminate the keywords (q2b-soln.l). To get the third program (q2c-soln.l), eliminate the operators, too. There are clever tricks to get even fewer states. One is to use the | operator (q2aa-soln.l) to collect all of the patterns that call the same action.

Grading

There were a lot of ways to lose points on this quiz, such as

Points off For what
5 No subject
5 Missing { } for actions, get radically wrong # of table entries
2 Wrong file extension (e.g., lex1.1 instead of lex1.l)
5 Missing some actions (e.g., for numbers or ids)
2 Missing number definition in part 2
5 Left keywords in lex2.l and/or lex3.l with same action as an id
2 Missing %{ and/or before C code in first part
3 Blank line between operators and last set of definitions caused error; fix is to put all actions inside of {} or eliminate blank line
5 Less than 10 states
5 No action for {other}

The number of states for each part was also interesting:

File States
lex1.l 650, 651, 687, 690, 694, 697, 702, 708, 711, 723, 729, 736, 764, 782, 790, 801, 848
lex2.l 412, 423, 427, 433, 457, 484, 487, 529, 634
lex3.l 300, 308, 316, 323, 351, 358, 439, 529
Scores ranged from 36 to 50 with 45 appearing as the mean.

Quiz 3 (10/8/2002)

This is to be done by yourself without external help. Please spend no more than 75 minutes working on this quiz. Please email me your solution with the subject CS 441 Quiz 3 no later than 2pm on Tuesday, October 8. Remember to send a copy to your own email address. Note: If you use the email link in this paragraph, it will put the correct subject in for you.

Please refer to pages 47-48 of the class notes. You are going to modify the desk calculator on those two pages to deal with errors gracefully. Using just the error terminal symbol and the yyerrok action, fix the grammar so that the interactive desk calculator handles all errors. See the Notes web page for links to the already typed up lex and yacc files. If there are any unfortunate typos, please fix them.

I am sure you can book search this one. Please do not. You will learn something from the experience. You should send me your lex and yacc files and an input script that is full of silly errors and some legitimate input.

Solution

The solution codes are those of Mr. Stewart and can be found on the notes page. All of you noted that the given text files had errors in them. At least one was noted in class in the lex file. Some of you started from scratch and produced working codes. That was OK, but not as good as fixing my files. Not many of the submitted solutions work.

Quiz 4 (10/24/2002)

This is to be done by yourself without external help. Please spend no more than 75 minutes working on this quiz. Please email me your solution with the subject CS 441 Quiz 4 no later than 2pm on Friday, October 25. Remember to send a copy to your own email address. Note: If you use the email link in this paragraph, it will put the correct subject in for you.

You are going to write a lexer and parser for dealing with command arguments to a dinosaur type computer program that is meant to be run by typing to a command line interpreter. Your arguments will be of the form

-arg value

where arg is a character string and value is something that is dependent on what arg wants (string, integer, or floating point). Your codes should be easily extensible so that new arguments can be added in seconds, not minutes or hours.

Your code will read lines of code. The first string on a line is the command name. After that are arguments. You should be able to process multiple commands (one per input line). Given the input line

foobar -echo this_word_and_note:_no_whitespace_in_it dval 3.1415e0 -ival 31415

your output should be something like

Command:  foobar
Argument 1:  String: -echo this_word_and_note:_no_whitespace_in_it
Argument 2:  FPNum: -dval 3.1415e0
Argument 3:  Int: -ival 31415

If there is an error on input (e.g., no value after the last argument), you should print an error message and continue. Note: You have to correctly identify each arg's data type, too, not just echo the value. Your parser should use the functions atoi and atof to translate the numbers before printing them.

You probably want to start with the lexer from Quiz 3 (see Notes). However, you need to modify it so that it correctly swallows the -arg and value parts of the command line and returns something useful. Do not be fancy, just quickly make it work. You are going to have to know which arg wants a character string, integer, or floating point number to get the output right.

Include each of the following arguments in your lexer/parser:

String        -echo, -filename, -ofile, -ifile, -name
FPNum    -dval, -tol, -minval
Int            -ival, -iters, -restart, -maxtime

Use the q4.makefile so that we all are using the same file names. I have also provided a sample input file.

Solution

You needed to recognize that you were not writing a desk calculator. The commands at the beginning of an input line are just a string. You needed to recognize error situations and print a message. You were supposed to use my Makefile, not create one that added to the complexity of the quiz.

There were several good, easy to extend lexer-parser combinations. I am posting one here as soon as I determine what happened to four of your exams, which appear never to have been delivered by email.

Grading

There were a number of clever ways to lose points. This is the list.

Points

For what

50

Nothing turned in
50 0 length tar file (try again)
5 Error handling almost right, but not quite
5 Basically works except for end of line problems
20 Lexer OK, but parser is clueless or missing entirely
25 Had to guess at files (use tar next time), does not compile
5 Added termination symbol
5 uh-oh incorrectly parsed (command name is just a string)
0 Had to remove trailing Control-M's on every line (next time its points off)
5 Does not use standard input
5 Period in string mistaken for starting a number
5 Period in string mistaken for starting a number and many more problems)

The scores were 50 (5), 45 (2), 40 (2), 30 (2), 25 (1), 0 (1), and missing (4).

Quiz 5 (11/19/2002)

This is to be done by yourself without external help. Please spend no more than 75 minutes working on this quiz. Please email me your solution with the subject CS 441 Quiz 5 no later than 2pm on Wednesday, November 20. Remember to send a copy to your own email address. Note: If you use the email link in this paragraph, it will put the correct subject in for you.

We are going to have some fun on this quiz. The class is going to write a large part of a code generator as a group. Each of you will be assigned one small piece to do. If everyone does his or her piece, we will have most of a working code generator, at least in theory. This assignment comes in two parts:

  1. Send me an email with your name (spelled correctly) to me acknowledging that you will do your part. (10 points).
  2. Do your piece of the code generator listed below. (40 points)

From the class notes (circa page 107), we will do most of the Itti language using a stack based approach. It is not terribly efficient, but it will be quick and dirty. Sometimes, the latter is what works best. Elegance should be employed when there is time and resources available. Otherwise it is usually not worthwhile.

Let me remind you of the notation. All variables will be simple ones that we will reference directly. So the variable A or the constant 3.1415 will be used in the text. (In your homework 3 assignments this will not be the case.)

Examples

Let's look at a few example from the notes (circa page 108). T refers to a data record with a Val subrecord.

Case Var:      Write( Mov -(SP),, T.Val)

Case *:         Gen(A)
                     Gen(B)
                     Write( Mov R1,(SP)+)
                     Write( Mul R1,(SP)+)
                     Write( Mov (SP),R1)

Case +:         Gen(A)
                     Gen(B)
                     Write( Add (SP),(SP)+)

Note that all results end up in (SP), the top of the stack.

Your Assignments

So we need a few more operators. This is where you volunteered (e.g., when you signed up for CS 441G) to complete your part, which is

Ok, this should be simple enough. Do not make it hard. (It is not meant to be hard.)

I want a simple document:  plain text is fine or some sort of Evil Empire document (i.e., Adobe or Microsoft). Your code should look like what is in the Examples section. I want a case statement with calls to Gen and Write. Explain in clear English what you are assuming and what your code is supposed to do. Provide a simple, worked example.

Note: There is no actual programming in this quiz.

Solution

The solution I am providing is not necessarily the only approach. In particular, I did not count off for quite different solutions that are compact.

Grading

There were a only a ways to lose points. This is the list.

Points For what
10 Did not do Part 1
10 No assumptions
10 No example
10 Code snippet somewhat wrong
5 Misinterpretation of an operator