臺灣博碩士論文加值系統

快速地找出程式中含有的語法錯誤，一直是軟體開發過程中，很重要的問題。在現在應用程式日趨複雜的情況下，盡快找出程式中含有的語法錯誤顯得更為重要。漸進式語法分析是一個可以幫助使用者在程式編輯時期便找到語法錯誤並修正的方法。藉由漸進式語法分析器的幫助，使用者不必等到完成程式編輯，再交由編譯器處理，才可得知程式中的語法錯誤，如此可縮短軟體開發的時間。

本篇論文提出了一個漸進式語法分析器產生器之實作，以及一個結合漸進式語法分析器與編輯器的應用程式介面。本論文實作之漸進式語法分析器產生器奠基於目前使用最多的Bison 語法分析器產生器。藉由漸進式語法分析器產生器和應用程式介面的幫助，使用者可以自行製作一個可針對自定語言進行漸進式語法分析的編輯器。

Quickly fixing syntax errors in programs is always an important issue for software development. The increasing complexity of application developed nowadays makes this issue even more crucial. Incremental parsing is a method that allows programmers to fix syntax errors in an interactive manner. With the assistance of the incremental parser, programmers could fix syntax errors as early as possible, which can greatly speed up software development.

This thesis introduces an implementation of a generator for incremental parser, and an API (Application Program Interface) that facilitate the integration of an incremental parser and an editor. The incremental parser generator implemented in the thesis is based on a popular parser generator called “Bison.” With the help of the incremental parser generator and the API, a programmer can easily construct a syntax-directed editor for his/her own language.

1 導論 1
1.1 研究背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究動機與貢獻. . .. . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 論文結構. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 3
2 相關技術與研究 5
2.1 狀態比對演算法. . . . . . . .. . . . . . . . . . . . . . . . . . . . . 5
2.1.1 線緒樹語法分析. . . . . . .. . . . . . . . . . . . . . . . . . . . . 6
2.1.2 復用節點. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 6
2.1.3 實作方式. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 7
2.2 句型語法分析演算法. . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 語法分析. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 8
2.2.2 版本控制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.3 實作方式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 狀態比對演算法和句型語法分析演算法的比較. . . . . . . . . . . . . . . 10
2.3.1 錯誤回復. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 進行處理時的額外負擔. . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.3 實作的複雜程度. . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Bison 語法分析器產生器13
3.1 Bison 的使用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Bison 的語法分析表. . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 語法分析表. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.2 內部使用表格. . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.3 除錯用表格. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Bison 的語法分析驅動程式. . . . . . . . . . . . . . . . . . . . . . . 24
3.3.1 範例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4 線緒樹語法分析31
4.1 線緒樹簡介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 線緒樹語法分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2.1 線緒樹的讀取. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2.2 線緒樹的化簡. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3 線緒樹語法分析驅動程式. . . . . . . . . . . . . . . . . . . . . . . . 34
4.3.1 整合方式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3.2 線緒樹管理模組. . . . . . . . . . . . . . . . . . .. .. . . . . . . 35
4.3.3 線緒樹語法分析模組. . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4 線緒樹繪製工具. . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5 線緒樹語法分析流程圖. . . . . . . . . . . . . . . . . . . . . . . . . 40
4.6 範例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.7 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5 漸進式線緒樹語法分析43
5.1 節點復用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 漸進式語法分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2.1 初始化步驟. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.2.2 語法分析步驟. . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2.3 尋找接枝節點. . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2.4 完成語法分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2.5 核心函式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3 漸進式語法分析驅動程式. . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.1 語法分析器與語彙分析器的溝通. . . . . . . . . . . . . . . . .. . . 54
5.3.2 實際進行語法分析. . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4 與Larchevˆeque 演算法不同之處. . . . . . . . . . . . . . . . . . . . 56
5.4.1 執行化簡的順序. . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.4.2 執行接技多加的條件. . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4.3 漸進式線緒樹語法分析流程圖. . . . . . . . . . . . . . . . . . . . . 57
5.5 範例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.5.1 結果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.6 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6 語法分析器和編輯器的介面77
6.1 外覆類別的設計. . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 編輯模式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.1 編輯基本動作. . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.2 按鍵分類. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.3 設定變動開頭和結尾. . . . . . . . . . . . . . . . . . . . . . . . . 79
6.2.4 範例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3 外覆類別的動作. . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.3.1 更新變動的方式. . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.4 範例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.5 小結. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7 結論與未來展望89

[ASU88] Alfred V. Aho, Ravi Sethi, and Jeffery D. Ullman. Compilers Principles, Techniques, and Tools. Addison Wesley, 1st edition, 1988.
[DDH84] Peter Dencker, Karl D¨urre, and Johannes Heuft. Optimization of parser tables for portable compilers. ACM Transaction on Programming Languague and Systems, 6(4):546–572, 1984.
[DMM88] Pierpaolo Degano, Stefano Mannucci, and Bruno Mojana. Efficient incremental LR parsing for syntax-directed editors. ACM Transaction on Programming Languague and Systems, 10(3):345–373, 1988.
[GM80] Carlo Ghezzi and Dino Mandrioli. Augmenting Parsers to Support Incrementality. Journal of ACM, 27(3):564–579, 1980.
[HSAF92] Ellis Horowitz, Sartaj Sahni, and Susan Anderson-Freed. Fundamentals of Data Structures in C. W. H. Freeman & Co., New York, NY, USA, 1992.
[Joh] John Ellson at el. Graphviz—Graph Visualization Software. http://www.
graphviz.org.
[Joh75] S. C Johnson. YACC—Yet another compiler compiler. Technical report, AT&T
Bell Laboratories, Murray Hill, N. J., 1975.
[Lar91] J.-M. Larchevˆeque. Techniques de compilation pour le development incremental sur base de donness orientees-objets. Technical report, INRIA, 1991.
[Lar95] J.-M. Larchevˆeque. Optimal incremental parsing. ACM Transaction on Programming Languague and Systems, 17(1):1–15, 1995.
[PJPG] Vern Paxson, Van Jacobson, Jef Poskanzer, and Kevin Gong. GNU Flex, Fast Lexical Analyzer Generator. http://www.gnu.org/software/flex.
[Tem] Brad Templeton. Alice Pascal, syntax-directed programming environment. http://www.templetons.com/brad/alice.html.
[TR81] Tim Teitelbaum and Thomas Reps. The Cornell program synthesizer: a syntaxdirected programming environment. Communication of ACM, 24(9):563–573, 1981.
[WG97] Tim A. Wagner and Susan L. Graham. Efficient self-versioning documents. Comp-Con IEEE Computer Society Press, pages 62–69, 1997.
[WG98] Tim A. Wagner and Susan L. Graham. Efficient and flexible incremental parsing.
ACM Transaction on Programming Languague and Systems, 20(5):980–1013, 1998.
[WG99] Tim A. Wagner and Susan L. Graham. History-Sensitive Error Recovery. IEEE Transactions on software engineering, 1999.
[Yan94] Wuu Yang. Incremental LR Parsing. International Computer Symposium Conference Proceedings, 9, 1994.