PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q6(a)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing

Question

List down the different phases of compiler design. Explain how tokens are generated by lexical analyzer for the following instructions:

Input InstructionsC
#include<stdio.h>
int func(int a, int b)
{
if(a>b)
return a,
else
return b,
}

Solution

Phases of Compiler Design: The standard phases of a compiler pipeline are:

  1. Lexical Analysis (Scanner): Converts source character stream into tokens.
  2. Syntax Analysis (Parser): Verifies tokens against context-free grammar to generate a parse/syntax tree.
  3. Semantic Analysis: Type-checking, scope verification, and semantic consistency.
  4. Intermediate Code Generation (ICG): Generates machine-independent intermediate code (e.g., Three-Address Code / Quadruples).
  5. Code Optimization: Transforms intermediate code to improve speed and reduce resource utilization.
  6. Target Code Generation: Generates machine code / assembly for the target architecture.

(Symbol Table Management and Error Handling operate across all phases).

Token Generation for the Given Code Block: The lexical analyzer scans the text using maximal munch and discards whitespace and newlines:

  1. #include<stdio.h>: Handled as preprocessor directive tokens: ⟨PREPROCESSOR, "#include"⟩, ⟨HEADER, "<stdio.h>"⟩.
  2. int func(int a, int b):
    • int ⟨KEYWORD, "int"⟩
    • func ⟨IDENTIFIER, "func"⟩
    • ( ⟨DELIMITER, "("⟩
    • int ⟨KEYWORD, "int"⟩
    • a ⟨IDENTIFIER, "a"⟩
    • , ⟨SEPARATOR, ","⟩
    • int ⟨KEYWORD, "int"⟩
    • b ⟨IDENTIFIER, "b"⟩
    • ) ⟨DELIMITER, ")"⟩
  3. { ⟨DELIMITER, "{"⟩
  4. if(a>b):
    • if ⟨KEYWORD, "if"⟩
    • ( ⟨DELIMITER, "("⟩
    • a ⟨IDENTIFIER, "a"⟩
    • > ⟨RELOP, ">"⟩
    • b ⟨IDENTIFIER, "b"⟩
    • ) ⟨DELIMITER, ")"⟩
  5. return a,:
    • return ⟨KEYWORD, "return"⟩
    • a ⟨IDENTIFIER, "a"⟩
    • , ⟨PUNCTUATION, ","⟩
  6. else ⟨KEYWORD, "else"⟩
  7. return b,:
    • return ⟨KEYWORD, "return"⟩
    • b ⟨IDENTIFIER, "b"⟩
    • , ⟨PUNCTUATION, ","⟩
  8. } ⟨DELIMITER, "}"⟩
Answer:

The 6 compiler phases are Lexical, Syntax, Semantic, ICG, Optimization, and Code Generation. The scanner categorizes characters into tokens: keywords (int, if, return, else), identifiers (func, a, b), relational operator (>), and delimiters/punctuation ((, ), {, }, ,).

All past exam questions for Theory of Computation