利用最小成本的文法剖析來產生機器碼

Code Generation with a Least-Cost Parsing Technique

徐德發(Te-Fa Hsu)

指導教授 ： 楊武

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00836

摘要

在編譯器領域中有許多自動產生程式碼的技術，一種稱作BURS的樹狀樣式比對配合動態規劃的演算法是其中流行的一種做法。但是在本篇論文中，樣式比對改由文法剖析的方式來進行，亦即，利用文法剖析器依據指令文法來針對中間表示法(Intermediate Representation)去進行樣式比對。但指令文法是一個模糊文法，因此要由一個更為通用的剖析器，稱作GLR parser來處理。因為我們語法剖析器也是採用原本BURS演算法中的成本機制來去找尋成本最低的剖析方式，
所以若要解決在模糊文法中所存在的兩種衝突：S/R conflict和R/R conflict時，必須保證不會影響GLR parser尋找最低成本的結果。因此，我們針對這兩種衝突，提出新的方法來處理，前者是在runtime之前處理，藉由分析文法的方式來找出在該文法中每個S/R conflict相關的規則，並判斷哪些規則屬於shift，哪些規則屬於reduce，然後比較彼此的成本大小；後者則是在runtime時處理，針對由相同衝突衍伸出來的剖析堆疊做比較，比較的是其剖析路徑。這兩個解決衝突的技術雖無法解決所有的衝突，但從測試的結果中仍可看出當這兩個技術被執行時，確實可以減少GLR parser剖析所需的時間。此外，因為我們要將GLR Parser當作一個指令選取器，來跟BURS演算法做個比較，因此我們會將GLR Parser整合到一個現存的編譯器，而該編譯器的指令選取機制就是使用BURS演算法。但我們並未完全取代該編譯器的後端部分，而是要用GLR parser來取代原本的BURS指令選取機制，然後比較兩者所產生出來的指令序列是否相同。

關鍵字

模糊文法 ； 指令文法 ； 通用剖析器 ； BURS ； 中間表示樹

並列摘要

There are many automatic code generation techniques in a compiler. A tree-
pattern matching algorithm with dynamic programming called BURS is one of the most popular. However, in this thesis, pattern matching is performed as a parsing process for code generation. The set of pattern rules in an instruction grammar is transformed into a context-free grammar and a Generalized LR parser is used to do the matching work with the transformed instruction grammar since the grammar is usually ambiguous. Each pattern rule in the transformed grammar is equipped with a numeric cost and this cost criterion is used to select the least-cost result among all the final parsing results and is also used to reduce the overhead of parsing process.

並列關鍵字

GLR Parser ； Instruction Grammar ； Ambiguous Grammar ； IR Tree ； BURS

參考文獻

Generation Using Tree Pattern Matching and Dynamic Programming”, ACM

Transactions on Programming Languages and Systems, 1989, 491-516.

[2].Alfred V. Aho, and Margaret J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search”, Communications of the ACM archive. Volume 18 , Issue 6, 1975, 333-340.

[5].Christopher W. Fraser, David R. Hanson, and Todd A. Proebsting, “Engineering a Simple, Efficient Code-Generator Generator”, ACM Letters on Program Language and Systems, 1992, 213-226.

[6].Christopher W. Fraser and Robert R. Henry, “Hard-Coding Bottom-Up Code Generation Tables to Save Time and Space”, Software—Practice and Experience, 1991, 1–12.