CSS Prepare

optional · CSS study notes

9. Theory of Automata & Compiler Construction

FPSC CSS Computer Science past papers (2016–2026) — 54 questions: 10 MCQs, 44 subjective parts. Newest first.

Part A — Subjective Questions

2026 · Paper-I · Q7(a) (6 marks)

Question

Construct a Deterministic Finite Automaton (DFA) for the regular expression (a|b)*abb.

Solution

The regular expression (a|b)*abb describes all strings over {a,b} that end with the substring 'abb'. This is a classic textbook DFA construction. States track how much of the suffix 'abb' has been matched so far:

  • q0 (start state): no relevant suffix matched yet.
  • q1: last character seen was 'a' (one character of 'abb' matched).
  • q2: last two characters seen were 'ab' (two characters of 'abb' matched).
  • q3 (accepting state): last three characters seen were 'abb' — string ends in 'abb'.

Transition table:

Stateon 'a'on 'b'Accepting?
q0 (start)q1q0No
q1q1q2No
q2q1q3No
q3 (accepting)q1q0Yes

Explanation of transitions: from q0, seeing 'a' starts a potential match (go to q1), seeing 'b' with nothing matched yet stays at q0. From q1 (have 'a'), seeing another 'a' stays at q1 (still just have a trailing 'a'), seeing 'b' advances progress to q2 (have 'ab'). From q2 (have 'ab'), seeing 'a' resets progress to q1 (the 'a' could start a new match), seeing 'b' completes the pattern 'abb', moving to accepting state q3. From q3 (just matched 'abb'), seeing 'a' restarts potential matching at q1, seeing 'b' drops back to q0 (since '...abbb' no longer ends in exactly the needed pattern position, though the string still 'contains' abb — for this classic DFA, since we only need it to END in abb, reaching q3 makes the whole string accepted at that point, but transitions continue to correctly track further suffixes for longer strings). This DFA correctly accepts exactly the strings over {a,b} ending in 'abb', matching the language of (a|b)*abb.

2026 · Paper-I · Q7(b) (6 marks)

Question

Explain the difference among lexeme, token, and pattern with examples.

Solution

During lexical analysis, the compiler's scanner reads source code and classifies pieces of it using three related but distinct concepts:

  • Lexeme: the actual sequence of characters in the source code that matches a token's pattern — the literal, concrete substring found in the program text. Example: in the source line int count = 10;, the lexemes are int, count, =, 10, and ;.

  • Token: an abstract category/classification assigned to a lexeme, typically represented as a pair (token-type, attribute-value), used by later compiler phases (parsing) instead of dealing with raw text. Example: the lexeme count is classified as the token <IDENTIFIER, "count">, the lexeme 10 is classified as <NUMBER, 10>, and int might be classified as the token <KEYWORD, "int">.

  • Pattern: the rule (commonly expressed as a regular expression) that describes the set of possible character sequences that can form a lexeme for a given token type. Example: the pattern for the IDENTIFIER token might be defined as the regular expression [a-zA-Z_][a-zA-Z0-9_]* (a letter/underscore followed by any number of letters/digits/underscores) — any lexeme matching this pattern (like count, x1, total_sum) is recognized as an IDENTIFIER token.

In short: the pattern is the general rule, the lexeme is the specific text found that satisfies that rule, and the token is the categorized/labelled representation of that lexeme passed on to the parser.

2026 · Paper-I · Q7(c) (8 marks)

Question

Consider the three-address code: t1 = a + b t2 = t1 + c t3 = t2 + d If the machine has only two registers, how should the compiler allocate registers to minimize memory spills?

Solution

With only two registers (say R1, R2) available and three temporaries whose values chain together (t1 feeds into t2, t2 feeds into t3), the compiler should exploit the fact that each temporary is only needed until it is consumed by the very next instruction, reusing registers instead of dedicating one to each temporary:

Step 1: t1 = a + b

  • Load a into R1: MOV R1, a
  • Add b into R1: ADD R1, b → R1 now holds t1 (no separate register needed for t1)

