SPCC

30 March 2024 23:15

[Link] between system software and application software

(ls-1)

Param System Software Application Software

eter
Definiti System Software is the type of Application Software is the
on software which is the interface type of software which runs as
between application software per user request. It runs on the
and system. platform which is provide by
system software.
Develo In general, System software are In case of Application
pment developed using low-level software, high level language
Langu language which is more is used for their development
age compatible with the system as they are developed as
hardware in order to interact some specific purpose
with. software.
Neces System software are essential Application software are not
sity for operating the computer essential for the operation of
hardware. Without these the computer. These are
software, a computer even may installed as per the user’s
not start or function properly. requirements.
Usage System software is used for Application software is used by
operating computer hardware. user to perform specific task.
Installa System software are installed Application software are
tion on the computer when operating installed according to user’s
system is installed. requirements.
User System software are specific to Users can interact with an
interac system hardware, so less or no application software with the
tion user interaction available in help of a User Interface (UI).
case of system software.
Depen System software can run An application software cannot
dency independently. It provides run independently. It cannot
platform for running application run without the presence of
software. system software.
Examp Examples of system software Examples of application
les include operating systems, software include word
compilers, assemblers, processors, web browsers,
debuggers, drivers, etc. media players, etc.
_________________________________________________________
____________________

2. Explain with flow chart the design of two pass assembler (ls-2)

SPCC Page 1
SPCC Page 2
 In Pass 1 of the assembly process, the assembler goes through the
source program to assign locations to instructions and data, as well
as define values for symbols (labels). Here's a breakdown of the
steps involved:
1. Initialize Location Counter (LC): Set LC to the first location in the
program (usually 0).
2. Read Source Statement: Read a source statement from the input.
3. Check Operation Code: Examine the operation code field to
determine if it's a machine instruction or a pseudo-operation (pseudo-
op).
4. Process Machine Instructions: If it's a machine instruction, search the
Machine Op-Codes Table (MOT) to find a match for the op-code field.
Determine the length of the instruction and update the LC accordingly.
If a literal is found in the operand field, add it to the Literal Table (LT).
If there's a symbol in the label field, save it in the Symbol Table (ST)
with the current value of LC.
5. Process Pseudo-Operations: For pseudo-ops like USING and DROP,
simply save the cards for pass 2. For EQU, evaluate the expression in
the operand field to define the symbol.
6. Handle OS and DC Pseudo-Ops: These pseudo-ops can affect both
the location counter and symbol definition. Examine the operand field
to determine storage requirements. Adjust the LC if necessary due to
alignment conditions.
7. Terminate Pass 1: When encountering the END pseudo-op, terminate
Pass 1. Perform housekeeping operations like assigning locations to
collected literals and reinitialize conditions for Pass 2.
Pass 1 primarily focuses on assigning locations, defining symbols,
and collecting information needed for Pass 2, such as literals and
pseudo-ops.

SPCC Page 3
Pass 2 of the assembly process finalizes the assembly by generating
code based on the symbols defined in Pass 1. Here's how it works:

Initialize Location Counter (LC): Same as Pass 1, set LC to the starting

location.

Read Source Card: Read a card from the source file left by Pass 1.

Process Machine Instructions: Similar to Pass 1, examine the operation

code field to determine if it's a machine instruction. Search the Machine
Op-Codes Table (MOT) to find a match for the op-code field. Determine
the length, binary op-code, and format type of the instruction. Process
the operand field based on the instruction format type.

Handle Pseudo-Ops: Handle pseudo-ops like END, EQU, USING,

DROP, OS, and DC. For END, terminate the assembly. For EQU, print
the EQU card. For USING and DROP, evaluate the operand fields and
mark entries in the Base Table accordingly. Process OS and DC as in
Pass 1, but generate actual code for DC pseudo-op in Pass 2.

Generate Code: For RR-format instructions, evaluate and insert register

specification fields into the instruction. For RX-format instructions,
evaluate register and index fields and generate an Effective Address
SPCC Page 4
Generate Code: For RR-format instructions, evaluate and insert register
specification fields into the instruction. For RX-format instructions,
evaluate register and index fields and generate an Effective Address
(EA). Format the instructions for later processing by the loader, typically
placing several instructions on a single card. Print a listing line
containing the source card, its storage location, and hexadecimal
representation.

Housekeeping Tasks: Perform various tasks such as generating code for

remaining literals in the Literal Table (LT).

Terminate Pass 2: When encountering the END pseudo-op, terminate

Pass 2. Perform any remaining housekeeping tasks.

Pass 2 completes the assembly process by generating machine code

based on the symbols defined in Pass 1 and preparing it for further
processing by the loader.

_________________________________________________________
_________________________________________

3. Numerical based two pass assembler consider the following

assembly program
START 501
A DS I
B DS I
C DS I
READ A
READ B
MOVER AREG,A
ADD AREG,B
MOVEM AREG,C
PRINT C
END
Generate pass-1 and pass-2 and also show the content of database
table involved in. (ls-2)

ANS:-

Pass 1:

START 501: Set LC (Location Counter) to 501.

A DS I: Define symbol A with length I (Integer) and increment LC by the

size of I.

B DS I: Define symbol B with length I and increment LC by the size of I.

C DS I: Define symbol C with length I and increment LC by the size of I.

READ A: No processing needed as it's an instruction.

READ B: No processing needed.

MOVER AREG, A: Check MOT for MOVER, increment LC by the size of

SPCC Page 5
READ B: No processing needed.

MOVER AREG, A: Check MOT for MOVER, increment LC by the size of

MOVER instruction.

ADD AREG, B: Check MOT for ADD, increment LC by the size of ADD
instruction.

MOVEM AREG, C: Check MOT for MOVEM, increment LC by the size of

MOVEM instruction.

PRINT C: No processing needed.

END: End of the program.

Pass 2:

START 501: LC = 501.

A DS I: Symbol table: A - 501.

B DS I: Symbol table: B - 505.

C DS I: Symbol table: C - 509.

READ A: No code generation.

READ B: No code generation.

MOVER AREG, A: Generate machine code for MOVER instruction, store

in object code.

ADD AREG, B: Generate machine code for ADD instruction, store in

object code.

MOVEM AREG, C: Generate machine code for MOVEM instruction,

store in object code.

PRINT C: No code generation.

END: Terminate Pass 2.

Database Tables:

Symbol Table (ST):

A: 501
B: 505
C: 509
Machine Op-Codes Table (MOT):

MOVER: Size
ADD: Size
MOVEM: Size
Literal Table (LT):

SPCC Page 6
ADD: Size
MOVEM: Size
Literal Table (LT):

Empty, as there are no literals in the program.

Base Table (BT):

Not applicable for this program.

_________________________________________________________
____________________

4. With reference to assembler explain the following tables with

suitable examples POT, MOT, ST, LT, BT (ls-2)
ANS:-
POT (Pseudo-Op Table):
The POT contains a list of all the pseudo-operations supported by the
assembler along with their definitions.
Example:
START 101
END
DS 4
USING *, 15
MOT (Machine Op-Code Table):

The MOT contains a list of all the machine instructions recognized by the
assembler along with their op-codes and formats.
Example:
ADD 01 3
SUB 02 3
MOVER 04 2
ST (Symbol Table):

The ST contains a list of all symbols (labels, variables, etc.) defined in

the program along with their corresponding addresses.
Example:
A 101
B 105
C 109
LT (Literal Table):

The LT contains a list of all the literals (constants) used in the program
along with their addresses.
Example:
'HELLO' 201
1234 205
BT (Base Table):

The BT contains information about the base registers used in the

program.
Example:
B 15

These tables are essential components of an assembler, helping in the

translation of assembly language code into machine code. They aid in
symbol resolution, instruction lookup, and other processing tasks
required during assembly.
SPCC Page 7
These tables are essential components of an assembler, helping in the
translation of assembly language code into machine code. They aid in
symbol resolution, instruction lookup, and other processing tasks
required during assembly.

_________________________________________________________
____________________

5. Explain forward reference problem and how it is handled in

assembler design (LS-2)
ANS:-
The forward reference problem in assembler design occurs when the
assembler encounters a symbol (such as a label or variable) that is
referenced before it is defined in the source code. This poses a
challenge for the assembler because it needs to assign addresses to
symbols in a linear pass through the source code, but it cannot assign
an address to a symbol before it is defined. Here's a detailed explanation
of how this problem is handled in assembler design:

