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)
      • Errata
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:
    • Participation (10%)
    • Exercise (20%)
    • Midterm Exam (20%)
    • Oral Presentation (optional) (10%)
    • Final Project (20%)
    • Written Report (20%)
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/21 Parsing SQL (2)
    14. 5/14 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種能力，打造競爭實力
        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
        • [Moodle] Brute Force , Running Time
        • [CPL23L] [CPL23R] Breadth-First Search (BFS)
    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
        • [CPL29] LR(1) Parser
    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:

• Stanford Compiler @Coursera
• Computer Language Engineering.
  This is not a course for programming languages. Actually, it requires students to learn parsing and write a compiler.

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.