Compiler Design

Answers of Compiler Design(PYQ)
Pure and impure interpreters
In a pure interpreter, the source program is maintained in the source form throughout its
interpretation. This arrangement acquires substantial analysis overheads when interpreting
a statement.
An impure interpreter carries out some preliminary processing of the source program to
decrease the analysis overheads during interpretation. The preprocessor transforms the
program to an intermediate representation (IR) that is used during interpretation. This
speeds up interpretation since the code component of the IR that is the IC, can be analyzed
more resourcefully than the source form of the program.
Removal of left recursion
A → A α |β.
The above Grammar is left recursive because the left of production is occurring
at a first position on the right side of production. It can eliminate left recursion
by replacing a pair of production with
A → βA′
A → αA′|ϵ
Elimination of Left Recursion
Left Recursion can be eliminated by introducing new non-terminal A such that.

Symbol Table is an important data structure created and maintained by the
compiler in order to keep track of semantics of variables .
Items stored in Symbol table:
 Variable names and constants
 Procedure and function names
 Literal constants and strings
 Compiler generated temporaries
 Labels in source languages
Information used by the compiler from Symbol table:
 Data type and name
 Declaring procedures
 Offset in storage
 If structure or record then, a pointer to structure table.
 For parameters, whether parameter passing by value or by reference
 Number and type of arguments passed to function
 Base Address
How relocation is performed by linker

Relocation is an essential task performed by the linker in the process of
creating an executable program or shared library from multiple object files
(compiled source code). Relocation is necessary because object files contain
references to symbols (functions, variables, etc.) that are defined in other object
files or libraries. These references need to be resolved to their actual memory
locations during the linking process.
Here's a step-by-step explanation of how relocation is performed by a linker:
1. Symbol Table: During compilation, each object file generates a symbol table
that contains information about the symbols (functions, variables, etc.)
defined in the object file and their associated addresses or offsets. Symbols
can be either external (defined in other files) or internal (defined within the
same file).
2. Linker Input: The linker takes as input one or more object files, along with
any required libraries. These object files may contain references to external
symbols that are not defined within the same file.
3. Symbol Resolution: The linker first resolves all external symbol references. It
does this by searching the symbol tables of all input files and libraries to find
the definitions of the required symbols. If a symbol is not found, it may result
in a linker error.
4. Relocation Entries: Once the linker has resolved external symbol references,
it identifies the locations within the code and data sections of the object files
where these references exist. These locations are marked with relocation
entries or records.
5. Adjusting Addresses: The linker calculates the actual addresses or offsets of

the symbols being referenced and modifies the relocation entries
accordingly. It updates the object files to reflect the resolved addresses or
offsets.
6. Generating the Final Output: After all relocation entries have been processed
and addresses adjusted, the linker combines the modified object files to
produce the final executable program or shared library. This output file
contains the resolved symbols and their correct addresses.
7. Symbol Table Stripping: Depending on the linker options and requirements,

the symbol tables from the object files may be stripped from the final output
to reduce the size and protect the symbols from being accessed externally.
In summary, relocation is a crucial task performed by the linker to ensure that

symbols referenced across different object files are correctly resolved to their
actual memory locations or offsets. This process allows the creation of a
coherent and functional executable program or shared library from multiple
source code files and libraries.
Absolute Loader, Relocating Loader, and Direct Linking Loader are different types of
loaders used in the context of loading and executing programs in a computer system.
They differ in terms of their functionality and purpose:
1. Absolute Loader:
 Functionality: An absolute loader is the simplest type of loader. It loads a
program into memory without making any adjustments or relocations. The
program is loaded at a specific, fixed memory location.
 Addressing: All addresses in the program are assumed to be absolute and fixed.
This means that the program must be loaded into the same memory location
every time it runs.
 Use Case: Absolute loaders are typically used on older systems where memory
management was simple, and programs were designed to run from a specific
memory address.
2. Relocating Loader:
 Functionality: A relocating loader is more advanced than an absolute loader. It
loads a program into memory and can adjust the program's memory references
based on the actual location where it is loaded.
 Addressing: Programs can use relative addresses, and the loader will adjust these