1. First Pass:
During the first pass of the assembler, the assembler performs the
following tasks:
• Symbol Table Initialization: The assembler initializes an empty symbol
table to store information about symbols encountered in the source
code.
• Scan Source Code: The assembler scans through the entire source
code line by line, analyzing each line to identify symbols, instructions,
and directives.
• Symbol Table Entry: When the assembler encounters a symbol (label
or variable), it creates an entry in the symbol table for that symbol.
The entry includes the symbol's name, its associated address (initially
set to zero or an arbitrary value), and any other relevant information.
• Forward References: If the assembler encounters a symbol that is
referenced before it is defined, it marks it as a forward reference. The
assembler continues processing, temporarily leaving the address
unresolved.

2. Second Pass:
After completing the first pass, the assembler revisits the source code in
a second pass to resolve forward references. During the second pass:
• Revisit Source Code: The assembler reprocesses each line of the
source code, including those with forward references.
• Resolve Forward References: When the assembler encounters a
forward reference, it looks up the symbol in the symbol table to find its
address, which should have been resolved during the first pass.
• Update Symbol Address: The assembler updates the address of the
symbol with its correct value obtained from the first pass.
• Generate Object Code: As the assembler processes each instruction,
it generates the corresponding machine code and stores it in memory
or generates an object file.

Error Handling:
• If a symbol is referenced but not defined anywhere in the source
code, it leads to an unresolved external symbol error.
• Assemblers typically detect such errors and report them to the user,
indicating the line number and context where the error occurred.
• Resolving unresolved external symbols might require modifications to
SPCC Page 8
 code, it leads to an unresolved external symbol error.
• Assemblers typically detect such errors and report them to the user,
indicating the line number and context where the error occurred.
• Resolving unresolved external symbols might require modifications to
the source code to define the missing symbols or correct the
references.

Example:
Consider the following assembly code:
START 100
LOOP ADD A, B
SUB C, A
JMP LOOP
A DS 1
B DS 1
C DS 1
END

_________________________________________________________
____________________

6. Explain different Assembler directives with example

(LS-2)
ANS:-
Assembler directives, also known as pseudo-operations or pseudo-ops,
are commands that direct the assembler to perform certain tasks during
the assembly process. These directives do not represent machine
instructions but instead provide instructions to the assembler itself. Here
are some common assembler directives along with examples:
• START/END: Specifies the beginning and end of the program.
START 1000
; Program code goes here
END

• ORG (Origin): Specifies the origin or starting address of the program

or a section of code.
ORG 2000
; Program code goes here

• EQU (Equate): Defines a symbol with a constant value.

COUNT EQU 10

• DS (Define Storage): Reserves memory space for variables.

VAR1 DS 1 ; Reserves 1 memory location for VAR1
VAR2 DS 2 ; Reserves 2 memory locations for VAR2

• DC (Define Constant): Defines constants.

MSG DC 'Hello, World!' ; Defines a string constant
VALUE DC 123 ; Defines a numeric constant

• DSORG (Data Set Origin): Specifies the origin of a dataset.

DSORG 3000

• USING: Establishes a base register for addressing.

USING *, 12 ; Set base register to register 12

SPCC Page 9
• USING: Establishes a base register for addressing.
USING *, 12 ; Set base register to register 12

• LTORG (Literal Origin): Specifies the location for literals.

LTORG

• CSECT (Control Section): Marks the beginning of a control section.

CSECT

• TITLE: Provides a title or comment for the program.

TITLE 'Sample Assembly Program'

• SPACE: Reserves storage space.

SPACE 20 ; Reserves 20 bytes of space

• RESW (Reserve Word): Reserves storage space in words.

RESW 5 ; Reserves 5 words of storage space

• RESB (Reserve Byte): Reserves storage space in bytes.

RESB 10 ; Reserves 10 bytes of storage space

• RECORD: Specifies record format.

RECORD FORMAT=F,LENGTH=80

_________________________________________________________
____________________

7. Enlist different types of error that are handle by pass 1 and pass
2 assemblers (LS-2)
ANS:-
In a two-pass assembler, both pass 1 and pass 2 handle different types
of errors during the assembly process. Here are the different types of
errors that are typically handled by each pass:
Errors Handled by Pass 1:
• Syntax Errors: Pass 1 checks for syntax errors in the assembly code,
such as missing commas, incorrect operand formats, or invalid
mnemonics.
• Undefined Symbols: Pass 1 identifies undefined symbols used in the
code by checking the symbol table. If a symbol is used before being
defined, it is flagged as an error.
• Forward Referencing: Pass 1 handles forward references by
allocating temporary addresses or placeholders for symbols that are
referenced before being defined. These addresses are later resolved
in pass 2.
• Invalid Instructions: Pass 1 verifies the validity of machine instructions
by checking against the opcode table. If an instruction is not
recognized or supported, it is reported as an error.
• Literal Pool Management: Pass 1 manages literal pools by identifying
literals in the code and assigning them temporary addresses. These
literals are later processed in pass 2.
• Base Register Management: If base-relative addressing is used, pass
1 manages the base register assignments and ensures that base-
relative instructions are properly handled.
Errors Handled by Pass 2:
• Address Calculation Errors: Pass 2 calculates the final addresses for
instructions and data, resolving any forward references encountered
SPCC Page 10
 relative instructions are properly handled.
Errors Handled by Pass 2:
• Address Calculation Errors: Pass 2 calculates the final addresses for
instructions and data, resolving any forward references encountered
in pass 1. If there are errors in address calculation, such as overflow
or underflow, they are reported in pass 2.
• Symbol Resolution: Pass 2 resolves symbols to their final addresses
based on the symbol table generated in pass 1. If a symbol cannot be
resolved or conflicts with existing symbols, it is flagged as an error.
• Literal Pool Processing: Pass 2 processes literal pools generated in
pass 1 by assigning them final addresses and generating machine
code instructions or data for them.
• Base Register Resolution: Pass 2 resolves base-relative addressing
by substituting base register values and computing displacement
values for instructions referencing memory locations relative to a base
register.
• Output Code Generation: Pass 2 generates the final machine code
instructions or object code based on the resolved addresses and
assembled instructions. If there are errors in generating the output
code, they are reported in pass 2.

_________________________________________________________
____________________

8. Draw a neat flowchart of two pass macro processor , explain

with the help of an example (ls-3)

ANS:-

SPCC Page 11
PASS 1- MACRO DEFINITION
In pass 1 of the assembler, the focus is on processing macro
definitions. Here's how it works:
• Identification of Macro Definitions: Pass 1 scans each input line to
identify if it contains a macro definition. This is typically done by
checking for the presence of a specific pseudo-opcode, such as
"MACRO."
• Saving Macro Definitions: When a macro definition is encountered,
the entire definition is saved in the Macro Definition Table (MDT). This
table stores all the lines of code that constitute the macro, including
any parameters and their replacements.
• Macro Name Table (MNT): The name of the macro is extracted from
the definition and stored in the Macro Name Table (MNT). This table
maintains a list of all defined macros along with pointers to their
corresponding entries in the MDT.
• Processing Macro Definitions: Pass 1 continues processing
subsequent lines of code until it reaches the END pseudo-op,
indicating the end of the source program or assembly file. During this
process, all macro definitions encountered are saved in the MDT and
their names are recorded in the MNT.
• Transfer to Pass 2: Once all macro definitions have been processed,
SPCC Page 12
 indicating the end of the source program or assembly file. During this
process, all macro definitions encountered are saved in the MDT and
their names are recorded in the MNT.
• Transfer to Pass 2: Once all macro definitions have been processed,
control is transferred to pass 2 of the assembler. Pass 2 will handle
the processing of macro calls, where macros are invoked in the
source code.

SPCC Page 13
 PASS 2-MACRO CALLS AND EXPANSION:
In pass 2 of the assembler, the focus is on processing macro calls and
expanding them. Here's how it works:
1. Identification of Macro Calls: Pass 2 examines the operation mnemonic
of each input line to determine if it matches a macro name stored in the
Macro Name Table (MNT). If a macro call is found, further processing is
initiated.
2. Setting the Macro Definition Table Pointer (MDTP): When a macro call is
detected, the call processor sets a pointer, known as the Macro
Definition Table Pointer (MDTP), to the corresponding macro definition
stored in the Macro Definition Table (MDT). The initial value of the
MDTP is obtained from the "MDT index" field of the MNT entry.
3. Preparing the Argument List Array (ALA): The macro expander prepares
the Argument List Array (ALA), which consists of a table of dummy
argument indices and corresponding arguments to the macro call. Each
argument is matched to its corresponding dummy argument in the macro
definition.
4. Substituting Arguments in Macro Definition: As the macro definition is
read from the MDT, the values from the argument list are substituted for
the dummy argument indices in the macro definition. This process
continues until the MEND line in the MDT is encountered, indicating the
end of the macro definition.
5. Handling Argument References: Arguments can be referenced either by
position or by name. For positional references, the substitution process
is straightforward. For references by name, the macro processor locates
the dummy argument on the macro name line to determine the proper
index.
6. Expansion of Macro Calls: The expansion of the macro call involves
substituting the arguments into the macro definition and generating the
corresponding lines of code. This expanded code becomes part of the
source deck and is further processed by the assembler.
7. Completion of Expansion: Once all macro calls have been expanded and
the END pseudo-op is encountered, the expanded source deck is
transferred to the assembler for further processing. This includes
handling any remaining instructions or data in the source program.

