GTU 3160715 System Software Summer 2026 Solved Paper & Solutions

1. Semantic Gap:
The distance between the semantics of problem domain concepts (high-level logic) and execution domain concepts (machine instructions, registers, bit sequences). System software reduces this gap.

2. Specification Gap:
The difference between the specification of a problem (e.g., formal requirements or design) and the programming language constructs used to express the solution.

3. Execution Gap:
The difference between the semantics of the source programming language and the machine architecture that executes the program. Bridging this gap is the core objective of language processors (compilers/assemblers).

Role of Symbol Table (SYMTAB)

1. Definition & Storage: Created by the assembler to record every user-defined identifier (labels, variable names) along with its allocated memory address, length, and relocation attribute.
2. Resolution: During Pass 1, addresses are assigned as labels are defined. During Pass 2, SYMTAB is queried to substitute operand label names with their assigned binary addresses.

Role of Literal Table (LITTAB)

1. Definition & Storage: Stores literals (constants written directly in instructions, e.g., ='5') encountered in the source code along with their assigned target addresses.
2. Allocation & Pool Handling: Literals are assigned memory locations when an LTORG or END directive occurs. The assembler references LITTAB in Pass 2 to generate machine representations for constant operands.

Definition of System Software

System software consists of a collection of programs that manage, control, and support computer hardware operations and facilitate the development and execution of application programs (e.g., Operating Systems, Compilers, Assemblers, Loaders, Linkers).

Life Cycle of a Source Program

1. Creation / Editing: Developer writes human-readable source code using an editor.
2. Translation (Compilation / Assembly):

• The translator scans lexical tokens, validates syntactic and semantic correctness, and translates high-level constructs into an object module.

3. Linking:

• Combines independently compiled object files with runtime library routines.
• Resolves cross-module references (external symbols) and produces a unified load module.

4. Loading:

• The loader brings the executable program into primary memory, adjusts relocation addresses to physical memory offsets, and prepares the runtime stack and heap.

5. Execution:

• The CPU executes machine instructions sequentially, handling I/O and terminating with exit status.

What is a Macro?

A Macro is a named, user-defined sequence of assembly statements that can be invoked repeatedly with varying parameters. Unlike subroutines (which use call-return overhead at runtime), macros are expanded inline at assembly time.

Macro Expansion Process

1. Macro Definition: Stored in Macro Definition Table (MDT) and Macro Name Table (MNT).
2. Call Recognition: The macro processor recognizes a macro call statement in the source.
3. Argument Substitution: Formal parameters defined in the macro prototype are mapped to actual parameters passed in the call.
4. Statement Generation: The body statements from MDT are copied into the source stream with parameters substituted, replacing the macro invocation line.

Example:

; Macro Definition
MACRO
SWAP &A, &B
MOV REG, &A
MOV &A, &B
MOV &B, REG
MEND

; Source Call:
SWAP VAL1, VAL2

; Expanded Code:
MOV REG, VAL1
MOV VAL1, VAL2
MOV VAL2, REG

What are Assembler Directives?

Assembler directives (pseudo-ops) are instructions directing the assembler during translation rather than generating executable machine instructions for the CPU.

Key Assembler Directives with Examples

1. START
   :

• Specifies the starting execution address and program name.
• Example: SAMPLE START 1000 (informs assembler to load starting at location counter 1000).

2. END []:

• Marks the physical end of the source module and optionally provides the entry point execution address.
• Example: END FIRST (signals assembly termination; sets execution start at label FIRST).

3. ORIGIN :

• Resets the Location Counter (LC) to a specific target address or relative offset.
• Example: ORIGIN LOOP + 4 (sets LC 4 bytes beyond symbol LOOP).

4. EQU (Equate):

• Defines a symbolic name for a numeric constant or address without reserving storage.
• Example: MAX_LEN EQU 500 (replaces occurrences of MAX_LEN with 500).

5. LTORG (Literal Origin):

• Instructs the assembler to allocate addresses immediately for all literals collected since the previous LTORG or START.
• Example:

MOVER AREG, ='5'
     LTORG ; Literals pool assigned memory addresses here

6. DS (Declare Storage) & DC (Declare Constant):

• DS reserves specified number of words; DC reserves storage initialized to a literal value.
• Example: ARR DS 10 (allocates 10 memory words), PI DC '3.14' (reserves word containing 3.14).

Ambiguity in Grammar

A context-free grammar is ambiguous if there exists at least one string $w \in L(G)$ that can produce two or more distinct:

1. Parse trees, or
2. Leftmost derivations, or
3. Rightmost derivations.

Elimination of Left Recursion

Given grammar:

where $\alpha = a$ and $\beta = b$.

Direct left recursion occurs because $A$ appears as the leftmost symbol in the production $A \to Aa$.

Standard Elimination Rule:

Transformed Non-Left-Recursive Grammar:

Types of Errors Encountered During Program Execution

1. Compile-Time / Translation Errors:

• Lexical Errors: Invalid characters or unrecognized tokens (e.g., 123var, unclosed string literals).
• Syntax Errors: Violations of language grammatical rules (e.g., missing semicolons, unmatched parentheses).
• Semantic Errors: Incompatible types or undeclared identifiers (e.g., assigning a string to an integer).

