B.Tech (Sem V) – Theory Notes & Exam Answers
SECTION A – Short Answer Type
a. Parse Tree vs Abstract Syntax Tree (AST)
A parse tree shows the complete grammatical structure of the source program including all grammar symbols, while an AST is a simplified version that removes unnecessary grammar details and represents the essential structure.
b. Problems with Top-Down Parser
Top-down parsers cannot handle left recursion, require grammar transformations like left factoring, and may face backtracking issues.
c. Errors in Compilation Process
Lexical errors, syntactic errors, semantic errors, runtime errors, and logical errors may occur during compilation.
d. Types of Attributes
Two types of attributes are synthesized attributes and inherited attributes, used in syntax-directed translation.
e. Language Translator and Compiler
A language translator converts code from one language to another. A compiler translates high-level language into machine code.
f. Hashing
Hashing is a technique used to store and retrieve data efficiently using a hash function, commonly used in symbol tables.
g. Left Factoring
Left factoring removes common prefixes in grammar productions to make them suitable for predictive parsing.
h. Left Recursion
A grammar is left recursive if a non-terminal derives itself as the leftmost symbol.
Given grammar:
E → E+E | E*E | a | b
Yes, it is left recursive.
i. Ambiguous Grammar
A grammar is ambiguous if it produces more than one parse tree for the same string.
Example:
E → E+E | id
j. Shift-Reduce Conflicts
Shift-reduce conflict and reduce-reduce conflict occur during bottom-up parsing.
SECTION B – Descriptive Answers
Activation Record & Runtime Storage
An activation record stores information about a function call such as parameters, return address, local variables, and temporaries. It plays a key role in runtime storage management.
Intermediate Code Representation
For expression:
(x + y)*(y + z) + (x + y + z)
Intermediate representations include quadruples, triples, and indirect triples, which help in optimization and code generation.
Basic Block, Flow Graph & Next Use
A basic block is a sequence of instructions with single entry and exit.
A flow graph represents control flow among basic blocks.
Next-use information helps in register allocation.
Predictive Parsing
Predictive parsing uses FIRST and FOLLOW sets to build a parse table and avoids backtracking.
SECTION C – Long Answer Type
SLR Parsing Table
SLR parser uses LR(0) items and FOLLOW sets to build parsing tables. It is simpler but less powerful than LALR and CLR parsers.
Stack vs Heap Allocation
Stack allocation is fast and uses LIFO order, while heap allocation is flexible but slower and used for dynamic memory.
Syntax Directed Definition
SDD associates grammar rules with semantic rules to generate intermediate code.
DAG & Peephole Optimization
DAG removes redundant computations in basic blocks.
Peephole optimization improves code by eliminating inefficient instruction patterns.
Lexical & Syntactic Errors
Lexical errors occur during tokenization, while syntactic errors occur due to grammar violations. Error recovery includes panic mode and phrase-level recovery.
Induction Variable Optimization
Induction variables change linearly in loops and can be optimized to reduce repeated calculations.
LL(1) Grammar Test
A grammar is LL(1) if parsing table has no conflicts. FIRST and FOLLOW sets are used for testing.
Static vs Dynamic Scope
Static scope is determined at compile time, while dynamic scope is decided at runtime.
Code Generator Issues
Instruction selection, register allocation, and instruction scheduling are major design issues.
Three Address Code
Three address code represents control structures using labels, jumps, and temporary variables.
