## Quiz Solutions

Each quiz is out of 3 points. The 3 worst quiz grades are dropped at the end of term.

#### Quiz #15 (27 Apr)

Minimize this DFA:

Solution:

```          Group 1              Group 2
(Non-accepting)        (Accepting)
---------------	     -----------
0, 2, 4            1, 3, 5, 6
On a:        |                 /     \
0, 2, 4            1, 3   5, 6
On b:      /   \               |      |
0   2, 4           1, 3,  5, 6

On a again: no change
On b again: no change
```

Both DFAs corresponded to the regex `a|b((a|b)(a|b)+)?`

#### Quiz #14 (25 Apr)

Construct a DFA from this NFA:

Solution:

Both NFA and DFA corresponded to the regex `a+c*b*`

#### Quiz #13 (13 Apr)

Provide a grammar for `{a3b3nc4nd5 | n >= 0}`.

S -> aaaXddddd
X -> bbbXcccc | ε

This could also be written this way:

S -> a3Xd5
X -> b3Xc4 | ε

#### Quiz #12 (11 Apr)

1. Construct a parse of : a*a+a*a.

```    SYMBOL    STATE    INPUT*     TRANSITION/REDUCTION
1.  [empty]   0        a*a+a*a|   Initial state
2.  a         0 4       *a+a*a|   "a" trans from 0 to 4
3.  T         0 3       *a+a*a|   T->a reduction
4.  T *       0 3 5      a+a*a|   "*" trans from 3 to 5
5.  T * a     0 3 5 7     +a*a|   "a" trans from 5 to 7
6.  T         0 3         +a*a|   T->T*a reduction
7.  E         0 1         +a*a|   E->T reduction
8.  E +       0 1 2        a*a|   "+" trans from 1 to 2
9.  E + a     0 1 2 4       *a|   "a" trans from 2 to 4
10. E + T     0 1 2 6       *a|   T->a reduction
11. E + T *   0 1 2 6 5      a|   "*" trans from 6 to 5
12. E + T * a 0 1 2 6 5 7     |   "a" trans from 5 to 7
13. E + T     0 1 2 6         |   T->T*a reduction
14. E         0 1             |   E->E+T reduction
15. ACCEPT
```

2. What happens if you try to parse a non-sentence, such as a+aa?

You reach a state with no edge matching the next input symbol. For the given example, you reach state 4. The only legal departure from this state is by applying the "T->a if {*,+,|}" reduction. However, the next input symbol would be the final "a", which means the rule does not apply.

#### Midterm (23 Mar)

```1.)
sub1	PROC
push	bp
mov	bp, sp

mov	ax, [bp+6]	;a) put the value of Y into AX
mov	bx, [bp+4]
mov	cx, [bx]	;b) put the value of Z into CX

pop	bp
ret	6

sub1	ENDP

2.)
mov	ax, A
cmp	ax, B
jne	NOT_EQUAL
mov	ax, T
mov	R, ax
jmp	DONE
NOT_EQUAL:
mov	ax, S
mov	R, ax
DONE:

3.)
;copy MES1 to MES2 w/ string handling and no loops
push	ds
pop	es
cld
mov	si, offset mes1
mov	di, offset mes2
mov	cx, 20
rep	movsb

4.)
mov	cx, 20
mov	bx, 0
COPY_BYTE:
mov	al, [mes1 + bx]
mov	[mes2 + bx], al
inc	bx
loop	COPY_BYTE

5.)
ABS	MACRO X
local	DONE
mov	ax, X
cmp	ax, 0
jge	DONE
neg	ax	;neg to pos value
DONE:
ENDM	ABS

6.)
fld	A
fld	B
fmul
fld	C		;(tho C is a reserved word)
fld	D
fmul
fsub
fstp	E

7.)
;assuming already in graphics mode: ax = 0013h, int 10h
push	0A000h
pop	es
mov	di, (320 * 40) + 130	;starting at top of triangle
mov	al, 04h			;red pixel

mov	cx, 60
LEFT_SIDE:
stosb
add	di, 318			;after stosb, to get 319 total
loop	LEFT_SIDE

BOTTOM:
mov	cx, 120			;60 back to center, then 60 more
rep	stosb

mov	cx, 60
RIGHT_SIDE:
stosb
sub	di, 322			;after stosb, to get -321 total
loop	RIGHT_SIDE

```