2. Link-Time Errors:

• Unresolved External Symbols: A function or variable referenced in code has no definition in any linked object file or library.
• Duplicate Definitions: The same global symbol is defined multiple times across modules.

3. Run-Time Errors:

• Arithmetic Exceptions: Division by zero, floating-point overflow.
• Memory Access Violations: Segmentation faults, null pointer dereferences, stack overflows, buffer overruns.
• System Resource Failures: Out of memory, file not found, permission denied.

Flowchart of a Single-Pass Assembler

Table of Incomplete Instructions (TII)

Because a single-pass assembler does not scan code twice, it cannot resolve forward references immediately. It uses a Table of Incomplete Instructions (TII):

• Stores instruction memory address and the forward-referenced symbol.
• When the label is eventually defined, the assembler traverses TII and backpatches the actual address into the partially emitted binary word.

Advantages of Single-Pass Assembler

1. High Translation Speed: Only reads source program once from disk/memory, reducing I/O overhead.
2. Reduced Temporary Storage: No need to save intermediate representations on disk between passes.

Limitations Compared to Two-Pass Assembler

1. Memory Overhead: TII and intermediate unresolved instructions must remain resident in RAM.
2. Restricted Features: Difficult to implement complex macro structures or multi-level address relocations without heavy memory backtracking.

What is a Self-Relocating Program?

A self-relocating program is an executable module that can be loaded into any arbitrary memory location and can execute correctly without requiring the external loader to adjust its internal address references.

How Does It Work?

1. Self-Relocation Routine: The program includes a small initialization bootstrap header code executed immediately upon startup.
2. Base Register Discovery: The routine reads the current instruction pointer (PC) into a base register (e.g., using a call instruction like CALL next; next: POP EBX).
3. Internal Address Fixing: Using the discovered base address, the code adjusts internal jump/data tables dynamically in memory before continuing program execution.

Basic Structure of a LEX Program

A LEX source file consists of three sections separated by %%:

1. Definitions Section: Declares regular definitions (shorthand names for regexes), includes C header files, and declares global variables.
2. Rules Section: Contains regular expressions matched against input; when matched, associated C code blocks execute. yytext holds the matched token.
3. User Code Section: Contains main(), yywrap(), and application helper logic compiled directly into the scanner.

Phases of Compilation

1. Lexical Analysis: Reads characters, strips whitespace/comments, and groups characters into tokens (identifiers, keywords, operators).
2. Syntax Analysis: Validates token sequences against context-free grammar rules to produce a Parse Tree or AST.
3. Semantic Analysis: Checks semantic consistency (type compatibility, array boundary validation, scope resolution).
4. Intermediate Code Generation (ICG): Converts AST into machine-independent intermediate representations (e.g., Three-Address Code, quadruples).
5. Code Optimization: Transforms intermediate code to run faster and utilize less memory.
6. Code Generation: Maps optimized IR to target machine instructions, registers, and memory addresses.

Overlay Structured Programs

An overlay technique allows a program whose total size exceeds physical memory to execute by loading only currently required modules into memory, overwriting inactive modules.

Linking Overlays

1. Overlay Tree Construction: The linker creates an overlay tree structure where non-concurrent phases (mutually exclusive routines) share the same memory region.
2. Root Module: The root module contains permanent resident code and the overlay supervisor, remaining resident in low memory.
3. Execution & Swapping: When a routine in an overlay segment is called, the overlay manager verifies if it is in memory; if not, it loads it over the memory previously occupied by other overlay segments.

Use of AIF and AGO Directives

In macro processors, AIF (Conditional Branch) and AGO (Unconditional Branch) control conditional macro expansion and loop unrolling during assembly.

1. AIF () .:

• Evaluates a boolean condition. If true, macro expansion jumps to the specified sequence symbol (. label).

2. AGO .:

• Unconditionally jumps macro expansion directly to the sequence symbol.

Example

MACRO
COPY_N &SRC, &DEST, &COUNT
LCL &I
&I SET 1
.LOOP
MOV &DEST[&I], &SRC[&I]
&I SET &I + 1
AIF (&I LE &COUNT) .LOOP
AGO .DONE
.DONE
MEND

The macro loops and expands the MOV instruction until &I > &COUNT.

What is an Interpreter?

An interpreter is a language processor that directly executes high-level source instructions statement-by-statement without generating an intermediate machine-code executable file on disk.

Pure vs. Impure Interpreters

1. Pure Interpreter:

• Mechanism: Analyzes the raw source code text directly during each step of execution.
• Working: In loops, statements are re-scanned, re-parsed, and interpreted repeatedly on every iteration.
• Pros/Cons: Zero compilation delay, but extremely slow execution due to redundant syntax parsing.

2. Impure Interpreter:

• Mechanism: Pre-compiles source code into an intermediate representation (such as bytecode or an annotated Abstract Syntax Tree) during a quick first pass.
• Working: The execution engine runs directly against the pre-parsed bytecode (e.g., Python P-code, JVM bytecode).
• Pros/Cons: Eliminates redundant parsing in loops, resulting in significantly faster execution while retaining dynamic flexibility.