SPCC Page 14
 _________________________________________________________
____________________

8. Explain macro and different features of macro with examples

(ls-3)
ANS:-
A macro in assembly language is a named block of code that can be
invoked multiple times throughout a program. It serves as a mechanism
for code reuse and simplification, allowing programmers to define and
use custom instructions tailored to their specific needs. Macros are
especially useful in assembly language programming, where repetitive
tasks are common and code efficiency is crucial.
Here are some key features of macros along with examples:

• Named Block of Code: A macro is defined with a name, which serves

as its identifier throughout the program.
Example:
MACRO ADDITION
ADD A, B
MEND

• Parameterized: Macros can accept parameters, allowing for flexibility

in the generated code.
Example:
MACRO ADDITION A, B
ADD A, B
MEND
SPCC Page 15
 MACRO ADDITION A, B
ADD A, B
MEND

• Reusability: Once defined, macros can be invoked multiple times at

different points in the program.
Example:
ADDITION X, Y
ADDITION A, B

• Expansion: When a macro is invoked, it expands into the

corresponding block of code defined in its definition.
Example: If ADDITION X, Y is invoked, it expands to ADD X, Y.

• Parameter Substitution: Parameters passed to the macro are

substituted into the macro definition.
Example: If ADDITION A, B is invoked, it expands to ADD A, B.

• Conditional Assembly: Macros can include conditional assembly

directives to generate different code based on conditions.
Example:
MACRO MAX A, B
IF A > B
MOVE A, MAXIMUM
ELSE
MOVE B, MAXIMUM
ENDIF
MEND

• Nesting: Macros can be defined within other macros, allowing for

hierarchical organization and code abstraction.
Example:
MACRO OUTER_MACRO
MACRO INNER_MACRO
; Inner macro definition
MEND
MEND

• Scope: Macros have their own scope, and their definitions are valid
within the scope where they are defined.
Example:
MACRO EXAMPLE_MACRO
; Macro definition
MEND
; Code outside the macro definition

_________________________________________________________
_________________________

9. Explain with example conditional macro expansion (ls-3)

ANS:-
Conditional macro expansion allows the macro to generate different
code based on certain conditions. This is achieved using conditional
assembly directives (IF, ELSE, ENDIF) within the macro definition.
Here's an example of a conditional macro expansion:
Suppose we want to create a macro called COMPARE_AND_SWAP,
SPCC Page 16
 code based on certain conditions. This is achieved using conditional
assembly directives (IF, ELSE, ENDIF) within the macro definition.
Here's an example of a conditional macro expansion:
Suppose we want to create a macro called COMPARE_AND_SWAP,
which compares two values and swaps them if the first value is greater
than the second. However, we want the macro to handle both signed
and unsigned comparison based on a parameter passed during its
invocation.

Here's how we can define the COMPARE_AND_SWAP macro with

conditional expansion:

MACRO COMPARE_AND_SWAP VALUE1, VALUE2, SIGNED

IF %SIGNED EQ 1
CMP VALUE1, VALUE2 ; Compare signed values
JG NO_SWAP ; Jump if greater
ELSE
CMPU VALUE1, VALUE2 ; Compare unsigned values
JGU NO_SWAP ; Jump if greater
ENDIF
; Swap values
MOVE VALUE1, TEMP
MOVE VALUE2, VALUE1
MOVE TEMP, VALUE2
NO_SWAP:
MEND

In this example, the COMPARE_AND_SWAP macro takes three

parameters: VALUE1, VALUE2, and SIGNED. The SIGNED parameter
is used to determine whether the comparison should be signed or
unsigned.

If SIGNED is 1, the macro compares VALUE1 and VALUE2 using the

CMP instruction for signed comparison.

If SIGNED is 0, the macro compares VALUE1 and VALUE2 using the

CMPU instruction for unsigned comparison.

After the comparison, if VALUE1 is greater than VALUE2, the values are
swapped. Otherwise, no swapping occurs.

Here's how you can use the COMPARE_AND_SWAP macro with

conditional expansion:
COMPARE_AND_SWAP R1, R2, 1 ; Compare signed values

This invocation compares the values in registers R1 and R2 using

signed comparison.
COMPARE_AND_SWAP R3, R4, 0 ; Compare unsigned values

This invocation compares the values in registers R3 and R4 using

unsigned comparison.
By using conditional macro expansion, we can create versatile macros
that adapt their behavior based on specific requirements, enhancing
code flexibility and reusability.

10. Explain Macro and Macro expansion

SPCC Page 17
 that adapt their behavior based on specific requirements, enhancing
code flexibility and reusability.

10. Explain Macro and Macro expansion

A Macro is a programmable pattern that translates a specific sequence
of input into a preset sequence of output. It is a way to repeat frequently-
used lines of code, which can improve performance by requiring fewer
instructions and system resources to execute. Macros are often used in
system programming to define an abbreviation for a piece of code,
allowing programmers to use a shorter syntax for repetitive tasks.

Macro expansion is the process of substituting a macro call with the

appropriate macro definition. This process involves three main activities:
macro definition, macro invocation, and macro expansion. The macro
definition defines the macro and its behavior, the macro invocation calls
the macro, and the macro expansion substitutes the macro call with the
macro definition.
In Lisp, for example, macro expansion is achieved through the use of
the macroexpand function, which takes a form and an environment as
arguments and returns the expansion of the form. The macroexpand-
hook variable is a special variable that can be set to a function that is
called during macro expansion.

Here is an example of how macro expansion works in Lisp:

