Compiler Design for GATE
Compiler Design is one of the most reliably weighted subjects in GATE CS, typically contributing 5 to 7 marks per year. Unlike some subjects where question...
How GATE Tests Compiler Design: Key Topics and Mark Distribution
Compiler Design is one of the most reliably weighted subjects in GATE CS, typically contributing 5 to 7 marks per year. Unlike some subjects where question types vary widely, Compiler Design has a stable set of tested topics, which means focused preparation yields predictable returns.
The highest-yield area is parsing, which includes both top-down and bottom-up techniques. Questions ask you to compute FIRST and FOLLOW sets, fill in LL(1) parsing tables, identify whether a grammar is LL(1) or not, construct LR(0) or SLR(1) items and tables, and identify shift-reduce or reduce-reduce conflicts. These are mechanical, practised skills that reward repetition. Budget at least 40 percent of your Compiler Design preparation time to parsing alone.
Lexical analysis questions test your understanding of how tokens are defined by regular expressions and recognized by DFAs. A typical question gives you a set of token patterns and an input string and asks how many tokens are produced, or which token type a given string matches.
Syntax-directed translation questions test attribute grammars. GATE gives you a grammar with semantic rules attached to productions and an input string, then asks you to evaluate a specific attribute at the root or at a specific parse tree node. These questions are straightforward if you have practiced building annotated parse trees, but they are time-consuming if you try to reason through them abstractly.
Runtime environment questions test how compilers implement function calls using activation records. You need to know what an activation record contains: the return address, the return value, actual parameters, local variables, and control and access links. Questions often ask about the state of the runtime stack at a specific point during execution of a recursive program.
Code optimization questions ask you to identify which optimization applies to a given code snippet, or to trace the effect of an optimization on a three-address code sequence. Focus on constant propagation, dead code elimination, and loop invariant code motion for GATE.
Previous year analysis shows that GATE has repeatedly asked questions on SLR parsing tables, LL(1) conflict resolution, and attribute grammar evaluation. If you master these three skill types, you are well positioned to capture the majority of Compiler Design marks.
FIRST, FOLLOW, and LL(1) Parsing Tables: A Step-by-Step Approach
Computing FIRST and FOLLOW sets and constructing LL(1) parsing tables are among the most frequently tested mechanical skills in Compiler Design for GATE. Mastering the procedure lets you answer these questions reliably within the time constraints of the exam.
The FIRST set of a grammar symbol alpha is the set of terminals that can appear as the first symbol of some string derivable from alpha. To compute FIRST sets, follow these rules: if X is a terminal, FIRST of X is just X. If there is a production X goes to epsilon, add epsilon to FIRST of X. If there is a production X goes to Y1 Y2 ... Yk, add FIRST of Y1 to FIRST of X, and if epsilon is in FIRST of Y1 also add FIRST of Y2, and so on. Continue until all FIRST sets stabilize.
The FOLLOW set of a nonterminal A is the set of terminals that can appear immediately to the right of A in some sentential form. To compute FOLLOW sets: place the end-of-input marker in FOLLOW of the start symbol. For each production B goes to alpha A beta, add FIRST of beta minus epsilon to FOLLOW of A. If epsilon is in FIRST of beta, or if beta is empty, add FOLLOW of B to FOLLOW of A.
To construct the LL(1) parsing table, for each production A goes to alpha: for each terminal a in FIRST of alpha, add A goes to alpha to table entry A comma a. If epsilon is in FIRST of alpha, for each terminal b in FOLLOW of A, add A goes to alpha to table entry A comma b. Also add the production to the entry for A with the end-of-input marker if epsilon is in FIRST of alpha and the end-of-input marker is in FOLLOW of A.
A grammar is LL(1) if and only if no table entry has more than one production. If two productions for the same nonterminal lead to the same table entry, you have a conflict and the grammar is not LL(1). Common sources of conflict are left recursion and common prefixes that have not been left-factored.
A worked tip: when GATE gives you a grammar and asks whether it is LL(1), check first for left recursion, because any grammar with direct left recursion cannot be LL(1). Then check whether any two alternatives for the same nonterminal share a symbol in their FIRST sets. These two checks catch most conflicts without needing to build the full table.
LR Parsing, SLR Tables, and Runtime Environments for GATE
LR parsing is more powerful than LL parsing and is the technique underlying most real-world parser generators like Yacc and Bison. GATE tests LR parsing through questions on LR(0) item construction, SLR(1) table construction, and conflict identification.
An LR(0) item is a production with a dot indicating how far the parser has progressed. For example, A goes to alpha dot beta means the parser has recognized alpha and expects to see something that beta can derive. The closure of a set of items adds items for the nonterminal immediately after the dot: if A goes to alpha dot B beta is in the set, add all items B goes to dot gamma for each production for B. The goto operation computes what state to move to after shifting a symbol by advancing the dot past that symbol in all relevant items.
The collection of canonical LR(0) items is the set of all states reachable from the initial item by closure and goto operations. This collection is used to build the LR parsing table. For SLR(1) parsing, reduce actions are added only for tokens in the FOLLOW set of the nonterminal being reduced. For canonical LR(1), each item carries a lookahead symbol, giving finer control. LALR(1) merges states with identical cores from the canonical LR(1) collection, trading some power for smaller tables.
Shift-reduce conflicts occur when a state has both a shift action and a reduce action for the same input token. Reduce-reduce conflicts occur when a state has two different reduce actions for the same token. SLR(1) resolves some conflicts that LR(0) cannot because it restricts reduces using FOLLOW sets. LALR(1) resolves some conflicts that SLR(1) cannot. Canonical LR(1) is the most powerful and conflict-free for any unambiguous grammar.
Runtime environments implement the dynamic aspects of program execution. The call stack grows when a function is called and shrinks when it returns. Each stack frame, also called an activation record, holds the return address, the caller's frame pointer, local variables, and parameters. For recursive functions, multiple activation records for the same function may be on the stack simultaneously.
For GATE, a question might show a recursive function and ask how many activation records are on the stack at a given recursive depth. The answer is simply the recursion depth. Another common question asks what information the access link in an activation record holds: it points to the activation record of the statically enclosing scope, which is needed to implement lexical scoping in languages that allow nested function definitions.