Compiler design connects theory of computation with practical programming-language implementation. PSC questions often ask compiler phases, tokenization, lexical analyzer, parser, parse tree, syntax errors and syntax-directed translation.

Engineering Definitions

Compiler

Standard definition: A program that translates source code from a high-level language into target code.

Exam meaning: High-level source program लाई target/machine/intermediate code मा translate गर्ने program।

Lexical analysis

Standard definition: Compiler phase that converts character stream into tokens.

Exam meaning: Characters लाई identifiers, keywords, operators जस्ता tokens मा बदल्ने phase।

Parsing

Standard definition: Syntax analysis phase that checks token sequence against grammar.

Exam meaning: Token sequence grammar अनुसार valid छ कि छैन जाँच्ने phase।

Syntax-directed translation

Standard definition: A translation method that attaches semantic actions/attributes to grammar productions.

Exam meaning: Grammar productions सँग semantic actions जोडेर translation गर्ने method।

Concept Teaching

A compiler is a pipeline. Lexical analysis handles words/tokens, parsing handles grammar structure, semantic analysis handles meaning, intermediate code abstracts target machine, optimization improves code and code generation emits target instructions.

Compiler Phases

Know phase input and output.

Phase Input Output
Lexical analysis Characters Tokens
Syntax analysis Tokens Parse tree/AST
Semantic analysis AST Annotated AST/symbol table checks
Intermediate code generation Annotated AST IR
Optimization IR Improved IR
Code generation IR Target code

Lexical Analysis

Scanner groups characters into tokens.

  • Removes whitespace/comments where irrelevant.
  • Recognizes keywords, identifiers, literals and operators.
  • Uses regular expressions and finite automata.
  • Stores identifiers in symbol table.
  • Reports lexical errors such as invalid character sequence.

Parsing

Parser checks grammatical structure.

  • Top-down parsing builds tree from start symbol.
  • Bottom-up parsing reduces input to start symbol.
  • LL parsers scan left to right and derive leftmost derivation.
  • LR parsers scan left to right and construct rightmost derivation in reverse.
  • Ambiguous grammar causes multiple parse trees.
  • Error recovery lets compiler continue after syntax error.

Syntax-Directed Translation

Attributes carry semantic information.

  • Synthesized attribute computed from children.
  • Inherited attribute passed from parent/siblings.
  • Semantic action can build AST or generate code.
  • Type and value attributes help expression translation.
  • SDT bridges syntax and semantic processing.

Engineering Mechanism

  • Read source program.
  • Scanner emits tokens.
  • Parser builds parse tree/AST.
  • Semantic analysis checks declarations/types/scopes.
  • Syntax-directed actions compute attributes or generate IR.
  • Later phases optimize and generate code.

Diagrams / Models To Draw

  • Draw compiler phase pipeline.
  • Draw token stream from sample assignment.
  • Draw parse tree for expression.
  • Draw syntax-directed annotated tree.
  • Draw symbol table entries.

Formulas, Algorithms and Rules

  • Token = token-name + optional attribute value.
  • Regular expressions specify token patterns.
  • FIRST/FOLLOW sets guide predictive parsing.
  • LL(1) parsing uses one lookahead token.
  • Left recursion must be removed for many top-down parsers.
Concept Role Exam trap
Scanner Token generation Not full syntax checking
Parser Grammar checking Works on tokens
Symbol table Stores names/attributes Used by multiple phases
Parse tree Concrete grammar derivation Different from AST
AST Simplified structure Better for semantic/codegen
SDT Grammar + actions Attributes matter

Exam Point

  • Lexical analysis uses regular expressions/finite automata.
  • Parsing uses context-free grammar.
  • Compiler phases are high-yield order question.
  • Ambiguous grammar has multiple parse trees.
  • Synthesized vs inherited attributes are common MCQs.

Worked Example

For `sum = a + 5`, lexical analyzer emits ID(sum), ASSIGN, ID(a), PLUS, NUM(5). Parser checks assignment grammar and builds an AST with assignment node and plus expression child.

Subjective Answer Pattern

  • Define compiler.
  • List phases in order.
  • Explain lexical analysis and token.
  • Explain parsing and parse tree.
  • Discuss SDT and attributes.
  • Conclude with error handling/symbol table.

Common Engineering Mistakes

  • Saying lexer checks full grammar.
  • Confusing token and lexeme.
  • Ignoring symbol table.
  • Mixing parse tree and syntax tree.
  • Forgetting semantic analysis after parsing.

MCQ Revision

  • Which phase outputs tokens?
  • Which grammar type is used in parsing?
  • What is lexeme?
  • What is symbol table?
  • What is synthesized attribute?
  • What does LL(1) mean?

Final Summary

  • Compiler translates source through multiple phases.
  • Lexical analysis creates tokens.
  • Parsing validates grammatical structure.
  • SDT attaches meaning/actions to grammar.
  • Symbol table and error handling support many phases.