(defmacro hello-world ()
`(format t "Hello, World!"))
(macroexpand '(hello-world))
; Output: (format t "Hello, World!")
In this example, the hello-world macro is defined to expand to the
form (format t "Hello, World!"). When the macroexpand function is called
with the form (hello-world), it returns the expansion of the form, which
is (format t "Hello, World!").
In summary, Macros are a way to repeat frequently-used lines of code,
and macro expansion is the process of substituting a macro call with the
appropriate macro definition.

11. Short note on macro facilities

_________________________________________________________
____________________

12. What is loader and explain the function of loader with an example
(ls-4)
ANS:-
A loader is a program that loads an executable program from disk into
memory for execution. Its primary function is to place the program into
memory in such a way that it can be executed by the CPU. The loader
performs several tasks to accomplish this, including allocating memory,
relocating the program, resolving external references, and setting up the
program's execution environment.

Here's an overview of the functions of a loader:

• Memory Allocation: The loader allocates memory space in the main
memory (RAM) to accommodate the program. This involves
determining the size of the program and finding a suitable region of
memory to load it.
• Loading: The loader reads the program file from disk into memory. It
SPCC Page 18
 memory (RAM) to accommodate the program. This involves
determining the size of the program and finding a suitable region of
memory to load it.
• Loading: The loader reads the program file from disk into memory. It
copies the program instructions and data from the executable file on
disk to the allocated memory space in RAM.
• Relocation: Many programs are compiled to be position-independent,
meaning they can be loaded into any memory location. However,
some programs may have absolute memory addresses embedded in
their code. The loader performs relocation by adjusting these
addresses so that they point to the correct memory locations based
on where the program is loaded in memory.
• Linking: In case the program has external references to functions or
data located in other modules or libraries, the loader resolves these
references by linking them to the appropriate addresses in memory.
This involves updating the references to point to the correct locations
in memory where the referenced functions or data reside.
• Initialization: After loading and linking the program, the loader
performs any necessary initialization tasks. This may include setting
up the program's stack and heap, initializing global variables, and
preparing the program for execution.
• Transfer of Control: Once the program is loaded and initialized, the
loader transfers control to the entry point of the program, typically the
main() function for high-level programming languages like C or the
start address for assembly language programs. This allows the CPU
to begin executing the program's instructions.

Here's a simplified example of how a loader works:

Suppose we have a simple program written in C and compiled into an
executable file called [Link]. When we run [Link], the
operating system's loader performs the following steps:
• The loader allocates memory space in RAM to accommodate the
program's instructions and data.
• It reads the contents of the [Link] file from disk into the
allocated memory space.
• The loader performs relocation, adjusting any absolute memory
addresses in the program's code to match the allocated memory
space.
• If the program has external references to functions or data in other
modules, the loader resolves these references by linking them to the
correct memory addresses.
• Any necessary initialization tasks are performed, such as setting up
the program's stack and heap.
• Finally, the loader transfers control to the entry point of the program,
allowing the CPU to begin executing the program's instructions.

_________________________________________________________
____________________

13. Explain design and flowchart of absolute loader

(ls-4)
ANS:-
The absolute loader is a type of loader used in computer systems to load
a program into memory for execution. Unlike other loaders, such as the
relocatable loader or the linkage editor, the absolute loader does not
SPCC Page 19
ANS:-
The absolute loader is a type of loader used in computer systems to load
a program into memory for execution. Unlike other loaders, such as the
relocatable loader or the linkage editor, the absolute loader does not
perform any relocation or linking. Instead, it assumes that the program is
to be loaded into a specific memory location. Here's an explanation of
the design and a flowchart for an absolute loader:
Design of Absolute Loader:
Input:
The input to the absolute loader is an object program in absolute
format. This object program contains machine instructions and data in
absolute memory addresses.
Memory Allocation:
The absolute loader assumes that the program is to be loaded into a
specific memory location. Therefore, it does not perform any
relocation or linking. Instead, it loads the program directly into
memory at the specified address.
Loading Process:
The loading process involves reading the object program and copying
its contents into memory starting from the specified address.
It reads the object program one block at a time and copies it to the
specified memory location.
Error Handling:
The absolute loader performs error checking to ensure that the object
program is loaded correctly into memory.
It checks for errors such as memory overflow, invalid format, or any
other inconsistencies in the object program.

Explanation of Flowchart:
• Start:
The process begins.
• Read object program into memory:
The object program is read into memory.
• Initialize memory pointer:
A memory pointer is initialized to point to the specified memory
address where the program is to be loaded.
• Repeat until end of object program:
This loop continues until the end of the object program is reached.
• Read one block of the object program:
Each block of the object program is read.
• Copy block into memory at memory pointer:
The block of the object program is copied into memory at the
SPCC Page 20
 • Read one block of the object program:
Each block of the object program is read.
• Copy block into memory at memory pointer:
The block of the object program is copied into memory at the
memory pointer.
• Increment memory pointer:
The memory pointer is incremented to point to the next memory
location.
• End loop:
The loop continues until the entire object program is loaded into
memory.
• Perform error checking:
After loading the object program, error checking is performed.
• If errors found, display error message and abort:
If errors are found during error checking, an error message is
displayed, and the loading process is aborted.
• Else, display success message:
If no errors are found, a success message is displayed.
• End:
The process ends.

_________________________________________________________
____________________

14. Explain the working of Direct Linking Loader with an example and
also show entry in different built by DLL (ls-4)
ANS:-
• A Direct Linking Loader is a type of loader used in computer systems to
load a program into memory for execution. Unlike other loaders, such as
the relocatable loader or the linkage editor, the direct linking loader
performs both linking and loading in a single step. Here's how a Direct
Linking Loader works, along with an example and an illustration of the
entry in different built by DLL:
• Working of Direct Linking Loader:
• Input:
The input to the Direct Linking Loader is an object program in relocatable
format. This object program contains machine instructions and data with
relative addresses.
• Memory Allocation:
The Direct Linking Loader loads the object program into memory,
starting at a specified base address.
• Linking and Loading Process:
During the loading process, the loader adjusts the addresses in the
object program to reflect the actual memory locations where the program
will be loaded.
It performs this adjustment by adding the base address to the relative
addresses in the program code.
• Error Handling:
The Direct Linking Loader performs error checking to ensure that the
object program is loaded correctly into memory.
It checks for errors such as memory overflow, invalid format, or any
other inconsistencies in the object program.

Example:
Suppose we have an object program with the following instructions:
SPCC Page 21
 other inconsistencies in the object program.

Example:
Suppose we have an object program with the following instructions:
Address Instruction
----------------------
100 ADD 200
101 SUB 300
102 JMP 400
And suppose we want to load this program into memory starting at
address 500. The Direct Linking Loader would perform the following
steps:
1. Adjust Addresses:
Since the program is relocatable, the loader adjusts the addresses in
the program code to reflect the actual memory locations where the
program will be loaded.
The addresses are adjusted by adding the base address (500) to the
relative addresses in the program code.

Adjusted Address Instruction

--------------------------------
600 ADD 700
601 SUB 800
602 JMP 900
2. Loading Process:
The loader copies the object program into memory, starting at
address 500.
Memory Address Instruction
----------------------------
500 ADD 700
501 SUB 800
502 JMP 900
3. Error Handling:
The loader performs error checking to ensure that the object program
is loaded correctly into memory.
It checks for errors such as memory overflow, invalid format, or any
other inconsistencies in the object program.

Entry in Different Build by DLL:

Assuming the Direct Linking Loader creates an entry in the DLL
(Dynamic Link Library) format, the entry would look like this:
Name Base Address Size
----------------------------------
Program 500 3

This entry indicates that the program "Program" starts at memory

address 500 and has a size of 3 memory locations. This information
allows the operating system to locate and execute the program
correctly.

_______________________________________________________
______________________

15. Explain Dynamic Linking Loader in details (ls-4)

ANS:-
SPCC Page 22
15. Explain Dynamic Linking Loader in details (ls-4)
ANS:-
Dynamic linking loader is a mechanism used in operating systems to
load and link shared libraries or dynamic-link libraries (DLLs) into a
program's address space at runtime. Unlike static linking, where library
code is incorporated into the executable file, dynamic linking allows
multiple programs to share a single copy of a library in memory, reducing
memory usage and improving system performance.

Key Components of Dynamic Linking Loader:

• Dynamic Linker: The dynamic linker is a system component
responsible for resolving references to functions and symbols in
shared libraries at runtime. It loads the necessary shared libraries into
memory and updates the program's symbol table with the addresses
of the functions and variables provided by these libraries.
• Shared Libraries: Shared libraries are compiled code modules
containing functions and symbols that can be dynamically linked to
executable programs. These libraries are typically stored in separate
files on disk and are loaded into memory when needed by one or
more programs.

Process of Dynamic Linking:

• Loading: When a program starts execution, the dynamic linker loads
the program's executable file into memory as usual. However, instead
of resolving all external references immediately, it leaves placeholders
or stubs for functions and symbols that are defined in shared libraries.
• Resolution: As the program executes and encounters calls to
functions or references to symbols in shared libraries, the dynamic
linker intervenes. It searches for the required functions or symbols in
the available shared libraries and updates the placeholders or stubs
with the actual memory addresses of these functions or symbols.
• Loading Shared Libraries: If a required shared library is not already
loaded into memory, the dynamic linker loads it from disk and
resolves references to functions and symbols in the same manner as
described above.
• Linking: Once all external references are resolved, the program's
address space contains the necessary code and data from both the
executable file and the shared libraries. The dynamic linker updates
the program's symbol table to reflect the resolved addresses, allowing
the program to execute seamlessly.
• Execution: With all external references resolved and shared libraries
loaded into memory, the program can continue its execution as usual.
It can call functions and access variables defined in shared libraries
without any issues.

Advantages of Dynamic Linking:

• Reduced Memory Usage: Dynamic linking allows multiple programs to
share a single copy of a library in memory, reducing memory usage
compared to static linking, where each program includes its copy of
the library.
• Easy Updates: Since shared libraries are loaded at runtime, updates
to a shared library automatically apply to all programs that use it
without requiring recompilation of the programs themselves.
• Faster Program Startup: By deferring the loading and linking of
shared libraries until they are needed, dynamic linking can reduce
SPCC Page 23
 to a shared library automatically apply to all programs that use it
without requiring recompilation of the programs themselves.
• Faster Program Startup: By deferring the loading and linking of
shared libraries until they are needed, dynamic linking can reduce
program startup time.
• Improved System Flexibility: Dynamic linking enables the system to
load and unload shared libraries dynamically, allowing for more
flexible memory management and resource allocation.

Example:
Consider a program that uses functions from a shared library [Link].
Instead of including the entire [Link] library in the executable file, the
program only contains references to the functions it needs. At runtime,
the dynamic linker loads [Link] into memory, resolves the
references, and updates the program's symbol table, allowing the
program to call the functions from [Link] as needed.

_________________________________________________________
____________________

16. Difference between Dynamic loading and Dynamic linking with

example (ls-4)
ANS:-
Dynamic Loading:
1. Loading Process:
Dynamic loading loads the libraries into memory only when they are
required during program execution.
2. Trigger:
Loading process is initiated explicitly by the program when it requires
access to a particular library or module.
3. Memory Usage:
Reduces memory usage as libraries are loaded into memory only
when they are required.
4. Program Startup:
Programs start more quickly because they do not need to load all
libraries at startup.
5. Example:
A multimedia application may dynamically load image processing
libraries only when the user requests to edit an image, and load video
processing libraries only when the user requests to edit a video.
6. Complexity:
Requires additional code to handle the loading and unloading of
libraries, increasing complexity.
7. Runtime Overhead:
There is a slight overhead associated with dynamically loading
libraries at runtime.
8. Dependencies:
The program needs to manage dependencies and explicitly handle
loading and unloading of libraries.
9. Flexibility:
Provides flexibility in terms of memory usage and program startup
time.
10. Example Scenario: - Consider a web browser that supports various
media formats. When a user tries to play a video file, the browser may
SPCC Page 24
 Provides flexibility in terms of memory usage and program startup
time.
10. Example Scenario: - Consider a web browser that supports various
media formats. When a user tries to play a video file, the browser may
dynamically load the necessary codecs only when required. This allows
the browser to start quickly and reduces memory usage.

Dynamic Linking:
1. Linking Process:
Dynamic linking is a technique in which the linking of libraries to an
executable program is deferred until runtime.
2. Deferred Linking:
Libraries are linked to the program at runtime rather than at compile
time.
3. Memory Usage:
Reduces memory usage as libraries are shared among multiple
programs.
4. Program Startup:
Slightly slower program startup compared to dynamic loading
because of the linking process at runtime.
5. Example:
A text editor application may use a shared library for spell checking.
Instead of statically linking the spell checking library at compile time,
the text editor is dynamically linked to the spell checking library at
runtime.
6. Runtime Overhead:
There is a slight overhead associated with dynamic linking because
the linking process occurs at runtime.
7. Dependency Management:
Introduces dependencies between the executable program and the
shared libraries it uses.
8. Simplified Updates:
Updates to shared libraries automatically apply to all programs that
use them.
9. Flexibility:
Provides flexibility in terms of memory usage and library updates.
10. Example Scenario: - Consider a Linux system where multiple
applications use the same C standard library (libc). Instead of each
application having its own copy of libc, the system dynamically links
each application to the shared libc library, reducing memory usage and
simplifying updates.

_________________________________________________________
____________________

17. What is relocation and Linking concept in loaders (ls-4)

ANS:-
Relocation:
Definition: Relocation is the process of adjusting the addresses of
symbols in an object file so that they point to the correct locations in
memory.
Purpose: When a program is compiled, it contains symbolic references
to memory locations. During relocation, these references are adjusted to
reflect the actual memory addresses where the program will be loaded.
Process: During relocation, the loader scans the object file, identifies the
SPCC Page 25
 Purpose: When a program is compiled, it contains symbolic references
to memory locations. During relocation, these references are adjusted to
reflect the actual memory addresses where the program will be loaded.
Process: During relocation, the loader scans the object file, identifies the
memory addresses that need to be adjusted, and calculates the correct
addresses based on the program's load location.
Example: Suppose a program contains a reference to a global variable x
at address 1000. If the program is loaded into memory at address 5000,
relocation is performed to adjust the reference to x to address 6000.

Linking:
Definition: Linking is the process of combining multiple object files and
libraries into a single executable file.
Purpose: The purpose of linking is to resolve symbolic references
between different object files and libraries and create a single executable
file that can be loaded into memory and executed.
Process: During linking, the linker combines the object files and libraries,
resolves symbolic references, performs relocation, and generates an
executable file.
Example: Suppose a program consists of multiple source files main.c,
util.c, and math.c. After compiling these source files into object files
(main.o, util.o, math.o), the linker combines them, resolves the
references between them, performs relocation, and generates a single
executable file ([Link]).

_________________________________________________________
____________________

18. Explain different types of Loaders in detail : absolute, relocating,

compile and go, direct linking, dynamic linking, dynamic loading
(ls-4)
ANS:-
1. Absolute Loader:

• Functionality:
Absolute loaders load an executable file into memory at a specific
location and execute it.
• Process:
SPCC Page 26
 • Functionality:
Absolute loaders load an executable file into memory at a specific
location and execute it.
• Process:
Reads the absolute machine code and loads it into memory at a
predetermined memory location specified in the program.
• Relocation:
No relocation is performed as the program is loaded at a fixed
memory location.
• Advantages:
Simple and fast loading process.
• Disadvantages:
Lack of flexibility as the program is always loaded at the same
memory location.
• Example:
Older systems that used absolute loading methods.
2. Relocating Loader:
• Functionality:
Relocating loaders load an executable file into memory and perform
relocation, adjusting the addresses of the program's symbols based
on the load location.
• Process:
Scans the object file, identifies the memory addresses that need to be
adjusted, and calculates the correct addresses based on the
program's load location.
• Types of Relocation:
Static Relocation: Relocation is performed at compile time.
Dynamic Relocation: Relocation is performed at runtime.
• Advantages:
Provides flexibility as the program can be loaded at different memory
locations.
• Disadvantages:
Requires additional processing to perform relocation.
• Example:
Modern operating systems use relocating loaders to load and execute
programs.
3. Compile and Go Loader:

• Functionality:
Compile and Go loaders compile the source code into machine code
and then load and execute it.
• Process:
Reads the source code, compiles it into machine code, loads the
machine code into memory, and executes it.
• Advantages:
Simplifies the loading process by combining compilation and loading
into a single step.
• Disadvantages:

SPCC Page 27
 Simplifies the loading process by combining compilation and loading
into a single step.
• Disadvantages:
Requires the entire program to be compiled before execution.
• Example:
Early systems where programs were compiled and executed
immediately.
4. Direct Linking Loader:
• Functionality:
Direct linking loaders link the object program with library routines by
placing library code directly into the object code.
• Process:
Combines the object program with library routines before loading it
into memory.
• Advantages:
Faster execution as library routines are directly integrated into the
object code.
• Disadvantages:
Increased memory usage as library routines are duplicated in each
object program.
• Example:
Early systems where library routines were linked directly into the
object code.
5. Dynamic Linking:
• Functionality:
Dynamic linking loaders load and link shared libraries or modules into
memory during runtime.
• Process:
Dynamically loads shared libraries or modules into memory when they
are needed during program execution.
• Advantages:
Saves memory by loading only the necessary modules.
Allows for the use of shared libraries, reducing disk space and
memory usage.
• Disadvantages:
Slight overhead associated with dynamic linking.
• Example:
Dynamic loading of libraries in modern operating systems and
applications.
6. Dynamic Loading:
• Functionality:
Dynamic loading loaders load executable modules into memory and
link them dynamically during runtime.
• Process:
Dynamically loads shared libraries or modules into memory when they
are needed during program execution.
• Advantages:
Saves memory by loading only the necessary modules.
• Disadvantages:
Requires additional code to handle the loading and unloading of
modules.
• Example:
Dynamic loading of modules in modern operating systems and
applications.
_________________________________________________________
SPCC Page 28
 • Example:
Dynamic loading of modules in modern operating systems and
applications.
_________________________________________________________
____________________

19. Explain absolute loader. State its advantages and disadvantages

ANS:
• Absolute Loader:
An absolute loader is a type of loader that loads an executable file
into memory at a specific location and executes it without performing
any relocation.
Reads the absolute machine code and loads it into memory at a
predetermined memory location specified in the program.
No relocation is performed as the program is loaded at a fixed
memory location.

• Advantages of Absolute Loader:

Simple and Fast Loading:
Absolute loaders have a simple and fast loading process as they do
not need to perform any relocation.
Less Memory Usage:
Absolute loaders require less memory and processing power
compared to relocating loaders as they do not need to perform any
relocation.
Suitable for Small Programs:
Absolute loaders are suitable for small programs where the memory
location is known in advance.

• Disadvantages of Absolute Loader:

Lack of Flexibility:
Absolute loaders lack flexibility as the program is always loaded at the
same memory location, making it difficult to load programs into
different memory locations.
Inefficient Memory Usage:
Absolute loaders lead to inefficient use of memory as programs
cannot be loaded into different memory locations, leading to memory
fragmentation.
Not Suitable for Large Programs:
Absolute loaders are not suitable for large programs or systems with
limited memory as they cannot perform relocation, making it difficult to
load large programs into memory.
_______________________________________________________
______________________

20. Explain different phrases of compiler with example (LS 5)

Ans:
A compiler is a complex software system that converts source code
written in a high-level programming language into machine code that can
be executed directly by the computer’s processor. The compilation
process involves several phases, each of which plays a crucial role in
transforming the source code into machine code. Here are the different
phases of a compiler with examples:
• Lexical Analysis (Tokenization): This phase breaks the source code
into a sequence of tokens, such as keywords, identifiers, literals, and
symbols. For example, the source code int x = 5; would be tokenized
into the following tokens: INT, x, =, 5, ;.
SPCC Page 29
 • Lexical Analysis (Tokenization): This phase breaks the source code
into a sequence of tokens, such as keywords, identifiers, literals, and
symbols. For example, the source code int x = 5; would be tokenized
into the following tokens: INT, x, =, 5, ;.

• Syntax Analysis (Parsing): This phase analyzes the tokens produced

in the previous phase and checks whether they conform to the rules
of the programming language. For example, the parser would check
that the tokens INT, x, =, 5, ; form a valid declaration statement.

• Semantic Analysis (Analysis): This phase checks the meaning of the

source code, including the types of variables, the scope of identifiers,
and the relationships between variables. For example, the analyzer
would check that the variable x is declared as an integer and that the
assignment x = 5 is valid.

• Intermediate Code Generation: This phase generates an intermediate

representation of the source code, such as three-address code, which
is a low-level, platform-independent representation of the code. For
example, the intermediate code for the source code int x = 5; might
be x := 5;.

• Optimization: This phase analyzes the intermediate code and applies

various optimizations to improve the performance of the generated
machine code. For example, the optimizer might eliminate
unnecessary assignments or reorder operations to reduce the number
of instructions.

• Code Generation: This phase converts the optimized intermediate

code into machine code that can be executed directly by the
computer’s processor. For example, the code generator might
produce machine code that loads the value 5 into a register and
stores it in the memory location corresponding to the variable x.

• Code Emission: This phase writes the generated machine code to a

file or loads it into memory for execution. For example, the code
emitter might write the machine code to a file called [Link] or load it
into memory for execution.

Here’s an example of the compilation process:

Source Code: int x = 5;
1. Lexical Analysis: INT, x, =, 5, ;
2. Syntax Analysis: Valid declaration statement
3. Semantic Analysis: x is declared as an integer, assignment is valid
4. Intermediate Code Generation: x := 5;
5. Optimization: Eliminate unnecessary assignments
6. Code Generation: Load 5 into a register and store it in memory
location x
7. Code Emission: Write machine code to file [Link] or load into memory
for execution
_________________________________________________________
____________________

20. Compare Bottom up and top down parser (LS 5)

ANS:

SPCC Page 30
20. Compare Bottom up and top down parser (LS 5)
ANS:

_________________________________________________________
____________________

21. Short note on Syntax directed analysis (LS 5)

ANS:
Syntax Directed Translation has augmented rules to the grammar that
facilitate semantic analysis. SDT involves passing information bottom-up
and/or top-down to the parse tree in form of attributes attached to the
nodes. Syntax-directed translation rules use 1) lexical values of nodes,
2) constants & 3) attributes associated with the non-terminals in their
definitions.
The general approach to Syntax-Directed Translation is to construct a
parse tree or syntax tree and compute the values of attributes at the
nodes of the tree by visiting them in some order. In many cases,
translation can be done during parsing without building an explicit tree.

Example :

E -> E+T | T
T -> T*F | F
F -> INTLIT

This is a grammar to syntactically validate an expression having

additions and multiplications in it. Now, to carry out semantic analysis we
will augment SDT rules to this grammar, in order to pass some
information up the parse tree and check for semantic errors, if any. In
this example, we will focus on the evaluation of the given expression, as
we don’t have any semantic assertions to check in this very basic
example.

E -> E+T { [Link] = [Link] + [Link] } PR#1

SPCC Page 31
 we don’t have any semantic assertions to check in this very basic
example.

E -> E+T { [Link] = [Link] + [Link] } PR#1

E -> T { [Link] = [Link] } PR#2
T -> T*F { [Link] = [Link] * [Link] } PR#3
T -> F { [Link] = [Link] } PR#4
F -> INTLIT { [Link] = [Link] } PR#5

For understanding translation rules further, we take the first SDT

augmented to [ E -> E+T ] production rule. The translation rule in
consideration has val as an attribute for both the non-terminals – E & T.
Right-hand side of the translation rule corresponds to attribute values of
the right-side nodes of the production rule and vice-versa. Generalizing,
SDT are augmented rules to a CFG that associate 1) set of attributes to
every node of the grammar and 2) a set of translation rules to every
production rule using attributes, constants, and lexical values.
Let’s take a string to see how semantic analysis happens – S = 2+3*4.
Parse tree corresponding to S would be

Advantages of Syntax Directed Translation:

• Ease of implementation: SDT is a simple and easy-to-implement method
for translating a programming language. It provides a clear and
structured way to specify translation rules using grammar rules.
• Separation of concerns: SDT separates the translation process from the
parsing process, making it easier to modify and maintain the compiler. It
also separates the translation concerns from the parsing concerns,
allowing for more modular and extensible compiler designs.
• Efficient code generation: SDT enables the generation of efficient code
by optimizing the translation process. It allows for the use of techniques
such as intermediate code generation and code optimization.

Disadvantages of Syntax Directed Translation:

• Limited expressiveness: SDT has limited expressiveness in comparison
to other translation methods, such as attribute grammars. This limits the
types of translations that can be performed using SDT.
• Inflexibility: SDT can be inflexible in situations where the translation rules
are complex and cannot be easily expressed using grammar rules.
• Limited error recovery: SDT is limited in its ability to recover from errors
during the translation process. This can result in poor error messages
and may make it difficult to locate and fix errors in the input program.

_________________________________________________________
____________________

22. Compare compiler and Interpreter (LS 5)

SPCC Page 32
 ____________________

22. Compare compiler and Interpreter (LS 5)

ANS:

_________________________________________________________
____________________

23. Explain compiler with Interpreter (LS 5)

ANS:
A compiler and an interpreter are two different approaches to translating
source code written in a high-level programming language into machine
code that can be executed by a computer. While both compilers and
interpreters can be used to convert source code into machine code, they
work in different ways and have distinct characteristics.

Compiler:
A compiler is a program that translates source code written in a high-
level programming language into machine code.
The compiled machine code is then stored in an object file, which can be
linked with other object files to create an executable file. The executable
file can be run directly on the computer.

Interpreter:
An interpreter, on the other hand, is a program that translates source
SPCC Page 33
 Interpreter:
An interpreter, on the other hand, is a program that translates source
code written in a high-level programming language into machine code
line by line, as it is executed. The interpreter does not generate machine
code ahead of time; instead, it translates the source code into machine
code as it is executed. This means that the interpreter does not require a
compilation step, and the source code is executed directly.

Key differences:
• Compilation vs. Interpretation: Compilers translate the entire source
code into machine code ahead of time, while interpreters translate the
source code line by line as it is executed.
• Code generation: Compilers generate machine code, while interpreters
do not generate machine code; instead, they translate the source code
into machine code as it is executed.
• Code optimization: Compilers can optimize the generated machine code
to improve performance, while interpreters do not have the opportunity to
optimize the code.
• Error handling: Compilers can detect and report errors at compile-time,
while interpreters detect and report errors at runtime.
• Execution speed: Compiled code is generally faster than interpreted
code, as the machine code has already been generated and optimized.
Interpreted code, on the other hand, is slower, as the interpreter
translates the source code into machine code line by line.
_________________________________________________________
____________________

24. Short note on Operator Precedence parsing

Operator Precedence Parsing:
Operator Precedence Parsing is a simple and efficient method for
parsing expressions based on the precedence of operators.
Operator Precedence Parsing is a method for parsing expressions
based on the precedence of operators.
-Process:
- It uses a table of operator precedence to determine the order in which
operators should be applied when parsing an expression.

- Algorithm:
- The algorithm scans the input expression from left to right,
maintaining two stacks: one for operands and one for operators.
- It compares the precedence of the current operator with the
precedence of the operator on the top of the operator stack.
- If the precedence of the current operator is higher, it pushes the
operator onto the operator stack.
- If the precedence of the current operator is lower or equal, it performs
the necessary operations using the top elements of the operand stack
until the precedence is satisfied, and then pushes the current operator
onto the operator stack.

- Example:
```plaintext
Expression: 2 + 3 * 4
SPCC Page 34
 - Example:
```plaintext
Expression: 2 + 3 * 4

Stack: [2] []
Stack: [2] [+]
Stack: [2, 3] [+]
Stack: [2, 3] [+, *]
Stack: [2, 3, 4] [+, *]
```

- Advantages:
- Simple and efficient parsing technique for expressions.
- Requires minimal memory and processing power.

- Disadvantages:
- Limited to expressions with unary and binary operators.
- May require additional rules to handle associativity.

Operator Precedence Parsing is a simple and efficient method for

parsing expressions based on the precedence of operators. It uses a
table of operator precedence to determine the order in which operators
should be applied when parsing an expression, making it a popular
choice for implementing expression parsers in compilers and
interpreters.
_________________________________________________________
____________________

25. Compare pattern, lexeme and token (LS 5)

Criteria Token Lexeme Pattern

Definiti Token is basically a It is a sequence of It specifies a
on sequence of characters in the source set of rules
characters that are code that are matched by that a
treated as a unit as given predefined language scanner
it cannot be further rules for every lexeme to follows to
broken down. be specified as a valid create a
token. token.
Interpre all the reserved int, goto The
tation keywords of that sequence of
of type language(main, characters
Keywor printf, etc.) that make the
d keyword.
Interpre name of a variable, main, a it must start
tation function, etc with the
of type alphabet,
Identifie followed by
r the alphabet
or a digit.
Interpre all the operators are +, = +, =
tation considered tokens.
of type
Operato
r
SPCC Page 35
 tation considered tokens.
of type
Operato
r
Interpre each kind of (, ), {, } (, ), {, }
tation punctuation is
of type considered a token.
Punctu e.g. semicolon,
ation bracket, comma,
etc.
Interpre a grammar rule or “Welcome to any string of
tation boolean literal. GeeksforGeeks!” characters
of type (except ‘ ‘)
Literal between ”
and “

_________________________________________________________
____________________

26. What are the different ways of representing intermediate code

explain with example (LS 6)
ANS:
• Postfix Notation:
• Also known as reverse Polish notation or suffix notation.
• In the infix notation, the operator is placed between operands, e.g., a +
b. Postfix notation positions the operator at the right end, as in ab +.
• For any postfix expressions e1 and e2 with a binary
operator (+) , applying the operator yields e1e2+.
• Postfix notation eliminates the need for parentheses, as the operator’s
position and arity allow unambiguous expression decoding.
• In postfix notation, the operator consistently follows the operand.
Example 1: The postfix representation of the expression (a + b) * c is :
ab + c *
Example 2: The postfix representation of the expression (a – b) * (c + d)
+ (a – b) is : ab – cd + *ab -+

Three-Address Code:
• A three address statement involves a maximum of three references,
consisting of two for operands and one for the result.
• A sequence of three address statements collectively forms a three
address code.
• The typical form of a three address statement is expressed as x = y op z,
where x, y, and z represent memory addresses.
• Each variable (x, y, z) in a three address statement is associated with a
specific memory location.
• While a standard three address statement includes three references,
there are instances where a statement may contain fewer than three
references, yet it is still categorized as a three address statement.
Example: The three address code for the expression a + b * c + d : T1 =
b * c T2 = a + T1 T3 = T2 + d; T 1 , T2 , T3 are temporary variables.
There are 3 ways to represent a Three-Address Code in compiler
design:
i) Quadruples
ii) Triples
SPCC Page 36
 There are 3 ways to represent a Three-Address Code in compiler
