語法剖析時之屬性計算

Abstract

屬性文法產生的編譯器往往效率不及手寫的編譯器。其原因之一是大 部份屬性計算皆在剖析完成後才開始。本文提出將屬性計算的程式碼插入 剖析動作中的演算法。首先我們提出將語法樹建構序列(tree construction sequence)和遊歷序列(visit sequence)合併在一起的演算 法。由此演算法產生的序列可直接配合LL(k)剖析使用。對於LR(k)語法， 由此產生的序列，還需經過額外的步驟，以排入適當的空閒位置( free position)。 This thesis presents a method to determine the positions where semantic actions can be added and the LR(k) grammar is not affected. The circumstances that semantic actions added in where LR(k) grammar conflicts occur are discussed and a suggestion is proposed. Based on the information of positions, the visit-sequences of visit-oriented parsers are analyzed and transformed to parse-time visit-sequences which describe what attribute evaluations can be done at what positions. The algorithms exhibit the detail steps of analysis and transformation are presented.