addresses at load time to reflect the actual memory location where the program
is loaded.
 Use Case: Relocating loaders are used in systems where programs need to be
loaded into different memory locations, and the loader is responsible for
resolving the addresses to match the current loading location.
3. Direct Linking Loader:
 Functionality: A direct linking loader combines the functions of a linker and a
loader. It not only loads a program into memory but also resolves references to
external symbols (functions or variables) by linking them to their actual memory
locations.
 Addressing: Programs can use symbolic references to external symbols, and the
direct linking loader will replace these references with actual addresses during
loading.
 Use Case: Direct linking loaders are commonly used in modern computer
systems to handle modular programming, where code is divided into separate
modules, and references between modules need to be resolved during the
loading process.
In summary, the key differences lie in their capabilities regarding address handling and
symbol resolution:
 Absolute Loader loads programs at fixed memory locations with no address

adjustments.
 Relocating Loader adjusts addresses in the program to match the loading location,
allowing for flexibility in memory allocation.
 Direct Linking Loader not only loads the program but also resolves symbolic
references to external symbols, enabling modular programming and dynamic linking.
The choice of loader depends on the specific requirements of the computer system and
the type of programming used. Modern systems often use more advanced loaders like
direct linking loaders to support flexible and modular program development.
problems with top down parsing

Top-down parsing is a parsing technique used in the field of compiler construction and natural
language processing. It starts from the highest-level grammar rule and recursively breaks down the
input into smaller parts until it reaches the terminal symbols. While top-down parsing has its
advantages, it also has some problems and limitations:
1. Left-Recursion Problem: One of the major issues with top-down parsing is left recursion. When a
grammar rule directly or indirectly refers to itself from the left side, it can lead to infinite loops during
parsing. Top-down parsers often struggle with handling left-recursive grammars, and they require
modifications or additional techniques to handle them.
2. Ambiguity Problem: If the grammar of the language being parsed is ambiguous, meaning that
there are multiple valid parse trees for a single input, top-down parsers may not be able to resolve
the ambiguity effectively. Ambiguity can lead to unpredictable parsing results.
3. Predictive Parsing: Top-down parsing often relies on predictive parsing tables (e.g., LL(1) tables) to
make parsing decisions. Constructing these tables can be challenging, especially for grammars with
conflicts or ambiguities. Resolving these conflicts may require manual intervention, which can be
cumbersome for larger grammars.
4. Limited Expressiveness: Some context-sensitive languages or constructs are challenging to parse
using top-down techniques. Context-sensitive languages, which cannot be parsed using context-free
grammars, may require more powerful parsing techniques such as LR parsing.
5. Performance Overhead: In some cases, top-down parsers can be less efficient than bottom-up
parsers like LR parsers. They may require more backtracking or trial-and-error parsing, which can
lead to performance overhead, especially for large input strings.
6. Difficulty Handling Operator Precedence: Parsing expressions with operator precedence and
associativity can be complex with top-down parsing. It may require additional grammar rules and
precedence levels to ensure correct parsing.
7. Recursive Descent Parsing: Recursive descent parsing is a specific type of top-down parsing where
each non-terminal in the grammar corresponds to a recursive function in the parser code. This
approach can lead to excessive function calls and inefficient parsing for some grammars.

Compiler Design

Uploaded by

Copyright:

Available Formats

Compiler Design

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Compiler Design

Uploaded by

Copyright:

Available Formats

Answers of Compiler Design(PYQ)

Pure and impure interpreters

Removal of left recursion

Elimination of Left Recursion

Left Recursion can be eliminated by introducing new non-terminal A such that.

How relocation is performed by linker

Here's a step-by-step explanation of how relocation is performed by a linker:

5. Adjusting Addresses: The linker calculates the actual addresses or offsets of

7. Symbol Table Stripping: Depending on the linker options and requirements,

In summary, relocation is a crucial task performed by the linker to ensure that

 Absolute Loader loads programs at fixed memory locations with no address

problems with top down parsing

You might also like