{"pinia":{"ui":{"prefs":{"theme":"system","textScale":"md","fontFamily":"sans","reducedMotion":false,"highContrast":false}},"academy":{"universities":[],"universitySummaries":[{"slug":"rtu","name":"RTU","fullName":"Rajasthan Technical University","branches":[{"slug":"first-year-common","name":"First Year (Common)"},{"slug":"computer-science","name":"Computer Science"},{"slug":"mechanical","name":"Mechanical"},{"slug":"civil","name":"Civil"},{"slug":"ai-data-science","name":"AI & Data Science"},{"slug":"ee-ec-eee","name":"EE / EC / EEE"}]},{"slug":"aktu","name":"AKTU","fullName":"Dr. A. P. J. Abdul Kalam Technical University","branches":[{"slug":"first-year-common","name":"First Year (Common)"},{"slug":"computer-science","name":"Computer Science"}]}],"activePapers":[{"id":"compiler-design-2023","title":"Compiler Design (2023)","subjectSlug":"compiler-design","subjectName":"Compiler Design","universitySlug":"rtu","branchSlug":"computer-science","year":3,"semester":5,"examYear":2023,"paperCode":"5E1752","questions":[{"id":"v2-compiler-design-2023-pA-q1","number":1,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Compiler."}],"answer":{"summary":"A compiler translates high-level source code into low-level machine code.","explanation":[{"type":"paragraph","content":"A compiler is a highly complex system software program that acts as a translator. It aggressively reads an entire program written in a high-level programming language (like C, C++, or Java) and mathematically translates it entirely into low-level machine code or assembly language before executing it, ensuring the target processor can physically understand the instructions."}]}},{"id":"v2-compiler-design-2023-pA-q2","number":2,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is a Token?"}],"answer":{"summary":"A token is the smallest logical sequence of characters meaningful to a compiler.","explanation":[{"type":"paragraph","content":"In compiler design, a token represents the absolute smallest atomic unit of source code that possesses a distinct logical meaning. Tokens are generated during the lexical analysis phase. Common examples of tokens include language keywords (`if`, `while`), mathematical identifiers (variable names), logical operators (`+`, `=`), and punctuation symbols like semicolons."}]}},{"id":"v2-compiler-design-2023-pA-q3","number":3,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Lexical Analysis."}],"answer":{"summary":"Lexical analysis is the very first phase of a compiler that converts characters into tokens.","explanation":[{"type":"paragraph","content":"Lexical Analysis, mathematically known as scanning, is the first and most fundamental phase of compiler architecture. It aggressively reads the raw source code character by character from left to right, stripping out all whitespace and comments, and logically groups the remaining characters into a rigid sequence of meaningful units called tokens."}]}},{"id":"v2-compiler-design-2023-pA-q4","number":4,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Context-Free Grammar?"}],"answer":{"summary":"A Context-Free Grammar (CFG) mathematically defines the rigid syntax of a programming language.","explanation":[{"type":"paragraph","content":"A Context-Free Grammar (CFG) is a strict formal mathematical system utilized by compiler engineers to precisely define the syntax of a programming language. It is defined by a 4-tuple $G = (V, \\Sigma, R, S)$, where $V$ are non-terminals, $\\Sigma$ are terminal symbols, $R$ are production rules (always in the form $A \\rightarrow \\alpha$), and $S$ is the start symbol."}]}},{"id":"v2-compiler-design-2023-pA-q5","number":5,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Parse Tree."}],"answer":{"summary":"A parse tree visually graphs the syntactic derivation of a string using CFG rules.","explanation":[{"type":"paragraph","content":"A Parse Tree, or derivation tree, is a rigorous hierarchical graphical data structure. It mathematically represents the exact syntactic structure of a string according to a specific Context-Free Grammar. The interior nodes violently represent the grammar's non-terminals, while the absolute leaf nodes represent the terminal symbols (the actual tokens) of the language."}]}},{"id":"v2-compiler-design-2023-pA-q6","number":6,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Left Recursion?"}],"answer":{"summary":"Left recursion occurs when a grammar rule allows a non-terminal to derive itself as its leftmost symbol.","explanation":[{"type":"paragraph","content":"Left Recursion is a highly dangerous grammatical phenomenon where a non-terminal mathematically derives a sequence of symbols that strictly begins with itself, usually expressed as the production rule $A \\rightarrow A\\alpha$. This creates a catastrophic infinite loop in Top-Down parsers, completely crashing the compiler because the parser will endlessly call itself without consuming any input."}]}},{"id":"v2-compiler-design-2023-pA-q7","number":7,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Syntax-Directed Translation."}],"answer":{"summary":"SDT attaches semantic rules to grammar productions to evaluate and translate syntax.","explanation":[{"type":"paragraph","content":"Syntax-Directed Translation (SDT) is an advanced compiler mechanism that physically attaches operational semantic rules directly to the abstract productions of a Context-Free Grammar. As the parser constructs the parse tree, these embedded rules are aggressively evaluated simultaneously, allowing the compiler to perform type checking or immediately generate intermediate code during the parsing phase."}]}},{"id":"v2-compiler-design-2023-pA-q8","number":8,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Three-Address Code?"}],"answer":{"summary":"TAC is an intermediate code format where each instruction has at most three operands.","explanation":[{"type":"paragraph","content":"Three-Address Code (TAC) is a highly optimized, linear intermediate representation utilized internally by compilers. It strictly mandates that every single mathematical or logical instruction contains a maximum of exactly three operands (e.g., two sources and one destination, like `x = y + z`). This structure flawlessly mimics the actual hardware registers of the target CPU."}]}},{"id":"v2-compiler-design-2023-pA-q9","number":9,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Symbol Table."}],"answer":{"summary":"A Symbol Table is a highly optimized data structure tracking all source code identifiers.","explanation":[{"type":"paragraph","content":"The Symbol Table is an absolutely critical, centralized database data structure constructed and relentlessly maintained by the compiler. It aggressively stores every single identifier (variables, function names, classes) found in the source code alongside its strict attributes, including its data type, memory scope, parameter list, and actual physical memory allocation address."}]}},{"id":"v2-compiler-design-2023-pA-q10","number":10,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Code Optimization?"}],"answer":{"summary":"Code optimization mathematically transforms intermediate code to consume less memory and execute faster.","explanation":[{"type":"paragraph","content":"Code Optimization is a highly aggressive, optional compiler phase that mathematically analyzes and transforms the generated intermediate code. The ultimate objective is to physically reduce the execution time and minimize the RAM consumption of the final machine code, achieved through complex algorithms like dead-code elimination, loop unrolling, and constant folding."}]}},{"id":"v2-compiler-design-2023-pB-q1","number":1,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the phases of a compiler."}],"answer":{"summary":"A comprehensive architectural breakdown of the six sequential phases of a compiler: Lexical, Syntax, Semantic, Intermediate Code, Optimization, and Target Code generation.","explanation":[{"type":"heading","content":"The Six Phases of Compiler Architecture"},{"type":"paragraph","content":"The compilation of high-level source code into low-level machine code is not a singular event, but rather an incredibly complex, multi-stage engineering pipeline. A modern compiler mathematically decomposes the translation process into exactly six strict, sequential phases. These phases are structurally grouped into the \"Front-End\" (analysis) and the \"Back-End\" (synthesis), both of which communicate aggressively with the centralized Symbol Table and the Error Handler."},{"type":"subheading","content":"1. Lexical Analysis (Scanner)"},{"type":"paragraph","content":"This is the absolute first phase. The scanner violently rips through the raw source code text, stripping away all developer comments and whitespace. It mathematically groups the remaining characters into logical atomic units called \"Tokens\" (e.g., keywords, identifiers, operators). If it encounters illegal characters, it throws a lexical error."},{"type":"subheading","content":"2. Syntax Analysis (Parser)"},{"type":"paragraph","content":"The parser receives the continuous stream of tokens and aggressively verifies them against the Context-Free Grammar (CFG) of the programming language. It attempts to mathematically build a massive hierarchical structure known as a Parse Tree or Syntax Tree. If the tokens violate the grammatical rules (e.g., missing semicolons), a syntax error is violently triggered."},{"type":"subheading","content":"3. Semantic Analysis"},{"type":"paragraph","content":"Even if the code is grammatically perfect, it must make logical sense. This phase rigorously checks for semantic consistency. It performs absolute type checking (e.g., ensuring a string is not multiplied by an integer) and validates that variables are declared before they are used, annotating the syntax tree with data types."},{"type":"subheading","content":"4. Intermediate Code Generation"},{"type":"paragraph","content":"Once the syntax and semantics are proven flawless, the compiler generates an abstract, machine-independent representation of the code. This is usually rendered as Three-Address Code (TAC), which breaks complex mathematical expressions into simple, register-like instructions."},{"type":"subheading","content":"5. Code Optimization"},{"type":"paragraph","content":"This phase aggressively attacks the intermediate code, mathematically transforming it to consume less RAM and execute faster on the CPU. It violently eliminates \"dead code\" (code that is never executed) and pre-calculates constant math expressions (Constant Folding)."},{"type":"subheading","content":"6. Target Code Generation"},{"type":"paragraph","content":"The final phase translates the highly optimized intermediate code directly into the absolute physical machine code or assembly instructions required by the specific target CPU architecture (e.g., x86, ARM), mapping virtual variables to physical silicon registers."},{"type":"svg","content":""}]}},{"id":"v2-compiler-design-2023-pB-q2","number":2,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Describe the role of Lexical Analyzer in a compiler."}],"answer":{"summary":"The Lexical Analyzer mathematically scans source code to generate tokens, eliminate whitespace, track lines, and interact directly with the Symbol Table.","explanation":[{"type":"heading","content":"The Critical Role of the Lexical Analyzer (Scanner)"},{"type":"paragraph","content":"The Lexical Analyzer is the vanguard phase of the compiler architecture. It acts as the absolute primary interface between the physical source code file written by the programmer and the highly abstract mathematical phases of the compiler. Its primary directive is to forcefully scan the source code, character by character, utilizing complex Finite Automata (specifically Deterministic Finite Automata - DFA) to mathematically recognize structural patterns defined by Regular Expressions."},{"type":"subheading","content":"Core Responsibilities and Functions"},{"type":"list","items":["**1. Token Generation:** The scanner groups raw characters (lexemes) into logical tokens. For example, if it reads `i`, `n`, `t`, ` `, `x`, `=`, `5`, `;`, it mathematically categorizes them into ``, ``, ``, ``, and ``. It then continuously feeds these token streams directly to the Syntax Analyzer (Parser) upon request.","**2. Whitespace and Comment Elimination:** Source code contains massive amounts of non-executable data designed strictly for human readability (spaces, tabs, newlines, and comments `/* ... */`). The Lexical Analyzer ruthlessly strips all of this data out of the pipeline, ensuring the parser only receives mathematically relevant executable symbols, drastically speeding up compilation.","**3. Symbol Table Interaction:** The moment the scanner identifies a completely new user-defined identifier (like a new variable name or function name), it immediately interfaces with the Symbol Table data structure. It violently inserts the new lexeme into the table, reserving a memory slot for the Semantic Analyzer to populate later with data types and scope.","**4. Error Tracking and Line Number Correlation:** When the compiler inevitably encounters a syntax error later in the pipeline, the programmer must be notified of the exact location. The Lexical Analyzer rigorously tracks the current line number and column number of the source file, attaching this spatial data to every single token it generates."]},{"type":"paragraph","content":"In summary, the Lexical Analyzer isolates the extreme complexity of character I/O from the parser, operating as an ultra-fast, pattern-matching machine that filters chaos into a perfectly structured token array."}]}},{"id":"v2-compiler-design-2023-pB-q3","number":3,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of FIRST and FOLLOW sets with an example."}],"answer":{"summary":"FIRST and FOLLOW sets are mathematically calculated terminal collections that dictate exactly how predictive Top-Down Parsers (like LL(1)) choose production rules without backtracking.","explanation":[{"type":"heading","content":"Mathematical Construction of FIRST and FOLLOW Sets"},{"type":"paragraph","content":"In the realm of compiler design, specifically for Top-Down Predictive Parsers (like the LL(1) parser), the parser must decide exactly which grammatical production rule to execute just by looking at the current input token. To achieve this deterministic, non-backtracking behavior, the compiler engineers mathematically compute two critical sets for the Context-Free Grammar: the `FIRST` set and the `FOLLOW` set."},{"type":"subheading","content":"Defining the FIRST Set"},{"type":"paragraph","content":"The `FIRST(X)` set is mathematically defined as the absolute collection of all terminal symbols that can begin any string derived from the symbol `X`. If `X` can derive the empty string $\\epsilon$, then $\\epsilon$ is violently injected into `FIRST(X)`. It tells the parser: \"If I am trying to build X, what are the possible first tokens I should expect to see?\""},{"type":"subheading","content":"Defining the FOLLOW Set"},{"type":"paragraph","content":"The `FOLLOW(A)` set is strictly defined for non-terminals. It is the collection of all terminal symbols that can physically appear immediately to the right of `A` in any valid derivation. Crucially, the $\\epsilon$ symbol is absolutely never allowed in a FOLLOW set. If `A` is the rightmost symbol in a derivation, the end-of-input marker `$` is injected."},{"type":"subheading","content":"A Rigorous Example"},{"type":"paragraph","content":"Consider the following Context-Free Grammar:\n1. $S \rightarrow AB$\n2. $A \rightarrow a | \\epsilon$\n3. $B \rightarrow b | c$"},{"type":"list","items":["**Calculating FIRST sets:**\n- `FIRST(A)`: The rules are $A \rightarrow a$ and $A \\rightarrow \\epsilon$. Therefore, `FIRST(A) = {a, epsilon}`.\n- `FIRST(B)`: The rules are $B \rightarrow b$ and $B \rightarrow c$. Therefore, `FIRST(B) = {b, c}`.\n- `FIRST(S)`: $S$ starts with $A$. So we include `FIRST(A)` (which is `a`). But because $A$ can become $\\epsilon$, $S$ can also start with $B$. So we must also include `FIRST(B)`. Therefore, `FIRST(S) = {a, b, c}`.","**Calculating FOLLOW sets:**\n- `FOLLOW(S)`: Because $S$ is the start symbol, we immediately inject the end marker `$`. `FOLLOW(S) = {$}`.\n- `FOLLOW(A)`: Look at $S \rightarrow AB$. What directly follows $A$? It is $B$. Therefore, `FOLLOW(A)` mathematically inherits `FIRST(B)`. `FOLLOW(A) = {b, c}`.\n- `FOLLOW(B)`: Look at $S \rightarrow AB$. $B$ is at the absolute end of the string, meaning whatever follows $S$ must follow $B$. Therefore, `FOLLOW(B) = FOLLOW(S) = {$}`."]},{"type":"paragraph","content":"By computing these sets, the parser can perfectly populate its predictive parsing table, completely eliminating catastrophic trial-and-error backtracking."}]}},{"id":"v2-compiler-design-2023-pB-q4","number":4,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Discuss the LL(1) parsing technique."}],"answer":{"summary":"The LL(1) parsing technique is a deterministic, top-down parser that scans Left-to-right, constructs a Leftmost derivation, and uses 1 token of lookahead.","explanation":[{"type":"heading","content":"The Architecture of LL(1) Parsing"},{"type":"paragraph","content":"LL(1) parsing represents the absolute pinnacle of deterministic Top-Down parsing methodologies. The acronym itself mathematically defines its strict operational parameters: the first \"L\" mandates that the parser scans the input stream strictly from Left-to-right. The second \"L\" mandates that the parser continuously constructs a Leftmost derivation of the syntax tree. The \"(1)\" signifies that the algorithm requires exactly one single token of lookahead to make an absolute, deterministic decision about which grammatical production rule to fire."},{"type":"subheading","content":"Core Components of the LL(1) System"},{"type":"list","items":["**1. The Stack Structure:** The parser utilizes a massive Last-In-First-Out (LIFO) stack to track the current state of the derivation. The stack is aggressively initialized with the end-of-input marker `$` followed by the Start Symbol of the grammar.","**2. The Input Buffer:** A linear buffer holding the incoming stream of tokens, terminated violently by the `$` marker.","**3. The Predictive Parsing Table (M-Table):** This is the brain of the algorithm. It is a strict 2D mathematical matrix where the rows represent Non-Terminals and the columns represent Terminal symbols. The cells contain the exact production rule to fire. This table is populated entirely using the rigorously calculated FIRST and FOLLOW sets of the grammar."]},{"type":"subheading","content":"The LL(1) Execution Algorithm"},{"type":"paragraph","content":"The parser operates in an endless loop, comparing the symbol at the Top of the Stack (let's call it $X$) with the current lookahead token in the buffer (let's call it $a$):"},{"type":"list","items":["If $X$ is a terminal symbol and it perfectly matches $a$, the parser mathematically \"pops\" $X$ off the stack and advances the input pointer. (Match condition).","If $X$ is a terminal but does NOT match $a$, the parser violently throws a fatal Syntax Error.","If $X$ is a Non-Terminal, the parser queries the Parsing Table at $M[X, a]$. If a valid production rule exists (e.g., $X \\rightarrow YZ$), the parser pops $X$ and aggressively pushes $Z$ then $Y$ onto the stack (in reverse order, so $Y$ is now on top).","If $M[X, a]$ is blank, it triggers an immediate Error."]},{"type":"paragraph","content":"For a grammar to be mathematically classified as strictly LL(1), its predictive parsing table must never contain any multiple-defined entries (no cell can have two rules). This completely outlaws grammars with Left Recursion or Left Factoring conflicts."}]}},{"id":"v2-compiler-design-2023-pB-q5","number":5,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of Shift-Reduce parsing."}],"answer":{"summary":"Shift-Reduce parsing is a bottom-up methodology that aggressively shifts tokens onto a stack and reduces them into non-terminals until the start symbol is formed.","explanation":[{"type":"heading","content":"Shift-Reduce Parsing Architecture"},{"type":"paragraph","content":"Shift-Reduce Parsing is the foundational algorithm for almost all modern Bottom-Up compiler architectures (including powerful LR parsers). Unlike top-down methods that attempt to build the parse tree from the root, Shift-Reduce Parsing aggressively begins at the absolute bottom (the leaf nodes/tokens) and mathematically works its way backward, attempting to collapse (reduce) the string into the original Start Symbol of the Context-Free Grammar."},{"type":"subheading","content":"The Core Data Structures"},{"type":"paragraph","content":"The architecture relies heavily on two primary components: a physical Input Buffer containing the raw string of tokens (terminated by `$`), and a LIFO Stack (initialized with `$`) which temporarily holds grammar symbols as they are processed."},{"type":"subheading","content":"The Four Primary Operations"},{"type":"paragraph","content":"The parser continuously executes one of four strict, mathematical operations during every cycle:"},{"type":"list","items":["**1. Shift:** The parser aggressively plucks the next terminal token from the Input Buffer and physically pushes it onto the Top of the Stack. This occurs when the parser determines it does not yet have enough information on the stack to form a valid grammatical rule.","**2. Reduce:** When the parser mathematically detects that a sequence of symbols at the Top of the Stack perfectly matches the Right-Hand Side (RHS) of a known production rule (e.g., detecting the string `A B` matching rule `X -> A B`), it violently executes a reduction. It pops `A` and `B` off the stack and replaces them with the Non-Terminal `X` (the Left-Hand Side of the rule). This physical matching sequence is technically known as isolating a \"Handle.\"","**3. Accept:** If the Input Buffer is completely empty (showing only `$`) and the Stack contains absolutely nothing but the Start Symbol (and `$`), the parser has successfully built the tree and halts, accepting the string as mathematically valid.","**4. Error:** If the parser cannot execute a Shift or a Reduce, and has not reached the Accept state, a fatal syntax error is triggered, indicating the code is grammatically malformed."]},{"type":"subheading","content":"The Conflict Dilemmas"},{"type":"paragraph","content":"Naive shift-reduce parsers frequently suffer from catastrophic mathematical conflicts. A \"Shift/Reduce Conflict\" occurs when the algorithm cannot decide whether to shift the next token or reduce the current stack. A \"Reduce/Reduce Conflict\" occurs when the stack matches two entirely different grammatical rules simultaneously. Advanced LR(1) parsers utilize complex lookahead matrices to systematically eliminate these conflicts."}]}},{"id":"v2-compiler-design-2023-pB-q6","number":6,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Describe the various storage allocation strategies."}],"answer":{"summary":"Compilers deploy three rigid storage allocation strategies: Static Allocation (compile-time memory), Stack Allocation (dynamic runtime memory for functions), and Heap Allocation (unstructured dynamic memory).","explanation":[{"type":"heading","content":"Storage Allocation Strategies in Compilers"},{"type":"paragraph","content":"When a compiler transforms abstract source code into a physical executable binary, it must mathematically dictate exactly how the operating system will allocate silicon RAM to the program's variables, objects, and function calls during execution. Compiler engineers classify memory allocation into three rigid, highly optimized architectural strategies: Static Allocation, Stack Allocation, and Heap Allocation."},{"type":"subheading","content":"1. Static Storage Allocation"},{"type":"paragraph","content":"In this primitive but ultra-fast strategy, memory is violently and permanently locked in during the actual compilation phase (Compile-Time), long before the program ever runs. The exact memory addresses for variables are hard-coded into the binary executable. \n- **Application:** Used for global variables, static variables, and constants.\n- **Merits:** Zero runtime overhead; execution is blindingly fast because there is no dynamic memory calculation.\n- **Demerits:** It catastrophically fails to support recursion, because a recursive function requires multiple separate memory blocks for each instance, which static allocation physically cannot provide. The memory size must be mathematically known in advance."},{"type":"subheading","content":"2. Stack Storage Allocation (Dynamic)"},{"type":"paragraph","content":"This is a dynamic, runtime strategy that organizes memory into a strict Last-In-First-Out (LIFO) architecture. Whenever a function is called, the CPU aggressively pushes a new \"Activation Record\" (or Stack Frame) onto the stack. This frame contains the function's local variables, return address, and parameters.\n- **Application:** Used exclusively for local variables inside functions and methods.\n- **Merits:** It flawlessly supports infinite recursion, as every recursive call simply pushes a new frame onto the stack. Memory is automatically and violently freed (popped) the exact millisecond the function returns, completely preventing memory leaks.\n- **Demerits:** Variables are destroyed upon function exit; they cannot persist."},{"type":"subheading","content":"3. Heap Storage Allocation (Dynamic)"},{"type":"paragraph","content":"The Heap is an unstructured, massive pool of available RAM. Allocation and deallocation can occur randomly at any point during runtime, completely ignoring the strict LIFO rules of the stack.\n- **Application:** Used for dynamic memory requested manually by the programmer (e.g., using `malloc()` in C or `new` in C++/Java) for data structures like Linked Lists or Trees where the size is utterly unknown at compile-time.\n- **Merits:** Massive flexibility; data violently persists until explicitly deleted.\n- **Demerits:** Extremely slow overhead to track fragmented memory. If the programmer forgets to free the memory, it causes a catastrophic Memory Leak."}]}},{"id":"v2-compiler-design-2023-pB-q7","number":7,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the basic blocks and flow graphs in code optimization."}],"answer":{"summary":"In code optimization, a Basic Block is a strictly linear sequence of code with no branches, while a Flow Graph mathematically links these blocks to map execution paths.","explanation":[{"type":"heading","content":"Basic Blocks and Control Flow Graphs"},{"type":"paragraph","content":"During the Code Optimization phase, the compiler refuses to analyze the raw, massive list of intermediate Three-Address Code (TAC) linearly. Instead, to apply advanced mathematical optimization algorithms (like loop invariant removal or data-flow analysis), the compiler must architecturally slice the code into strict, indivisible atomic units known as \"Basic Blocks,\" and then map their relationships using a \"Control Flow Graph\" (CFG)."},{"type":"subheading","content":"The Architecture of a Basic Block"},{"type":"paragraph","content":"A Basic Block is mathematically defined as a strictly linear, continuous sequence of executable instructions that guarantees absolutely no branching. It operates under two unbreakable physical laws:\n1. Execution MUST enter exactly at the first instruction of the block.\n2. Execution MUST exit exactly at the last instruction of the block, without halting or branching out in the middle."},{"type":"paragraph","content":"To aggressively isolate Basic Blocks from a massive file of code, the compiler utilizes the \"Leader Algorithm\":\n- The absolute first instruction of the code is a Leader.\n- Any instruction that is the specific target of a conditional or unconditional jump (e.g., a `GOTO` label) is instantly marked as a Leader.\n- Any instruction that immediately physically follows a jump or `GOTO` is marked as a Leader.\nA Basic Block mathematically consists of a Leader and all subsequent instructions right up to, but strictly excluding, the next Leader."},{"type":"subheading","content":"The Control Flow Graph (CFG)"},{"type":"paragraph","content":"Once the compiler has violently shattered the code into isolated Basic Blocks, it must understand how the program actually executes. It constructs a Control Flow Graph (CFG)."},{"type":"list","items":["The CFG is a highly rigorous, directed mathematical graph.","**Nodes:** Every single Basic Block becomes a solid Node in the graph.","**Edges:** Directed arrows (Edges) are drawn between nodes to represent the physical jump of execution. If Block B mathematically executes immediately after Block A, an arrow connects A to B.","**Loop Detection:** The CFG allows the compiler to instantly visually detect infinite loops and nested loops (represented by physical back-edges in the graph). By identifying these heavily executed loops, the compiler can violently focus its optimization algorithms on the most critical bottlenecks of the software."]}]}},{"id":"v2-compiler-design-2023-pC-q1","number":1,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the architecture of a compiler in detail. (b) Differentiate between Compiler, Interpreter, and Assembler."}],"answer":{"summary":"An exhaustive architectural analysis detailing the six specific internal phases of a compiler, followed by a rigorous technical differentiation between Compilers, Interpreters, and Assemblers based on execution speed, memory footprint, and translation methodology.","explanation":[{"type":"heading","content":"(a) The Architecture of a Compiler"},{"type":"paragraph","content":"A modern compiler is not a monolithic script; it is a highly advanced, multi-stage software engineering architecture designed to mathematically translate human-readable source code into bare-metal machine code. The architecture is strictly divided into the \"Front-End\" (which heavily depends on the source language) and the \"Back-End\" (which is specifically engineered for the target hardware architecture). These phases operate sequentially while constantly communicating with two centralized modules: the **Symbol Table Manager** and the **Error Handler**."},{"type":"subheading","content":"Phase 1: Lexical Analysis (Scanner)"},{"type":"paragraph","content":"The absolute first phase. The source code is read as a raw stream of ASCII characters. The Lexical Analyzer utilizes strict Deterministic Finite Automata (DFA) to eliminate whitespace and comments, violently grouping the remaining characters into meaningful atomic units called \"Tokens\" (Keywords, Identifiers, Operators). It simultaneously populates the Symbol Table with newly discovered variables."},{"type":"subheading","content":"Phase 2: Syntax Analysis (Parser)"},{"type":"paragraph","content":"The stream of tokens is fed into the Parser. Utilizing advanced mathematical Context-Free Grammars (CFG) and push-down automata, the parser aggressively verifies that the sequence of tokens forms grammatically correct statements. It constructs a massive hierarchical \"Parse Tree.\" If a programmer forgets a semicolon, this phase violently throws a syntax error and halts."},{"type":"subheading","content":"Phase 3: Semantic Analysis"},{"type":"paragraph","content":"Grammar alone does not guarantee logic. The Semantic Analyzer aggressively traverses the parse tree to ensure the code makes mathematical sense. It strictly enforces Type Checking (e.g., ensuring a string is not divided by a float) and validates that variables are mathematically declared before they are invoked."},{"type":"subheading","content":"Phase 4: Intermediate Code Generation"},{"type":"paragraph","content":"The compiler translates the validated parse tree into a highly optimized, machine-independent format, most commonly Three-Address Code (TAC). TAC forces every mathematical expression into a strict format utilizing a maximum of three operands per instruction, perfectly mimicking CPU hardware registers without committing to a specific processor architecture."},{"type":"subheading","content":"Phase 5: Code Optimization"},{"type":"paragraph","content":"This optional but highly critical phase aggressively transforms the intermediate code. It utilizes data-flow analysis to execute Dead Code Elimination, Constant Folding, and Loop Unrolling. The singular, ruthless objective is to mathematically reduce execution time and memory consumption to the absolute physical minimum."},{"type":"subheading","content":"Phase 6: Target Code Generation"},{"type":"paragraph","content":"The final phase. The optimized intermediate code is translated directly into the native Assembly language or Binary Machine Code of the specific target processor (e.g., ARM, x86-64). Variables are mapped directly to physical silicon registers and RAM memory addresses."},{"type":"heading","content":"(b) Compiler vs. Interpreter vs. Assembler"},{"type":"paragraph","content":"While all three are translator programs, their architectural methodologies and execution paradigms differ catastrophically."},{"type":"subheading","content":"The Compiler"},{"type":"paragraph","content":"A Compiler translates the *entire* high-level source code file into a standalone, executable machine-code file (like an `.exe`) *before* any execution begins. \n- **Speed:** Compilation is slow, but the resulting binary execution is blindingly fast because it directly interfaces with the CPU.\n- **Error Detection:** It aggressively scans the entire file and reports all syntax errors at once.\n- **Memory:** Requires significantly more memory during compilation to build massive abstract syntax trees, but the final product runs independently. Examples: C, C++, Rust."},{"type":"subheading","content":"The Interpreter"},{"type":"paragraph","content":"An Interpreter mathematically translates and executes the source code line-by-line, statement-by-statement, in real-time during execution. It never creates a standalone binary file.\n- **Speed:** Execution is significantly slower because the code is being translated on-the-fly while running.\n- **Error Detection:** It halts violently at the exact millisecond it hits the first error, making debugging extremely rapid.\n- **Memory:** Highly memory efficient as it only processes one line at a time. Examples: Python, JavaScript, Ruby."},{"type":"subheading","content":"The Assembler"},{"type":"paragraph","content":"An Assembler is a highly specific, primitive translator. It exclusively translates low-level Assembly Language (mnemonics like `MOV`, `ADD`, `JMP`) directly into raw binary machine code (0s and 1s).\n- **Abstraction Level:** It does not understand loops, variables, or functions. It operates strictly on a 1-to-1 instruction mapping.\n- **Speed:** It is incredibly fast and operates at the bare-metal hardware level. It is typically the final stage of a C++ compiler pipeline."}]}},{"id":"v2-compiler-design-2023-pC-q2","number":2,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"Explain the concept of Top-Down Parsing in detail. Discuss Recursive Descent Parsing and LL(1) parsing with suitable examples."}],"answer":{"summary":"A deep mathematical breakdown of Top-Down Parsing architectures, explicitly differentiating the backtracking inefficiency of Recursive Descent Parsing from the highly deterministic, table-driven execution of LL(1) Predictive Parsing.","explanation":[{"type":"heading","content":"The Architecture of Top-Down Parsing"},{"type":"paragraph","content":"Top-Down Parsing is a fundamental grammatical strategy utilized during the Syntax Analysis phase of compilation. Architecturally, it attempts to mathematically construct a Parse Tree starting from the absolute Root (the Start Symbol of the Context-Free Grammar) and continuously expanding downwards toward the Leaf nodes (the terminal tokens generated by the scanner). To successfully parse a string, the parser must rigorously search for a sequence of production rules that derive the exact input string, reading the input strictly from left to right. Top-Down parsers violently reject grammars containing \"Left Recursion\" (which triggers catastrophic infinite loops) and \"Left Factoring\" (which causes deterministic confusion)."},{"type":"subheading","content":"Recursive Descent Parsing (The Brute Force Approach)"},{"type":"paragraph","content":"Recursive Descent Parsing is the most primitive form of Top-Down parsing. It is implemented as a set of highly intertwined, recursive functions, where exactly one function is mathematically constructed for every single Non-Terminal in the grammar."},{"type":"list","items":["**Execution Mechanism:** When a function representing Non-Terminal $A$ is executed, it attempts to match the current input token against the Right-Hand Side (RHS) of $A$'s production rules.","**The Backtracking Nightmare:** If $A$ has multiple production rules (e.g., $A \\rightarrow aB | aC$), a naive Recursive Descent parser will blindly pick the first rule. It will aggressively consume the input token `a` and call function `B`. If function `B` suddenly mathematically fails to match the subsequent tokens, the parser realizes it made a catastrophic error. It must violently \"Backtrack\": un-consume the token, destroy the partially built tree, and attempt the second rule $A \\rightarrow aC$.","**Architectural Demerit:** This relentless backtracking causes massive exponential time complexity, making standard Recursive Descent completely unviable for commercial compilers."]},{"type":"subheading","content":"LL(1) Predictive Parsing (The Deterministic Solution)"},{"type":"paragraph","content":"To eradicate the catastrophic inefficiency of backtracking, compiler engineers developed LL(1) Predictive Parsing. It is a highly advanced, table-driven Top-Down architecture. \n- **The First L:** Scans input Left-to-right.\n- **The Second L:** Produces a Leftmost derivation.\n- **The (1):** Utilizes exactly 1 token of mathematical lookahead."},{"type":"paragraph","content":"Instead of blindly guessing which production rule to use, an LL(1) parser looks exactly one token ahead in the input stream and consults a mathematically rigid 2D Parsing Table (the M-Table). Because the M-Table is constructed using heavily calculated FIRST and FOLLOW sets, the parser knows with absolute, deterministic mathematical certainty exactly which rule to fire."},{"type":"subheading","content":"LL(1) Execution Example"},{"type":"paragraph","content":"Consider the grammar:\n1. $S \\rightarrow a A b$\n2. $A \\rightarrow c | d$"},{"type":"paragraph","content":"We want to parse the string: `a c b`."},{"type":"list","items":["**Initialization:** The parser utilizes a Stack, initially containing the start symbol `$` and `S`. The input buffer contains `a c b $`.","**Step 1:** The stack top is `S`. The lookahead token is `a`. The parser queries the M-Table at $M[S, a]$. The table rigorously dictates the rule $S \\rightarrow a A b$. The parser pops `S` and pushes `b`, `A`, `a` onto the stack (in reverse).","**Step 2:** The stack top is now `a`. The lookahead is `a`. This is a perfect physical terminal match. The parser pops `a` from the stack and advances the input pointer to `c`.","**Step 3:** The stack top is now `A`. The lookahead is `c`. The parser queries $M[A, c]$. Because `FIRST(A)` includes `c` derived from the rule $A \\rightarrow c$, the table commands the rule $A \\rightarrow c$. The parser pops `A` and pushes `c`.","**Step 4:** The stack top is `c`, lookahead is `c`. Match. Pop and advance input to `b`.","**Step 5:** The stack top is `b`, lookahead is `b`. Match. Pop and advance input to `$`.","**Step 6:** The stack is empty (only `$`), and the input is empty (only `$`). The parser halts and violently accepts the string as grammatically perfect."]},{"type":"paragraph","content":"Notice that at no point did the LL(1) parser ever have to guess or backtrack. Its execution is a flawless, linear mathematical progression."}]}},{"id":"v2-compiler-design-2023-pC-q3","number":3,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the concept of Bottom-Up Parsing. (b) Discuss LR parsing techniques (SLR, CLR, LALR) with examples."}],"answer":{"summary":"A definitive engineering analysis of Bottom-Up (Shift-Reduce) Parsing, thoroughly exploring the mathematical hierarchies and state machine complexities of SLR, CLR(1), and LALR parsing algorithms.","explanation":[{"type":"heading","content":"(a) The Architecture of Bottom-Up Parsing"},{"type":"paragraph","content":"Bottom-Up Parsing, mathematically known as Shift-Reduce Parsing, is the most powerful and universally deployed syntax analysis architecture in modern compilers (forming the foundation of tools like YACC and Bison). Unlike Top-Down parsers that start at the root symbol, a Bottom-Up parser aggressively begins at the extreme leaf nodes—the physical sequence of tokens generated by the scanner. Its singular mathematical objective is to continuously compress and reduce this raw string of tokens upward, aggressively collapsing matched patterns into non-terminals until the entire sequence violently collapses into the single Start Symbol of the grammar."},{"type":"paragraph","content":"It operates using a massive LIFO Stack and an Input Buffer. It executes two primary physical actions: **Shift** (pushing the next terminal token onto the stack) and **Reduce** (recognizing that the top elements of the stack perfectly match the right side of a production rule, popping them, and replacing them with the left-side Non-Terminal—a process formally known as \"Handle Pruning\"). The architecture continuously builds a Rightmost derivation in reverse."},{"type":"heading","content":"(b) The LR Parsing Family (SLR, CLR, LALR)"},{"type":"paragraph","content":"The most advanced subset of Bottom-Up parsers are the LR parsers (Left-to-right scan, Rightmost derivation in reverse). They completely eliminate the guesswork of basic shift-reduce parsers by utilizing heavily complex Deterministic Finite Automata (DFA) state machines and rigid parsing tables. However, they differ massively in their mathematical complexity and power."},{"type":"subheading","content":"1. SLR (Simple LR) Parsing"},{"type":"paragraph","content":"SLR is the weakest and most primitive of the LR family. It constructs its DFA state machine using strictly LR(0) items (production rules with a mathematical dot indicating the current parsing position, e.g., $A \\rightarrow \\alpha . \\beta$)."},{"type":"list","items":["**Reduction Logic:** When an SLR parser reaches a state containing a completed item ($A \\rightarrow \\alpha .$), it must decide whether to execute a Reduce action. To prevent catastrophic Reduce/Reduce conflicts, the SLR parser looks at the current input token. It mathematically allows the reduction ONLY if the input token explicitly belongs to the `FOLLOW(A)` set.","**Demerit:** Because the `FOLLOW` set is calculated globally for the entire grammar, it is highly imprecise. It often allows a reduction in a state where, logically, the token should never appear, leading to fatal Shift/Reduce conflicts in complex grammars."]},{"type":"subheading","content":"2. CLR (Canonical LR) Parsing - The Absolute Powerhouse"},{"type":"paragraph","content":"CLR (or strictly LR(1)) is the most mathematically powerful and flawless parser in existence. It aggressively solves the imprecision of SLR by completely abandoning LR(0) items and global FOLLOW sets. Instead, it utilizes LR(1) items."},{"type":"list","items":["**Lookahead Injection:** An LR(1) item is structurally defined as $[A \\rightarrow \\alpha . \\beta, a]$, where `a` is the strictly calculated terminal lookahead symbol mathematically glued directly to the production rule.","**Reduction Logic:** When a state reaches completion ($[A \\rightarrow \\alpha ., a]$), the CLR parser will execute a Reduce action IF AND ONLY IF the current input token is exactly `a`. It completely ignores the global FOLLOW set.","**Demerit:** The mathematical precision is absolute, but the cost is catastrophic state explosion. A CLR state machine for a standard programming language like C will violently generate tens of thousands of unique states, demanding massive RAM to store the parsing tables."]},{"type":"subheading","content":"3. LALR (Look-Ahead LR) Parsing - The Industry Standard"},{"type":"paragraph","content":"LALR is a highly advanced, mathematically optimized compromise utilized by almost all commercial compilers (like YACC). It attempts to retain the extreme precision of CLR while violently crushing the memory footprint down to the size of SLR."},{"type":"list","items":["**The Merge Algorithm:** LALR begins by calculating the massive CLR(1) state machine. It then aggressively analyzes the states. If it finds two separate states that have the exact same core LR(0) items, but different lookahead symbols, it ruthlessly crushes and mathematically merges them into a single state, combining their lookaheads.","**The Result:** The state count collapses from thousands (CLR) down to hundreds (SLR size). It retains nearly all of CLR's power. However, the violent merging process can occasionally mathematically introduce a rare Reduce/Reduce conflict that did not exist in the CLR grammar, meaning LALR is infinitesimally less powerful than CLR."]},{"type":"svg","content":""}]}},{"id":"v2-compiler-design-2023-pC-q4","number":4,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"Explain Syntax-Directed Definitions (SDD) and Syntax-Directed Translation (SDT). Discuss the translation of arithmetic expressions with examples."}],"answer":{"summary":"A rigorous exposition on Syntax-Directed Definitions (SDD) and Translation (SDT), explaining the critical mathematical difference between Synthesized and Inherited attributes, accompanied by an arithmetic expression translation model.","explanation":[{"type":"heading","content":"Syntax-Directed Definitions (SDD) and Translation Schemes (SDT)"},{"type":"paragraph","content":"In compiler architecture, a Context-Free Grammar (CFG) is mathematically capable of defining the rigid structure of a language, but it is physically incapable of defining the meaning or semantics of that structure. To evaluate mathematical logic (like calculating the result of an addition, or generating target code), compiler engineers utilize Syntax-Directed Definitions (SDD) and Syntax-Directed Translation (SDT). This paradigm aggressively attaches logical, executable semantic rules and data attributes directly to the abstract nodes of the parse tree during the compilation process."},{"type":"subheading","content":"Syntax-Directed Definitions (SDD)"},{"type":"paragraph","content":"An SDD is a high-level, mathematically declarative specification. It strictly defines the grammar rules alongside a set of associated semantic rules, but crucially, it completely ignores the physical order in which these rules must be evaluated by the CPU. In an SDD, every grammar symbol (like an expression `E` or a variable `id`) is assigned mathematical \"Attributes\" (e.g., a data type, a memory location, or an integer value). Attributes are strictly divided into two distinct engineering classes:"},{"type":"list","items":["**1. Synthesized Attributes:** The value of a synthesized attribute at a node is mathematically calculated exclusively by combining the attribute values of its absolute child nodes. Data flows violently from the bottom of the tree (leaves) upwards to the root. This is universally compatible with Bottom-Up (LR) parsing.","**2. Inherited Attributes:** The value of an inherited attribute at a node is mathematically forced upon it from above or the side; it is calculated using the attributes of its parent node or its sibling nodes. Data flows downwards or laterally. This is highly complex to implement in standard Bottom-Up parsers without structural modifications."]},{"type":"subheading","content":"Syntax-Directed Translation (SDT)"},{"type":"paragraph","content":"While an SDD is purely declarative, an SDT is aggressively operational. An SDT explicitly embeds physical semantic action code (usually enclosed in curly braces `{ }`) directly inside the right-hand side of the grammar productions. It violently enforces the exact execution sequence. When the parser mathematically recognizes the surrounding grammatical symbols, it physically executes the embedded code."},{"type":"subheading","content":"Practical Example: Translating Arithmetic Expressions"},{"type":"paragraph","content":"Let us mathematically model a simple SDD designed to evaluate the physical value of standard arithmetic expressions (e.g., calculating `3 * 5 + 4`). We will utilize exclusively Synthesized Attributes (specifically, the `.val` attribute, which stores the integer value). Data will flow from the bottom up."},{"type":"paragraph","content":"Consider the following grammar and attached Semantic Rules:"},{"type":"list","items":["**Production 1:** $L \rightarrow E \\text{ \\textbf{n}}$ \n**Semantic Rule:** `print(E.val)` \n*(Explanation: When the entire expression is reduced, print the final mathematical value).*","**Production 2:** $E \rightarrow E_1 + T$ \n**Semantic Rule:** `E.val = E_1.val + T.val` \n*(Explanation: The value of this addition node is strictly the mathematical sum of its left child and right child).*","**Production 3:** $E \rightarrow T$ \n**Semantic Rule:** `E.val = T.val` \n*(Explanation: Direct mathematical value transfer).*","**Production 4:** $T \rightarrow T_1 * F$ \n**Semantic Rule:** `T.val = T_1.val * F.val` \n*(Explanation: The value of this multiplication node is the mathematical product of its children).*","**Production 5:** $T \rightarrow F$ \n**Semantic Rule:** `T.val = F.val`","**Production 6:** $F \rightarrow ( E )$ \n**Semantic Rule:** `F.val = E.val` \n*(Explanation: Parentheses physically alter precedence but do not alter the inner value).*","**Production 7:** $F \rightarrow \\text{\\textbf{digit}}$ \n**Semantic Rule:** `F.val = digit.lexval` \n*(Explanation: The absolute leaf node. The lexical analyzer physically scanned a digit (like '3'). Its value is passed up the tree).*"]},{"type":"paragraph","content":"As the Bottom-Up parser aggressively builds the tree from the tokens `3`, `*`, `5`, it will eventually reduce them to $T \rightarrow T_1 * F$. At the exact millisecond of reduction, the semantic rule `T.val = 3 * 5` is executed, storing `15` in `T.val`, which is then passed upwards to complete the mathematical translation flawlessly."}]}},{"id":"v2-compiler-design-2023-pC-q5","number":5,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"Explain Code Optimization techniques in detail. Discuss local optimizations and loop optimizations with examples."}],"answer":{"summary":"A highly technical breakdown of Code Optimization algorithms, explicitly analyzing Machine-Independent optimizations like Constant Folding, Dead-Code Elimination, and advanced Loop Optimizations (Code Motion, Induction Variables).","explanation":[{"type":"heading","content":"Advanced Code Optimization Techniques"},{"type":"paragraph","content":"Code Optimization is a highly aggressive, mathematically intensive phase of the compiler. Its absolute singular objective is to ruthlessly transform the Intermediate Representation (IR) of the program to drastically reduce execution time (CPU cycles) and minimize physical memory footprint (RAM), all without altering the mathematical logic or output of the original source code. Optimization algorithms are architecturally split into two massive categories: Machine-Independent Optimization (which operates on the abstract intermediate code) and Machine-Dependent Optimization (which utilizes specific CPU hardware features like registers and cache)."},{"type":"paragraph","content":"To execute Machine-Independent optimizations, the compiler violently shatters the continuous intermediate code into isolated atomic sequences called **Basic Blocks**, and mathematically maps their execution paths using a **Control Flow Graph (CFG)**. Optimizations are then applied either \"Locally\" (inside a single Basic Block) or \"Globally\" (across the entire CFG)."},{"type":"subheading","content":"1. Local Optimization Techniques"},{"type":"paragraph","content":"These algorithms aggressively target the code within the strict confines of a single Basic Block."},{"type":"list","items":["**A. Constant Folding:** The compiler mathematically evaluates constant expressions at compile-time instead of runtime. If the code contains `x = 22 * 7 / 2;`, the compiler calculates this value during compilation and violently replaces the entire expression with the physical result `x = 77;`. This saves the CPU from executing useless math operations during runtime.","**B. Constant Propagation:** If a variable is aggressively assigned a constant value (e.g., `pi = 3.14`), and then used in a subsequent expression (`area = pi * r * r`), the compiler will mathematically substitute the constant directly into the expression (`area = 3.14 * r * r`), freeing up a memory lookup.","**C. Common Subexpression Elimination:** If the compiler detects that the exact same mathematical operation is executed multiple times within a block without the variables changing (e.g., `a = b * c` followed by `d = b * c + 5`), it will calculate `b * c` exactly once, store it in a temporary register, and reuse the result, slashing CPU cycle waste.","**D. Dead-Code Elimination:** The compiler utilizes data-flow analysis to mathematically prove that a specific variable or block of code can absolutely never be reached or used (e.g., code following a `return` statement, or a variable that is assigned but never read). The compiler ruthlessly deletes this code from the binary."]},{"type":"subheading","content":"2. Loop Optimization Techniques (Global)"},{"type":"paragraph","content":"Because loops (like `for` and `while`) are executed continuously, they consume the massive majority of a program's CPU time. Loop optimization yields the highest performance gains in compiler architecture."},{"type":"list","items":["**A. Code Motion (Loop Invariant Computation):** If a mathematical expression inside a loop produces the exact same result during every single iteration (e.g., `while (i < n) { x = y + z; i++; }` where `y` and `z` do not change), the compiler forcefully rips the expression `x = y + z;` out of the loop and places it physically before the loop begins. This prevents the CPU from re-calculating the identical equation thousands of times.","**B. Induction Variable Elimination:** In a `for(i=0; i<10; i++)` loop, the variable `i` is an induction variable. If the loop contains `j = 4 * i`, `j` is a derived induction variable. The compiler can mathematically replace the expensive multiplication operation (`4 * i`) with a highly efficient addition operation (`j = j + 4`), drastically increasing execution speed on primitive CPUs.","**C. Loop Unrolling:** To eliminate the continuous overhead of evaluating the loop condition (e.g., `i < n`) and jumping back to the top of the loop, the compiler will physically duplicate the inner code of the loop multiple times. For a loop running 4 times, it will just write the code out 4 times in a row, completely destroying the loop structure but resulting in blisteringly fast straight-line execution."]}]}}]},{"id":"compiler-design-2024","title":"Compiler Design (2024)","subjectSlug":"compiler-design","subjectName":"Compiler Design","universitySlug":"rtu","branchSlug":"computer-science","year":3,"semester":5,"examYear":2024,"paperCode":"5E1752","questions":[{"id":"v2-compiler-design-2024-pA-q1","number":1,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Preprocessor?"}],"answer":{"summary":"A preprocessor is a program that processes the source code before the compiler proper, handling directives like macro expansion, file inclusion, and conditional compilation.","explanation":[{"type":"paragraph","content":"A preprocessor is a program that processes the source code before it is passed to the compiler. It handles preprocessor directives (commands starting with # in C/C++) and produces a modified source file that the compiler then processes."},{"type":"list","items":["Macro Expansion: Replaces macro names with their defined bodies (e.g., #define MAX 100).","File Inclusion: Inserts the contents of included files (e.g., #include ).","Conditional Compilation: Includes/excludes code sections based on conditions (e.g., #ifdef, #ifndef, #endif).","Line Control: Provides line number information for error messages."]}]}},{"id":"v2-compiler-design-2024-pA-q2","number":2,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Regular Expression."}],"answer":{"summary":"A Regular Expression is a notation for specifying patterns of strings over an alphabet, used in lexical analysis to define the patterns of tokens.","explanation":[{"type":"paragraph","content":"A Regular Expression (RE) is a formula that describes a set of strings (a regular language) over an alphabet Σ. Regular expressions are the standard notation for specifying the patterns of tokens in lexical analysis. They are defined inductively:"},{"type":"list","items":["Basis: ε (empty string), ∅ (empty set), and any symbol a ∈ Σ are regular expressions.","Union (Alternation): If r and s are REs, then r|s is an RE denoting L(r) ∪ L(s).","Concatenation: If r and s are REs, then rs is an RE denoting L(r) · L(s).","Kleene Closure: If r is an RE, then r* is an RE denoting zero or more repetitions of strings in L(r).","Positive Closure: r+ = rr* (one or more repetitions).","Optional: r? = r|ε (zero or one occurrence).","Example: Identifier = letter(letter|digit)* where letter = [a-zA-Z_]."]}]}},{"id":"v2-compiler-design-2024-pA-q3","number":3,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Ambiguous Grammar?"}],"answer":{"summary":"An Ambiguous Grammar is a grammar for which some string in its language has more than one parse tree (or equivalently, more than one leftmost or rightmost derivation).","explanation":[{"type":"paragraph","content":"A Context-Free Grammar G is ambiguous if there exists at least one string w in L(G) that has two or more distinct parse trees. Equivalently, w has two or more distinct leftmost derivations or two or more distinct rightmost derivations."},{"type":"paragraph","content":"Classic example: The grammar E → E + E | E * E | id | (E) is ambiguous because the string 'id + id * id' has two parse trees — one that groups as (id+id)*id and another as id+(id*id). Ambiguity is undesirable because it creates uncertainty in the meaning of programs. Compilers use disambiguation rules (operator precedence and associativity) or rewrite the grammar to be unambiguous."}]}},{"id":"v2-compiler-design-2024-pA-q4","number":4,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Handle."}],"answer":{"summary":"A Handle is a substring of the current right-sentential form that matches the RHS of some production and whose reduction to the LHS is a step in the reverse rightmost derivation.","explanation":[{"type":"paragraph","content":"In bottom-up parsing, a handle of a right-sentential form γ is a production A → β and a position in γ where β appears such that: (1) S ⟹*rm αAw and (2) αAw ⟹rm αβw = γ. That is, reducing β to A at that position is a step in the rightmost derivation of γ from the start symbol S."},{"type":"paragraph","content":"In shift-reduce parsing, the handle is the string on top of the stack that should be reduced next. Identifying the correct handle at each step is the fundamental problem in bottom-up parsing. LR parsers (SLR, LALR, CLR) use a finite automaton to efficiently locate handles. A right-sentential form may have at most one handle, which uniquely determines the next reduction step."}]}},{"id":"v2-compiler-design-2024-pA-q5","number":5,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Semantic Analysis?"}],"answer":{"summary":"Semantic Analysis is the compiler phase that checks the source program for semantic correctness (type compatibility, scope rules, declarations) beyond what grammar rules can express.","explanation":[{"type":"paragraph","content":"Semantic Analysis is the third major phase of a compiler. It operates on the parse tree/AST produced by the syntax analyzer and verifies that the program is semantically correct — that it conforms to the rules of the language that cannot be captured by context-free grammars."},{"type":"list","items":["Type Checking: Ensures that operators are applied to compatible types (e.g., no integer + string without conversion). Every expression has a type.","Declaration Checking: Verifies that all identifiers are declared before use and that there are no multiple declarations in the same scope.","Scope Resolution: Determines which declaration an identifier refers to based on scoping rules.","Function Call Checking: Verifies correct number and types of arguments in function calls.","Return Type Checking: Ensures function return values match the declared return type."]}]}},{"id":"v2-compiler-design-2024-pA-q6","number":6,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Activation Record."}],"answer":{"summary":"An Activation Record (stack frame) is a block of memory allocated on the runtime stack to hold information needed for a single execution (activation) of a procedure.","explanation":[{"type":"paragraph","content":"An Activation Record (also called a stack frame) is a contiguous block of memory allocated on the runtime stack each time a procedure is called. It holds all information needed for one invocation of the procedure. When the procedure returns, its activation record is deallocated."},{"type":"list","items":["Return Value: Space for the value returned by the procedure.","Actual Parameters: Values (or references) of arguments passed to the procedure.","Control Link (Dynamic Link): Pointer to the activation record of the calling procedure.","Access Link (Static Link): Pointer to the activation record of the lexically enclosing scope (for languages with nested procedures).","Saved Machine Status: Contents of registers saved before the call (to be restored on return).","Local Data: Memory for local variables of the procedure.","Temporaries: Space for intermediate values during expression evaluation."]}]}},{"id":"v2-compiler-design-2024-pA-q7","number":7,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Intermediate Code?"}],"answer":{"summary":"Intermediate Code is a machine-independent, source-language-independent representation of the source program, generated between the front end and back end of the compiler.","explanation":[{"type":"paragraph","content":"Intermediate Code (Intermediate Representation, IR) is a form of the program generated by the compiler's front end and consumed by the back end. It is designed to be independent of both the source language and the target machine, making it easy to retarget the compiler and to perform machine-independent optimizations."},{"type":"list","items":["Three-Address Code (TAC): Instructions of the form x = y op z, each with at most three addresses.","Quadruples: Table form of TAC — each instruction stored as (op, arg1, arg2, result).","Triples: Like quadruples but without the result field — results referenced by instruction number.","DAG (Directed Acyclic Graph): Graph representation of basic block that identifies common subexpressions.","Abstract Syntax Tree (AST): Tree form showing hierarchical structure of expressions and statements.","Bytecode: Stack-based IR used by virtual machines (e.g., JVM bytecode)."]}]}},{"id":"v2-compiler-design-2024-pA-q8","number":8,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define DAG (Directed Acyclic Graph)."}],"answer":{"summary":"A DAG (Directed Acyclic Graph) is a directed graph with no cycles, used in compilers to represent the structure of basic blocks and to identify common subexpressions.","explanation":[{"type":"paragraph","content":"A Directed Acyclic Graph (DAG) is a directed graph in which there are no cycles — following directed edges from any node will never lead back to that same node. In the context of compilers, DAGs are used as an intermediate representation for basic blocks."},{"type":"paragraph","content":"In a DAG for a basic block: leaf nodes represent identifiers (variables) or constants; interior nodes represent operators; a node represents the result of the operation — if the same subexpression appears multiple times, only one node is created (shared). This sharing naturally identifies common subexpressions that need to be computed only once. DAGs are also used to represent data dependencies and for register allocation. Example: for t1 = a+b; t2 = a+b; both t1 and t2 point to the same '+' node with children a and b."}]}},{"id":"v2-compiler-design-2024-pA-q9","number":9,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"What is Peephole Optimization?"}],"answer":{"summary":"Peephole Optimization is a machine-code level optimization that examines a small sliding window (peephole) of consecutive instructions and replaces them with shorter or faster equivalent sequences.","explanation":[{"type":"paragraph","content":"Peephole optimization is a local optimization technique applied to the generated machine code or assembly code. The optimizer examines a small window of consecutive instructions (the 'peephole') and looks for patterns that can be replaced by more efficient instruction sequences."},{"type":"list","items":["Redundant Load/Store Elimination: MOV R, x; MOV x, R → MOV R, x (the second instruction is redundant if R hasn't changed).","Constant Folding: Replace compile-time constants with their computed values.","Strength Reduction: Replace expensive operations: MUL R, 2 → ADD R, R or SHL R, 1.","Unreachable Code Elimination: Remove instructions after an unconditional jump that are never reached.","Jump Optimization: GOTO L1; L1: GOTO L2 → GOTO L2 (jump to jump elimination).","Algebraic Simplification: ADD R, 0 → NOP; MUL R, 1 → NOP."]}]}},{"id":"v2-compiler-design-2024-pA-q10","number":10,"marks":2,"tags":["Part A"],"text":[{"type":"paragraph","content":"Define Register Allocation."}],"answer":{"summary":"Register Allocation is the compiler phase that maps program variables (and temporaries) in intermediate code to a limited number of machine registers, minimizing costly memory accesses.","explanation":[{"type":"paragraph","content":"Register allocation is the process of assigning machine registers to the variables and temporaries used in a program's intermediate representation. Since machine registers are limited and much faster than memory, keeping frequently used values in registers significantly improves execution speed."},{"type":"paragraph","content":"The key challenge is that the number of live variables at any point may exceed the number of available registers. When a variable must be stored in memory due to insufficient registers, it is 'spilled' to the stack. Register allocation is typically formulated as a graph coloring problem: build an interference graph where nodes represent variables and edges connect live-range-overlapping variables; then color the graph with k colors (k = number of registers) such that no two adjacent nodes share the same color."}]}},{"id":"v2-compiler-design-2024-pB-q1","number":1,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of Finite Automata and its role in lexical analysis."}],"answer":{"summary":"Finite Automata (FA) are abstract machines that recognize regular languages. They form the mathematical foundation of lexical analyzers, which are implemented as DFAs to recognize token patterns.","explanation":[{"type":"heading","content":"Finite Automata"},{"type":"paragraph","content":"A Finite Automaton (FA) is a mathematical model consisting of a finite set of states, a set of input symbols (alphabet), a transition function, a start state, and a set of final (accepting) states. Two types:"},{"type":"list","items":["NFA (Nondeterministic Finite Automaton): Can have multiple transitions from a state on the same input, and ε-transitions (transitions on empty string). Formally: M = (Q, Σ, δ, q0, F) where δ: Q × (Σ ∪ {ε}) → 2^Q.","DFA (Deterministic Finite Automaton): Exactly one transition from each state on each input symbol. No ε-transitions. Formally: M = (Q, Σ, δ, q0, F) where δ: Q × Σ → Q. DFAs are more efficient to simulate."]},{"type":"heading","content":"Role in Lexical Analysis"},{"type":"paragraph","content":"The construction pipeline for a lexical analyzer is: Regular Expressions → NFA (Thompson's construction) → DFA (subset construction) → Minimized DFA (state minimization). The minimized DFA is then implemented as the lexer. For each token pattern, the regular expression is converted to an NFA. All NFAs are combined (with ε-transitions from a new start state to each sub-NFA's start state). The combined NFA is converted to a DFA. The DFA recognizes the longest possible token at each step (maximal munch rule) and identifies the token type."}]}},{"id":"v2-compiler-design-2024-pB-q2","number":2,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Describe the construction of Predictive Parsing Table."}],"answer":{"summary":"The Predictive Parsing Table M[A,a] is constructed using FIRST and FOLLOW sets; entry M[A,a] specifies which production to use when the current non-terminal is A and the lookahead is a.","explanation":[{"type":"heading","content":"Steps to Construct Predictive Parsing Table"},{"type":"list","items":["Step 1: Eliminate left recursion from the grammar (if any).","Step 2: Apply left factoring (if needed) to ensure each non-terminal's alternatives begin with distinct terminals.","Step 3: Compute FIRST sets for all grammar symbols and strings.","Step 4: Compute FOLLOW sets for all non-terminals.","Step 5: For each production A → α: (a) For each terminal a ∈ FIRST(α), add A → α to M[A, a]. (b) If ε ∈ FIRST(α), then for each terminal b ∈ FOLLOW(A), add A → α to M[A, b]; if $ ∈ FOLLOW(A), add A → α to M[A, $].","Step 6: All undefined entries are error entries.","Step 7: If any entry has multiple productions, the grammar is not LL(1)."]},{"type":"paragraph","content":"Example for `E' → +TE' | ε`: `FIRST(+TE') = {+}`, so `M[E', +] = E'→+TE'`. Since `ε ∈ FIRST(E'→ε)` and `FOLLOW(E') = {), $}`, we add `M[E', )] = E'→ε` and `M[E', $] = E'→ε`. This table is then used by the LL(1) parser to make deterministic parsing decisions."}]}},{"id":"v2-compiler-design-2024-pB-q3","number":3,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of operator precedence parsing."}],"answer":{"summary":"Operator Precedence Parsing is a shift-reduce parsing method for operator grammars that uses precedence relations (⋖, ≐, ⋗) between terminal symbols to identify handles without building the full LR automaton.","explanation":[{"type":"paragraph","content":"Operator Precedence Parsing is a simple, efficient bottom-up parsing technique for a class of grammars called operator grammars (no production has two adjacent non-terminals or ε on the RHS). It uses three precedence relations between pairs of terminals:"},{"type":"list","items":["a ⋖ b (a 'yields precedence' to b): b has higher precedence — a will be shifted before any reduction involving b.","a ≐ b (a 'has equal precedence' to b): a and b are at the same level (e.g., operators with the same associativity).","a ⋗ b (a 'takes precedence over' b): a has higher precedence — reduce a before considering b."]},{"type":"paragraph","content":"The precedence relations are stored in a precedence table. During parsing, the parser compares the terminal on top of the stack with the incoming terminal to decide shift or reduce. A handle is found between ⋖ and ⋗ in the stack. The method is simple and efficient but limited — it can only handle operator grammars and cannot handle all ambiguity. It is used in calculators and simple expression parsers."}]}},{"id":"v2-compiler-design-2024-pB-q4","number":4,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Discuss the runtime environment in compilers."}],"answer":{"summary":"The runtime environment manages memory layout, activation record management, parameter passing, and scope resolution during program execution, supporting features like recursion, dynamic allocation, and nested procedures.","explanation":[{"type":"heading","content":"Runtime Environment"},{"type":"paragraph","content":"The runtime environment is the set of data structures and procedures the compiler generates to support the execution of the compiled program. It manages the organization of memory and the way procedures interact."},{"type":"heading","content":"Memory Layout"},{"type":"list","items":["Code Segment (Text): Machine instructions of the compiled program (read-only).","Static/Data Segment: Statically allocated global and static variables (fixed size, known at compile time).","Stack Segment: Activation records for procedure calls. Grows and shrinks with calls/returns. Supports recursion.","Heap Segment: Dynamically allocated memory (malloc/new). Grows upward; managed by runtime (garbage collection or manual deallocation)."]},{"type":"heading","content":"Key Runtime Functions"},{"type":"list","items":["Activation Record Management: Creating and destroying stack frames on procedure call/return.","Parameter Passing: By value (copy of argument), by reference (address of argument), by value-result, by name.","Scope and Name Resolution: Using static (access) links for lexical scope or dynamic links for dynamic scope.","Heap Management: Allocating and reclaiming heap memory; garbage collection in managed languages."]}]}},{"id":"v2-compiler-design-2024-pB-q5","number":5,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the concept of Intermediate Code Generation with examples (TAC, Quadruples, Triples)."}],"answer":{"summary":"Intermediate Code Generation produces a machine-independent IR (Three-Address Code, Quadruples, Triples) from the annotated parse tree, forming the bridge between the compiler's front end and back end.","explanation":[{"type":"heading","content":"Three-Address Code (TAC)"},{"type":"paragraph","content":"TAC is the most common IR. Each instruction has the form: x = y op z (at most three addresses, one operator). Temporary variables (t1, t2, ...) are introduced as needed. TAC is easy to generate from an annotated parse tree and easy to translate to machine code."},{"type":"heading","content":"Quadruples"},{"type":"paragraph","content":"Quadruples represent each TAC instruction as a 4-tuple: (operator, operand1, operand2, result). Example for t1 = b * c: (*, b, c, t1). For x = -b: (uminus, b, _, x). For goto L: (goto, _, _, L). Quadruples are easy to rearrange (for optimization) since the result is explicitly named."},{"type":"heading","content":"Triples"},{"type":"paragraph","content":"Triples represent each instruction as a 3-tuple: (operator, operand1, operand2). The result is implicitly the instruction number, not stored explicitly. Example: instruction (0): (*, b, c) — result is (0). instruction (1): (+, a, (0)) — means a + result-of-instruction-0. Triples save space (no result field) but are harder to rearrange. Indirect triples add a level of indirection to facilitate rearrangement."},{"type":"heading","content":"Example: a = b + c * d"},{"type":"list","items":["TAC: t1 = c * d; t2 = b + t1; a = t2","Quadruples: (*, c, d, t1); (+, b, t1, t2); (=, t2, _, a)","Triples: (0): (*, c, d); (1): (+, b, (0)); (2): (=, a, (1))"]}]}},{"id":"v2-compiler-design-2024-pB-q6","number":6,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Describe the concept of Data Flow Analysis."}],"answer":{"summary":"Data Flow Analysis is a framework for gathering information about the flow of data values along program paths in the control flow graph, used to enable global optimizations.","explanation":[{"type":"paragraph","content":"Data Flow Analysis (DFA) is a technique for computing information about programs at compile time by analyzing how data values are produced (defined) and consumed (used) along control flow paths. It operates on the Control Flow Graph (CFG) and associates data flow information with each point in the program."},{"type":"heading","content":"Key Data Flow Problems"},{"type":"list","items":["Reaching Definitions: A definition d of variable v reaches point p if there is a path from d to p along which v is not redefined. Used for constant propagation and copy propagation. Direction: Forward.","Live Variable Analysis: A variable v is live at point p if there is a path from p to a use of v with no intervening definition. Used for dead code elimination and register allocation. Direction: Backward.","Available Expressions: An expression e is available at point p if on every path from the start to p, e is computed and none of its operands are redefined after the last computation. Used for CSE. Direction: Forward.","Very Busy Expressions: An expression is very busy at point p if it is definitely computed before any of its operands are changed on every path from p. Direction: Backward."]},{"type":"paragraph","content":"Data flow equations are solved iteratively using fixed-point algorithms (worklist algorithm) until the information stabilizes (reaches a fixed point). The general form: OUT[B] = gen[B] ∪ (IN[B] - kill[B]) for forward problems; IN[B] = gen[B] ∪ (OUT[B] - kill[B]) for backward problems."}]}},{"id":"v2-compiler-design-2024-pB-q7","number":7,"marks":4,"tags":["Part B"],"text":[{"type":"paragraph","content":"Explain the different types of code generation techniques."}],"answer":{"summary":"Code generation translates optimized intermediate code into target machine code, performing instruction selection, register allocation, and instruction scheduling.","explanation":[{"type":"paragraph","content":"Code generation is the final major phase of a compiler, responsible for translating the optimized intermediate representation into executable target machine code (or assembly). The code generator must produce correct code that efficiently uses machine resources."},{"type":"heading","content":"Key Tasks in Code Generation"},{"type":"list","items":["Instruction Selection: Mapping IR operations to machine instructions. Multiple machine instructions may implement a single IR operation; the code generator selects the most efficient sequence. Tree pattern matching or dynamic programming is used.","Register Allocation: Deciding which variables/temporaries to keep in registers at each program point. More variables than registers require 'spilling' to memory. Graph coloring is the standard approach.","Register Assignment: Assigning specific physical registers to the allocated register slots.","Instruction Scheduling (Ordering): Reordering instructions to minimize pipeline stalls, fill delay slots, and improve instruction-level parallelism while preserving data dependencies.","Memory Access Optimization: Choosing between stack, static, and register storage; generating efficient address computations for arrays and pointers."]},{"type":"heading","content":"Code Generation Techniques"},{"type":"list","items":["Simple code generation: Generate one or a few machine instructions per IR instruction, using a fixed mapping. Simple but not optimal.","Macro expansion: Each IR operator is independently expanded into a fixed machine code template.","Tree rewriting: Represent IR as a tree and use a pattern-matching rewriter to select instruction sequences that cover the tree (optimal via dynamic programming).","Graph coloring register allocation: Build an interference graph and color it with k colors (registers); spill nodes that can't be colored."]}]}},{"id":"v2-compiler-design-2024-pC-q1","number":1,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain the construction of NFA from Regular Expression. (b) Describe the conversion of NFA to DFA with an example."}],"answer":{"summary":"Thompson's construction builds an NFA from a regular expression bottom-up. The subset construction (powerset construction) converts a NFA to an equivalent DFA by treating sets of NFA states as single DFA states.","explanation":[{"type":"heading","content":"Part (a): Construction of NFA from Regular Expression (Thompson's Construction)"},{"type":"paragraph","content":"Thompson's construction algorithm builds an NFA from a regular expression by structural induction on the RE. Each sub-NFA has exactly one start state and one accepting state, with no transitions into the start state and no transitions out of the accepting state."},{"type":"list","items":["Base case — symbol a: NFA with start state i and accepting state f, with a single transition i →(a)→ f.","Base case — ε: NFA with start state i and accepting state f, with a single ε-transition i →(ε)→ f.","Union (r|s): Add new start state i and new accepting state f. Add ε-transitions from i to start states of NFAs for r and s. Add ε-transitions from accepting states of NFAs for r and s to f.","Concatenation (rs): Merge the accepting state of NFA for r with the start state of NFA for s (or add ε-transition between them).","Kleene Closure (r*): Add new start state i and new accepting state f. Add ε-transitions: i→start(r), f(r)→start(r) (loop back), f(r)→f (exit), i→f (accept empty string).","Result: The final NFA may have many ε-transitions but correctly recognizes L(r)."]},{"type":"heading","content":"Part (b): Conversion of NFA to DFA (Subset Construction / Powerset Construction)"},{"type":"paragraph","content":"The subset construction converts an NFA N = (Q, Σ, δ, q0, F) into an equivalent DFA D = (Q', Σ, δ', q0', F'). Each DFA state corresponds to a set (subset) of NFA states."},{"type":"heading","content":"Algorithm Steps"},{"type":"list","items":["ε-closure(T): The set of NFA states reachable from any state in set T using only ε-transitions (including the states in T themselves). Computed using BFS/DFS on ε-transitions.","move(T, a): The set of NFA states reachable from any state in T on input symbol a (non-ε transition).","Start state of DFA: ε-closure({q0}) — the ε-closure of the NFA's start state.","Transitions: For each DFA state S and each input symbol a, compute ε-closure(move(S, a)). This is the target DFA state.","DFA accepting states: Any DFA state that contains at least one NFA accepting state.","Repeat until no new DFA states are created."]},{"type":"heading","content":"Example: NFA for (a|b)*abb to DFA"},{"type":"paragraph","content":"For the RE (a|b)*abb, Thompson's construction gives an NFA with states 0-9. Subset construction: q0' = ε-closure({0}) = {0,1,2,4,7}. On input 'a': move({0,1,2,4,7}, a) = {3,8}; ε-closure = {1,2,3,4,6,7,8} = q1'. On input 'b': move({0,1,2,4,7}, b) = {5}; ε-closure = {1,2,4,5,6,7} = q2'. Continue until all states are computed. The DFA typically has 5 states for this example, far fewer than 2^10 possible subsets."},{"type":"svg","src":"/assets/diagrams/rtu/cs/2024/compiler-design/nfa-to-dfa.svg","alt":"NFA to DFA conversion example","caption":"Fig 1: NFA to DFA Conversion using Subset Construction"}]}},{"id":"v2-compiler-design-2024-pC-q2","number":2,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"Explain LL(1) parsing in detail. Construct LL(1) parse table for the following grammar: E→E+T|T, T→T*F|F, F→(E)|id. Eliminate left recursion and left factoring."}],"answer":{"summary":"LL(1) parsing requires eliminating left recursion and applying left factoring to the grammar, then computing FIRST/FOLLOW sets to build the parsing table. The given grammar E→E+T|T, T→T*F|F, F→(E)|id must be transformed before an LL(1) table can be built.","explanation":[{"type":"heading","content":"Step 1: Eliminate Left Recursion"},{"type":"paragraph","content":"The grammar E→E+T|T and T→T*F|F has direct left recursion (E starts with E, T starts with T). Apply the transformation A→Aα|β becomes A→βA', A'→αA'|ε:"},{"type":"list","items":["E → E+T | T → E → TE', E' → +TE' | ε","T → T*F | F → T → FT', T' → *FT' | ε","F → (E) | id (no change — no left recursion)"]},{"type":"heading","content":"Step 2: Left Factoring"},{"type":"paragraph","content":"After eliminating left recursion, check for common prefixes. The resulting grammar has no common prefixes (E'→+TE'|ε, alternatives +TE' and ε start differently; T'→*FT'|ε, alternatives * and ε start differently). No left factoring needed."},{"type":"heading","content":"Step 3: Compute FIRST Sets"},{"type":"list","items":["FIRST(id) = {id}, FIRST(+) = {+}, FIRST(*) = {*}, FIRST(() = {(}, FIRST()) = {)}","FIRST(F) = {(, id} [from F→(E)|id]","FIRST(T') = {*, ε} [from T'→*FT'|ε]","FIRST(T) = FIRST(F) = {(, id} [from T→FT']","FIRST(E') = {+, ε} [from E'→+TE'|ε]","FIRST(E) = FIRST(T) = {(, id} [from E→TE']"]},{"type":"heading","content":"Step 4: Compute FOLLOW Sets"},{"type":"list","items":["FOLLOW(E): E is the start symbol → add `$`. E appears in `F→(E)` → `)` follows E. `FOLLOW(E) = {$, )}`","FOLLOW(E'): E' appears in `E→TE'` at end → FOLLOW(E') ⊇ FOLLOW(E). `FOLLOW(E') = {$, )}`","FOLLOW(T): T in `E→TE'`, so `FIRST(E')-{ε} = {+}` ∈ FOLLOW(T). ε ∈ FIRST(E') so FOLLOW(E') ⊆ FOLLOW(T). `FOLLOW(T) = {+, $, )}`","FOLLOW(T'): T' in `T→FT'` at end → FOLLOW(T') ⊇ FOLLOW(T). `FOLLOW(T') = {+, $, )}`","FOLLOW(F): F in `T→FT'`, `FIRST(T')-{ε} = {*}` ∈ FOLLOW(F). ε ∈ FIRST(T') so FOLLOW(T') ⊆ FOLLOW(F). `FOLLOW(F) = {*, +, $, )}`"]},{"type":"heading","content":"Step 5: LL(1) Parsing Table"},{"type":"paragraph","content":"Construct table M[Non-terminal, Terminal] using rules: for A→α, add to M[A,a] for a∈FIRST(α); if ε∈FIRST(α), add to M[A,b] for b∈FOLLOW(A)."},{"type":"list","items":["`M[E, id] = E→TE'`, `M[E, (] = E→TE'`","`M[E', +] = E'→+TE'`, `M[E', )] = E'→ε`, `M[E', $] = E'→ε`","`M[T, id] = T→FT'`, `M[T, (] = T→FT'`","`M[T', *] = T'→*FT'`, `M[T', +] = T'→ε`, `M[T', )] = T'→ε`, `M[T', $] = T'→ε`","`M[F, id] = F→id`, `M[F, (] = F→(E)`"]},{"type":"paragraph","content":"No cell has multiple entries — the grammar is LL(1). The parser uses this table to deterministically parse any input string of arithmetic expressions without backtracking."}]}},{"id":"v2-compiler-design-2024-pC-q3","number":3,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"Explain the LALR parsing in detail. Construct LALR parsing table for a given grammar and demonstrate parsing of an input string."}],"answer":{"summary":"LALR parsing merges LR(1) states with identical cores (LR(0) items) to produce a compact parser almost as powerful as canonical LR(1). It is the standard parsing method used in tools like yacc and bison.","explanation":[{"type":"heading","content":"LALR (Look-Ahead LR) Parsing"},{"type":"paragraph","content":"LALR(1) parsing is a practical compromise between the large CLR(1) parser and the weaker SLR(1) parser. It constructs the canonical LR(1) collection, then merges states that have the same LR(0) core (same items ignoring lookaheads) and unions their lookahead sets."},{"type":"heading","content":"LR(1) Items"},{"type":"paragraph","content":"An LR(1) item is a pair [A → α•β, a] where A→αβ is a production, • marks the current parser position, and a is a lookahead terminal. The lookahead a is used only when β = ε (i.e., the item is a reduce item) — reduce by A→αβ only when the next input symbol is a."},{"type":"heading","content":"Example Grammar: S' → S, S → CC, C → cC | d"},{"type":"heading","content":"Step 1: Augment Grammar"},{"type":"paragraph","content":"S' → S (new start production). Productions: (0) S'→S, (1) S→CC, (2) C→cC, (3) C→d."},{"type":"heading","content":"Step 2: LR(1) Canonical Collection (selected states)"},{"type":"list","items":["I0: `{[S'→•S, $], [S→•CC, $], [C→•cC, c/d], [C→•d, c/d]}`","I1 (goto I0, S): `{[S'→S•, $]}` — accept state","I2 (goto I0, C): `{[S→C•C, $], [C→•cC, $], [C→•d, $]}`","I3 (goto I0, c): `{[C→c•C, c/d], [C→•cC, c/d], [C→•d, c/d]}`","I4 (goto I0, d): `{[C→d•, c/d]}` — reduce by C→d on c,d","I5 (goto I2, C): `{[S→CC•, $]}` — reduce by S→CC on `$`","I6 (goto I2, c): `{[C→c•C, $], [C→•cC, $], [C→•d, $]}`","I7 (goto I2, d): `{[C→d•, $]}` — reduce by C→d on `$`","I8 (goto I3/I6, C): `{[C→cC•, c/d]}` or `{[C→cC•, $]}` — same core!","I9 (goto I3/I6, d): `{[C→d•, c/d]}` same as I4 core"]},{"type":"heading","content":"Step 3: LALR State Merging"},{"type":"paragraph","content":"States with same LR(0) core are merged. I3 and I6 have the same core `[C→c•C]`, so merge to I36 with lookaheads `{c, d, $}`. I4 and I7 have core `[C→d•]`, merge to I47 with lookaheads `{c, d, $}`. The merged states form the LALR automaton with fewer states than CLR."},{"type":"heading","content":"Step 4: LALR Action/Goto Table"},{"type":"list","items":["State 0: on c → shift to 36; on d → shift to 47; on S → goto 1; on C → goto 2","State 1: on `$` → accept","State 2: on c → shift to 36; on d → shift to 47; on C → goto 5","State 36: on c → shift to 36; on d → shift to 47; on C → goto 8","State 47: on `c/d/$` → reduce C→d","State 5: on `$` → reduce S→CC","State 8: on `c/d/$` → reduce C→cC"]},{"type":"heading","content":"Parsing `'cdcd$'`"},{"type":"paragraph","content":"Stack: [0], Input: `cdcd$`. Shift c→[0,36]. Shift d→[0,36,47]. Reduce C→d: pop 47, goto(36,C)=8→[0,36,8]. Reduce C→cC: pop 8,36, goto(0,C)=2→[0,2]. Shift c→[0,2,36]. Shift d→[0,2,36,47]. Reduce C→d→[0,2,36,8]. Reduce C→cC→[0,2,5]. Reduce S→CC: pop 5,2, goto(0,S)=1→[0,1]. Accept."}]}},{"id":"v2-compiler-design-2024-pC-q4","number":4,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"(a) Explain Type Checking. (b) Discuss Backpatching with an example. (c) Explain how boolean expressions are translated."}],"answer":{"summary":"Type Checking enforces type safety rules; Backpatching resolves forward references in jump instructions during code generation; Boolean expression translation generates conditional jump code for if-then-else and loops.","explanation":[{"type":"heading","content":"Part (a): Type Checking"},{"type":"paragraph","content":"Type checking is the process of verifying that each operation in the program receives operands of the correct type, either at compile time (static type checking) or at runtime (dynamic type checking). The type checker traverses the annotated parse tree and assigns types to expressions based on the types of their operands."},{"type":"list","items":["Type Expressions: Types are represented as type expressions. Basic types: int, float, char, bool. Constructed types: arrays (array(10, int)), functions (int→float), pointers (pointer(int)), records.","Type Equivalence: Structural equivalence — two types are equivalent if they have the same structure. Name equivalence — two types are equivalent only if they are the same named type.","Coercions: Implicit type conversions. E.g., int + float → the int is coerced to float. Explicit coercions are type casts.","Overloading: Same operator/function with different type signatures — type checking resolves which version to use.","Example: For E1 + E2, if type(E1) = type(E2) = int, then type(E1+E2) = int. If one is float, coerce int to float and result is float."]},{"type":"heading","content":"Part (b): Backpatching"},{"type":"paragraph","content":"Backpatching is a technique to handle forward references in jump instructions during one-pass intermediate code generation. When a jump instruction is generated, the target label (jump destination) may not yet be known. Backpatching keeps a list of incomplete jump instructions and fills in (patches) the target addresses when they become known."},{"type":"list","items":["makelist(i): Creates a new list containing the single instruction number i (where i has an unfilled jump target).","merge(p1, p2): Returns a new list containing instructions in both p1 and p2.","backpatch(p, i): Fills in instruction number i as the target of all jump instructions in list p."]},{"type":"heading","content":"Backpatching Example: if (a < b) x = 1; else x = 2;"},{"type":"list","items":["100: if a < b goto _ [makelist(100)] → truelist = {100}","101: goto _ [makelist(101)] → falselist = {101}","Backpatch(truelist, 102): 100: if a < b goto 102","102: x = 1","103: goto _ [list to patch later with S.nextlist]","Backpatch(falselist, 104): 101: goto 104","104: x = 2"]},{"type":"heading","content":"Part (c): Translation of Boolean Expressions"},{"type":"paragraph","content":"Boolean expressions in control structures (if, while, for) are translated using the 'jumping code' method: instead of computing a boolean value, the compiler generates code that jumps to different targets based on the truth value."},{"type":"list","items":["For E → E1 || E2: If E1 is true, the whole expression is true (short-circuit). Backpatch(E1.falselist, E2.firstinstr). E.truelist = merge(E1.truelist, E2.truelist). E.falselist = E2.falselist.","For E → E1 && E2: If E1 is false, the whole expression is false. Backpatch(E1.truelist, E2.firstinstr). E.truelist = E2.truelist. E.falselist = merge(E1.falselist, E2.falselist).","For E → !E1: E.truelist = E1.falselist; E.falselist = E1.truelist.","For E → a relop b: Generate: if a relop b goto _; goto _. E.truelist = makelist(first goto); E.falselist = makelist(second goto)."]}]}},{"id":"v2-compiler-design-2024-pC-q5","number":5,"marks":10,"tags":["Part C"],"text":[{"type":"paragraph","content":"Explain Code Generation in detail. Discuss register allocation and assignment, and the DAG representation of basic blocks."}],"answer":{"summary":"Code generation translates IR to target machine code through instruction selection, register allocation (graph coloring), and instruction scheduling. DAG representation of basic blocks enables common subexpression elimination and efficient register use.","explanation":[{"type":"heading","content":"Code Generation"},{"type":"paragraph","content":"Code generation is the process of mapping optimized intermediate representation to target machine instructions. The code generator must correctly implement the program's semantics while efficiently using machine resources (registers, cache, pipeline)."},{"type":"heading","content":"Instruction Selection"},{"type":"paragraph","content":"For each IR operation, the code generator selects appropriate machine instructions. Multiple instruction sequences may implement the same operation; the choice affects performance. Tree pattern matching selects instructions by matching the IR tree against patterns corresponding to machine instructions and choosing covers with minimum cost."},{"type":"heading","content":"Register Allocation and Assignment"},{"type":"paragraph","content":"Register allocation determines which program variables/temporaries are kept in registers at each point. It is formulated as a graph coloring problem:"},{"type":"list","items":["Liveness Analysis: Compute which variables are live (still needed) at each program point using backward data flow analysis. IN[B] = use[B] ∪ (OUT[B] - def[B]); OUT[B] = ∪ IN[S] for successors S.","Build Interference Graph: Create a node for each variable. Add an edge between two nodes if the variables are simultaneously live (their live ranges overlap). Simultaneously live variables cannot share a register.","Graph Coloring: Color the interference graph with k colors (k = number of available registers) such that no two adjacent nodes have the same color. Each color represents a register.","Spilling: If the graph cannot be k-colored, select a variable to spill (store in memory instead of a register). Add load/store instructions for the spilled variable and repeat coloring.","Register Assignment: Map each color to a specific physical register."]},{"type":"heading","content":"DAG Representation of Basic Blocks"},{"type":"paragraph","content":"A DAG (Directed Acyclic Graph) is a compact representation of a basic block that makes common subexpressions explicit and identifies dead computations. Construction:"},{"type":"list","items":["For each statement x = y op z in the basic block: check if a node labeled op with children node(y) and node(z) already exists; if yes, do not create a new node (CSE identified); if no, create a new interior node labeled op with children node(y) and node(z). Label the new node with x.","Leaf nodes represent variables/constants as they appear at the start of the block.","Interior nodes represent computed values; labels on nodes are the variables that currently hold that value.","Dead computations: nodes with no labels (their values are never used) can be eliminated."]},{"type":"heading","content":"Example: DAG for basic block"},{"type":"list","items":["t1 = a + b","t2 = a + b → same as t1 (CSE: t2 and t1 share the same '+' node)","t3 = t1 * t2 → '*' node with children being the shared '+' node (equivalent to t1^2)","Generated code using DAG: t1 = a + b; t3 = t1 * t1 (saving one addition)"]},{"type":"svg","src":"/assets/diagrams/rtu/cs/2024/compiler-design/dag-basic-block.svg","alt":"DAG representation of a basic block showing CSE","caption":"Fig 2: DAG for Basic Block — Common Subexpression Elimination"},{"type":"heading","content":"Instruction Scheduling"},{"type":"paragraph","content":"Instruction scheduling reorders instructions to minimize pipeline stalls while preserving data and control dependencies. It exploits instruction-level parallelism. List scheduling is a common greedy technique: maintain a list of ready instructions (all dependencies satisfied), schedule the highest-priority ready instruction, update the ready list, and repeat."}]}}]}],"loading":false,"error":null}}}

Q9Compiler Design

Question

Answer