linux編譯lex庫
Ⅰ 為什麼要學習編譯原理
大學課程為什麼要開設編譯原理呢?這門課程關注的是編譯器方面的產生原理和技術問題,似乎和計算機的基礎領域不沾邊,可是編譯原理卻一直作為大學本科的必修課程,同時也成為了研究生入學考試的必考內容。編譯原理及技術從本質上來講就是一個演算法問題而已,當然由於這個問題十分復雜,其解決演算法也相對復雜。我們學的數據結構與演算法分析也是講演算法的,不過講的基礎演算法,換句話說講的是演算法導論,而編譯原理這門課程講的就是比較專註解決一種的演算法了。在20世紀50年代,編譯器的編寫一直被認為是十分困難的事情,第一Fortran的編譯器據說花了18年的時間才完成。在人們嘗試編寫編譯器的同時,誕生了許多跟編譯相關的理論和技術,而這些理論和技術比一個實際的編譯器本身價值更大。就猶如數學家們在解決著名的哥德巴赫猜想一樣,雖然沒有最終解決問題,但是其間誕生不少名著的相關數論。
推薦參考書
雖然編譯理論發展到今天,已經有了比較成熟的部分,但是作為一個大學生來說,要自己寫出一個像TurbocC,Java那樣的編譯器來說還是太難了。不僅寫編譯器困難,學習編譯原理這門課程也比較困難。
第一本書的原名叫《CompilersPrinciples,Techniques,andTools》,另外一個響亮的名字就是龍書。原因是這本書的封面上有條紅色的龍,也因為獗臼樵詒嘁朐?砘?嘴域確實?忻?所以很多國外的學者都直接取名為龍書。最近機械工業出版社已經出版了此書的中文版,名字就叫《編譯原理》。該書出的比較早,大概是在85或86年編寫完成的,作者之一還是著名的貝爾實驗室的科學家。裡面講解的核心編譯原理至今都沒有變過,所以一直到今天,它的價值都非凡。這本書最大的特點就是一開始就通過一個實際的小例子,把編譯原理的大致內容羅列出來,讓很多編譯原理的初學者很快心裡有了個底,也知道為什麼會有這些理論,怎麼運用這些理論。而這一點是我感覺國內的教材缺乏的東西,所以國內的教材都不是寫給願意自學的讀者,總之讓人看了半天,卻不知道裡面的東西有什麼用。
第二本書的原名叫《ModernCompilerDesign》,中文名字叫做《現代編譯程序設計》。該書由人民郵電出版社所出。此書比較關注的是編譯原理的實踐,書中給出了不少的實際程序代碼,還有很多實際的編譯技術問題等等。此書另外一個特點就是其現代而字。在傳統的編譯原理教材中,你是不可能看到如同Java中的垃圾回收等演算法的。因為Java這樣的解釋執行語言是在近幾年才流行起來的東西。如果你想深入學習編譯原理的理論知識,那麼你肯定得看前面那本龍書,如果你想自己動手做一個先進的編譯器,那麼你得看這本《現代編譯程序設計》。
第三本書就是很多國內的編譯原理學者都推薦的那本《編譯原理及實踐》。或許是這本書引入國內比較早吧,我記得我是在高中就買了這本書,不過也是在前段時間才把整本書看完。此書作為入門教程也的確是個不錯的選擇。書中給出的編譯原理講解也相當細致,雖然不如前面的龍書那麼深入,但是很多地方都是點到為止,作為大學本科教學已經是十分深入了。該書的特點就是注重實踐,不過感覺還不如前面那本《現代編譯程序設計》的實踐味道更重。此書的重點還是在原理上的實踐,而非前面那本那樣的技術實踐。《編譯原理及實踐》在講解編譯原理的各個部分的同時,也在逐步實踐一個現代的編譯器TinyC.等你把整本書看完,差不多自己也可以寫一個TinyC了。作者還對Lex和Yacc這兩個常用的編譯相關的工具進行了很詳細的說明,這一點也是很難在國內的教材中看到的。
推薦了這三本教材,都有英文版和中文版的。很多英文好的同學只喜歡看原版的書,不我的感覺是這三本書的翻譯都很不錯,沒有必要特別去買英文版的。理解理論的實質比理解表面的文字更為重要。
編譯原理的實質
幾乎每本編譯原理的教材都是分成詞法分析,語法分析(LL演算法,遞歸下降演算法,LR演算法),語義分析,運行時環境,中間代碼,代碼生成,代碼優化這些部分。其實現在很多編譯原理的教材都是按照85,86出版的那本龍書來安排教學內容的,所以那本龍書的內容格式幾乎成了現在編譯原理教材的定式,包括國內的教材也是如此。一般來說,大學裡面的本科教學是不可能把上面的所有部分都認真講完的,而是比較偏重於前面幾個部分。像代碼優化那部分東西,就像個無底洞一樣,如果要認真講,就是單獨開一個學期的課也不可能講得清楚。所以,一般對於本科生,對詞法分析和語法分析掌握要求就相對要高一點了。
詞法分析相對來說比較簡單。可能是詞法分析程序本身實現起來很簡單吧,很多沒有學過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講解詞法分析的時候,重點把正則表達式和自動機原理加了進來,然後以一種十分標準的方式來講解詞法分析程序的產生。這樣的做法道理很明顯,就是要讓詞法分析從程序上升到理論的地步。
語法分析部分就比較麻煩一點了。現在一般有兩種語法分析演算法,LL自頂向下演算法和LR自底向上演算法。LL演算法還好說,到了LR演算法的時候,困難就來了。很多自學編譯原理的都是遇到LR演算法的理解成問題後就放棄了自學。其實這些東西都是只要大家理解就可以了,又不是像詞法分析那樣非得自己寫出來才算真正的會。像LR演算法的語法分析器,一般都是用工具Yacc來生成,實踐中完全沒有比較自己來實現。對於LL演算法中特殊的遞歸下降演算法,因為其實踐十分簡單,那麼就應該要求每個學生都能自己寫。當然,現在也有不少好的LL演算法的語法分析器,不過要是換在非C平台,比如Java,Delphi,你不能運用YACC工具了,那麼你就只有自己來寫語法分析器。
等學到詞法分析和語法分析時候,你可能會出現這樣的疑問:詞法分析和語法分析到底有什麼?就從編譯器的角度來講,編譯器需要把程序員寫的源程序轉換成一種方便處理的數據結構(抽象語法樹或語法樹),那麼這個轉換的過程就是通過詞法分析和語法分析的。其實詞法分析並非一開始就被列入編譯器的必備部分,只是我們為了簡化語法分析的過程,就把詞法分析這種繁瑣的工作單獨提取出來,就成了現在的詞法分析部分。除了編譯器部分,在其它地方,詞法分析和語法分析也是有用的。比如我們在DOS,Unix,linux下輸入命令的時候,程序如何分析你輸入的命令形式,這也是簡單的應用。總之,這兩部分的工作就是把不規則的文本信息轉換成一種比較好分析好處理的數據結構。那麼為什麼編譯原理的教程都最終把要分析的源分析轉換成樹這種數據結構呢?數據結構中有Stack,Line,List這么多數據結構,各自都有各自的特點。但是Tree這種結構有很強的遞歸性,也就是說我們可以把Tree的任何結點Node提取出來後,它依舊是一顆完整的Tree。這一點符合我們現在編譯原理分析的形式語言,比如我們在函數裡面使用函樹,循環中使用循環,條件中使用條件等等,那麼就可以很直觀地表示在Tree這種數據結構上。同樣,我們在執行形式語言的程序的時候也是如此的遞歸性。在編譯原理後面的代碼生成的部分,就會介紹一種堆棧式的中間代碼,我們可以根據分析出來的抽象語法樹,很容易,很機械地運用遞歸遍歷抽象語法樹就可以生成這種指令代碼。而這種代碼其實也被廣泛運用在其它的解釋型語言中。像現在流行的Java,.NET,其底層的位元組碼bytecode,可以說就是這中基於堆棧的指令代碼的。
關於語義分析,語法制導翻譯,類型檢查等等部分,其實都是一種完善前面得到的抽象語法樹的過程。比如說,我們寫C語言程序的時候,都知道,如果把一個浮點數直接賦值給一個整數,就會出現類型不匹配,那麼C語言的編譯器是怎麼知道的呢?就是通過這一步的類型檢查。像C++語言這中支持多態函數的語言,這部分要處理的問題就更多更復雜了。大部編譯原理的教材在這部分都是講解一些比較好的處理策略而已。因為新的問題總是在發生,舊的辦法不見得足夠解決。
本來說,作為一個編譯器,起作用的部分就是用戶輸入的源程序到最終的代碼生成。但是在講解最終代碼生成的時候,又不得不講解機器運行環境等內容。因為如果你不知道機器是怎麼執行最終代碼的,那麼你當然無法知道如何生成合適的最終代碼。這部分內容我自我感覺其意義甚至超過了編譯原理本身。因為它會把一個計算機的程序的運行過程都通通排在你面前,你將來可能不會從事編譯器的開發工作,但是只要是和計算機軟體開發相關的領域,都會涉及到程序的執行過程。運行時環境的講解會讓你更清楚一個計算機程序是怎麼存儲,怎麼裝載,怎麼執行的。關於部分的內容,我強烈建議大家看看龍書上的講解,作者從最基本的存儲組織,存儲分配策略,非局部名字的訪問,參數傳遞,符號表到動態存儲分配(malloc,new)都作了十分詳細的說明。這些東西都是我們編寫平常程序的時候經常要做的事情,但是我們卻少去探求其內部是如何完成。
關於中間代碼生成,代碼生成,代碼優化部分的內容就實在不好說了。國內很多教材到了這部分都會很簡單地走馬觀花講過去,學生聽了也只是作為了解,不知道如何運用。不過這部分內容的東西如果要認真講,單獨開一學期的課程都講不完。在《編譯原理及實踐》的書上,對於這部分的講解就恰到好處。作者主要講解的還是一種以堆棧為基礎的指令代碼,十分通俗易懂,讓人看了後,很容易模仿,自己下來後就可以寫自己的代碼生成。當然,對於其它代碼生成技術,代碼優化技術的講解就十分簡單了。如果要仔細研究代碼生成技術,其實另外還有本叫做《》,那本書現在由機械工業出版社引進的,十分厚重,而且是英文原版。不過這本書我沒有把它列為推薦書給大家,畢竟能把龍書的內容搞清楚,在中國已經就算很不錯的高手了,到那個時候再看這本《》也不遲。代碼優化部分在大學本科教學中還是一個不太重要的部分,就是算是實踐過程中,相信大家也不太運用得到。畢竟,自己做的編譯器能正確生成執行代碼已經很不錯了,還談什麼優化呢?
編譯原理的課程畢竟還只是講解原理的課程,不是專門的編譯技術課程。這兩門課程是有很大的區別的。編譯技術更關注實際的編寫編譯器過程中運用到的技術,而原理的課
Ⅱ linux下安裝PBC庫,configure時出錯,大神幫幫忙啊
通過源碼安裝linux軟體的步驟,一般是到源碼目錄進行以下三步:
1. ./configure xxx 這是通過configure文件生成Makefile,期間,會有檢查編譯時所需要的依賴庫是否滿足。configure命令後面也可以添加選項來使能一些模塊,具體選項可以通過./configure --help進行查看,如果不需要用到的模塊,則可以去掉使能不編譯,如果未添加選項,則全部使用默認值。
2. make
這是根據生成的Makefile進行編譯
3. make install
根據Makefile中install這個TARGET進行安裝。也可以通過make DESTDIR=XXX install指定安裝目錄
綜上所述,你的情況是依賴庫沒滿足,導致configure失敗,沒有生成Makefile,所以運行make命令會因為沒有Makefile提示找不到TARGET。關鍵信息是這句:checking for flex no,checking for xxx表示檢測的xxx依賴,解決辦法就是先安裝flex這個包,然後再重新運行configure,如果是ubuntu的話應該可以使用sudo apt-get install flex安裝。另,flex安裝後不一定能保證configure能通過,有可能還會遇到其他依賴庫未滿足的情況,請參照flex進行處理。
這是關於flex包的描述及下載地址:
Description: A tool for generating text-scanning programs
Upstream URL: http://flex.sourceforge.net
Ⅲ linux中make makefiles這個命令是什麼意思
無論是在Linux還是在Unix環境中,make都是一個非常重要的編譯命令。不管是自己進行項目開發還是安裝應用軟體,我們都經常要用到
make或make
install。利用make工具,我們可以將大型的開發項目分解成為多個更易於管理的模塊,對於一個包括幾百個源文件的應用程序,使用make和
makefile工具就可以簡潔明快地理順各個源文件之間紛繁復雜的相互關系。而且如此多的源文件,如果每次都要鍵入gcc命令進行編譯的話,那對程序員
來說簡直就是一場災難。而make工具則可自動完成編譯工作,並且可以只對程序員在上次編譯後修改過的部分進行編譯。因此,有效的利用make和
makefile工具可以大大提高項目開發的效率。同時掌握make和makefile之後,您也不會再面對著Linux下的應用軟體手足無措了。
但令人遺憾的是,在許多講述Linux應用的書籍上都沒有詳細介紹這個功能強大但又非常復雜的編譯工具。在這里我就向大家詳細介紹一下make及其描述文件
makefile。
Makefile文件
Make工具最主要也是最基本的功能就是通過makefile文件來描述源程序之間的相互關系並自動維護編譯工作。而makefile 文件需要按照某種語法進行編寫,文件
中
需要說明如何編譯各個源文件並連接生成可執行文件,並要求定義源文件之間的依賴關系。makefile 文件是許多編譯器--包括 Windows NT
下的編譯器--維護編譯信息的常用方法,只是在集成開發環境中,用戶通過友好的界面修改 makefile 文件而已。
在 UNIX 系統中,習慣使用 Makefile 作為 makfile 文件。如果要使用其他文件作為 makefile,則可利用類似下面的 make 命令選項指定 makefile 文件:
$ make -f Makefile.debug
例如,一個名為prog的程序由三個C源文件filea.c、fileb.c和filec.c以及庫文件LS編譯生成,這三個文件還分別包含自
己的頭文件a.h
、b.h和c.h。通常情況下,C編譯器將會輸出三個目標文件filea.o、fileb.o和filec.o。假設filea.c和fileb.c都要
聲明用到一個名為defs的文件,但filec.c不用。即在filea.c和fileb.c里都有這樣的聲明:
#include "defs"
那麼下面的文檔就描述了這些文件之間的相互聯系:
#It is a example for describing makefile
prog : filea.o fileb.o filec.o
cc filea.o fileb.o filec.o -LS -o prog
filea.o : filea.c a.h defs
cc -c filea.c
fileb.o : fileb.c b.h defs
cc -c fileb.c
filec.o : filec.c c.h
cc -c filec.c
這個描述文檔就是一個簡單的makefile文件。
從上面的例子注意到,第一個字元為 # 的行為注釋行。第一個非注釋行指定prog由三個目標文件filea.o、fileb.o和filec.o鏈接生成。第三行描述了如何從prog所依賴的文件建立可執行文件。接下來的4、6、8行分別指定三個目標文件,以及它們所依賴的.c和.h文件以及defs文件。而5、7、9行則指定了如何從目標所依賴的文
件建立目標。
當filea.c或a.h文件在編譯之後又被修改,則 make 工具可自動重新編譯filea.o,如果在前後兩次編譯之間,filea.C 和a.h 均沒有被修改,而且 test.o 還存在的話,就沒有必要重新編譯。這種依賴關系在多源文件的程序編譯中尤其重要。通過這種依賴關系的定義,make 工具可避免許多不必要的編譯工作。當然,利用 Shell
腳本也可以達到自動編譯的效果,但是,Shell 腳本將全部編譯任何源文件,包括哪些不必要重新編譯的源文件,而 make 工具則可根據目標上一次編譯的時間和目標所依賴的源文件的更新時間而自動判斷應當編譯哪個源文件。
Makefile文件作為一種描述文檔一般需要包含以下內容:
◆ 宏定義
◆ 源文件之間的相互依賴關系
◆ 可執行的命令
Makefile中允許使用簡單的宏指代源文件及其相關編譯信息,在Linux中也稱宏為變數。在引用宏時只需在變數前加$符號,但值得注意的是,如果變數名的長度超過一個字元,在引用時就必須加圓括弧()。下面都是有效的宏引用:
$(CFLAGS)
$2
$Z
$(Z)
其中最後兩個引用是完全一致的。需要注意的是一些宏的預定義變數,在Unix系統中,$*、$@、$?和$<四個特殊宏的值在執行命令的過程中會發生相應的變化,而在GNU make中則定義了更多的預定義變數。關於預定義變數的詳細內容,宏定義的使用可以使我們脫離那些冗長乏味的編譯選項,為編寫makefile文
件帶來很大的方便。
# Define a macro for the object files
OBJECTS= filea.o fileb.o filec.o
# Define a macro for the library file
LIBES= -LS
# use macros rewrite makefile
prog: $(OBJECTS)
cc $(OBJECTS) $(LIBES) -o prog
……
此時如果執行不帶參數的make命令,將連接三個目標文件和庫文件LS;但是如果在make命令後帶有新的宏定義:
make "LIBES= -LL -LS"
則命令行後面的宏定義將覆蓋makefile文件中的宏定義。若LL也是庫文件,此時make命令將連接三個目標文件以及兩個庫文件LS和LL。
在Unix系統中沒有對常量NULL作出明確的定義,因此我們要定義NULL字元串時要使用下述宏定義:
STRINGNAME=
Make命令
在make命令後不僅可以出現宏定義,還可以跟其他命令行參數,這些參數指定了需要編譯的目標文件。其標准形式為:
target1 [target2 …]:[:][dependent1 …][;commands][#…]
[(tab) commands][#…]
方括弧中間的部分表示可選項。Targets和dependents當中可以包含字元、數字、句點和"/"符號。除了引用,commands中不能含有"#",也不允許換行。
在通常的情況下命令行參數中只含有一個":",此時command序列通常和makefile文件中某些定義文件間依賴關系的描述行有關。如果與目標相關連的那些描述行指定了相關的command序列,那麼就執行這些相關的command命令,即使在分號和(tab)後面的aommand欄位甚至有可能是NULL。如果那些與目標相關連的行沒有指定command,那麼將調用系統默認的目標文件生成規則。
如果命令行參數中含有兩個冒號"::",則此時的command序列也許會和makefile中所有描述文件依賴關系的行有關。此時將執行那些與目標相關連的描述行所
指向的相關命令。同時還將執行build-in規則。
如果在執行command命令時返回了一個非"0"的出錯信號,例如makefile文件中出現了錯誤的目標文件名或者出現了以連字元打頭的命令字元串,make操作一般會就此終止,但如果make後帶有"-i"參數,則make將忽略此類出錯信號。
Make命本身可帶有四種參數:標志、宏定義、描述文件名和目標文件名。其標准形式為:
Make [flags] [macro definitions] [targets]
Unix系統下標志位flags選項及其含義為:
-f file 指定file文件為描述文件,如果file參數為"-"符,那麼描述文件指向標准輸入。如果沒有"-f"參數,則系統將默認當前目錄下名為makefile或者名為Makefile的文件為描述文件。在Linux中, GNU make 工具在當前工作目錄中按照GNUmakefile、makefile、Makefile的順序搜索 makefile文件。
-i 忽略命令執行返回的出錯信息。
-s 沉默模式,在執行之前不輸出相應的命令行信息。
-r 禁止使用build-in規則。
-n 非執行模式,輸出所有執行命令,但並不執行。
-t 更新目標文件。
-q make操作將根據目標文件是否已經更新返回"0"或非"0"的狀態信息。
-p 輸出所有宏定義和目標文件描述。
-d Debug模式,輸出有關文件和檢測時間的詳細信息。
Linux下make標志位的常用選項與Unix系統中稍有不同,下面我們只列出了不同部分:
-c dir 在讀取 makefile 之前改變到指定的目錄dir。
-I dir 當包含其他 makefile文件時,利用該選項指定搜索目錄。
-h help文擋,顯示所有的make選項。
-w 在處理 makefile 之前和之後,都顯示工作目錄。
通過命令行參數中的target ,可指定make要編譯的目標,並且允許同時定義編譯多個目標,操作時按照從左向右的順序依次編譯target選項中指定的目標文件。如果命令行中沒有指定目標,則系統默認target指向描述文件中第一個目標文件。
通常,makefile 中還定義有 clean 目標,可用來清除編譯過程中的中間文件,例如:
clean:
rm -f *.o
運行 make clean 時,將執行 rm -f *.o 命令,最終刪除所有編譯過程中產生的所有中間文件。
隱含規則
在make 工具中包含有一些內置的或隱含的規則,這些規則定義了如何從不同的依賴文件建立特定類型的目標。Unix系統通常支持一種基於文件擴展名即文件名後綴的隱含規則。這種後綴規則定義了如何將一個具有特定文件名後綴的文件(例如.c文件),轉換成為具有另一種文件名後綴的文件(例如.o文件):
.c:.o
$(CC) $(CFLAGS) $(CPPFLAGS) -c -o $@ $<
系統中默認的常用文件擴展名及其含義為:
.o 目標文件
.c C源文件
.f FORTRAN源文件
.s 匯編源文件
.y Yacc-C源語法
.l Lex源語法
在早期的Unix系統系統中還支持Yacc-C源語法和Lex源語法。在編譯過程中,系統會首先在makefile文件中尋找與目標文件相關的.C文件,如果還有與之相依賴的.y和.l文件,則首先將其轉換為.c文件後再編譯生成相應的.o文件;如果沒有與目標相關的.c文件而只有相關的.y文件,則系統將直接編譯.y文件。
而GNU make 除了支持後綴規則外還支持另一種類型的隱含規則--模式規則。這種規則更加通用,因為可以利用模式規則定義更加復雜的依賴性規則。模式規則看起來非常類似於正則規則,但在目標名稱的前面多了一個 % 號,同時可用來定義目標和依賴文件之間的關系,例如下面的模式規則定義了如何將任意一個 file.c 文件轉換為 file.o 文件:
%.c:%.o
$(CC) $(CFLAGS) $(CPPFLAGS) -c -o $@ $<
#EXAMPLE#
下面將給出一個較為全面的示例來對makefile文件和make命令的執行進行進一步的說明,其中make命令不僅涉及到了C源文件還包括了Yacc語法。本例選自"Unix
Programmer's Manual 7th Edition, Volume 2A" Page 283-284
下面是描述文件的具體內容:
#Description file for the Make command
#Send to print
P=und -3 | opr -r2
#The source files that are needed by object files
FILES= Makefile version.c defs main.c donamc.c misc.c file.c \
dosys.c gram.y lex.c gcos.c
#The definitions of object files
OBJECTS= vesion.o main.o donamc.o misc.o file.o dosys.o gram.o
LIBES= -LS
LINT= lnit -p
CFLAGS= -O
make: $(OBJECTS)
cc $(CFLAGS) $(OBJECTS) $(LIBES) -o make
size make
$(OBJECTS): defs
gram.o: lex.c
cleanup:
-rm *.o gram.c
install:
@size make /usr/bin/make
cp make /usr/bin/make ; rm make
#print recently changed files
print: $(FILES)
pr $? | $P
touch print
test:
make -dp | grep -v TIME>1zap
/usr/bin/make -dp | grep -v TIME>2zap
diff 1zap 2zap
rm 1zap 2zap
lint: dosys.c donamc.c file.c main.c misc.c version.c gram.c
$(LINT) dosys.c donamc.c file.c main.c misc.c version.c \
gram.c
rm gram.c
arch:
ar uv /sys/source/s2/make.a $(FILES)
通常在描述文件中應象上面一樣定義要求輸出將要執行的命令。在執行了make命令之後,輸出結果為:
$ make
cc -c version.c
cc -c main.c
cc -c donamc.c
cc -c misc.c
cc -c file.c
cc -c dosys.c
yacc gram.y
mv y.tab.c gram.c
cc -c gram.c
cc version.o main.o donamc.o misc.o file.o dosys.o gram.o \
-LS -o make
13188+3348+3044=19580b=046174b
最後的數字信息是執行"@size make"命令的輸出結果。之所以只有輸出結果而沒有相應的命令行,是因為"@size make"命令以"@"起始,這個符號禁止列印輸出它所在的命令行。
描述文件中的最後幾條命令行在維護編譯信息方面非常有用。其中"print"命令行的作用是列印輸出在執行過上次"make print"命令後所有改動過的文件名稱。系
統使用一個名為print的0位元組文件來確定執行print命令的具體時間,而宏$?則指向那些在print文件改動過之後進行修改的文件的文件名。如果想要指定執行print命令後,將輸出結果送入某個指定的文件,那麼就可修改P的宏定義:
make print "P= cat>zap"
在Linux中大多數軟體提供的是源代碼,而不是現成的可執行文件,這就要求用戶根據自己系統的實際情況和自身的需要來配置、編譯源程序後,軟體才能使用。只有掌握了make工具,才能讓我們真正享受到到Linux這個自由軟體世界的帶給我們無窮樂趣。
Ⅳ 編譯原理試題·
Lex和Yacc應用方法(一).初識Lex
草木瓜 20070301
Lex(Lexical Analyzar 詞法分析生成器),Yacc(Yet Another Compiler Compiler
編譯器代碼生成器)是Unix下十分重要的詞法分析,語法分析的工具。經常用於語言分
析,公式編譯等廣泛領域。遺憾的是網上中文資料介紹不是過於簡單,就是跳躍太大,
入門參考意義並不大。本文通過循序漸進的例子,從0開始了解掌握Lex和Yacc的用法。
一.Lex(Lexical Analyzar) 初步示例
先看簡單的例子(註:本文所有實例皆在RetHat Linux下完成):
一個簡單的Lex文件 exfirst.l 內容:
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下執行命令flex解析,會自動生成lex.yy.c文件:
[root@localhost liweitest]flex exfirst.l
進行編譯生成parser可執行程序:
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意:如果不加-ll鏈結選項,cc編譯時會出現以下錯誤,後面會進一步說明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status
創建待解析的文件 file.txt:
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通過已生成的可執行程序,進行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法會有個直觀的了解:
1.定義Lex描述文件
2.通過lex,flex工具解析成lex.yy.c文件
3.使用cc編譯lex.yy.c生成可執行程序
再來看一個比較完整的Lex描述文件 exsec.l :
%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
進行解析編譯:
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
這里就沒有加-ll選項,但是可以編譯通過。下面開始著重整理下Lex描述文件.l。
二.Lex(Lexical Analyzar) 描述文件的結構介紹
Lex工具是一種詞法分析程序生成器,它可以根據詞法規則說明書的要求來生成單詞識
別程序,由該程序識別出輸入文本中的各個單詞。一般可以分為<定義部分><規則部
分><用戶子程序部分>。其中規則部分是必須的,定義和用戶子程序部分是任選的。
(1)定義部分
定義部分起始於 %{ 符號,終止於 %} 符號,其間可以是包括include語句、聲明語句
在內的C語句。這部分跟普通C程序開頭沒什麼區別。
%{
#include "stdio.h"
int linenum;
%}
(2) 規則部分
規則部分起始於"%%"符號,終止於"%%"符號,其間則是詞法規則。詞法規則由模式和
動作兩部分組成。模式部分可以由任意的正則表達式組成,動作部分是由C語言語句組
成,這些語句用來對所匹配的模式進行相應處理。需要注意的是,lex將識別出來的單
詞存放在yytext[]字元數據中,因此該數組的內容就代表了所識別出來的單詞的內容。
類似yytext這些預定義的變數函數會隨著後面內容展開一一介紹。動作部分如果有多
行執行語句,也可以用{}括起來。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.規則部分的正則表達式
規則部分是Lex描述文件中最為復雜的一部分,下面列出一些模式部分的正則表達式字
符含義:
A-Z, 0-9, a-z 構成模式部分的字元和數字。
- 指定范圍。例如:a-z 指從 a 到 z 之間的所有字元。
\ 轉義元字元。用來覆蓋字元在此表達式中定義的特殊意義,
只取字元的本身。
[] 表示一個字元集合。匹配括弧內的任意字元。如果第一個字
符是^那麼它表示否定模式。例如: [abC] 匹配 a, b, 和C
的任何一個。
^ 表示否定。
* 匹配0個或者多個上述模式。
+ 匹配1個或者多個上述模式。
? 匹配0個或1個上述模式。
$ 作為模式的最後一個字元時匹配一行的結尾。
{ } 表示一個模式可能出現的次數。 例如: A{1,3} 表示 A 可
能出現1次或3次。[a-z]{5} 表示長度為5的,由a-z組成的
字元。此外,還可以表示預定義的變數。
. 匹配任意字元,除了 \n。
( ) 將一系列常規表達式分組。如:{Letter}({Letter}|{Digit})*
| 表達式間的邏輯或。
"一些符號" 字元的字面含義。元字元具有。如:"*" 相當於 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"後跟有後續表達式,
只匹配模版中"/"前面的部分。如:模式為 ABC/D 輸入 ABCD,
時ABC會匹配ABC/D,而D會匹配相應的模式。輸入ABCE的話,
ABCE就不會去匹配ABC/D。
B.規則部分的優先順序
規則部分具有優先順序的概念,先舉個簡單的例子:
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此時,如果輸入內容:
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析詞法時,是逐個字元進行讀取,自上而下進行規則匹配的,讀取到第一個A字元
時,遍歷後發現三個規則皆匹配成功,Lex會繼續分析下去,讀至第五個字元時,發現
"AAAA"只有一個規則可用,即按行為進行處理,以此類推。可見Lex會選擇最長的字元
匹配規則。
如果將規則
AAAA {printf("THREE\n");};
改為
AAAAA {printf("THREE\n");};
./parser < file1.txt 輸出結果為:
THREE
TWO
再來一個特殊的例子:
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
並輸入title,Lex解析完後發現,仍然存在兩個規則,這時Lex只會選擇第一個規則,下面
的則被忽略的。這里就體現了Lex的順序優先順序。把這個例子稍微改一下:
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex編譯時會提示:warning, rule cannot be matched.這時處理title字元時,匹配
到第一個規則後,第二個規則就無效了。
再把剛才第一個例子修改下,加深下印象!
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 顯示效果是一樣的,最後一項規則肯定是會忽略掉的。
C.規則部分的使用變數
且看下面示例:
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之間,加入了一些類似變數的東西,注意是沒有;的,這表示int,float分
別代指特定的含義,在兩個%%之間,可以通過{int}{float}進行直接引用,簡化模
式定義。
(3) 用戶子程序部分
最後一個%%後面的內容是用戶子程序部分,可以包含用C語言編寫的子程序,而這些子
程序可以用在前面的動作中,這樣就可以達到簡化編程的目的。這里需要注意的是,
當編譯時不帶-ll選項時,是必須加入main函數和yywrap(yywrap將下後面說明)。如:
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
三.Lex(Lexical Analyzar) 一些的內部變數和函數
內部預定義變數:
yytext char * 當前匹配的字元串
yyleng int 當前匹配的字元串長度
yyin FILE * lex當前的解析文件,默認為標准輸出
yyout FILE * lex解析後的輸出文件,默認為標准輸入
yylineno int 當前的行數信息
內部預定義宏:
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字元的
默認動作
內部預定義的函數:
int yylex(void) 調用Lex進行詞法分析
int yywrap(void) 在文件(或輸入)的末尾調用。如果函數的返回值是1,就停止解
析。 因此它可以用來解析多個文件。代碼可以寫在第三段,這
樣可以解析多個文件。 方法是使用 yyin 文件指針指向不同的
文件,直到所有的文件都被解析。最後,yywrap() 可以返回1
來表示解析的結束。
lex和flex都是解析Lex文件的工具,用法相近,flex意為fast lexical analyzer generator。
可以看成lex的升級版本。
相關更多內容就需要參考flex的man手冊了,十分詳盡。
四.關於Lex的一些綜述
Lex其實就是詞法分析器,通過配置文件*.l,依據正則表達式逐字元去順序解析文件,
並動態更新內存的數據解析狀態。不過Lex只有狀態和狀態轉換能力。因為它沒有堆棧,
它不適合用於剖析外殼結構。而yacc增加了一個堆棧,並且能夠輕易處理像括弧這樣的
結構。Lex善長於模式匹配,如果有更多的運算要求就需要yacc了。
Ⅳ Windows、Linux、UNIX、Dos操作系統分別是用什麼語言編寫的
Windows、Linux、UNIX、Dos操作系統的核心代碼大部分是使用C和C++編寫,底層介面用匯編編寫.
以windows為例,根據幾年前微軟在美國公布的內容,WINDOWS本身屬於微內核系統,WINDOWS98總共大概不到10萬行代碼,而WINDOWS2000則已經有20餘萬行代碼,其中80%是用C++編寫,其餘部分有C和匯編,底層介面用匯編編寫。
微內核系統從概念上是指「只包括操作系統的基本功能,例如內存管理和進程管理等等」,就連對各個文件系統的支持也不算在內.
所以一個微內核系統的操作系統能夠有20萬行代碼已經很多了。
之所以微軟選擇了C++而不想LINUX一樣選擇C,其根本原因就是WINDOWS操作系統本身是微內核系統,所以擴展性及以後的維護要求非常重要,所以C++的類的概念就能在這里很好的利用,但是畢竟C++的效率不如標准C及匯編,所以在一些明顯以效率為重的地方用的還是標准C及匯編。
編寫完畢後,WINDOWS上的其他用戶態程序(包括所有驅動程序、計算器、游戲等等所有你現在拿滑鼠能夠操作的東西)另行開發,例如:掃雷游戲就是用VB寫的。