UGC NET Computer Science Theory of Computation and Compilers Flashcards

24 sample cards from the Theory of Computation and Compilers deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. Define S-attributed and L-attributed Syntax-Directed Definitions.

   S-attributed: uses only synthesized attributes; evaluable bottom-up in a single pass (suits LR parsing). L-attributed: each inherited attribute of a symbol depends only on attributes of its parent and the siblings to its left (plus any synthesized); evaluable in one left-to-right depth-first pass.

2. What is a Dependency Graph and how does it determine Evaluation Order?

   A directed graph whose nodes are attribute instances and whose edges go from each attribute to those that depend on it. A valid evaluation order is any topological sort of this graph; a cycle means no valid evaluation order exists.

3. What does Type Checking accomplish in semantic analysis?

   It verifies that operations are applied to operands of compatible types using the language's type rules, performs type inference and coercion/conversion where allowed, and reports type errors. It is typically implemented with synthesized type attributes via syntax-directed definitions.

4. What is an Activation Record (stack frame) and what does it typically contain?

   A block of memory for one procedure activation containing: return value, actual parameters, control link (to caller's frame), access/static link, saved machine status (return address, registers), and local/temporary variables.

5. What is an Activation Tree and how does stack allocation relate to it?

   An activation tree depicts the nesting of procedure calls during execution (root = main, children = called procedures). Because calls follow last-in-first-out nesting, activation records are pushed/popped on a run-time stack, mirroring a depth-first traversal of the tree.

6. Compare call-by-value, call-by-reference, and call-by-name parameter passing.

   Call-by-value: the actual's value is copied; callee changes don't affect the caller. Call-by-reference: the actual's address is passed; callee changes affect the caller's variable. Call-by-name: the actual is re-evaluated (textually substituted) on each use. Call-by-value-result copies in and copies the result back on return.

7. What information does a compiler Symbol Table store and why?

   For each identifier it stores name, type, scope, storage/offset, kind (variable, function, parameter), and other attributes. It supports semantic analysis (type checking, scope resolution) and code generation; it is typically implemented as a hash table with scope handling.

8. Name common Intermediate Representations used in compilers.

   Three-address code (e.g., quadruples, triples, indirect triples), syntax trees / DAGs, postfix notation, and static single-assignment (SSA) form. IRs decouple the front end from the back end and ease optimization.

9. How is a Boolean expression translated using short-circuit (jumping) code?

   Boolean operators are translated into conditional jumps rather than computing 0/1 values: for a&&b, if a is false jump to the false-exit; for a||b, if a is true jump to the true-exit. Backpatching fills in jump targets (truelist/falselist) once labels are known. This realizes short-circuit evaluation.

10. How is an if-then-else / control-flow statement translated to three-address code?

    The boolean condition is given true and false target labels; code emits a conditional jump to the false label, the then-block, a jump past the else, the false label, then the else-block, then the merge label. Loops (while) similarly use a begin label, condition test, body, and a jump back.

11. What is the distinction between Local Optimization and Global Optimization?

    Local optimization works within a single basic block (e.g., common-subexpression elimination, constant folding using a DAG). Global optimization spans basic blocks across the whole procedure using control-flow and data-flow analysis (e.g., global CSE, code motion).

12. What is Data-Flow Analysis and name two classic problems with their direction.

    It gathers information about how data values propagate through a program's control-flow graph by solving equations to a fixed point. Reaching definitions and available expressions are forward problems; live variable analysis and very-busy expressions are backward problems.

13. What is Control-Flow Analysis and what is a basic block?

    Control-flow analysis builds the control-flow graph (CFG) and identifies loops and dominators. A basic block is a maximal sequence of consecutive instructions with one entry (a leader) and one exit—no branches in except at the start and none out except at the end.

14. Describe Loop Optimization techniques.

    Loop-invariant code motion (hoist computations that don't change out of the loop), induction-variable elimination/strength reduction (replace expensive ops like multiply with add), and loop unrolling. These reduce work performed per iteration; they target the most frequently executed code.

15. What is Peephole Optimization?

    A machine-dependent technique that examines a small sliding window (peephole) of target/intermediate instructions and replaces inefficient sequences with shorter/faster ones: removing redundant loads/stores, eliminating unreachable code, algebraic simplification, strength reduction, and using machine idioms.

16. What is Instruction Scheduling and why is it performed?

    Reordering instructions to improve performance on pipelined/superscalar processors—filling delay slots, avoiding pipeline stalls, and hiding memory/functional-unit latencies—while preserving data dependences. List scheduling over a dependence DAG is a common approach.

17. What is a Non-Computational (undecidable) problem, with an example?

    A problem for which no algorithm (Turing machine) can produce the correct yes/no answer for all inputs. Examples: the Halting Problem, the Post Correspondence Problem, and determining whether two CFGs are equivalent.

18. How is the Halting Problem's undecidability typically proven?

    By diagonalization/contradiction: assume a decider H(M,w) exists; build D(M) that halts iff H says M loops on M; then D(D) halts iff it loops—a contradiction. Hence no such H exists and halting is undecidable.

19. How are complexity classes P and NP defined?

    P is the class of decision problems solvable by a deterministic TM in polynomial time. NP is the class solvable by a non-deterministic TM in polynomial time, equivalently problems whose 'yes' certificates are verifiable in polynomial time. P⊆NP; whether P=NP is open.

20. What does NP-complete mean and how is NP-completeness proved?

    A problem is NP-complete if it is in NP and every NP problem reduces to it in polynomial time (NP-hard). It is proved by polynomial-time reduction from a known NP-complete problem (e.g., SAT via Cook-Levin theorem). If any NP-complete problem is in P, then P=NP.

21. How do you construct a Turing machine for a simple problem like recognizing {a^n b^n c^n | n≥1}?

    Repeatedly scan the tape: mark the leftmost unmarked a (e.g., as X), move right to mark the next b (Y), then the next c (Z), and return left; loop until all are marked. Accept if every a,b,c is matched in correct order with equal counts; reject otherwise. (This language is context-sensitive, not context-free.)

22. How is the translation of a declaration like 'int x' handled in syntax-directed translation?

    A semantic rule computes the type and width from the type specifier and uses inherited attributes to record each identifier's type, width, and relative storage offset in the symbol table, advancing the offset for the next declaration.

23. How is an assignment statement translated into three-address code?

    Each sub-expression is evaluated into a temporary; the synthesized attribute holds the place (name/temp) of the result. For x = a+b*c, emit t1 = b*c; t2 = a+t1; x = t2. Array and indexed assignments compute the address offset first.

24. How are Procedure Calls handled at the code-generation/runtime level?

    The caller evaluates and passes actual parameters (via the param instruction / pushing onto the stack), saves machine state, sets up the activation record, and transfers control (call). On return the callee restores state, passes back any return value, and control resumes after the call site.

What this deck covers

Theory of Computation and Compilers flashcards FAQ