design:
i) Quadruples
ii) Triples
iii) Indirect Triples

Syntax Tree:
• A syntax tree serves as a condensed representation of a parse tree.
• The operator and keyword nodes present in the parse tree undergo a
relocation process to become part of their respective parent nodes in the
syntax tree. the internal nodes are operators and child nodes are
operands.
• Creating a syntax tree involves strategically placing parentheses within
the expression. This technique contributes to a more intuitive
representation, making it easier to discern the sequence in which
operands should be processed.
• The syntax tree not only condenses the parse tree but also offers an
improved visual representation of the program’s syntactic structure,
Example: x = (a + b * c) / (a – b * c)

• _________________________________________________________
____________________

27. Explain different issues in code generation (LS 6)

ANS:
In the code generation phase, various issues can arises:
• Input to the code generator
• Target program
• Memory management
• Instruction selection
• Register allocation
• Evaluation order

1. Input to the code generator

• The input to the code generator contains the intermediate
representation of the source program and the information of the
symbol table. The source program is produced by the front end.
• Intermediate representation has the several choices:
a) Postfix notation
b) Syntax tree
c) Three address code
• We assume front end produces low-level intermediate representation
i.e. values of names in it can directly manipulated by the machine
SPCC Page 37
 b) Syntax tree
c) Three address code
• We assume front end produces low-level intermediate representation
i.e. values of names in it can directly manipulated by the machine
instructions.
• The code generation phase needs complete error-free intermediate
code as an input requires.

