搜尋

隨機推薦

02 十二月 2009

http://i.imgur.com/d5yV5hF.jpg

Lex 與 Yacc 介紹

Lex 和 Yacc 是 UNIX 兩個非常重要的、功能強大的工具。事實上,如果你熟練掌握 Lex 和 Yacc 的話,它們的強大功能使創建 FORTRAN 和 C 的編譯器如同兒戲。Ashish Bansal 為您詳細的討論了編寫自己的語言和編譯器所用到的這兩種工具,包括常規表達式、聲明、匹配模式、變量、Yacc 語法和解析器代碼。最後,他解釋了怎樣把 Lex 和 Yacc 結合起來。

Lex 代表 Lexical Analyzar。Yacc 代表 Yet Another Compiler Compiler。 讓我們從 Lex 開始吧。

上回提要:我們開始著手編寫編譯部份,從那棵 Parse tree 生成代碼,做法跟之前的 Analyser 差不多,都是用 mutual recursion 來遍歷 Parse tree。上回我們已經寫好了大部份的編譯,只剩下兩款 expression 未寫好,即 if 和 while,本節就是要把這兩款 expression 都寫出來。

終於來到最重要一步了,我們要把之前建立好的 parse tree 變成可以被 Wemachine 運行的代碼,有了編譯器才是真正的 compiler!在這一步,我們還是要用那個老技巧,即 mutual recursion,來遍歷我們的 parse tree,並輸出相應的代碼。事不宜遲,現在就開始了。

為什麼我們需要虛擬機呢?因為我們要運行我們編譯好的程式。那為什麼我們不直接編譯到 native binary code 呢?這是因為真正的電腦資源十分有限,我們編寫起上來會比用虛擬機的做法難很多,那就嚴重超出了本教程的範圍了(其實是因為西傑還不太認識這個課題,要偷懶一下)。當然,虛擬機的做法和 native code 的也有幾分相似,這裡就給讀者們一個初步的概念,大家真的想再接觸多一點底層的東西就要自己摸索一下了……

接著下來,我們就稱我們的虛擬機為 Wemachine 吧。

大家好,又見到西傑了。在上兩章我們探討了如何編寫 Scanner 和 Parser,能夠把一份程式文件轉變成一棵 Parse tree,如果文件有 syntax error 的話亦能夠被偵測出來並且告訴開發人員,現在要進行最後一步的分析了。今天要說的是語意分析,即 Semantic analysis,這是什麼來的?Semantic analysis 要做的工作就是分析語意啦!哈哈。同學們或許你們會問,當我們建立了一棵 Parse tree 之後,不就可以 compile 了嗎?其實不然,你現在有的只是 N 句句子,但這還不是一個完整故事,還要分析一下上文下理電腦才知道你說的是什麼故事,Semantic analysis 就是做這樣的工作了。給你一個例子:

上回提到,我們要寫一個 Recursive descent parser,從 Scanner 一直讀 Token 進來,並建立一棵 Parse tree。在建立途中,我們還用了 lookahead 的技巧,就是偷看下一個 Token 但是不會佔用它,原因是我們需要用它來判斷下一步怎麼走,但是我們又不能用掉它,否則到下一步時我們就用不到了。現在我們就來完成餘下的部份吧!

寫 Compiler 第一步通常都是先寫 Scanner,什麼是 Scanner 呢?這裡只給你初步概念,詳細解釋在維基看吧。試想像有一句英文句子(例子:”The quick brown fox jumps over the lazy dog” is an English-language pangram.),人類看英文的方法就是逐個逐個詞語地看,電腦怎樣才能知道要跳過 ” 雙引號才能讀取第一個詞語呢?那就是要靠 Scanner 來分析了,Scanner 會逐個逐個字元讀進來並且在“適當時候”把字元合成一組詞語供後邊的 Parser 做其他處理工作。

相信每個 programmer 都跟西傑一樣想過設計一種自己的編程語言,最近西傑就有機會要寫一個編譯器了。雖然在大學時已經讀過如何編寫一個編譯器,但要認真寫起上來還真的不容易,而且網上教寫編譯器的教材不多(尤其中文的),所以就把這次經驗記下來,疏理一下自己在開發過程中所學到的東西,也同時為互聯網增加一些有關編譯器這方面的中文資源吧。

西傑在開發過程中經常參考 Actionscript 編譯器的 source code(用Java 寫的),大家有興趣可以看看這裡(在 /trunk/modules/asc 裡), 是 open source 的

第 1 頁,共 7 頁

Please publish modules in offcanvas position.