Homework

Homework can either be printed out and turned in to me in class, or emailed to me (ztomasze@hawaii.edu). You may either attach the necessary files or paste them into the email itself. Please do not zip your files. You should send me both your code and example output for a couple test cases (as appropriate).

Each complete, on-time homework is worth 10 points. Partially incomplete or incorrect homeworks may receive a 5. Homework may be turned in up to 1 week past the due date at one point off. Homeworks are not otherwise graded, though you must complete them in order to pass the course.

Projects are properly graded. Note that projects have a different late policy. Projects are deducted 10% for each class meeting they are late. Thus, if a project is due Tuesday, you will be deducted 10% the following Thursday, 20% (total) the following Tuesday, and so on. You still have until midnight to submit it on whatever day it's due.

12 May (11:59pm) -- Final cut-off for submission of all lost/missing work.

PROJECT #5 (Due: 12 May - extended)

Write a compiler that translates the "airplane" language into assembly code.

Tip: Be sure to check out the sample compiler. If you have trouble with the links to the lex and yacc files, they are at lexair.txt and air.txt.

Hint: To code the fire function, you probably need to know the current location of the plane. You should probably save the current position of the plane in the plane function using a couple global, "system" variables. These variables can either be declared by your compiler (created at the same time it creates the beginning of the .DATA section); or they can simply be part of a common .DATA section used by your plane and fire subroutines.

Extra Credit Project (optional) (Due: 12 May - extended)

Write an airplane arcade game.

FINAL EXAM: Tues, 09 May. Noon to 2pm.

HW #25 (Due: 02 May)

Supply in hex the machine code for:
a) sub dx, bx
b) adc cx, sumz (where sumz has offset 2A3Bh)

Solution:

a) 001010 11 11 010 011
   => 2BD3h
b) 000100 11 00 001 110 00111011 00101010
   => 130E 3B2Ah

HW #24 (Due: 02 May)

Minimize the states in the following DFA:

Solution:

       a,b,d,e,f,g,h      c
On 0:     /       \       |
       a,b,e,g,h   d,f    c
On 1:   /  |   \   |      |
       g  a,e b,h  d,f    c

On 0 and 1 again: no change.

HW #23 (Due: 27 Apr)

Provide NFAs mechanically constructed (that is, combine the 7 basic building blocks given in Set27 slides) for:
1.) (00|11)*
2.) a*|b|c

3.) Construct DFAs for 1 & 2 above.
4.) Construct a regular expression equivalent to the DFA given below:

Solution: here.

HW #22 (Due: 27 Apr)

Write a floating-point calculator interpreter. Please include some sample output when you submit. (I recommend using the string given on the homework page to test the calculator!)

Hint: I recommend starting with the framework given for a calculator that handles only integers and addition.

• Get that to compile and work. Explore the code and see how it works.
• Add the other three arithmetic operators. Remember operator precedence! (Consider #5 of HW19 if you're stuck on this.)
• Then add support for parentheses.
• Finally, expand the definition of a number to allow for floating point. (Remember that atof function.)

Tip: Blank lines in the lex rule section should be completely blank--no spaces, tabs, or similar white space. If your lex file gets turned into yy.lex.c okay, but then you get a bunch of odd .l file errors when you try to compile, check this.

Tip: Watch out for macros and how they get expanded. Remember that macros are only glorified cut-and-pastes. If you have this macro:

M   [eE][0-9]

and use it in a expression like this:

...{M}?

it will get expanded like this:

...[eE][0-9]?

Note how only the last element of the M macro becomes optional. (This is a common evil of macros--it's hard to see the code that is going to reach the compiler just by looking at the macro invocation.) A fix for the M macro here would be:

M   ([eE][0-9])

This doesn't mean you should go crazy with the parentheses. It just means you should give a little thought whenever you use a macro as to what your code will look like when the macro is expanded. (Again, this not always an easy thing to do!)

Solution: calc.l, calc.y, and hw22output.txt

HW #21 (Due: 20 Apr)

Supply a regular expression for strings of the alphabet {0,1} for the language of all strings:
1) that do not end in 01
2) that contain an even number of 0s
3) in which every 0 is immediately followed by 11
(This is 3 separate problems.)

Solution: hw21.txt

HW #20 (Due: 20 Apr)

Counting vowel-consonant pairs. Send me the output of both counter.l and of your vowel-consonant counter.

Hint: Remember, if you don't have a rule for a certain character, lex just prints it to the screen. This is why it was noted in class you often have a rule for "\n" and ".".

Tip: I don't mind if you do this assignment on uhunix. I don't know if there will be important differences in later homeworks between the PC and unix versions. (If I discover any, I'll let you know.) We might later be using flex and bison, which can be found on uhunix in /usr/uh/unsupported/. As the directory name says, you're on your own when using these programs.

Solution: hw20.l and hw20output.txt

HW #19 (Due: 18 Apr)

Grammar homework -- 6 problems.

Tip: For problem #3, the grammar should literally produce all the possible even integers (positive only, if you want). It should not produce math formulas that evaluate to even integers.

Solution: hw19.txt

HW #18 (Due: 13 Apr)

Parse "a*a+a".

Solution: hw18.txt

HW #17 (Due: 11 Apr)

1.) Show the derivation and syntax tree for "the man pushed the poor boy", based on the grammar given in the beginning of the Set24 slides.