#### Quiz #11 (14 Feb)

Write the code to:
a) Get into graphics mode
b) Draw a red horizontal line of length 150 pixels, whose left-hand end is at COL 40, ROW 60 (in pixels!).

```;a)
mov	ah, 00h
mov	al, 13h
int	10h			;get into graphics mode

;b)
mov	ax, 0A000h		;direct memory access
mov	es, ax
mov	al, 04h			;a red byte
mov	di, (60*320 + 40) 	;row 60, col 40
mov	cx, 150			;draw 150 pixels
rep	stosb

```

Though not covered in lecture, another way to draw a graphical line (part b) is:

```	mov	ah, 0Ch			;draw pixel
mov	bh, 0			;set/clear page
mov	al, 04h			;a red byte
mov	cx, 40			;column
mov	dx, 60			;row
draw:	int 	10h
inc	cx			;move over one column
cmp	cx, 40+150		;destination
jl	draw
```

#### Quiz #10 (09 Feb)

Given:
``` X1 DD ? X2 DD ? ... X9 DD ? ```

Evaluate using floating point instructions:
Y = (x1 * x2 * x3 - x4 * x5 * x6)/(x7 * x8 * x9)

```	fld	x1
fld	x2
fld	x3
fmul
fmul				;st(0) = (x1 * x2 * x3)

fld	x4
fld	x5
fld	x6
fmul
fmul				;st(0) = (x4 * x5 * x6)

fsub				;st(0) = (x1 * x2 * x3)-(x4 * x5 * x6)

fld	x7
fld	x8
fld	x9
fmul
fmul				;st(0) = (x7 * x8 * x9)

fdiv

fstp	Y
```

#### Quiz #9 (07 Feb)

1. Given: `buf DB 240 dup(?)`
Write the code to initialize buf to 00h bytes. Do this using the "rep" prefix together with a string-manipulation function.

```;assuming ds == es
cld
mov	cx, 240
lea	di, buf
mov	al, 00h
rep	stosb
```

2. Write a macro to put the largest of 3 word arguments into AX.

```largest	MACRO A, B, C
LOCAL CmpC, Done
mov	ax, A
cmp	ax, B
jge	CmpC
mov	ax, B

CmpC:	cmp	ax, C
jge	Done
mov	ax, C
Done:
ENDM
```

#### Quiz #8 (02 Feb)

Write a main program and a separately compiled subprogram called Sub1 which evaluates 2(X-Y). In the main program:
```   X DW ?   Y DW ? ``` You must code this using the standard method emplyed by all commercial compilers. Your subroutine should be: call by value, args pushed from left to right, sub fixes up the stack, near program.

```;main.asm
EXTRN Sub1:NEAR

.MODEL small
.586
.STACK 100h

.DATA
X	DW	?
Y	DW	?

.CODE
Main	PROC
mov 	ax, @data
mov	ds, ax
...
push 	X
push	Y
call 	Sub1
...
Main	ENDP
END Main

```
```;sub1
PUBLIC Sub1

.MODEL small
.586

.CODE
Sub1	PROC	;2(X-Y)
push	bp
mov	bp, sp

mov	ax, [bp + 6]
sub	ax, [bp + 4]
shl 	ax, 1

pop	bp
Sub1	ENDP
END
```

#### Quiz #7 (31 Jan)

Write a main program which calls a separately compiled program SLAVE2 to evaluate 2(X+Y). Arguments are to be passed using the PUBLIC/EXTRN mechanism. Then write SLAVE2.

```;main.asm
EXTRN SLAVE2:NEAR
EXTRN X:BYTE, Y:BYTE

.MODEL small
.586
.STACK 100h
...
.CODE
Main	PROC
...
mov	X, al		;load X and Y somehow
...
mov	Y, al
call Slave2
...
Main	ENDP
END Main
```
```
;slave2.asm
PUBLIC Slave2
PUBLIC X, Y

.MODEL small
.586

.DATA
X	DB	?
Y	DB	?

.CODE
Slave2	PROC		;2 * (X+Y)
mov	al, X
shl 	al, 1
Slave2	ENDP
END
```

