※ [本文轉錄自 suhorng 信箱]

作者: yukuro (魔法師mystery) 看板: NCTU-Teacher
標題: [心得] 編譯器設計概論 - 徐慰中
時間: 2012/07/03 Tue 19:06:30

（按Ctrl+v 預覽，稍微修一下版面，可讓你這篇文章更專業喔^^）

⊕課名⊕

編譯器設計概論

▲教授▲

徐慰中

★修課年度★（請加註開課單位 如:大三通識、XX系選修、XX所）

大三資工組必修

￡教了什麼￡（課程大概內容。或是額外學會了什麼東西。）

課本是用 Crafting a Compiler
參考書是 Compilers: Principles, Techniques, and Tools(俗稱Dragon Book)

內容的話:

1. Introduction to Compiler

2. Simple Compiler Design

以上兩個就是簡介compiler是什麼,要做那些事,大致上可以分為6個階段:
(i) Lexical Analysis: 辨識那些token是屬於語言語言
(用Scanner辨識Identifier,某些符號...是否合法)
(ii) Syntax Analysis: 辨識token間怎樣排是合法的
(用Parser辨識文法)

(iii)Semantic Analysis: 判斷一些屬於程式語言的規則,但又沒辦法在(ii)處理的
是否合法(Ex: Type checking, Declaration...)

(iv) Intermediate Code Generation: 就像Java產生Byte code這種例子

(v) Optimization: 著重在產生出來的code,是否可以把它做的更有效率

(vi) Code Generation: 產生target code

3. Scanner的理論,Lex/Flex的規則和使用

4. Parser的理論, Yacc/Bison的使用

5. Top-Down Parsing(主要是LL(1) parsing) 以及限制

6. Bottom-Up Parsing(主要是LR(0), LR(1), SLR(1), LALR(1))

7. Declaration Processing, Type Checking, Name Space, Symbol Table

8. Reachable Analysis, Termination Analysis, Exception Handling
(這部分是Java有的特色, 上課也是稍微提一下)

9. Generate Codes by Mips Assembly Language
(i) Local Variable, Global Variable
(ii) Assignment Statement
(iii) if, if-else, while, for statement
(iv) function call
(v) Caller-saved, Callee-saved registers

10. Run-Time Support: Activation Record, Stack Allocation,
Compute Array Index, Deal with Non-local Variables by
static link, dynamic link, and display...

11. Simple Register Scheduling and Management

12. Leaf Routine Optimaztion, Jump Code Generation,
Switch Statement Code Generation


課本請參考

Chapter 1-6, 7.1, 7.2, Chapter8(除了8.7), 9.1, Chapter 12
至於Chapter 13,14可以看一下

◆上課方式◆（投影片、團體討論、老師教學風格）

主要是以老師自己做的投影片教學, 上課時很喜歡和學生互動和問問題
也很關心學生到底有沒有聽懂上課的內容, 也會藉著問問題的時候記住學生
這學期有兩次團體競賽搶答,主要是為了看學生了解多少，搶答答對會有額外加分

▼考試作業▼

1. 有6次project(50%)

project1: 做一個簡單的算數運算compiler,主要是改Java的code,來完成作業
,目的是了解compiler的6個phases

project2-6: 是實作C-- Compiler(簡化版的C)

project2: C-- Scanner

project3: C-- Parser

project4: C-- type checking, declararion, symbol table, name space

project5-6: Code generation for C-- by Mips

前3個比較簡單, 主要是為的熟悉Flex, Bison這些工具如何用來做scanner, parser
的功能

project4 是寫最多code的時候,有4個禮拜,但是要知道如何下手,可能要花2個禮拜

project5-6 要用QtSpim來測試自己產生的Mips assembly code是否正確
另外project4-6要注意如何用value stack, 和加action routine來幫自己做
type-checking, 操作symbol table, 和產生assembly code
還有就是因為我們project沒有產生abstract syntax tree, 所以多數都要在一個
文法的production內,就決定產生出來的code, 和決定source code的對錯,和課本
有點不一樣
(但你也可以產生abstract syntax tree, 應該不會禁止)

2. 期中考(20%): 內容Chpater 1-5

3. 期末考(25%): 內容是期中考後教的, 但是會以project實作部分為主

4. 額外加分(5%): 我猜是像上課搶答,學習態度之類的

另外期中期末可以開書,看講義,甚至用筆電,但不可上網


￥其他￥（是否注重出席率or嚴禁遲到？需要的基礎？）

我覺得需要的基礎應該比較著重程式設計的能力,我覺得需要

1. C program design: 基礎指令的不用講, 但是pointer, struct, union的使用能力,
我覺得非常重要, 不會活用應該很難完成project, 還有就是正確使用pointer,
不然絕對會dangling pointer, memory leak滿天飛
另外就是要會切割C source code, 分成好幾個source code 和 header file,
這真的很重要, 不然要再好幾千行code 搜尋某段程式碼會非常痛苦

2. Data Structure: 你能不能判斷在造一個parameter構成的list, 要用什麼data
structure才好處理, 每一個node要有那些東西, 才能存放所有資訊, 怎樣才能
有效率的插入,刪除和搜尋資料。我覺得用的data structure大多數都沒什麼特別的
(link list, stack, queue, hash table, binary search tree就夠了), 但是用的
好就需要好好思考