2.) Can you derive "the man pushed the poor pretty cat" from the grammar? (Show/explain why or why not.)

Solution: hw17.txt

PROJECT #4 (minor) (Due: 04 Apr)

Play a tune. Write a program that uses sound.asm (found in the Example) to play "Mary had a little lamb". The sheet music can be found here.

23 Mar: Midterm Exam

PROJECT #3 (minor) (Due: 21 Mar)

Euler's Extended Algorithm: Write a program to evaluate the recursive function Euler(a, b, x, y, d) where for any a, b, the function (on termination) sets x, y, d such that xa + yb = d (where d is the GCD). Note that you will need to use call-by-reference. See Set19 slides for more on the algorithm.

HW #16 (Due: 14 Mar)

Intro to Masm32. Write the two programs described.

Send me your source code and screenshots of your two windows. (Examples with different window titles below.) (Screenshot directions were given in HW14.)

Tip: If you have trouble opening the .chm file (as in it opens, but none of the pages can be found), download the file to your desktop. Right-click it and go to Properties. Click the Unblock button and hit OK.

Examples/Solution: hw16first.png and hw16window.png.
If you want to demonstrate that you positioned your window at 20x10, you can send me a full screenshot (like this, shrunk 50%), but it's not required.

PROJECT #2 (Due: 14 Mar)

Draw a plane that moves with the mouse, as described.

10 Mar: Last day for restricted withdrawals (with "W" grade)

HW #15 (Due: 09 Mar - extended) -- OPTIONAL

Write a TSR that hijacks the function keys.

Since it's a little hard to demonstrate the output for this one, just tell me how much you got to work. How far in this progression did you get?

1. You can mangle vector 09h, but can't prove your TSR is resident: After you run your program, nothing you type at the command line appears on the screen.
2. The TSR is resident and intercepting keypresses: You can get it to print something (anything) when you press any key (even if only for the first key).
3. The TSR can call the normal keyboard handler: What you type shows up on the command line while your TSR is intercepting keypresses (even if the TSR does nothing else because you commented-out all the printing code).
4. Both prints and calls: Prints something when you press a key, and the character shows up on the screen normally.
5. The TSR can differentiate keypresses: Can consistently print different things based on different keys pressed.
6. The TSR can recognize function keypresses: Prints "HI!" for F1 and "BYE" for F2
7. The TSR meets all the assignment requirements: You can stop printing by pressing F3.
8. You can turn printing on again by pressing F3 again.
9. Your TSR does all this without crashing after 20 or 30 keypresses. (Try running one of your previous homeworks while your TSR runs.)

Help: TSR Walk-thru
Tip: Bugs and Anomalies I've discovered (optional)

Tip: Don't "push cs, pop ds" in the resident part of your code or it will start crashing. However, since you are then not initializing ds, you can't refer to it in your code. When you print your messages with int 10h, fn. 13h, copy cs (not ds) into es. (bp should still hold the offset of your message to print, as normal.) [Tip derived from above Bugs page.]

Solution: hw15.asm

PROJECT #1 (Due: 28 Feb)

Draw a house, as described.

It seems you cannot take screen captures of DOS graphics mode, so no capture is required of your code. Just send me the source code.

Tip: When you run in graphics mode (13h), your command window usually goes to full screen. Switching back to text mode (03h) at the end of your program will make sure you get a readable command prompt back when your program quits. If your command window is still fullscreen, Alt + Enter will restore it to window-size, Alt + Tab will let you switch to a different application window, and just typing "exit" will let you quit.

Tip: You cannot have duplicate labels in your program. If you expand a macro with a label in it (such as when your macro contains a loop), you will get an error like this:

 Assembling: proj1.asm
proj1.asm(25) : error A2005: symbol redefinition : v_again
 vert(4): Macro Called From
  proj1.asm(25): Main Line Code

To avoid this, declare your label LOCAL at the beginning of your macro with the line LOCAL label_name. When the assembler expands your macro, it will replace each instance of a local label with a unique string. See section 8.1.4 of your textbook for more.

Tip: In graphics mode 13h, pixel colors are specified according to a palette. Although it is possible to display 64^3 (ie, 2^18) different colors in this mode, only 256 (2^8) different colors can be on the screen at one time. It is possible to change what colors are in the palette, but the details of doing so are beyond this course.

However, for your projects, it might be handy to know what colors are available. The first 16 colors are the same as they are in text mode. In other words, the lower 3 bits (bits 2,1,0) correspond to RGB and bit 3 determines intensity. Setting bit 4 gives you a 16-color greyscale. Beyond that, the indexing doesn't make much sense, and there are some duplicate colors. To see all the colors available in the default palette (given in order, so you can figure out what the corresponding value would be), you can run palette.asm

HW #14 (Due: 16 Feb)

Video Text. Draw the described red-on-black square in text mode (03h).

