ICS 331 Final Exam

ICS 331: System Software Final Exam Date: December 26,1998

Question 1

a) Indicate whether each of the following statements is TRUE (T) or FALSE (F). (7.5 points)

Statement	Truth
1. The relocation bits technique is used with programs with small size object codes.	F
2. EXTDEF assembler directive is used to define variables that are used in the control section but defined in other control sections.	F
3. Absolute loaders do not need to perform functions such as linking and program relocation.	T
4. Dynamic linking provides the ability to load the routines only when (and if) they are needed.	T
5. Top-down parsing techniques start from the source statements to the grammar rules.	F
6. The macro processor in the textbook does not allow the definition of a macro within a macro (Nested definition).	F

b) Complete the following definitions (be brief & precise) (8 points)

[1] ESTAB is a table that is used by the loader to store the addresses of all external symbols in the linked programs

[2] A grammar is a set of rules that specify the syntax, or form, of the legal statements in the language.

[3] NAMTAB is a table that is used by the macro processor to store and search for the names of all macros used
in the program.

[4] A linkage editor is a program that performs all the linking and relocation operations between a set of control
sections and produces a linked version of them that will be loaded later.

c) Binding is the process of associating an actual address to a symbolic name. It takes place at assembly time, at load time,
or at execution time. At what time do each of the following loading schemes perform binding? (4.5 points)

[1]	Absolute loaders	Assembly time
[2]	Dynamic linking loaders	Execution time
[3]	Linkage editors	Load time

Question 2

A program load address (PROGADD) of 1300 (Hex) is provided to the loader by the operating system to load consecutively in
memory the three control sections PROGA, PROGB, and PROGC (shown in the next page) in this order, where:

Control Section	Length
PROGA	0063
PROGB	007F
PROGC	0051

a) Generate the load map of all control sections and external symbols using the three object codes provided in the next sheet. (9 points)

Control Section	Symbol Name	Address
PROGA		1300
	LISTA	1340
	ENDA	1354
PROGB		1363
	LISTB	13C3
	ENDB	13D3
PROGC		13E2
	LISTC	1412
	ENDC	1424

b) Show the contents of the given memory locations after loading PROGA into the memory (6 points)

Address	Contents
1320-1322	03201D
1324-1326	1013C7
1354-1356	001426

c) What is dynamic linking? Give an example for its use? (5 points)

Dynamic Linking is a loader design option in which a subroutine (control section) is loaded and linked to the rest of the program when it is first called. An example, is when there are routines that handle errors in the program. Using dynamic linking will load the needed error-handling routine when the error occurs only.

Question 3

a) Given the following macro definition:

RAISE MACRO &NUM, &POWER

IF (&POWER EQ 0)

LDA #1

ELSEIF (&POWER EQ 1)

+LDA &POWER

ELSE

+LDA &NUM

ENDIF

RMO A, T

&POW SET &POWER

WHILE (&POW GE 1)

MULR T, A

&POW SET &POW - 1

ENDW

MEND

What would the following macro invocations expand to?

[1] RAISE NUMBER, 2                                  (5 points)                                       [2] RAISE INTEG, 1                                        (5 points)

       +LDA NUMBER                                                                                                  +LDA 1

       RMO A, T                                                                                                              RMO A, T

       MULR T, A                                                                                                           MULR T, A

        MULR T, A

b) What is the most important difference between the following two control structures? (5 points)

[1]     LDT #8                                                                  [2]      &CTR SET 0

        CLEAR X                                                                          WHILE (&CTR LT 8)

        LOOP                                                                                          .

            .                                                                                               .

            .                                                                                               .

        TIXR T                                                                              &CTR SET &CTR+1

        JLT LOOP                                                                        ENDW
The control structure in (1) is a regular SIC/XE assembly code that can be used anywhere in an assembly program, while the control structure in (2) is a macro-time structure that can only be used inside a definition of a macro.

c) What is the difference between general macro processors and integrated macro processors. (5 points)

A general Macro processor is a separate macro processor that can be used by an assembler or many compilers, while an integrated macro processor is a macro processor that is integrated with an assembler or a compiler as a single software.

Question 4

a) Describe how one-pass assemblers, that generate object code in the memory for immediate execution, handle the problem of forward
references. (6 points)

The assembler generates object code instructions as it scans the source program. If there is an operand who is a symbol that is not defined yet it is replaced by 0. If this symbol is not in the symbol table then it is inserted into the table with its value marked as undefined, and the address where it is used is stored in a list associated with that symbol. If the symbol is already in the table, then the new address is added to the list. When that symbol is later defined, its value is stored in the symbol table, and then it is stored in all the address in the associated list.

b) In handling multiple control sections the SIC/XE assembler generates two new records in the object program. For each of these new
records give the name, the purpose and the format. (8 points)

Define Record: which gives information about external symbols in the control section that are defined in
                           EXTDEF. Its format is as follows:

                            Col 1: D

                            Col 2-7: Name of external symbol defined in EXTDEF.

                            Col 8-13: Relative address of the symbol in the Control Section in hex.

                            Col 14-73: Repeat information in Cols. 2-13 for each defined symbol.

Refer Record: which gives information about symbols in the control section that are defined in EXTREF.
                        Its format is as follows:

                        Col 1: R

                        Col 2-7: Name of external symbol defined in EXTREF.

                        Col 8-73: Names of other external reference symbols.

c) A machine language version of a program that can be placed anywhere in memory without relinking or relocation, while still running
correctly, is called Position Independent Code or PIC.

[1] Is it possible to write PIC in SIC? Why? (3 points)

NO. It is not possible to write a PIC in SIC because there is only one instruction format in it and that uses the address of the operand directly.

[2] Is it possible to write PIC in SIC/XE? Why? (3 points)

Yes. SIC/XE provides relative addressing, so if a program is written without using format-4 instructions then that program would be a PIC.

Question 5

a) Briefly describe each of the three basic compiler functions. (9 points)

1. Lexical Analysis (scanning): This process involves scanning the source program and recognizing the tokens
that make up the source statements.

2. Syntactic Analysis (Parsing): During this process, the source statements, written by the programmer, are
recognized as language constructs described by the grammar being used.

3. Code Generation: During this process the object code of the compiled program, for the specified machine,
is generated for execution.

b) The textbook described two techniques for the syntactic analysis of programs that are used by compilers. Briefly describe how they
differ, and how each of them work to check the syntax of a given statement in a program? (11 points)

    1. Operator-precedence : which is a bottom-up parsing technique. In this method, the statement being analyzed is
        scanned for a sub expression whose operators have higher precedence than the surrounding operators. Then this
        expression is interpreted in terms of the rules of the grammar. This process continues until the root of the parse
        tree is reached, at which time the analysis is complete.

    2. Recursive Descent : which is a top-down parsing technique. Such a parser is made up of a procedure for each
        nonterminal symbol in the grammar. When a procedure is called, it attempts to find a substring of the input,
        beginning with the current token, that can be interpreted as the nonterminal with which the procedure is
        associated. In this process the procedure may call other procedures, or itself, to accomplish its task. The
        procedure can return an indication of success to its caller, if it finds the needed nonterminal; otherwise, it
        returns an indication of failure or an error message.