Step 2: t2 = t1 + c

  • t1 is already in R1, so simply add c to it: ADD R1, c → R1 now holds t2 (t1's value is no longer needed and is safely overwritten in place, since nothing else uses t1 again)

Step 3: t3 = t2 + d

  • t2 is already in R1, so add d to it: ADD R1, d → R1 now holds t3, the final result.

Generated code:

MOV R1, a
ADD R1, b     ; R1 = t1
ADD R1, c     ; R1 = t2
ADD R1, d     ; R1 = t3

Register allocation strategy: because this is a simple linear chain of dependent additions where each temporary is used exactly once (immediately by the next instruction) and then becomes dead, only ONE register (R1) is actually needed at any point in time to carry the running partial sum forward; the second register R2 is not required at all for this particular code sequence (it would only be needed if two live values had to be held simultaneously, e.g., if the expression instead needed two independent sub-results before combining them). The key principle applied is liveness analysis: allocate a register to a value only for the span between its definition and its last use, and reuse/overwrite a register as soon as its current value becomes dead (has no further uses), which is exactly what avoids any spill to memory here despite the tight two-register limit.

2026 · Paper-I · Q8(a) (6 marks)

Question

Suppose a lexical analyzer is scanning code and encounters the following input string: 9var = x + 12abc; Describe step-by-step how the lexical analyzer processes this input, identifies errors, and generates tokens. Explain which specific rules of lexical analysis it uses.

Solution

Processing 9var = x + 12abc; character by character using the maximal-munch (longest match) rule, which states the scanner always consumes the longest possible sequence of characters that still matches some token pattern:

  1. The scanner reads '9' — a digit, so it starts trying to match the NUMBER pattern (a digit followed by more digits). It then reads 'v' — since letters cannot legally continue a numeric literal in the NUMBER pattern, the scanner has matched a maximal numeric prefix '9' but immediately finds it is directly followed, with no separator, by letters ('var'), which is illegal in C-like languages (identifiers cannot start with a digit, and '9var' is not a valid token under any pattern). This is flagged as a LEXICAL ERROR — an invalid identifier/malformed token, since '9var' does not match the IDENTIFIER pattern ([a-zA-Z_][a-zA-Z0-9_]*, which must start with a letter/underscore) nor the NUMBER pattern (digits only) in full. The analyzer typically reports the error and may recover by skipping characters until the next likely token boundary (e.g., whitespace).
  2. Skipping the space, '=' is recognized as the ASSIGNMENT OPERATOR token, <ASSIGN_OP, "=">.
  3. 'x' matches the IDENTIFIER pattern → token <IDENTIFIER, "x">.
  4. '+' is recognized as the ARITHMETIC OPERATOR token, <PLUS_OP, "+">.
  5. '12abc' — again the scanner greedily matches digits '12' first, then hits letters 'abc' immediately after with no separator, again violating identifier/number rules (an identifier cannot start with a digit) → a second LEXICAL ERROR is reported for this malformed token.
  6. ';' matches the STATEMENT TERMINATOR token, <SEMICOLON, ";">.

Rules used: the maximal-munch/longest-match rule (always extend a match as far as possible before deciding a token is complete), pattern-priority rules (when a lexeme could match multiple patterns, e.g., keywords vs identifiers, the more specific rule/priority order applies), and lexical-error detection (any character sequence that cannot be matched to any valid token pattern, such as a digit immediately followed by letters with no delimiter, is reported as an illegal token rather than silently accepted).

2025 · Paper-I · Q8(a) (6 marks)

Question

Create a regular expression for the language that always starts with string " baa ". Also draw the deterministic finite automata (DFA) for such language. Provide a clear explanation of each step.

Solution

Regular expression: baa(a|b)* over alphabet {a,b} — i.e., the string "baa" followed by any number (including zero) of further a's or b's.

DFA description (states and transition table), since Σ = {a,b}:

  • q0 (start state): on 'b' → q1; on 'a' → qd (dead/trap state, since the string must begin with 'b').
  • q1 (after seeing 'b'): on 'a' → q2; on 'b' → qd (the required next symbol is 'a').
  • q2 (after seeing 'ba'): on 'a' → q3 (accepting); on 'b' → qd.
  • q3 (accepting state, after seeing 'baa'): on 'a' → q3 (self-loop); on 'b' → q3 (self-loop) — once "baa" has been matched, any further a's or b's keep the string accepted.
  • qd (dead/trap state, non-accepting): on 'a' → qd; on 'b' → qd — absorbs any string that failed to start with "baa".

Transition table:

StateabAccepting?
q0qdq1No
q1q2qdNo
q2q3qdNo
q3q3q3Yes
qdqdqdNo

Explanation: the DFA walks the prefix "b","a","a" through q0→q1→q2→q3 exactly tracking the required prefix; any deviation from this exact sequence is routed to the dead state qd, from which it can never escape, correctly rejecting all strings not starting with "baa". Once state q3 is reached the automaton accepts and stays accepting for any suffix, matching (a|b)*.

2025 · Paper-I · Q8(b) (6 marks)

Question

What is Instruction Scheduling? Explain its role during code generation process.

Solution

Instruction scheduling is a compiler optimization, performed during (or just after) code generation, that reorders the machine instructions produced for a basic block or a larger region without changing the program's semantics/output, in order to better exploit the target processor's pipeline and functional units.

Role during code generation:

  • Hides pipeline stalls: modern pipelined CPUs need several cycles before the result of one instruction is available; if a dependent instruction immediately follows, the pipeline stalls. The scheduler moves independent instructions in between to fill these gaps.
  • Avoids hazards: it reorders instructions so that data hazards (RAW/WAR/WAW) and structural hazards on functional units are minimized, without inserting extra NOPs where avoidable.
  • Maximizes instruction-level parallelism: on superscalar/VLIW architectures, the scheduler groups independent instructions so multiple functional units can execute them concurrently.
  • Respects dependencies: it builds a data-dependency graph of the basic block and only reorders instructions that have no dependency conflict, guaranteeing correctness is preserved.

It is typically applied after (or interleaved with) register allocation as one of the final back-end optimization passes, directly before final machine code emission, and it significantly improves the runtime performance of the generated code on pipelined hardware.

2025 · Paper-I · Q8(c) (8 marks)

Question

What is a parse tree? How the parse tree is used to check whether a specific string belongs to a language or not. Provide example to elaborate this.

Solution

A parse tree (derivation tree) is a hierarchical, ordered tree representation of how a string is derived from the start symbol of a context-free grammar. Its root is the grammar's start symbol, each internal node is a non-terminal expanded according to one of its production rules, and the leaves, read left to right, spell out the input string (the yield of the tree).

Using it to check language membership: to test whether a string w belongs to a language L(G) defined by grammar G, a parser attempts to construct a parse tree for w by applying G's production rules (top-down, e.g., LL parsing, or bottom-up, e.g., LR parsing). If such a tree can be built whose leaves exactly match w and whose root is the start symbol, then w is successfully derived and therefore belongs to L(G); if no valid sequence of rule applications can produce w (parsing fails/gets stuck), then w does not belong to the language (a syntax error is reported).

Example: grammar for simple expressions: E → E + T | T T → T * F | F F → id

For the string "id + id * id":

  • Root: E
  • E → E + T
  • Left E → T → F → id (first id)
  • T → T * F → F * F → id * id (second and third id's) The resulting tree has root E, branches for '+' and '*' respecting precedence (multiplication nested deeper, binding tighter), and its leaves read left to right give exactly "id + id * id". Since a complete, valid parse tree was constructed, the string is confirmed to belong to the language generated by this grammar; if instead the input were "id + + id", no legal sequence of productions could generate it, and parsing would fail, showing the string is not in the language.

2024 · Paper-I · Q8(a) (5 marks)

Question

Write Regular Expression(s) for the following (5 each): For date Format of standard e.g. (10.03.2024 | 12/30/2023| 01/01/2022)

Solution

^\d{1,2}[./]\d{1,2}[./]\d{4}$

This matches two 1-2 digit numeric groups (covering day/month values from 1-31 in either order, since the examples mix dd.mm.yyyy and mm/dd/yyyy formats) separated by either a dot or a slash, followed by a 4-digit year. A stricter, range-validated version enforcing day 01-31 and month 01-12 explicitly would be: ^(0[1-9]|[12]\d|3[01])[./](0[1-9]|1[0-2])[./]\d{4}$

2024 · Paper-I · Q8(b) (5 marks)

Question

Write a Regular Expression that will match URL e.g. (http://example.edu.pk)

Solution

^https?://[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}(/[^\s]*)?$

This matches an optional 's' after http (for https), followed by "://", a domain name made of letters/digits/dots/hyphens ending in a top-level domain of at least 2 letters, and an optional path component after a trailing slash.

2024 · Paper-I · Q8(c) (5 marks)

Question

Write a Regular Expression that will match an IP address. e.g. 192.168.0.1

Solution

^((25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$

Each of the four dot-separated octets is constrained to the valid range 0-255 using the alternation: 250-255 (25[0-5]), 200-249 (2[0-4][0-9]), or 0-199 (a 1-3 digit number not starting improperly, [01]?[0-9][0-9]?), giving a properly range-validated IPv4 address matcher.

2024 · Paper-I · Q8(d) (5 marks)

Question

Write a Regular Expression that will match an email address. e.g. (abc@example.com)

Solution

^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$

This matches one or more allowed local-part characters (letters, digits, dot, underscore, percent, plus, hyphen), followed by '@', a domain name of letters/digits/dots/hyphens, and a top-level domain of at least 2 letters.

2023 · Paper-I · Q7(a) (8 marks)

Question

Design and draw a finite automaton to recognize the regular language of all strings that contain the string '001' as a substring.

Solution

This can be recognized by a DFA that tracks how much of the pattern "001" has been matched so far as a suffix of the input read:

States: q0 (no progress / initial), q1 (matched "0"), q2 (matched "00"), q3 (matched "001" - accepting, and absorbing since once "001" appears anywhere, the string is accepted regardless of what follows).

Transition table:

  • q0 --0--> q1, q0 --1--> q0
  • q1 --0--> q2, q1 --1--> q0
  • q2 --0--> q2, q2 --1--> q3
  • q3 --0--> q3, q3 --1--> q3 (self-loop on both symbols; once accepted, it stays accepted)

Start state: q0. Accepting state: {q3}. Any input string that at any point produces the subsequence 0,0,1 causes the automaton to reach q3 and remain there, so it correctly accepts exactly the strings containing "001" as a substring.

2023 · Paper-I · Q7(b) (6 marks)

Question

Consider the following state diagram and extract the standard information, i.e., Q, Σ, q0, F and δ. (Diagram shows states a, b and a double-circled final state; arrows: self-loop 0 on a, a->b labeled 1, a curved top arc labeled 1 from a to the final state, b->final labeled 0, and a self-loop labeled 1 on the final state.)

Solution

Reading the given diagram (states a, b, and a double-circled accepting state, call it f):

Q = {a, b, f} Σ = {0, 1} q0 = a (the state with the initial incoming arrow) F = {f} (the double-circled state)

δ (transition function), read off the arrows shown:

  • δ(a, 0) = a (self-loop on a)
  • δ(a, 1) = {b, f} (the straight arrow a->b, and the curved top arc directly from a to f, both labeled 1 - making this an NFA)
  • δ(b, 0) = f
  • δ(f, 1) = f (self-loop on f)

This machine is a Non-deterministic Finite Automaton (NFA), since state a has two possible transitions on input symbol 1 (to b and to f).

2023 · Paper-I · Q7(c) (6 marks)

Question

How would you optimize a loop? Describe the techniques briefly.

Solution

Common loop optimization techniques used by compilers:

  1. Loop-invariant code motion: moving computations that produce the same result every iteration (do not depend on the loop variable) outside the loop body, so they execute only once instead of n times.

  2. Strength reduction: replacing expensive operations inside a loop with cheaper equivalent ones, e.g., replacing repeated multiplication i*4 in successive iterations with a running addition of 4 each iteration.

  3. Induction variable elimination: removing redundant loop-control variables that are simple linear functions of the main loop counter, keeping only the necessary one.

  4. Loop unrolling: replicating the loop body multiple times per iteration to reduce the relative overhead of loop-control instructions (test/increment/branch) and enable more instruction-level parallelism.

  5. Loop fusion/fission: merging (fusion) adjacent loops with the same iteration range to reduce loop overhead and improve cache locality, or splitting (fission) a large loop into smaller ones when it improves cache behavior or enables further optimization/parallelization.

  6. Common subexpression elimination inside loops: computing a repeated expression once and reusing the stored result rather than recomputing it every iteration.

2023 · Paper-I · Q8(a) (8 marks)

Question

Discuss the role of Syntax Tree in representing formal text structure. Develop a Syntax Tree structure for the following piece of code: while b ≠ 0 if a > b a = a - b; else b = b - a; return a;

Solution

A syntax tree (abstract syntax tree, AST) represents the hierarchical grammatical structure of source code, with each internal node representing an operator/language construct and each leaf representing an operand/identifier/literal. Unlike a parse tree, it omits purely syntactic details (parentheses, keywords used only for grouping) and captures only the meaningful structure needed for further processing (e.g., by a compiler for type-checking, optimization, or code generation).

Syntax tree for the given code:

              (sequence)
              /        \
         (while)      (return)
         /     \           |
     (!=)     (if)         a
     /  \    /   |   \
    b    0 (>) (then) (else)
          / \    |       |
         a   b (assign) (assign)
              /  \       /  \
             a   (-)    b   (-)
                 / \        / \
                a   b      b   a

The root sequences the while-loop followed by the return statement. The while node has a condition child (b != 0) and a body child (the if-statement). The if node has a condition (a > b), a then-branch (a = a - b), and an else-branch (b = b - a); each assignment is itself a small subtree with the '=' operator, the left-hand variable, and a '-' subtraction subtree on the right.

2023 · Paper-I · Q8(b) (6 marks)

Question

Describe your understanding on Constant Folding using a brief pseudo code.

Solution

Constant folding is a compiler optimization technique that evaluates expressions whose operands are all known constants at compile time, replacing the entire expression with its precomputed result, so that the computation does not need to be repeated every time the program runs.

// Before constant folding
x = 3 + 4 * 2;
y = x * (10 - 10);

// After constant folding (done by the compiler)
x = 11;      // 4*2=8, then 3+8=11, computed once at compile time
y = x * 0;   // 10-10 folded to 0

By performing this evaluation once during compilation instead of on every execution, constant folding reduces the number of run-time instructions, improving performance without changing the program's observable behavior; it is often combined with constant propagation, which substitutes known constant variable values into later expressions to expose further folding opportunities.

2022 · Paper-I · Q8(a) (8 marks)

Question

Draw a finite automaton over ∑ = {0, 1} that accepts all binary strings starting and ending with 0 (single-0 string counts).

Solution

We need a DFA that accepts strings whose first symbol is 0 AND whose last symbol is 0 (a single "0" satisfies both and must be accepted).

States: q0 (start, nothing read yet), qA (started with 0, currently ends in 0 - accepting), qB (started with 0, currently ends in 1 - non-accepting), qD (started with 1 - dead/trap state, can never be accepted since the first symbol was 1).

Transition table:

  • q0 --0--> qA (accept immediately: a single "0" both starts and ends with 0)
  • q0 --1--> qD
  • qA --0--> qA
  • qA --1--> qB
  • qB --0--> qA
  • qB --1--> qB
  • qD --0--> qD
  • qD --1--> qD

Start state: q0. Accepting state: {qA}. Any string is accepted if and only if it begins with 0 (reaching qA or qB, never qD) and its last transition lands on qA (i.e., the last symbol read was 0).

2022 · Paper-I · Q8(b) (6 marks)

Question

Write a regular expression over ∑ = {0, 1} to represent a set of strings that begin with 101 and end with 110.

Solution

Regular expression: 101(0|1)*110

This requires the string to start with the literal prefix "101", then allows any (possibly empty) sequence of 0s and 1s in the middle via (0|1), and requires the string to end with the literal suffix "110". The minimum-length string satisfying this is "101110" (length 6), obtained when the middle (0|1) part matches the empty string - here the prefix "101" and suffix "110" simply concatenate directly.

2022 · Paper-I · Q8(c) (6 marks)

Question

Write a Context-Free Grammar (CFG) over ∑ = {0, 1} for the language of all binary strings of the form 0^a 1^b 0^c where a+c=b.

Solution

Since b = a+c, the string 0^a 1^b 0^c can be rewritten as 0^a 1^(a+c) 0^c = (0^a 1^a)(1^c 0^c), i.e., the concatenation of a block generating equal 0s then 1s, followed by a block generating equal 1s then 0s. This gives a simple two-part grammar:

S -> X Y
X -> 0 X 1 | epsilon      (generates 0^a 1^a)
Y -> 1 Y 0 | epsilon      (generates 1^c 0^c)

Derivation check: S => XY => (0^a 1^a)(1^c 0^c) = 0^a 1^(a+c) 0^c, which is exactly 0^a 1^b 0^c with b=a+c, for any a,c >= 0. For example, with a=2, c=1 (so b=3): X derives "0011", Y derives "10", giving S => "0011" + "10" = "001110" = 0^2 1^3 0^1, matching the required pattern.

2021 · Paper-I · Q6(a) (8 marks)

Question

Convert following NFA to DFA:

Solution

Reading the NFA from the figure: states q0 (start), q1, q2 (accepting, double circle); alphabet {0,1}. Transitions: δ(q0,0)={q0}, δ(q0,1)={q1}; δ(q1,0)={q1}, δ(q1,1)={q2}; δ(q2,0)={q1,q2} (nondeterministic branch), δ(q2,1)={q1}. Applying the subset construction: Start state A = {q0}. A={q0}: on 0 → {q0}=A; on 1 → {q1}=B (new) B={q1}: on 0 → {q1}=B; on 1 → {q2}=C (new) C={q2}: on 0 → {q1,q2}=D (new); on 1 → {q1}=B D={q1,q2}: on 0 → δ(q1,0)∪δ(q2,0) = {q1}∪{q1,q2} = {q1,q2}=D; on 1 → δ(q1,1)∪δ(q2,1) = {q2}∪{q1} = {q1,q2}=D

Resulting DFA states: A={q0} (start), B={q1}, C={q2}, D={q1,q2}. Final (accepting) states: any DFA state containing q2, i.e. C and D. DFA transition table:

State01
A (start)AB
BBC
C (accepting)DB
D (accepting)DD

2021 · Paper-I · Q8(a) (4 marks)

Question

Consider the grammar S → cAd, A → a b | a, construct a top-down parse tree for the input string w = cad

Solution

Leftmost derivation: S ⇒ cAd ⇒ (choosing production A → a) ⇒ cad, which matches w = cad exactly. Top-down parse tree:

        S
      / | \
     c  A  d
        |
        a

The root S expands via S → cAd into the three children 'c', 'A', and 'd'; the non-terminal A then expands via the production A → a into the single leaf 'a'. Reading the leaves left to right gives exactly 'c a d' = w.

2021 · Paper-I · Q8(b) (4 marks)

Question

Is the above given grammar ambiguous or unambiguous? Justify your answer.

Solution

The grammar is UNAMBIGUOUS. A grammar is ambiguous only if some string it generates has two or more distinct parse trees (or leftmost derivations). Here, S has only one production (S → cAd), and A has exactly two alternative productions producing two entirely distinct, non-overlapping terminal strings: 'a' and 'ab'. For any string the grammar generates — 'cad' (via A → a) or 'cabd' (via A → ab) — there is exactly ONE way to choose which A-production applies, since the two alternatives never produce the same string. Hence every derivable string has a unique parse tree, and the grammar is unambiguous.

2021 · Paper-I · Q8(c) (4 marks)

Question

Write similarities and differences of CFG and regular expression.

Solution

Similarities: both are formal notations used to define/specify formal languages; every regular language expressible by a regular expression can ALSO be expressed by a context-free grammar (regular languages are a proper subset of context-free languages); both are used together in compiler construction — regular expressions for lexical analysis (tokenizing) and CFGs for syntax analysis (parsing). Differences: a regular expression can only describe REGULAR languages, recognisable by a finite automaton with no auxiliary memory, and cannot express nested or recursively-balanced structures (e.g. matched parentheses, palindromes). A context-free grammar can describe the strictly LARGER class of context-free languages, recognisable by a pushdown automaton equipped with a stack, and CAN express nested/recursive structures. Structurally, regular expressions are built from terminals using operators (concatenation, union '|', Kleene star '*'), whereas CFGs use recursive production rules over non-terminal and terminal symbols.

2021 · Paper-I · Q8(d) (4 marks)

Question

Design grammar for the following language: "The set of all strings of 0s and 1s such that every 0 is immediately followed by at least one 1".

Solution

Grammar (start symbol S):

S → 1S | 01S | ε

Reasoning: the empty string vacuously satisfies the condition (no 0 exists to violate it), so S → ε is allowed. A standalone '1' can always be generated (S → 1S) since 1s impose no constraint. Crucially, every '0' can ONLY be generated together with a '1' immediately after it, via S → 01S — there is no production that produces a lone '0' or a '0' at the very end of the string, so '00' and a trailing '0' are both structurally impossible to derive. Example derivations: S ⇒ 01S ⇒ 011S ⇒ 011 (via S→1S then ε) generates '011'; S ⇒ 1S ⇒ 101S ⇒ 1011 generates '1011' — both satisfy the condition that every 0 is immediately followed by a 1.

2020 · Paper-I · Q7(b) (5 marks)

Question

Create State Transition Table from the following graph

Solution

Reading the transitions shown in the figure (states q0-q5): δ(q0,a)=q1, δ(q0,b)=q1; δ(q1,a)=q2, δ(q1,b)=q3; δ(q2,a)=q4, δ(q2,b)=q4; δ(q3,a)=q2, δ(q3,b)=q4; δ(q4,a)=q5, δ(q4,b)=q5; δ(q5,a)=q5, δ(q5,b)=q5 (self-loop). State transition table:

Stateab
q0q1q1
q1q2q3
q2q4q4
q3q2q4
q4q5q5
q5q5q5

2020 · Paper-I · Q7(c) (4 marks)

Question

Draw Finite State Automata which accepts following input. i. JIM ii. JMI iii. JJIIM iv. JJMMII

Solution

Since this is a specific FIXED finite set of four strings (not a general repeating pattern), it is automatically a regular language (every finite language is regular) and can be accepted by a simple 'trie-shaped' DFA: a distinct path of states from the start state q0 spells out each string, sharing common prefixes, with a unique accepting state at the end of each string's path, and an implicit dead/trap state for any other symbol/continuation:

q0 --J--> q1
q1 --I--> q2 --M--> [F1] (accepts JIM)
q1 --M--> q3 --I--> [F2] (accepts JMI)
q1 --J--> q4 --I--> q5 --I--> q6 --M--> [F3] (accepts JJIIM)
q4 --M--> q7 --M--> q8 --I--> q9 --I--> [F4] (accepts JJMMII)

Every other input symbol from any state goes to a non-accepting dead state. This trie automaton accepts exactly the four given strings and nothing else.

2020 · Paper-I · Q7(d) (6 marks)

Question

Determine which of these inputs are valid for the FSM shown below: i. aaaaa ii. ababa iii. abcabc iv. abccba v. acbcd vi. acbcdcd

Solution

Reading the transitions shown in the figure (states S1 start, S2, S3, S4; alphabet {a,b,c}; self-loop 'a' on S2): δ(S1,a)=S2, δ(S1,b)=S3, δ(S2,a)=S2 (self-loop), δ(S2,b)=S4, δ(S3,a)=S1, δ(S3,c)=S4, δ(S4,c)=S2. (S4 assumed to be the accepting state.) i. aaaaa: S1-a->S2-a->S2-a->S2-a->S2-a->S2 → ends at S2 (not accepting) → INVALID. ii. ababa: S1-a->S2-b->S4-a-> undefined (S4 has no transition on 'a') → dead → INVALID. iii. abcabc: S1-a->S2-b->S4-c->S2-a->S2-b->S4-c->S2 → ends at S2 → INVALID. iv. abccba: S1-a->S2-b->S4-c->S2-c-> undefined (S2 has no transition on 'c') → dead → INVALID. v. acbcd: contains 'd', which is not in the machine's input alphabet {a,b,c} → INVALID. vi. acbcdcd: also contains 'd' → INVALID. (Answer given based on the transition structure read from the figure; the key general technique is to trace each input symbol-by-symbol from the start state and check whether it ends in an accepting state without ever hitting an undefined transition or an out-of-alphabet symbol.)

2019 · Paper-I · Q8(a) (10 marks)

Question

Write down the major steps involved in code generation.

Solution

Code generation is the final phase of a compiler, converting the optimized intermediate representation (IR) into target machine/assembly code. Major steps:

  1. Input acquisition — take the intermediate code (e.g. three-address code) and the symbol table (with type and address information) as input.
  2. Instruction selection — choose appropriate target-machine instructions to implement each IR operation, often using tree/DAG pattern matching against available instruction templates.
  3. Register allocation and assignment — decide which values are kept in the limited set of physical registers versus spilled to memory, and assign specific registers to variables/temporaries.
  4. Instruction ordering/scheduling — sequence the chosen instructions to respect data dependencies while exploiting pipeline parallelism and minimizing stalls.
  5. Address assignment — allocate storage locations (stack offsets, static addresses) for variables and temporaries not held in registers.
  6. Peephole optimization — a final local pass that scans short instruction sequences and replaces them with more efficient equivalents (removing redundant loads/stores, strength reduction, etc.).
  7. Target code emission — output the final assembly or machine code.

2019 · Paper-I · Q8(b) (5 marks)

Question

How would you optimize a loop? Describe the techniques briefly.

Solution

Common loop-optimization techniques:

  • Code motion (loop-invariant code motion) — move computations whose result does not change across iterations to just before the loop, so they execute once instead of every iteration.
  • Strength reduction — replace expensive operations with cheaper equivalents inside the loop, e.g. replacing i*4 with repeated addition, or multiplication with shifts.
  • Induction-variable elimination — remove redundant variables that merely track the loop counter in a derived way, expressing them in terms of the primary counter or eliminating them entirely.
  • Loop unrolling — replicate the loop body multiple times per iteration to reduce branch/counter overhead and expose more instruction-level parallelism.
  • Loop fusion/jamming — merge adjacent loops with the same iteration range into a single loop to reduce loop-control overhead and improve cache locality.
  • Loop-invariant boundary/condition simplification — hoist parts of the loop test that do not change.

2019 · Paper-I · Q8(c) (5 marks)

Question

Differentiate machine-dependent optimization and machine-independent optimization.

Solution

Machine-independent optimization works on the intermediate representation and improves the code without any knowledge of the target machine's architecture — it would give the same benefit regardless of which CPU the code eventually runs on. Examples: constant folding, dead-code elimination, common sub-expression elimination, and loop optimizations such as code motion. Machine-dependent optimization requires knowledge of the target machine's specific architecture — its register set, addressing modes, and instruction set — and is applied during/after code generation. Examples: register allocation/assignment, instruction selection tuned to the CPU's instruction set, and peephole optimization exploiting machine-specific instruction idioms. In short: machine-independent optimizations are portable and applied earlier (on IR); machine-dependent optimizations are architecture-specific and applied later (on/near the generated target code).

2018 · Paper-I · Q8(a) (5 marks)

Question

What is the difference between lexers and parsers?

Solution

A Lexer (Lexical Analyzer / Scanner) is the first phase of a compiler; it reads the raw source code character-by-character and groups characters into meaningful 'tokens' (keywords, identifiers, literals, operators, punctuation) based on the language's lexical rules, which are typically specified using regular expressions and implemented internally via finite automata (DFAs). It discards irrelevant content like whitespace and comments, and can detect lexical errors (e.g. an invalid character or malformed token).

A Parser (Syntax Analyzer) is the second phase; it takes the stream of tokens produced by the lexer and checks whether they form a syntactically valid program according to the language's Context-Free Grammar, building a parse tree or Abstract Syntax Tree (AST) representing the program's grammatical structure. It detects syntax errors (e.g. a missing semicolon, mismatched parentheses, invalid statement structure).

Key difference: the lexer operates on individual characters to produce tokens (a 'flat'/linear recognition task, handled by finite automata / regular languages), whereas the parser operates on the sequence of tokens to verify and structure the overall grammatical relationship between them (a 'hierarchical' recognition task, requiring the greater expressive power of context-free grammars and pushdown automata, since regular languages/finite automata cannot handle arbitrarily nested structures like matched parentheses).

2018 · Paper-I · Q8(b) (5 marks)

Question

Write a grammar (BNF) for the language of palindromes.

Solution

For palindromes over the alphabet {a, b} (strings that read the same forwards and backwards), a context-free grammar in BNF:

::= 'a' 'a' | 'b' 'b' | 'a' | 'b' | '' (empty string)

Explanation: the grammar builds a palindrome outward from its center. The base cases are the empty string (even-length center) and a single character 'a' or 'b' (odd-length center). The recursive rules wrap a matching character on BOTH the left and right sides of an already-valid (shorter) palindrome, guaranteeing the result reads identically forwards and backwards.

Example derivations: 'aba' via -> aa -> a(b)a = 'aba'. 'abba' via -> aa -> a(b)a... actually for 'abba': -> aa -> a(bb)a, using the empty-string base case for the inner , giving a(b()b)a = 'abba'. This grammar is not regular (cannot be expressed by a finite automaton) because it requires matching an unbounded number of characters on the outside with their mirror on the inside - it requires the greater power of a context-free grammar (recognized by a pushdown automaton with a stack).

2018 · Paper-I · Q8(c) (5 marks)

Question

Here DFA is given for the language L find the DFA for L^2 (squared/concatenated with itself). [DFA: start q0 (self-loop on 'a'), q0 --b--> q1 (final, double circle), q1 --a,b--> q2 (trap), q2 self-loops on a,b]

Solution

First, identify L: from the given DFA (q0 start, self-loop on 'a'; q0 --b--> q1 which is the sole accepting state; from q1, any symbol a or b goes to trap state q2; q2 self-loops on a,b forever, non-accepting), the accepted language is L = { a^n b : n >= 0 } - i.e., zero or more 'a's followed by exactly one 'b', and nothing else (any character after that single 'b' sends the automaton into the non-accepting trap state).

L^2 = L concatenated with L = { a^n b a^m b : n, m >= 0 } - strings consisting of some a's, a b, then more a's, then a final b, with nothing else allowed (exactly two b's total).

DFA for L^2 (concatenation automaton - essentially two copies of the original DFA chained together): States: r0 (start), r1 (intermediate, after first 'b'), r2 (final/accepting, after second 'b'), trap (dead state).

Transitions:

  • r0 --a--> r0 (self-loop, consuming leading a's)
  • r0 --b--> r1 (first 'b' seen)
  • r1 --a--> r1 (self-loop, consuming a's between the two b's)
  • r1 --b--> r2 (second 'b' seen - ACCEPT)
  • r2 --a--> trap
  • r2 --b--> trap
  • trap --a,b--> trap (dead state, non-accepting)

Only r2 is a final/accepting state. This DFA accepts exactly strings of the form a^n b a^m b, matching L^2.

2018 · Paper-I · Q8(d) (5 marks)

Question

Convert the following DFA to a RE: [states 1 (start) through 5 (final), forward edges labelled 3 advancing one state at a time (1-2-3-4-5), and additional edges labelled 6 skipping ahead one extra state (1-3, 2-4, 3-5)]

Solution

Note: the transition diagram in the original paper uses curved/overlapping arcs that are difficult to reproduce exactly from the scanned text; the derivation below uses the most natural reading of the figure - symbol '3' advances the state machine forward by exactly one position (1->2->3->4->5) and symbol '6' advances it forward by exactly two positions (1->3, 2->4, 3->5), with state 1 as the start state and state 5 as the only accepting (final) state, and no edges going backward or looping.

Since this is a simple forward-only DAG (no cycles), applying state elimination (Arden's method) reduces to directly enumerating every path from state 1 to state 5, where a '3'-edge contributes a 'weight' of 1 step and a '6'-edge contributes a weight of 2 steps, and any valid path's step-weights must sum to exactly 4 (the total distance from state 1 to state 5).

Enumerating all sequences of steps (each step being '3', weight 1, or '6', weight 2) that sum to 4:

  • 1+1+1+1 -> the string '3333'
  • 1+1+2 (in the three possible orders) -> '3336', '3363', '3633'
  • 2+2 -> the string '66'

So the resulting regular expression is:

RE = 3333 + 3336 + 3363 + 3633 + 66

This captures every distinct path (sequence of transition labels) that starts at state 1 and ends at the accepting state 5, which is exactly what state elimination on this acyclic diagram would also produce, since with no cycles present, the general state-elimination/Arden's-lemma procedure reduces to plain enumeration of all source-to-sink paths.

2017 · Paper-I · Q3(a) (8 marks)

Question

Three types of languages exist for use in programming of computers, Machine, Low Level and High Level languages. Elucidate on these three types, giving details of the conversion process between Low Level and High Level language into Machine language.

Solution

Machine Language: the lowest-level language, consisting of raw binary opcodes (0s and 1s) directly understood and executed by the CPU; it is specific to a particular processor architecture and extremely tedious/error-prone for humans to write.

Low-Level Language (Assembly Language): uses short mnemonics (e.g. MOV, ADD, JMP) that map almost one-to-one to machine instructions, giving fine control over hardware but still being architecture-specific and harder to write than high-level code.

High-Level Language (e.g. C++, Java, Python): uses English-like syntax and abstracts away hardware details (registers, memory addresses), making programs portable, easier to write, read, and maintain, at some cost of direct hardware control.

Conversion process:

  • Assembly to Machine code: an Assembler translates assembly mnemonics directly into machine code, essentially a one-to-one/simple mapping, producing object code.
  • High-Level to Machine code: a Compiler performs several phases - lexical analysis (tokenizing), syntax analysis (parsing into a parse tree per the language's grammar), semantic analysis (type-checking), intermediate code generation, code optimization, and finally target code generation (assembly or machine code), which is then assembled and linked into an executable. Alternatively, an Interpreter directly executes the high-level source (or an intermediate bytecode) statement by statement without producing a separate machine-code file.

2017 · Paper-I · Q7(a) (8 marks)

Question

The handling of syntax errors involves the use of parser and the lexical analyzer. Comment on its functioning.

Solution

The Lexical Analyzer (Scanner) reads the source program character-by-character and groups them into tokens (keywords, identifiers, operators, literals) based on the language's lexical rules (regular expressions/finite automata). It can detect lexical errors, such as illegal characters or malformed tokens (e.g. an unterminated string literal), and typically reports them and attempts simple recovery (e.g. skipping the bad character) so scanning can continue.

The Parser (Syntax Analyzer) takes the token stream from the lexer and checks it against the language's context-free grammar, building a parse tree/AST. When a sequence of tokens does not conform to any valid grammar production, a syntax error is detected (e.g. a missing semicolon, unbalanced parentheses, misplaced keyword).

Error-handling/recovery strategies used by parsers:

  • Panic mode: the parser discards tokens one at a time until a token from a predefined synchronizing set (e.g. ';', '}') is found, then resumes parsing - simple but may skip other real errors.
  • Phrase-level recovery: the parser performs local correction (inserting/deleting/replacing a token) at the point of error to continue parsing.
  • Error productions: the grammar is augmented with rules that explicitly anticipate common errors.
  • Global correction: computes the minimal sequence of edits needed to transform the erroneous input into a valid program (theoretically ideal but computationally expensive, rarely used in practice).

Together, the lexer and parser cooperate so that a single glitch does not halt compilation - both aim to detect as many genuine errors as possible in one pass while avoiding cascading false errors.

2017 · Paper-I · Q7(b) (6 marks)

Question

Using a suitable example, compare the operation of a top-down and a bottom-up Parser based compiler.

Solution

Top-down Parsing: begins construction of the parse tree from the root (start symbol) and works down toward the leaves (input tokens), trying to derive the input string by repeatedly expanding non-terminals using the grammar's productions, guessing/predicting which production to apply next (e.g. Recursive-Descent parsers, LL parsers). It matches the leftmost derivation of the grammar.

Bottom-up Parsing: begins from the input tokens (leaves) and works upward, repeatedly identifying substrings matching the right-hand-side of a production and reducing them to the corresponding non-terminal, until the whole input reduces to the start symbol (e.g. Shift-Reduce parsers, LR parsers). It matches the rightmost derivation in reverse.

Example with grammar E -> E + T | T, T -> id, for input 'id + id':

  • Top-down: start with E, expand to E + T, expand E again to T + T, then T -> id gives 'id + T', then T -> id gives 'id + id' - matching the input by predicting expansions from the start symbol downward.
  • Bottom-up: start with tokens 'id + id'; reduce first 'id' to T (T->id), then to E (E->T); shift '+'; reduce second 'id' to T; finally reduce 'E + T' to E - building up from the leaves to the root.

Top-down parsers (LL) are simpler to hand-write but cannot handle left-recursive grammars directly; bottom-up parsers (LR) are more powerful (handle a larger class of grammars, including left-recursion) but are more complex to construct, typically via parser-generator tools (e.g. YACC/Bison).

2017 · Paper-I · Q7(c) (6 marks)

Question

Explain the two different methods of code optimization that is Loop optimization and Peephole optimization by giving a suitable example.

Solution

Loop Optimization: since loops are executed repeatedly, optimizing them yields the greatest overall performance benefit. Common techniques:

  • Code motion (loop-invariant code motion): move computations that don't change across iterations outside the loop. Example: for(i=0;i<n;i++){ x = y+1; a[i]=xi; } --> x=y+1; for(i=0;i<n;i++){ a[i]=xi; } Here 'x=y+1' is invariant and computed only once instead of n times.
  • Strength reduction: replace an expensive operation with a cheaper equivalent one, e.g. replacing i*4 (multiplication) inside a loop with repeated addition of 4 (an accumulator), since addition is cheaper than multiplication.
  • Induction variable elimination: remove redundant loop-counter-derived variables.

Peephole Optimization: examines a small, sliding 'window' (peephole) of a few consecutive generated instructions at a time and replaces them with a shorter/faster equivalent sequence, applied directly to the generated (often target/assembly) code. Example: MOV R1, a MOV a, R1 The second instruction is redundant (storing a value right back to where it came from) and can be eliminated by the peephole optimizer. Another example: replacing 'x = x + 0;' or 'x = x * 1;' with nothing (removing no-op arithmetic), or combining two consecutive jumps into one.

Loop optimization targets algorithmic-level redundancy across iterations at a higher (often intermediate-code) level, while peephole optimization targets small, local, redundant instruction sequences at the final code-generation level.

2017 · Paper-I · Q8(e) (5 marks)

Question

Write short notes on any FOUR of the following (5 each): (e) Intermediate Code Generation

Solution

Intermediate Code Generation is a phase of compilation that occurs after semantic analysis and before final target code generation. The compiler translates the syntax tree/parse tree into an intermediate representation (IR) that is independent of both the source high-level language and the target machine.

Purpose:

  • Portability: the same front-end (lexer, parser, semantic analyzer) can target multiple machine architectures by writing different back-ends that consume the same IR, and the same back-end can support multiple source languages.
  • Optimization: many optimizations (constant folding, common sub-expression elimination, loop optimizations) are easier to perform on a simple, uniform IR than directly on the parse tree or final machine code.

Common IR forms:

  • Three-Address Code (TAC): each statement has at most one operator on the right and involves at most three addresses/operands, e.g. t1 = b * c; t2 = a + t1; for the expression a + b*c.
  • Postfix (Reverse Polish) notation: e.g. a b c * +.
  • Syntax trees / DAGs (Directed Acyclic Graphs): tree/graph representation that can also expose common sub-expressions for reuse.

After intermediate code is generated (and optionally optimized), the code generator translates it into the final target machine/assembly code.

2016 · Paper-I · Q7(a) (5 marks)

Question

Draw a diagram that illustrates the process of translating a C++ source file into an executable file. Give example of each phase depicted in your diagram of compilation process.

Solution

Compilation pipeline (source to executable):

Source Code (main.cpp) | Preprocessor (expands #include , #define macros, conditional compilation) v Expanded Source Code (main.i) | Compiler proper (lexical analysis -> syntax analysis -> semantic analysis -> code generation) v Assembly Code (main.s) | Assembler (translates mnemonics like MOV, ADD into machine opcodes) v Object Code (main.o / main.obj) -- relocatable machine code, unresolved external references | Linker (combines object files with library code, e.g. iostream library object code; resolves external symbols like cout, resolves addresses) v Executable File (main.exe / a.out) | Loader (loads the executable into main memory and starts execution) v Program Execution

Example: #include <iostream> is resolved by the preprocessor; cout << x; is parsed/type-checked by the compiler; cout calls become CALL instructions resolved by the linker against the C++ standard library.

2016 · Paper-I · Q7(b) (5 marks)

Question

Compare and contrast among compiler, interpreter and assembler.

Solution

Compiler: translates an entire high-level-language source program into machine code (or object code) in one pass before execution; produces a standalone executable; execution is fast since translation happens only once, but the whole program must compile before any part runs and errors are reported after full translation. Example: g++ for C++.

Interpreter: translates and executes a high-level program statement-by-statement at run time, without producing a separate executable; execution is generally slower (translation overhead repeats every run/every loop iteration) but allows immediate feedback and easier debugging, and one erroneous statement doesn't block execution of statements before it. Example: Python interpreter.

Assembler: translates low-level assembly language (mnemonics like MOV, ADD that map almost one-to-one to machine instructions) into machine code/object code; it does not need to understand high-level constructs like loops or classes.

Key contrast: a compiler and interpreter both process high-level languages but differ in when/how translation happens (ahead-of-time vs on-the-fly); an assembler processes a fundamentally lower-level language and is used mainly as the back end that a compiler's generated assembly passes through.

2016 · Paper-I · Q8(b) (5 marks)

Question

Explain five properties of language using the example of English. Explain why a software language like MiniJava meets these properties as well.

Solution

Five general properties any language (natural or programming) exhibits:

  1. Syntax - a set of rules governing how valid sentences/statements are structured. English: subject-verb-object order; MiniJava: statements must follow its grammar, e.g. if (cond) { ... }.
  2. Semantics - the meaning conveyed by syntactically valid constructs. English: 'The cat sat' conveys an action; MiniJava: x = x + 1; means increment x's value.
  3. Vocabulary/Lexicon - a finite (or generative) set of basic tokens/words the language is built from. English: dictionary words; MiniJava: keywords, identifiers, literals, operators.
  4. Compositionality - larger valid expressions are built by combining smaller valid ones according to rules. English: clauses combine into sentences; MiniJava: expressions combine into statements, statements into methods.
  5. Ambiguity/context-sensitivity - natural languages can be ambiguous depending on context; well-designed programming languages minimize this through strict formal grammar (though certain constructs like the 'dangling else' still need explicit disambiguation rules).

MiniJava, being a language with a formally defined grammar (BNF), lexicon (tokens), and precise semantics for each construct, satisfies all these properties just as English does, but with much stricter, unambiguous syntax/semantics so it can be mechanically parsed and compiled.

2016 · Paper-I · Q8(c) (5 marks)

Question

Lexical analysis: Consider the following regular expression r1 = (A | .... | Z) * (0 | .... | 9)*. Describe the language defined by r1 in English. Turn r1 into an equivalent finite automaton. Remove e-moves from the finite automation.

Solution

Language: r1 = (A|...|Z)(0|...|9) describes all strings consisting of zero or more uppercase letters (A-Z) followed by zero or more digits (0-9) - e.g. '', 'ABC', '123', 'AB12', 'Z9' are all valid; a digit may never appear before a letter.

NFA with epsilon-moves (typical Thompson construction, using two loop-states joined by an epsilon transition): Start state q0 (accepting, for the empty string):

  • q0 --A|...|Z--> q0 (self-loop consuming letters)
  • q0 --epsilon--> q1
  • q1 (accepting) --0|...|9--> q1 (self-loop consuming digits)

Removing the epsilon-move (epsilon-closure elimination): since eps(q0) = {q0,q1}, we merge the transitions of q1 into q0's transition table directly, and make q0 the sole accepting state carrying both loops: Resulting equivalent NFA/DFA without epsilon moves - single state q0 (start, accepting):

  • q0 --A|...|Z--> q0
  • q0 --0|...|9--> q0

This single-state automaton (a DFA) accepts exactly the language of letters-then-digits strings, since once a digit is seen the letter transitions are simply never used again by any valid string of the language, and self-looping on the same state correctly enforces 'letters can appear anywhere but digits can only follow, never precede, in this collapsed form is only valid because both symbol sets loop on the same state' - equivalently kept as two states q0->q1 (both accepting) with q0 looping on letters, q0 transitioning to q1 on a digit, and q1 looping on digits, is the safer minimal-change epsilon-free version of the original NFA.

2016 · Paper-I · Q8(d) (5 marks)

Question

What do you mean by Context Free Grammar (CFG)? Illustrate your answer with examples.

Solution

A Context-Free Grammar (CFG) is a formal grammar G = (V, T, P, S) where V is a finite set of non-terminal symbols, T is a finite set of terminal symbols, P is a finite set of production rules of the form A -> alpha (where A is a single non-terminal and alpha is any string of terminals/non-terminals - the replacement of A does not depend on surrounding context, hence 'context-free'), and S is the start symbol. CFGs are used to define the syntax of programming languages and are recognized by pushdown automata.

Example 1 - balanced parentheses: S -> ( S ) S | epsilon This generates strings like '()', '(())', '()()' - always properly nested/balanced.

Example 2 - simple arithmetic expressions: E -> E + T | T T -> T * F | F F -> ( E ) | id This generates expressions such as 'id + id * id' and correctly encodes operator precedence (multiplication binds tighter than addition) through the grammar's structure.

CFGs are the backbone of parser generation in compiler construction (e.g. LL and LR parsers), since a compiler's syntax analysis phase checks whether the token stream can be derived from the language's CFG.

Part B — MCQs

2026 · Paper-I · Q15 (MCQ)

A compiler needs to recognize tokens. Which phase does this?

  • A. Syntax Analysis
  • B. Lexical Analysis
  • C. Code Generation
  • D. None of these

Answer: B

Explanation: Lexical analysis (scanning) is the first compiler phase and is responsible for reading the source code character by character and grouping it into tokens.

2026 · Paper-I · Q16 (MCQ)

What is the advantage of using LL(1) grammars in the Syntax Analysis?

  • A. More complex parsing
  • B. Predictive parsing with less complexity
  • C. No need for grammar rules
  • D. None of these

Answer: B

Explanation: LL(1) grammars allow a predictive (top-down) parser to decide which production to apply by looking at only one lookahead token, avoiding backtracking and keeping parsing simple and efficient.

2026 · Paper-I · Q17 (MCQ)

What is the difference between Top-down and Bottom-up parsers?

  • A. Top-down is always faster
  • B. Bottom-up handles more grammars
  • C. Top-down starts from start symbol
  • D. None of these

Answer: C

Explanation: A top-down parser starts from the grammar's start symbol and tries to derive the input string by expanding productions, whereas a bottom-up parser starts from the input string and reduces it step by step up to the start symbol.

2026 · Paper-I · Q18 (MCQ)

What do compilers use for recognizing tokens?

  • A. Regular expressions
  • B. Context-free grammars
  • C. Machine code
  • D. None of these

Answer: A

Explanation: Token patterns (identifiers, numbers, keywords, operators) are specified using regular expressions, which the lexical analyzer implements (often as a DFA) to recognize tokens; context-free grammars are instead used for the syntax analysis phase.

2025 · Paper-I · Q13 (MCQ)

What is the role of parser?

  • A. To check logical errors
  • B. To find syntax errors
  • C. To identify run-time errors
  • D. None of these

Answer: B

Explanation: The parser performs syntax analysis, checking that the token stream conforms to the language's grammar and reporting syntax errors; logical and run-time errors are outside its scope.

2025 · Paper-I · Q14 (MCQ)

Which optimization method involves minimizing the memory access count in a program?

  • A. Constant folding
  • B. Register allocation
  • C. Instruction scheduling
  • D. None of these

Answer: B

Explanation: Register allocation keeps frequently-used variables in fast CPU registers instead of memory, directly reducing the number of memory accesses.

2025 · Paper-I · Q20 (MCQ)

Which phase of compiler is responsible for abstract syntax tree (AST) generation?

  • A. Syntax analysis
  • B. Semantic analysis
  • C. Lexical analysis
  • D. None of these

Answer: A

Explanation: The syntax analysis (parsing) phase builds the abstract syntax tree from the token stream according to the grammar; semantic analysis later annotates/checks that tree.

2024 · Paper-I · Q13 (MCQ)

When compiled, which of the following class of statement often yields no executable code?

  • A. Assignment statement
  • B. Structural statements
  • C. Input and output statements
  • D. None of these

Answer: B

Explanation: Structural/declarative statements (such as class or data-type declarations) describe program structure to the compiler and typically generate no executable machine code by themselves, unlike assignment or I/O statements which produce actual runtime instructions.

2024 · Paper-I · Q14 (MCQ)

A high-level language compiler that runs on one computer and generates code for another is known as:

  • A. One pass compiler
  • B. Multipass compiler
  • C. Cross compiler
  • D. None of these

Answer: C

Explanation: A cross compiler runs on one host platform/architecture but produces executable code targeted for a different target platform/architecture.

2024 · Paper-I · Q15 (MCQ)

Compiler can check ____ error.

  • A. Syntax
  • B. Content
  • C. Logical
  • D. None of these

Answer: A

Explanation: A compiler statically analyzes source code against the language's grammar, so it can detect syntax errors; logical errors (incorrect program behavior despite correct syntax) cannot be detected by the compiler.