Hints:

• To get a "square" you will probably need twice as many characters for the width as you do for the height.
• If you access video memory directly, remember you're dealing with words, not bytes, for each character. (This is especially important if you're incrementing di manually.)
• Remember the INT 10h functions 02h and 0Ah if you don't want to mess with memory directly. It's more work (longer code), but it might be easier.

Screen shot:

You can't "Mark" and cut+paste from the graphical text mode. Instead, you'll have to take a screen capture in order to send me your output. To do this:

1. Press Alt + Prt Sc (or whatever your Print Screen button is labeled--found near Scroll Lock and Num Lock). This will copy an image of the currently selected window to your clipboard. (Just hitting Prt Scrn by itself will get you a capture of your entire screen.)
2. Open an image-editing application of some sort--like Photoshop, The GIMP, or a recent version of Paint (found in Windows under Programs -> Accessories).
3. Paste into a new image.
4. Save as a GIF, JPEG, or PNG image. Do not send me BMPs or other file formats! Your file shouldn't be larger than about 50KB.
5. Done!
6. Let me know if you have questions or run into problems with this. There's an example of what you're going for below, under Solutions.

Solution: hw14.asm and hw14output.png

HW #13 (Due: 14 Feb)

Floating Point. Compute the volume of a sphere as described.

Solution: hw13.asm and hw13output.txt.

HW #12 (Due: 14 Feb)

File I/O. Print a file to the screen as described.

Solution: hw12.asm and hw12output.txt.

HW #11 (Due: 09 Feb)

Macros. Again, includes two parts: exercises (A) and a program (B).

Solution:
Problems: hw11prob.txt
Code: hw11.asm
Output: hw11output.txt

HW #10 (Due: 09 Feb)

String processing instructions. Includes two parts: exercises (A) and a program (B). You may change/customize the contents of your SHOUT variable if you like.

Solution:
Problems: hw10prob.txt
Code: hw10.asm
Output: hw10output.txt

HW #9 (Due: 07 Feb)

Passing arguments via the stack. 2 programs, as specified. The subroutines do not need to be external (in separate files) from their calling functions.

Solution: hw9.asm, hw9b.asm, and hw9output.txt.

HW #8 (Due: 02 Feb)

Adding up a variable number of numbers.

Solution:
hw8.asm and hw8output.txt
These do not use util.lib, though it was acceptable if you did.

As above, but with some error-checking: hw8extra.asm and hw8extra-output.txt

Exercise (Finish by: 31 Jan)

Explore the cv debugger. Be sure you understand and can do the following debugger notes. Knowing how to use a debugger is invaluable for assembly, since you cannot do debug printing without changing the state of the registers.

You do not need to submit anything for this exercise. (But still do it! It really will make your life easier later knowing how to use this.)

Solution: None.

HW #7 (Due: 31 Jan)

Write 2 programs to evaluate "X + Y - Z". Each program should employ an external subroutine. The first program should pass arguments through registers; the second should pass arguments via PUBLIC/EXTRN declarations.
(Given at the end of Set 11:Subroutines slides.)

Solution:
By registers: hw7regm.asm and hw7regp.asm
By global vars: hw7varm.asm and hw7varp.asm
Output: hw7output.txt

HW #6 (Due: 26 Jan)

Exercise 9.2 (p.233-234), nos. 1 & 2. Omit questions involving ROL, ROR.
(Given at the end of Set 9:Logic slides.)

You do not need to write/type out the question again. You can just give me the solutions in the same order of as the blanks--12 answers for 1 (after omitting), 7 answers for 2.

Solution: See Answers at the back of the book, p631-633.

HW #5 (Due: 26 Jan)

Write a program to read in a string of characters up to 20 bytes long using function 0Ah and then print it out using function 09h.
(Given at the end of Set 10:Multiplication slides.)

Give me both the code and the output for a couple test runs.

Solution:hw5.asm and hw5output.txt.

HW #4 (Due: 24 Jan)

Exercise 5.1 (p.109), nos. 1 - 4
Exercise 5.3 (p.115), no. 1
(Given at the end of Set8:Flow Control slides)

Solution: hw4.txt

HW #3 (Due: 24 Jan)

All 3 Example problems from the Set7:Flags lecture slides. (If you are using the Notes, 1d should be "NEG AL", not "NEG AX".)

Solution: hw3.txt

HW #2 (Due: 19 Jan)

Exercises 10.2 (p. 269), Problems 1 & 2

Solution:

1) See Answers at the back of the book, p.637.

2.a) Sums all the values in WArray into AX
  b) Sets AX to the largest value in WArray
  c) Sets WArray to contain 1, 2, 3, 4, 5, 6
  d) Finds the first occurrence of any digit in CArray.
     (BX will contain the offset/index within CArray
      of the first digit.)

HW #1 (Due: 19 Jan)

Write a program to read a character from the keyboard and display it at the beginning of the next line. (Use a question mark as a prompt, use Dos function 02h to read a single character, and save the character in another register.)

Solution:
hw1.asm -- My solution
hw1s.asm -- An old TAs solution, based on a different reading of the requirements.