Topic outline

  • CSE331-Compiler Design


    Compiler Design


    WELCOME NOTE

        

    Dear Students, 

    Welcome to the Fall 2022 Semester!

    Welcome to the course CSE331 (Compiler Design)!! . I am looking forward to the opportunity so we will have to learn and grow together in this course.  I always believe that your success is most important to me as a teacher.  Please don’t hesitate to contact me in case of having difficulties with the course materials and any other academic problems. To smooth this operation, general questions related to the courses should be posted on the Discussion Forum. Success in an online class requires just as much work and effort as success in a traditional classroom. Lastly, I am expecting much cooperation from all of you. Hope we will enjoy this journey joyfully.

    Stay safe and healthy. Thanks to all of you for joining this course.


    INSTRUCTOR


    Image

    Md. Sajib Hossain

    Lecturer
    Department of CSE
    Daffodil International University

    Email: sajib.cse0388.c@diu.edu.bd
    Mobile: (+88) 01711306945
    Room: 739, AB-4


    INSTRUCTION/GUIDELINE FOR THE COURSE
      • All the students registered for this course have to enroll in BLC
      • Students can find all the course materials from BLC.
      • All the students have to submit the soft copy of their "Assignment " in Moodle under assignment section created here and for this they will be graded here.
      • One weekly discussion or feedback forum is created under each of the lecture. Students have to give their feedback on these forum and marks will be given for their feedback
      • Announcement regarding the class will be posted on BLC. 
      • 3 Quizzes will be held on face-to-face class and 1 quiz will be held on online (BLC) and it will be announced before the class.
      • The question pattern and the syllabus for the quizzes, midterm and final exam is given here under each of the section (quizzes, midterm and final)
      • There are midterm and final exam preparation forum under these sections where students can discuss with each other about their midterm and final exam syllabus, any problem regarding the exam etc.


      COURSE RATIONALE

      The course is intended to teach the students the basic techniques that underlie the practice of Compiler Construction. The course will introduce the theory and tools that can be standard employed in order to perform syntax-directed translation of a high-level programming language into an executable code. These techniques can also be employed in wider areas of application, whenever we need a syntax-directed analysis of symbolic expressions and languages and their translation into a lower-level description. They have multiple applications for man-machine interaction, including verification and program analysis.


      COURSE OBJECTIVE

      The main objective of this course is to introduce the major concept areas of language translation and compiler design and to develop an awareness of the function and complexity of modern compilers. This course is a study of the theory and practice required for the design and implementation of interpreters and compilers for programming languages.


      COURSE OUTCOME (CO'S)

      COURSE OUTCOME

      CO1

      Explain various phases of a compiler.

      CO2

      Design token recognizer using modern tools.

      CO3

      Design Top-down and Bottom-up parsing Techniques.
      CO4 Translate given input to intermediate code.
      CO5 Identify various types of optimizations on intermediate code and generate assembly code.



      TEACHING AND LEARNING ACTIVITIES (TLA)

      TEACHING AND LEARNING ACTIVITIES

      TLA1

      Interactive discussion using Online/multimedia or whiteboard

      TLA2

      Group presentation regarding related problems and assigned task

      TLA3

      Evaluation of class performances to reach each student in a class for
      every topic


      ASSESSMENT PLAN





      GRADING SCHEME


      Theory Course

      Lab Course

      Class Attendance: 7%

      Class Attendance: 10%

      Class Tests/Quizzes: 15%

      Lab Submissions: 40%

      Assignment: 5%

      Lab Performance: 25%

      Presentation: 8%

      Report Submission: 25%

      Midterm Examination: 25%

       

      Final Examination: 40%

       



      COUNSELING HOURS

      COUNSELING HOURS

      Student Feedback


        



      Additional Support and Library Resources for Students



      • OBE Based Theory Course Outline [View]

      • Course Related Books

        Text Book:

        1. Compiler Principles, Techniques and Tools By Aho, Ullman, Sethi [Download]

        Reference Books:

        1.  Implementations of Compiler, A new approach to Compilers including the algebraic methods By Yunlin su, Song Y. Yan. [Download]

        2. Compiler construction, Principles and Practice, By Kenneth C Louden. [Download]

        3. Basics of Compiler Design by Torben. [Download]


    • Week 1: Preparing Background and Learn about Language Processing System

      Week1

      Discussion Topics: 

      • Overview of language processing
      • Discuss about pre-processors – compiler – assembler – interpreters.
      • Discuss about linkers & loaders
      • Distinguish in between Interpreter vs. Compiler.

      Expected Learning Outcomes:

      • Differentiate compiler with interpreter.
      • Recognize the language processing system
      • Conceptually understand the application of compiler.

      Resources of Learning:


       
       

    • Week - 2: Phase of a Compiler

      Week2

      Discussion Topics: 

      • Learn about the structure of a compiler.
      • Learn about the phases of a compiler.

      Expected Learning Outcomes:

      • Design the basic structure.
      • Recognize various phases of compiler

      Resources of Learning:

          


    • Week - 3: Context Free Grammar: LMD, RMD

      Week3

      Discussion Topics: 

      • Learn about Lexical Analysis –Role of Lexical Analysis
      • Discuss about Lexical Analysis Vs. Parsing
      • Discuss about Token, patterns and Lexemes
      • Discuss about Quiz Test.

      Expected Learning Outcomes:

      • Distinguish Token, patterns and Lexemes
      • Recognize Lexical errors.  

      Resources of Learning:


       
       

    • Week - 4: Regular Expression

      Week4

      Discussion Topics: 

      • Discuss about Regular definitions for the language constructs
      • Discuss about Transition diagram for recognition of tokens.

      Expected Learning Outcomes:

      • Capable to Design Transition Diagram.
      • Create Regular expression from sentence.

      Resources of Learning:


       
       

      • Self Test Week 4 URL
      • Answer Following Questions Forum

        Example 1:

        Write the regular expression for the language accepting all the string which are starting with 1 and ending with 0, over ∑ = {0, 1}.

        Example 2:

        Write the regular expression for the language starting and ending with a and having any having any combination of b's in between.


    • Presentation


      Submit your file in the given drive link asap.
      Date: 26 September 2022
      Topic: Computer Science related
      Duration: 10 Minutes
      Minimum 10 Slides.
      Please maintain proper dress code.

    • Assignment 1


      • Assignment 1
        Opened: Monday, 26 September 2022, 12:00 AM
        Due: Friday, 30 September 2022, 12:00 AM

    • Week - 5: NFA and DFA

      Week5

      Discussion Topics: 

      • Discuss about Automata Theory.
      • Discuss and Illustrate NFA and DFA.

      Expected Learning Outcomes:

      • Understand Tuples.
      • Design and Construct NFA and DFA

      Resources of Learning:


       
       

    • Week - 6: NFA to DFA Conversion

      Week6

      Discussion Topics: 

      • Discuss about subset construction method.
      • Discuss and Illustrate the techniques to construct DFA
      • Discuss about Class Test.

      Expected Learning Outcomes:

      • Design DFA from NFA.
      • Distinguish NFA and DFA.
      • Recognize the benefit to construct DFA.

      Resources of Learning:


       
       

    • Midterm Examination

      Week7

      Topics Covered for Midterm Examination

      • Language Processing System
      • Phase of a Compiler
      • Context Free Grammar
      • Regular Expression
      • NFA and DFA
      • NFA to DFA Conversion

      • Week - 8: Left Recursion and Left Factoring Elimination

        Week8

        Discussion Topics: 

        • Discuss about LMD and RMD
        • Discuss and Illustrate the elimination techniques

        Expected Learning Outcomes:

        • Recognize the elimination techniques
        • Understand the importance of Left Elimination

        Resources of Learning:

         
         

      • Week - 9: Determination of FIRST and FOLLOW Function

        Week9

        Discussion Topics: 

        • Discuss and illustrate the rules for FIRST and FOLLOW Function.
        • Discuss the techniques to find FIRST and FOLLOW function.

        Expected Learning Outcomes:

        • Recognize specific tokens
        • Identify FIRST and FOLLOW
        • Construct LL1 Table

        Resources of Learning:

         
         
         For LL(1) Parsing Table: 

          
          

      • Assignment 2


        • Assignment 2
          Opened: Monday, 14 November 2022, 12:00 AM
          Due: Sunday, 20 November 2022, 12:00 AM

      • Quiz


        • Quiz
          Opened: Sunday, 11 December 2022, 4:00 PM
          Closed: Sunday, 11 December 2022, 5:00 PM

          Date: 18th November, 2022

          Time: 40 Minutes

          Topic: Left Recursion, Left Factoring, FIRST and FOLLOW function, LL(1) Parsing Table

      • Week - 10: LR0 Parser and Canonical Table

        Week10

        Discussion Topics: 

        • Discuss and illustrate Kernel item, Non Kernel Item.
        • Discuss about Augmented grammar.
        • Discuss about Canonical Table.

        Expected Learning Outcomes:

        • Recognize kernel and non-kernel item.
        • Construct LR 0 Parser.
        • Design and construct canonical table.
        Resources of Learning:


          

          


      • Week - 11: Intermediate Code Generation

        Week11

        Discussion Topics: 

        • Discuss abstract syntax trees and Directed acyclic graph
        • Discuss and illustrate three address code, quadruples, and triples.
        • Discuss about Class Text.

        Expected Learning Outcomes:

        • Recognize techniques to eliminate common sub tree.
        • Design triples.
        Resources of Learning:



        • Weekly Discussion Forum

          Construct a DAG for the following three address code-

          1. a = b + c
          2. t1 = a x a
          3. b = t1 + a
          4. c = t1 x b
          5. t2 = c + b
          6. a = t2 + t2

      • Week - 12: Code Generation and Basic Block

        Week12

        Discussion Topics: 

        • Discuss about the rules for leader selection.
        • Discuss and illustrate the techniques to create basic block.
        • Discuss the techniques to design flow graph.

        Expected Learning Outcomes:

        • Recognize three address codes.
        • Design basic blocks for high level languages.
        • Understand the necessity of flow graph.

        Resources of Learning:


      • Week - 13: Code Optimization

        Week13

        Discussion Topics: 

        • Discuss about Machine independent code optimization.
        • Discuss and illustrate the techniques of code optimization.

        Expected Learning Outcomes:

        • Recognize machine independent code.
        • Able to apply techniques to optimize codes.

        Resources of Learning:


      • Week - 14: Preparation for Final Examination

        Week14

        Topics Covered for Final Examination

        • Left Recursion and Left Factoring Elimination
        • Determination of FIRST and FOLLOW Function
        • LR0 Parser and Canonical Table
        • Intermediate Code Generation
        • Code Generation and Basic Block
        • Code Optimization