※ [本文转录自 neoneon 信箱] 作者: [email protected] ("爱宕有机奈米负离子猫") 标题: [心得] 编译器设计概论 - 徐慰中 时间: Sun Jul 10 11:11:13 2016 作者: 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) ※ 转录者: neoneon (106.105.175.48), 07/12/2016 02:32:35