2. Target program:
The target program is the output of the code generator. The output can
be:
a) Assembly language: It allows subprogram to be separately compiled.
b) Relocatable machine language: It makes the process of code
generation easier.
c) Absolute machine language: It can be placed in a fixed location in
memory and can be executed immediately.

3. Memory management
• During code generation process the symbol table entries have to be
mapped to actual p addresses and levels have to be mapped to
instruction address.
• Mapping name in the source program to address of data is co-
operating done by the front end and code generator.
• Local variables are stack allocation in the activation record while
global variables are in static area.

4. Instruction selection:
• Nature of instruction set of the target machine should be complete
and uniform.
• When you consider the efficiency of target machine then the
instruction speed and machine idioms are important factors.
• The quality of the generated code can be determined by its speed and
size.

5. Register allocation
• Register can be accessed faster than memory. The instructions
involving operands in register are shorter and faster than those
involving in memory operand.
• The following sub problems arise when we use registers:
• Register allocation: In register allocation, we select the set of
variables that will reside in register.
• Register assignment: In Register assignment, we pick the register that
contains variable.
• Certain machine requires even-odd pairs of registers for some
operands and result.

6. Evaluation order
• The efficiency of the target code can be affected by the order in which
the computations are performed. Some computation orders need
fewer registers to hold results of intermediate than others.

