簡易檢索 / 詳目顯示

回結果列表
研究生： 楊岳霖
Yang, Yue-Lin
論文名稱： 編譯器課程教學輔助工具之設計與實作
The Design and Implementation of a Course Aid for Teaching Compiler Construction
指導教授： 陳　敬
Chen, Jing
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電腦與通信工程研究所
Institute of Computer & Communication Engineering
論文出版年： 2018
畢業學年度： 106
語文別： 中文
論文頁數： 89
中文關鍵詞： 編譯器 、教育 、LLVM
外文關鍵詞： Compiler, Education, LLVM
相關次數： 點閱：85  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 編譯器是計算機科學與工程相關科系中十分重要的ㄧ門課，扮演著讓學生理解從高階程式語言到機器指令這兩種抽象之間的橋梁，而編譯器課程實習專題則被視為是課程中的精華。但比起其他課程的專題複雜度更高、實作量更大，要考慮的課題也更多，因此專題的開發與維護也就成了教師不小的負擔。
    本論文設計並實作一可用於大學編譯器教學課程實作專題的輔助工具，提供教師用於開發課程專題。本論文規劃與設計過程汲取前人的相關研究，對許多課題進行探討，並整合過去的經驗與常見需求；整體設計重點如下：(1)評估大學編譯器課程的需求，規劃適合的實習內容；(2)模組化架構：可增加教師開發、運用、維護與修改專題編譯器的彈性，也方便教師將整個專題切分成數個子任務並給予個別評分；(3)整合編譯器開發工具：引入Flex與Bison，可增加教師開發、修改實習編譯器的開發效率，亦可作為學生練習的選項；(4)以LLVM IR作為目標語言：嘗試以傳統手寫方式而非常見的調用LLVM API的方式來生成LLVM IR檔案( .ll格式)；輸出的LLVM IR同樣適用於各種LLVM的分析、調試與轉換工具，可進一步作為「進階編譯器」或「編譯最佳化」等課程實習專題之前身；(5)資訊輔助檢視功能：將標記符、符號表、文字表與抽象句法樹這些編譯過程中產生的重要資訊儲存成易於判讀的格式，作為學生開發、除錯以及教師評量的輔助。為驗證上述設計，本論文以成功大學使用多年的教學用程式語言Vanilla-C為示範源語言，實作一示範編譯器。
    本論文之主要貢獻為建構大學基礎編譯器課程專題開發輔助工具，提供教師與學生開發課程專題編譯器，可以減少課前準備、學期中使用與後續維護的負擔；其模組化架構與輸出LLVM IR之設計則有利後續銜接更進階的編譯器相關課程專題，擴大實習專題的價值。本論文實作之示範編譯器也可以直接作為教師課堂講解的基本範例。

    Compiler is a very important subject in computer science and computer engineering related disciplines. It helps students understand and gain insights by playing the role of a bridge between the two abstractions from high-level programming languages to machine instructions. A course project on building a small compiler is considered to be an essential part in many courses on compiler construction. However, compared to other computer science courses, compiler construction practicum is more complex and there are many issues needed to be considered. The development and maintenance of a suitable, practical, progressive and pedagogical compiler construction project in general is one inevitable burden for teachers.

    This thesis presents the design and the implementation of a course aid, namely YACTA (short for Yet Another Compiler Teaching Aid), to support developing compiler construction projects for undergraduate-level compiler courses. The main features of YACTA include: (1) modularized and replaceable components; (2) mapping the whole compiler construction into progressive assignments; (3) adopting LLVM IR (Intermediate Representation) as object code. The architecture of YACTA is composed of five parts: (1) Framework Components, which implement the skeleton of the whole project and provide a collection of data structures and basic utility functions; (2) Core Components, which form the main part of practicing compiler construction and can be used as progressive assignments; (3) Presentation Components, which are a collection of functions that are intended to display important data structures produced during the compilation process in readable formats, such as tokens, syntax tree, symbol table, and literal table; (4) Generating Tools, which include popular compiler generating tools, such as Flex and Bison, and serve as alternatives in building scanner and/or parser of the target compiler; (5) LLVM Tools, which are used for processing the IR generated by the target compiler. In order to verify the feasibility of YACTA and for evaluation purpose, this study develops a demonstration version and implements a compiler, to be used as an example target compiler, based on the source language "Vanilla-C". The results of the verification process showed that LLVM IR were correctly produced and executed.

    The contribution of this thesis is the development of a framework as course aid for teaching compiler construction. It can help teachers develop flexible, long-sustaining and easy-to-maintain compiler projects effectively and efficiently. The demonstration compiler can also be used as an example of compiler construction in classroom.

    第1章　緒 論 1 1.1　研究背景 1 1.2　研究動機 3 1.3　研究方法 4 1.4　章節規劃 6 第2章 相關研究 7 2.1　編譯器教育 7 2.1.1　編譯器架構 7 2.1.2　大學編譯器課程 9 2.2　編譯器課程實習專題 10 2.2.1　編譯器課程專題的目標與範圍 10 2.2.2　源語言 12 2.2.3　目標語言 13 2.2.4　模組化與漸增式任務設計 15 2.2.5　教學輔助工具 15 2.2.6　其他議題 16 2.3　編譯器前端開發輔助工具 17 2.3.1　Lex/Flex 18 2.3.2　Yacc/Bison 19 2.3.3　Flex與Bison結合使用 20 2.4　Tiny Compiler 21 2.5　LLVM 22 2.5.1　LLVM發展簡介 22 2.5.2　LLVM與GCC的比較 24 2.5.3　LLVM 中間表示 25 2.6　討論 27 2.6.1　目標與範圍 27 2.6.2　專題進行安排 28 2.6.3　教學輔助工具之設計目標 28 第3章　架構與設計 31 3.1　整體運作模型設計 31 3.2　軟體架構 34 3.3　模組化設計 36 3.4　源語言 39 3.5　目標語言 42 3.6　編譯器開發工具 43 3.7　基本資訊輔助檢視工具 46 3.8　作業系統 46 第4章　實作 47 4.1　實作環境 47 4.2　編譯器實習專題實作 48 4.2.1　詞法分析器模組實作 49 4.2.2　符號表模組實作 51 4.2.3　句法分析模組實作 53 4.2.4　語意分析模組實作 58 4.2.5　中間表示碼生成模組實作 61 4.2.6　主程式實作 62 4.2.7　錯誤處理實作 64 4.3　基本資訊輔助檢視工具 64 4.3.1　表單檢視程序實作 65 4.3.2　樹的檢視程序實作 65 第5章　測試與成果 68 5.1　測試環境 68 5.2　系統測試範例 69 5.3　功能測試 71 5.3.1　測試流程 71 5.3.2　測試程式編譯與執行 72 5.3.3　測試程式之標記符輸出 74 5.3.4　測試程式之句法分析樹 74 5.3.5　測試程式之符號表與文字表內容 76 5.3.6　輸出LLVM IR 78 5.4　使用llc工具產生組合語言 79 5.5　成果運用 83 第6章　結論與展望 84 6.1　結論 84 6.2　未來展望 85 參考文獻 86

    [1]A. Aiken, “Cool: A portable project for teaching compiler construction,” Proc. ACM SIGPLAN, Vol. 31, Issue 7, pp. 19–24, July 1996.
    [2]A. Demaille, “Making Compiler Construction Projects Relevant to Core Curriculums,” Proc. ACM ITiCSE’05, pp. 266-270, Sep. 2005.
    [3]A. Demaille, R. Levillain, B, Perrot, “A set of tools to teach compiler construction,” Proc. ACM ITiCSE, Vol. 40, Issue 3, pp. 68-72, Sep. 2008.
    [4]ACM, “ACM Software System Award,” [Online]. Available: https://awards.acm.org/software-system/award-winners. [Accessed July 19, 2018].
    [5]Chris Lattner, “Introduction to the LLVM Compiler Infrastructure,” Gelato ICE 2006, Apr. 25, 2006.
    [6]Chris Lattner, “Introduction to the LLVM Compiler System,” ACAT’08, Nov. 04, 2008.
    [7]Electronic Joint Business, “Flex 和 Bison 簡介,” [Online]. Available: http://www.ejb.cc/archives/6185/flex-and-bison-introduction-a. [Accessed July 19, 2018].
    [8]I. Budiselic, D. Skvorc and S. Srbljic, “Design the Programming Assignment for a University Compiler Design Course,” Proc. IEEE Information and Communication Technology, Electronics and Microelectronics, May 2014.
    [9]IEEE, “The 2017 Top Programming Languages,” [Online]. Available: https://spectrum.ieee.org/computing/software/the-2017-top-programming-languages. [Accessed July 19, 2018].
    [10]J. Meyer, “Java Virtual Machine,” O'Reilly Associates, 1997.
    [11]Jim Huang, “What Can Compiler Do for Us,” SlideShare.net, [Online]. Available: https://www.slideshare.net/jserv/what-can-compilers-do-for-us. [Accessed July 19, 2018].
    [12]Jin-Gu Kai, “More Target Independent LLVM Bitcode,” [Online]. Available: http://llvm.org/devmtg/2011-09-16/EuroLLVM2011-MoreTargetIndependentLLVMBitcode.pdf. [Accessed July 19, 2018].
    [13]Justin Holewinski, “RE: LLVM IR is a compiler IR,” [Online]. Available: http://lists.llvm.org/pipermail/llvm-dev/2011-October/043777.html. [Accessed May 18, 2018].
    [14]K. C. Louden, “Compiler Construction: Principles and Practice,” PWS Publishing Company, 1997.
    [15]LLVM, “LLVM Language Reference Manual,” [Online]. Available: https://llvm.org/docs/LangRef.html. [Accessed May 18, 2018].
    [16]LLVM, “The LLVM Compiler Infrastructure,” [Online]. Available: https://llvm.org. [Accessed May 18, 2018].
    [17]Loyola Marymount University, “Intermediate Representation,” [Online]. Available: http://cs.lmu.edu/~ray/notes/ir/. [Accessed May 18, 2018].
    [18]M. I. Schwartzbach, “Design Choices in a Compiler Course or How to Make Undergraduates Love Formal Notation,” Compiler Construction: 17th international conference ETAPS 2008, pp. 1–15, 2008.
    [19]M. L. Corliss and E. C. Lewis, “Bantam: A customizable, Java-based, classroom compiler,” Proc. of the 39th SIGCSE Tech. Symp. on Computer Science Education, pp. 38-42, Mar. 2008.
    [20]P. Chakraborty, P. C. Saxena, C. P. Katti, G. Pahwa, and S. Taneja, “A New Practicum in Compiler Construction,” Computer Applications in Engineering Education, Vol. 22, Issue 3, pp. 429-441, Sep. 2014.
    [21]Pack Publishing, “Introducing LLVM Intermediate Representation,” [Online]. Available: https://hub.packtpub.com/introducing-llvm-intermediate-representation/. [Accessed May 18, 2018].
    [22]Peter Haggar, “Java bytecode: Understanding bytecode makes you a better programmer,” IBM.com, July 01, 2001. [Online]. Available: https://www.ibm.com/developerworks/ibm/library/it-haggar_bytecode/#opcode. [Accessed July 19, 2018].
    [23]Stephen O’Grady, “The RedMonk Programming Language Rankings: January 2018,” [Online]. Available: http://redmonk.com/sogrady/2018/03/07/language-rankings-1-18/. [Accessed May 18, 2018].
    [24]S. R. Vegdahl, “Using Visualization Tools to Teach Compiler Design,” Proc. ACM CCSC’00, pp.72-83, Jan. 2001.
    [25]Tutorialspoint, “Compiler - Intermediate Code Generation,” [Online]. Available: https://www.tutorialspoint.com/compiler_design/compiler_design_intermediate_code_generations.htm. [Accessed May 18, 2018].
    [26]Tutorialspoint, “Compiler Design – Architecture,” [Online]. Available: https://www.tutorialspoint.com/compiler_design/compiler_design_architecture.htm. [Accessed July 22, 2018].
    [27]Tutorialspoint, “Compiler Design – Phase of Compiler,” [Online]. Available: https://www.tutorialspoint.com/compiler_design/compiler_design_phases_of_compiler.htm. [Accessed July 22, 2018].
    [28]University of Mary Washington, “Using Flex,” [Online]. Available: http://cs.umw.edu/~finlayson/class/spring15/cpsc401/notes/04-flex.html. [Accessed July 19, 2018].
    [29]V. Kirandziska, M. Joyanov, M. Mihova and M. Gusev, “Lab assessments in Undergraduate Course in Compilers for Students with No Prior Knowledge in Assembly,” Proc. IEEE Information and Communication Technology, Electronics and Microelectronics, pp. 738-743, May 2014.
    [30]V. Nagaraj, “What is LLVM and how it is different from GCC,” [Online]. Available: https://www.quora.com/What-is-LLVM-and-how-it-is-different-from-GCC. [Accessed July 19, 2018].
    [31]W. M. Waite, “The Compiler Course in Today’s Curriculum: Three Strategies,” Proc. ACM SIGCSE’06, Vol. 38, Issue 1, pp. 87-91, Mar. 2006.
    [32]Wikipedia, “Compiler,” [Online]. Available: https://en.wikipedia.org/wiki/Compiler. [Accessed Aug. 28].
    [33]Wikipedia, “Flex, (lexical analyser generator),” [Online]. Available: https://en.wikipedia.org/wiki/Flex_(lexical_analyser_generator). [Accessed July 19, 2018].
    [34]Wikipedia, “GNU Bison,” [Online]. Available: https://en.wikipedia.org/wiki/GNU_bison. [Accessed July 19, 2018].
    [35]Wikipedia, “Intermediate representation,” [Online]. Available: https://en.wikipedia.org/wiki/Intermediate_representation. [Accessed July 19, 2018].
    [36]Wikipedia, “WebAssembly,” [Online]. Available: https://en.wikipedia.org/wiki/WebAssembly. [Accessed Aug. 28, 2018].
    [37]Z. S. Rakic, P.Rakic and T. Petric, “miniC Project for Teaching Compiler Course,” Proc. ICIST 2014, Vol. 2, pp.360-362, 2014.

    無法下載圖示 校內：立即公開
    校外：不公開
    電子論文尚未授權公開，紙本請查館藏目錄
    QR CODE