Compiler (編譯器)

  1. Course Name: Compiler
  2. Time: Tuesday, 08:10-11:00
  3. Credit: 3
  4. Classroom: TC-208 (ext. 94334492)
  5. Instructor: Dr. Quincy Wu
  6. TAs:
  7. Students: 10
  8. LINE Group for discussion: NCNU.Course.Compiler
  9. Textbook:
    1. John Levine, Flex & Bison, O'Reilly Media, Inc., August 2009. (292 pages)
  10. Reference books:
    1. Keith Cooper and Linda Torczon, "Engineering A Compiler", Second Edition, 2011. ISBN:978-0-12-088478-0
    2. Leland L. Beck, "Chapter 5 Compilers" in " System Software: An Introduction to Systems Programming", 3rd Edition. ISBN:0-321-21177-4
    3. Torben Mogensen, Basics of Compiler Design, DIKU, University of Copenhagen.
  11. Evaluation:
  12. Agenda:
    1. 2/20 Introduction
    2. 2/27 Using Flex (1)
    3. 3/5 Using Flex (2)
    4. 3/12 Using Bison (1)
    5. 3/19 Using Bison (2)
    6. 3/26 Midterm Exam
    7. 4/2 Spring Vacation
    8. 4/9 Proposal Review
    9. 4/16 SQL Syntax (1)
    10. 4/23 SQL Syntax (2)
    11. 4/30 SQL Syntax (3)
    12. 5/7 Parsing SQL (1)
    13. 5/14 Parsing SQL (2)
    14. 5/21 Google BigQuery language
    15. 5/28 Final Project Presentation
    16. 6/4 Report Review
  13. Outline:
    1. Characters in an Input Line
      1. Create Mail Filters
      2. Writing C Programs on a FreeBSD server
      3. How to submit your homework?
      4. [YouTube] What Is A Compiler
      5. [CPL01] Integer Multiplier
      6. [CPL02] Hexadecimal Multiplier
    2. String Handling
      1. Using UTF-8 as the internal representation for strings in C and C++
      2. How to print characters in hexadecimal in C
      3. [CPL03] UTF-8 Encoding
      4. C++ String Stream
      5. [CPL04] sum_str() in C++
      6. [CPL05] sum_str() in C
    3. Parsing - Understanding Contents in a Line
      1. [CPL06] Parsing A Configuration File with Fixed-Format Lines
      2. [CPL07] White Spaces and Larger Values
      3. [CPL08] Longer Variable Names
    4. Regular Expressions
      1. [YouTube] UNIX Shell Regular Expressions and the sed and grep commands
      2. [YouTube] C++ Regular Expression Library
      3. Regular Expressions in Grep Command with 10 Examples
      4. Regular expressions library (cppreference.com)
      5. [EX04] Word Count
      6. [CPL09] Delete Spaces
      7. [CPL10] White Spaces
      8. [CPL11] Validate Email Addresses
      9. [CPL12] Regular Expression (1)
      10. [CPL13] Regular Expression (2)
      11. [CPL14] Regular Expression (3)
      12. [CPL15] Regular Expression (4)
    5. Finite State Automata
      1. [CPL17] Finite Automata
    6. Nondterministic Finite Automata
      1. C++ STL Set
      2. [CPL18] Nondeterministic Finite Automata
      3. [CPL19] Nondeterministic Finite Automata with epsilon-Transition (NFA-e)
    7. 4/6 Midterm Exam
    8. Regular Expression to NFA: Thompson's Construction
    9. NFA to DFA: The Subset Construction
      1. [CPL20] The Subset Construction
    10. DFA to Minimal DFA: Hopcroft's Algorithm
      1. 5種能力,打造競爭實力video
      2. [CPL21] Hopcroft's Algorithm
      3. [HackingOff] Regular Expression to NFA (This site implements Thompson Construction and Subset Construction, but not Hopcroft's Algorithm.)
    11. Implementing Scanners
    12. Context-Free Grammar
      1. [YouTube] Sheep Baa
      2. C++ BNF Grammar
      3. [CPL22L] [CPL22R] Context-Free Grammar
    13. Top-Down Parsing
    14. Table-Driven LL(1) Parsers
      1. Removal of Left Recursion
      2. [CPL24] Depth-First Search (DFS) with Backtracking
      3. Left Factoring (P.107)
      4. [CPL25] Compute FIRST(), FOLLOW()
      5. [CPL26] Compute FIRST+().
      6. [CPL27] LL(1) Table Construction
      7. [CPL28] LL(1) Parser
      8. CFG to FIRST() and FOLLOW()
        • Use "->" to denote "derives".
        • Separate symbols by spaces.
    15. Bottom-Up Parsing
    16. Building LR(1) Tables
    17. 6/22 Final Exam, Seats
  14. 教育目標
  15. 核心能力

Exercises

  1. Identify symmetric strings
  2. Verify ID Numbers
  3. Verify C++ Variable Names
  4. 1-10,14-24,26-47,49-53
  5. Verify IPv4 addresses
  6. Verify IPv6 addresses
  7. Verify Email addresses
  8. Verify URLs
  9. Matrix operation
  10. Inner Product A.B
  11. See MATLAB
  12. The m4 Macro Package, Linux Journal, April 2002.
  13. Macro Magic: m4, Part One, Linux Magazine, February 2005.
  14. Exploiting the m4 Macro Language, Department of Computing Science and Mathematics University of Stirling.
  15. Software Similarity Tester by Dick Grune.

Other Resources:

TODO

  1. EX16
  2. EX36
  3. a longer sentence for EX16L
  4. EX37
  5. Read Compiler Chapter 5
  6. Jeffery EX12 test cases
  7. Jeffery EX13 test cases
  8. C++ STL Set for Compiler class. std::set::find(), insert(), empty(), count()
  9. 600 會造成 judge 讀不到檔案, Syntax Error, 然後就一直卡在那兒,沒有任何回應。 604 也不可,一定要 644. (640 呢?)
  10. JFLAP - software for experimenting with finite automata, pusd-down automata.

Network Header Steganography

  1. Term Project
  2. Libpcap File Format
  3. pylibpcap
  4. Wireshark Development: Chapter 9 Packet Dissection