CD Question Bank

on
https://docs.google.com/document/d/1_tZw7fmp25hnfVD4SUGDw4W-WDHG0o5h/edit?usp=sharing&ouid=112711162618141236570&rtpof=true&sd=true




This document is a detailed Question Bank organized into five units covering core concepts in Compiler Design, complete with Multiple Choice Questions (MCQs), Fill in the Blanks, Match the Following, and descriptive 5-Marks Questions.

The structure of the questions also includes the Bloom's Taxonomy Level (BTL: 1. Remembering to 6. Creating) and the corresponding Course Outcome (CO).UNIT I: Introduction & Lexical Analysis

This unit focuses on the initial stages of compilation, covering the role and structure of a compiler and the process of lexical analysis.
  • Compiler Fundamentals: The primary function of a compiler is to translate programs written in a high-level language into machine code. The phases of a compiler include Lexical analysis, Syntax analysis, Semantic analysis, and Code generation.
  • Lexical Analysis: The purpose is to break the source code into tokens (such as identifiers, symbols, or keywords). Key tools and concepts include:
    • Lexical-Analyzer Generator (Lex): A tool that generates the lexical analyzer from regular expressions.
    • Regular Expressions: Used to specify the patterns to be recognized.
    • Finite Automata (FA): A mathematical model used for recognizing patterns. This includes Deterministic Finite Automata (DFA), which has one next state for one input, and Non-deterministic Finite Automata (NFA), which may have multiple next states for one input.
    • Symbol Table: Used to store recognized identifiers.
    • Optimization: Optimization in DFA-based pattern matchers aims to improve the speed of recognition.
UNIT II: Syntax Analysis

This unit delves into grammar and parsing techniques, which are crucial for analyzing the structural correctness of the program.
  • Primary Goal: To analyze the syntax of the program.
  • Grammar: Context-free grammar is a common type used to specify the syntax of a programming language. An ambiguous grammar is one that can have multiple possible parses for a single sentence.
  • Parsing Techniques:
    • Top-down Parsing: Starts with the overall structure of the program. Examples include Recursive descent parsing and LL(1) parsing.
    • Bottom-up Parsing: Starts with the individual tokens of the program. Examples include Shift-reduce parsing, LR(1) parsing, and its variants SLR(1) parsing (simplified parsing table) and LALR parsing (more powerful parsing table).
  • Tools: Parser generator tools like Yacc, ANTLR, and Bison are used to generate parsers from a grammar specification. LR parsing uses a parsing table to specify the parsing actions for each state.
UNIT III: Syntax Directed Translation

This unit focuses on defining the meaning (semantics) of a program and generating intermediate code.
  • Syntax-Directed Definitions (SDD): Their primary purpose is to define the semantics of a programming language.
    • L-attributed vs. S-attributed: L-attributed definitions use inherited attributes and are often implemented with a top-down approach, while S-attributed definitions primarily use synthesized attributes. The evaluation order is determined by the dependency graph of the attributes.
  • Intermediate Code Generation: This process generates a platform-independent representation of the program from the source code.
    • Variants: Techniques include Syntax-tree generation (such as Abstract Syntax Tree) and Three-address code generation, which is a compact representation using a maximum of three addresses per instruction.
  • Language Features: The unit covers intermediate code generation for various language constructs, including types and declarations, control flow statements (if-then, while, for loops, switch statements), and procedure calls. It also includes Type checking to ensure the correctness of a programming language.
UNIT IV: Run-Time Environments

This unit covers how a program executes, focusing on memory management and the final phase of code generation.
  • Run-time Environment: The primary function is to manage memory allocation and deallocation and provide a platform for executing machine code.
  • Memory Allocation:
    • Stack Allocation: Provides fast and efficient memory allocation for local variables and function calls, accessed using a stack frame.
    • Heap Management: Manages memory allocation/deallocation for dynamic data.
  • Garbage Collection: A technique for automatically deallocating memory. Trace-based collection is a type of garbage collection used to identify reachable objects.
  • Code Generation: The process of generating machine code from intermediate code, aiming for efficient and correct machine code.
    • Basic Blocks: Sequences of instructions with a single entry point.
    • Flow Graphs: Used to represent the control flow of a program.
    • Optimization: Involves improving the performance of basic blocks.
UNIT V: Machine Independent Optimization

This unit covers techniques used to improve program performance universally, independent of the specific target machine.
  • Primary Goal: To improve the performance of a program across different machines.
  • Sources of Optimization: Include eliminating unnecessary computations, reducing the number of memory accesses, and improving cache locality.
  • Data-Flow Analysis (DFA): A key technique used to analyze the flow of data through a program and identify opportunities for optimization. It relies on concepts like the control-flow graph and data-flow equations.
  • Optimization Techniques:
    • Constant Propagation: Propagating constant values through a program, including Constant folding (evaluating constant expressions).
    • Partial-Redundancy Elimination: Eliminating redundant computations.
    • Dead-Code Elimination: Eliminating unreachable code.
    • Other techniques include Peephole optimization and Global optimization.

Comments

Post a Comment