3. Algorithm Design: 要用怎樣的流程, 才可以解決你的問題, 而不是馬上就開始寫
程式碼, 不然像type checking的時候, 光檢查variable reference的文法和語意
對不對, 就要100多行, 而且很容易忘記一些細節, 總不希望在好幾千的code慢慢
試到對為止吧? 所以要練習自己寫psuedocode, 才不會手忙腳亂
當然, 如果可以分析你的程式效率更好

4. Software Engineer: 怎樣把你的code變得好讀一點, 容易修改和擴充, 整個project
的程式加起來, 寫再簡潔也是3000行起跳, 而且project分好幾個階段, 所以我覺得
這個非常重要, 不然你會改code和debug得非常痛苦


5. 會寫 Linux, Unix 的make file: 因為要能把好幾個source code連結起來, 而且
flex/bison主要是在linux/unix運作的, 所以也要學習使用系上工作站,或是用
vitual box 裝linux也可以

6. 熟悉如何把 C code轉成assembly code: 其實上課會講一些, 只是基礎的還是要會,
雖然是用Mips assembly language, 但學會x86就可以了, 重要的是怎麼翻,而不是
語法

其實每次都會有助教的source code給你改, 也會把make file寫好, 不過自己會寫會比較
能照自己的意思寫, 比較有彈性

理論的部分:

Formal Language 的 Regular Language 和 Context-Free Grammer 以及一點Turing
Machine的知識就夠了, 因為會用的上課會教, 而且也沒考過證明, 所以我覺得會了是
真的比較好理解, 只是沒有很需要, 而且compiler著重的是如何把finite automata
轉成程式碼, LL(k), LR(k) parser怎麼實作, 其實和formal language上的東西有點
不一樣


￠最後想說的話￠

我覺得老師很認真, 很關心學生的學習狀況, 上課都是用自己的方式講解,
不是照本宣科, 所以整個學期上完, 是很有價值的, 而且他似乎很擅長把
很難的觀念, 用很容易理解的方式說明, 真的是好老師


＆誰適合修這門課＆

願意認真去上課,作筆記的人非常適合上他的課,
當然所有人都很適合


--
※ Origin: 交大次世代(bs2.to)
◆ From: 111-251-181-131.dynamic.hinet.net
推 dogsbear：看了好像不錯 07/03 19:12
糖 super9817020：大推!!! 07/03 19:12
→ kougousei：超級操.... 07/03 20:29
推 shaform：常常會有人想問到底為什麼要修編譯器，除了老師說的業界 07/03 20:34
→ shaform：需求外，正如這篇文章所述，編譯器幾乎可說是把三年所學 07/03 20:34
→ shaform：的知識、技巧，(資結、程式語言、正規語言、組語...) 07/03 20:34
→ shaform：全部結合起來，用一個小型專案的方式讓你操兵演練， 07/03 20:34
→ shaform：這樣的歷程絕對是獲益良多的。 07/03 20:34
→ shaform：我自己覺得dragon book和crafting兩本教科書其實 07/03 20:35
→ shaform：都不是那麼容易讀懂。 07/03 20:35
→ shaform：而老師的講課真的是非常清楚，很值得推薦。 07/03 20:35
推 kramasdia：徐慰中教授的課真的值得認真上 07/03 20:46

我寫的時候忘了加上一個重要科目:程式語言
其實程式語言課程上學的東西,真的也非常重要.因為這門課會介紹程式語言會有那些元素
,然後這些東西的語意或是結構上大概是怎麼樣,好像每個老師在這門課著重的點不同,像
黃問泙老師會要求你用各式各樣的語言寫程式,黃世強老師就教一些課本上會有的東西,
有一次project教你用common lisp 和 prolog寫簡單的程式, 有一次是要求你用virtual
function改他的C++ source code, 所以我覺得不管上誰的程式語言,認真學對compiler
這門課都會很有幫助

作者從 111-251-181-131.dynamic.hinet.net 修改文章於 2012/07/03 Tue 21:10:48
作者從 111-251-181-131.dynamic.hinet.net 修改文章於 2012/07/03 Tue 21:12:41
→ sa411022：程式語言這門課快沒了 07/03 21:28
→ mTwTm：程式語言要被砍掉了 我也很驚訝 07/03 21:53
推 aplmnbvcxz：要砍也先砍林正中好嗎@@唉~ 07/03 22:01
推 dogsbear：林正中老師其實還不錯 07/03 22:03
→ kougousei：樓上當真@@?! 07/03 22:06
推 dogsbear：林正中老師比較有個性 但真的是位好老師 07/03 22:15
→ yukuro：原來程式語言真的被砍了,而且很多課都提前了,真的改了不少 07/03 22:29
→ sa411022：電電學也被砍了 (雖然後來好像不是林正中教了 07/03 22:40
→ yukuro：還真可以說完全整容,而且compiler和OS一起修,不知道好不好? 07/03 22:52
→ sa411022：以後大四根本沒事情做... 07/03 23:01
推 windtw：雖然很操但是其實最後做出來一個堪用的compiler很有成就感 07/03 23:04
推 windtw：教授上課真的上的很不錯 推~ 07/03 23:06
推 b6683421：上他的課真的很有幫助 07/03 23:38
推 gh40402：推薦這篇文章 07/04 11:13
→ erase2004：這老師很專業=b 07/04 12:35
推 xatier：大推老爹阿！ 07/06 09:34
推 PG：推薦這篇文章 07/15 02:29
推 jpopaholic：我也是先修他的課,他的作業會讓你更加會寫程式語言 01/09 04:56


※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: suhorng (118.166.52.160), 時間: 08/25/2013 23:22:25
※ 編輯: suhorng 來自: 118.166.52.160 (08/25 23:22)