_________________________________________________________
____________________

28. Explain different code optimization techniques (LS 6)

ANS:
SPCC Page 38
 ____________________

28. Explain different code optimization techniques (LS 6)

ANS:

_________________________________________________________
____________________

29. Write short note on Peephole optimization (LS 6)

A statement-by-statement code-generations strategy often produce
target co<le that
contains redundant instructions and suboptimal constructs. The quality
of such target code can
be improved by applying "optimizing" transformations to the target
program.
A simple but effective technique for improving the target code is
peephole [Link],
a method for trying to improving the performance of the target program
by examining II short
sequence of target instructions (called the peephole) and replacing these
instructions by a
shorter sequence, whenever possible.
1l1e peephole is u small, moving window on the target program. The
code in the
peephole need not contiguous, although some implementations do
require this. It is
characteristic of peephole optimization that each improvement may
spawn opportunities for
additional improvements.

We shall give the following examples of program transformations that

are charecteristics
of peephole optimizations:

[Link] Instruction Elimination:

Redundant instruction elimination removes instructions that have no
effect on the program's behavior or produce the same result as a
previous instruction.
SPCC Page 39
 [Link] Instruction Elimination:
Redundant instruction elimination removes instructions that have no
effect on the program's behavior or produce the same result as a
previous instruction.
2. Constant Folding:
Constant folding evaluates constant expressions at compile time and
replaces them with their computed values.
3. Algebraic Simplification:
Algebraic simplification optimizes algebraic expressions to reduce the
number of instructions needed to compute the result.
4. Common Subexpression Elimination:
Common subexpression elimination identifies and eliminates
redundant calculations that produce the same result within the same
basic block.
5. Instruction Combining:
Instruction combining optimizes code by combining multiple
instructions into a single, more efficient instruction.
6. Register Allocation Optimization:
Register allocation optimization minimizes memory accesses by
efficiently using registers for temporary variables.

Advantages:
Simple and easy to implement.
Can result in significant improvements in code size and execution speed.
Complements other optimization techniques and can be applied
repeatedly in different phases of the compiler.