(The global variable X and Y can be declared in either file. Since their primary use here is to pass values to Slave2, I thought it most logical to define it in that file.)

#### Quiz #6 (26 Jan)

Write the code to input a name of up to 15 characters and then output on a new line "Your name is" followed by the inputted name.

```	.DATA
prompt	DB "Enter your name: \$"
prompt2	DB 10, 13, "Your name is \$"
inBuff	DB 16, ?, 16 DUP('\$'), '\$'	;room for 15 chars + CR

.CODE
...
mov	ah, 09h
lea	dx, prompt
int 21h

mov	ah, 0Ah
lea	dx, inBuff
int 21h

mov ah, 09h
lea dx, prompt2
int 21h

lea dx, [inBuff + 2]
int 21h

...
```

#### Quiz #5 (24 Jan)

Insert code to branch to the appropriate label depending on the value in AX.

```	.DATA
N	DW ?
...
.CODE
...
cmp	ax, 0

je	ZERO_CASE		;the 3 lines you need
jl	MINUS_CASE
jg	POSITIVE_CASE

ZERO_CASE:
...
MINUS_CASE:
...
POSITIVE_CASE:
...
```

#### Quiz #4 (19 Jan)

Given:

LIST3 DW 19, 8, 20, 14, 17, 22, 15, 1, 3, 8, 7

Write the code to add the numbers in List3. Preferably use the EQU operator in the Data segment to avoid having to count how many numbers List3 contains.

One way to do it:

```	.DATA
LIST3 	DW 	19, 8, 20, 14, 17, 22, 15, 1, 3, 8, 7

.CODE
...
mov	bx, NUM - 2 		;last element in LIST3
mov	cx, NUM / 2		;number of elements in LIST3

Sum:	mov	ax, [LIST3 + BX]
sub	bx, 2
dec	cx
jnz	Sum
```

Another way to do it:

```	.DATA
LIST3 	DW 	19, 8, 20, 14, 17, 22, 15, 1, 3, 8, 7
LAST	DW	\$ - LIST3 - 2

.CODE
Main	PROC
mov	ax, @data
mov	ds, ax

mov	ax, 0
mov 	bx, LAST

Sum:	add	ax, [LIST3 + bx]
sub	bx, 2
jge	Sum

```

And still another:

```	.DATA
LIST3 	DW 	19, 8, 20, 14, 17, 22, 15, 1, 3, 8, 7

.CODE
...
lea 	bx, LIST3		;start of LIST3
mov	ax, 0

add	bx, 2			;to next LIST3 index
cmp	bx, offset ANSWER	;if still in LIST3
jb	Sum

```

#### Quiz #3 (17 Jan)

1) The four 32-bit general registers: EAX, EBX, ECX, EDX.

2) For one 32-bit general register, show the 16 and 8-bit registers that form part of it.

```For EAX:
---------------- -------- --------
|                | AH (8) | AL (8) |
---------------- -----------------
^ <== AX (16) ==> ^
```

3) Besides the general registers, what other registers can be specified as operands?

The segment (CS, DS, ES, FS, GS, SS), pointer (BP, SP), and index (SI, DI) registers. (Basically, everything but IP and FLAGS can be manipulated directly.)

#### Quiz #2 (12 Jan -- Speed Test)

```1) 6 = 0110b
9 = 1001b
Ah = 1010b
Dh = 1101b

2) 2^5 = 32
2^8 = 256
2^3 = 8
2^11 = 2,048

3) 1110b = Eh
0101b = 5h
1011b = Bh
1100b = Ch
```

#### Quiz #1 (12 Jan)

```1) 2^9 = 512

2) 257,982 = Binary: 0011 1110 1111 1011 1110b
Hex:    3EFBEh

3) 0 1001 1010 1011 = Hex: 9ABh
Decimal: 2,475

4)  10 1101 1000
+ 00 1110 0110
11 1011 1110

5)  2FD03Fh
+ 3EE247h
6EB286h
```

 ~ztomasze Index : TA Details : ICS312 : Quiz Solutions http://www2.hawaii.edu/~ztomasze Last Edited: 15 May 2006 ©2006 by Z. Tomaszewski.