Disadvantages:
Limited to local optimizations and may not capture global optimization
opportunities.
Requires careful tuning of the peephole size and optimization rules to
avoid excessive compilation time.
_________________________________________________________
____________________

30. What is the need of intermediate code generation

(LS 6)
• Portability:
Intermediate code serves as a platform-independent representation of
the source code, allowing the compiler to generate target-specific
code for different architectures without modifying the source code.
• Optimization:
Intermediate code provides an intermediate representation that is
easier to analyze and optimize. Optimization techniques can be
applied to the intermediate code to improve the efficiency and
performance of the generated target code.
• Simplification of Compilation Process:
Intermediate code generation simplifies the compilation process by
breaking it down into smaller, more manageable steps. It separates
the front-end (analysis) phase from the back-end (synthesis) phase,
making the compiler design modular and extensible.
• Code Generation:
Intermediate code serves as input to the code generation phase,
where it is translated into target machine code. By generating
intermediate code, the compiler can focus on generating efficient
target code without having to directly analyze the complex syntax and
semantics of the source language.
SPCC Page 40
 where it is translated into target machine code. By generating
intermediate code, the compiler can focus on generating efficient
target code without having to directly analyze the complex syntax and
semantics of the source language.
• Error Detection and Reporting:
Intermediate code generation allows the compiler to detect and report
errors in the source code more effectively. Errors can be identified at
the intermediate code level, making it easier to locate and debug
issues in the source code.
• Support for High-Level Constructs:
Intermediate code provides a suitable representation for high-level
language constructs, making it easier to handle complex language
features such as functions, loops, and data structures during the
compilation process.
• Support for Optimization Techniques:
Intermediate code provides a convenient representation for applying
various optimization techniques such as constant folding, common
subexpression elimination, and loop optimization. These optimizations
can be applied more effectively to intermediate code than to source
code.
_________________________________________________________
____________________

31. Explain Machine Independent code optimization techniques

(LS 6)
Machine Independent code optimization tries to make the intermediate
code more efficient by transforming a section of code that doesn’t
involve hardware components like CPU registers or any absolute
memory location. Generally, it optimizes code by eliminating
redundancies, reducing the number of lines in code, eliminating useless
code or reducing the frequency of repeated code. Thus can be used on
any processor irrespective of machine specifications.
Machine independent code optimization can be achieved using the
following methods:

Function Preserving Optimization :

Function Preserving optimizations deals with the code in a given function
in an attempt of reducing the computational time.
It can be achieved by following methods:
• Common Subexpression elimination
• Folding
• Dead code elimination
• Copy Propagation

1. Common Subexpression elimination :

A common subexpression is the one which was computed and doesn’t
change after it last computation, but is often repeated in the program.
The compiler evaluates its value even if it does not change. Such
SPCC Page 41
 1. Common Subexpression elimination :
A common subexpression is the one which was computed and doesn’t
change after it last computation, but is often repeated in the program.
The compiler evaluates its value even if it does not change. Such
evaluations result in wastage of resources and time. Thus it better be
eliminated.

2. Constant Folding :
Constant Folding is a technique where the expression which is
computed at compile time is replaced by its value. Generally, such
expressions are evaluated at runtime, but if we replace them with their
values they need not be evaluated at runtime, saving time.

3. Dead Code Elimination :

Dead code is a program snippet that is never executed or never reached
in a program. It is a code that can be efficiently removed from the
program without affecting any other part of the program. In case, a value
is obtained and never used in the future, it is also regarded as dead
code.

4. Copy Propagation :
Copy Propagation suggests to use one variable instead of other, in
cases where assignments of the form x=y are used. These assignments
are copy statements. We can efficiently use y at all required place
instead of assign it to x. In short, elimination of copies in the code is
Copy Propagation.

Loop Optimizations :
The program spends most of its time inside the loops. Thus the loops
determine the time complexity of the program. So, in order to get an
optimal and efficient code, loop optimization is required. In order to apply
loop optimization, we first need to detect the loop using control flow
analysis with the help of program flow graph. A cycle in a program flow
graph will indicate presence of a loop. Note that, the code from
Intermediate code Generation phase which is in three-address format is
given as input to the optimization phase. It is difficult to identify loops in
such a format, thus a program flow graph is required.
The program flow graph consists of basic blocks, which is nothing but
the code divided into parts or blocks and show the execution flow of the
code,

Sample Program flow graph

The cycle in the above graph shows a presence of loop from block 2 to
block3.
Once the loops are detected following Loop Optimization techniques can
be applied :
• Frequency Reduction
• Algebraic expression simplification
• Strength Reduction
SPCC Page 42
 be applied :
• Frequency Reduction
• Algebraic expression simplification
• Strength Reduction
• Redundancy Elimination

1. Frequency Reduction :
It applies to the concept that a loop runs for least possible lines of code.
It can be achieved by following methods:
a. Code Motion :
Many times, in a loop, statements that remain unchanged for every
iteration are included in the loop. Such statements are loop invariants
and only result in the program spending more time inside the loop. Code
motion simply moves loop invariant code outside the loop, reducing the
time spent inside the loop.

b. Loop Unrolling :
If a loop runs doing the same operation for every iteration, we can
perform that same operation inside the loop more than once. This is
called loop unrolling. Such unrolled loop will perform the evaluation more
than once in a single loop iteration.

c. Loop Jamming :
Combining the loops that carry out the same operations is called as loop
jamming.
Thus, instead of executing same loops twice, that operation can be done
by executing the loop only once.

2. Algebraic expression simplification :

A program might contain some trivial algebraic expressions that do not
result in any useful computation or change of value. Such lines of code
can be eliminated so the compiler doesn’t waste time evaluating it. For
example,
A=A+0;
x=x*1;
These statements do not result in any useful computations. Such code
may seem harmless, but when used inside any loops they keep on being
evaluated by compiler. Thus it is best to eliminate them.

3. Strength Reduction :
It suggests replacing a costly operation like multiplication with a cheaper
one.
Example:
a*4
after reduction
a<<2
It is an important optimization for programs where array accesses occur
within loops and should be used with integer operands only.

4. Redundancy Elimination :
It may happen, that a specific expression is repeated in a code many
times. This expression is redundant to code because we may evaluate it
once and substitute its next occurrence with its evaluated value. This
substitution is nothing but redundancy elimination. Redundancy
elimination avoids evaluating the same expressions multiple times
resulting in faster execution.

SPCC Page 43
 substitution is nothing but redundancy elimination. Redundancy
elimination avoids evaluating the same expressions multiple times
resulting in faster execution.

_________________________________________________________
____________________
32. Explain the concept of basic blocks and flow graph with example
the three address code (LS 6)

In compiler design, a basic block is a sequence of consecutive

statements in which flow of control enters at the beginning and leaves at
the end without halt or possibility of branching except at the end. Basic
blocks are the building blocks for control flow analysis and optimization.

A flow graph is a graphical representation of a program's control flow. It

consists of nodes (basic blocks) connected by directed edges that
represent control flow between the basic blocks.

Three-Address Code:

1. t1 = a + b
2. t2 = c * d
3. t3 = t1 - t2
4. t4 = t1 * t3
5. e = t4 + t3
6. f = e - t1
Basic Blocks:
A basic block is a sequence of consecutive statements with the following
properties:
• Flow of control enters at the beginning.
• Flow of control leaves at the end.
• No branch or jump except at the end.

Basic Block 1:
t1 = a + b
t2 = c * d
In this block, control enters at statement 1 and leaves at statement 2.
There are no branches or jumps within this block.

Basic Block 2:
t3 = t1 - t2
t4 = t1 * t3
Control enters at statement 3 and leaves at statement 4. There are no
branches or jumps within this block.

Basic Block 3:
e = t4 + t3
Control enters at statement 5 and leaves at statement 5. There is only
one statement in this block.

Basic Block 4:
f = e - t1
Control enters at statement 6 and leaves at statement 6. There is only
one statement in this block.

Flow Graph:

SPCC Page 44
one statement in this block.

Flow Graph:
A flow graph is a graphical representation of a program's control flow.
Each basic block is represented as a node in the graph, and directed
edges represent the flow of control between the basic blocks.

+-------+
| Block 1|
+---+---+
|
v
+---+---+
| Block 2|
+---+---+
|
v
+---+---+
| Block 3|
+---+---+
|
v
+---+---+
| Block 4|
+-------+

In the flow graph:

Each basic block is represented by a node.
Directed edges represent the flow of control between basic blocks.
Flow graphs provide a visual representation of a program's control flow,
making it easier to analyze and optimize.

SPCC Page 45
SPCC Page 46