Lex和Yacc簡(jiǎn)明教程

《Lex和Yacc簡(jiǎn)明教程》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、Lex和Yacc簡(jiǎn)明教程作者:ThomasNiemann?翻譯：傅惠忠目錄序言3?導(dǎo)言4?Lex6?理論6?練習(xí)7?YACC11?理論11?練習(xí)，第一部分12?練習(xí)，第二部分15?計(jì)算器18?描述18?包含文件20?Lex輸入文件21?Yacc輸入文件22?解釋器26?編譯器27?圖28?Lex進(jìn)階34?字符串34?保留字35?lex的調(diào)試35?Yacc進(jìn)階37?遞歸37?IfElse歧義37?錯(cuò)誤信息38?繼承屬性39?內(nèi)含動(dòng)作39?調(diào)試Yacc39?參考書目40序言本書將教會(huì)你如何使用lex和yacc構(gòu)造一個(gè)編譯器。lex和yacc

2、是兩個(gè)用來生成詞匯分析器和剖析器的工具。我假設(shè)你能夠運(yùn)用C語言編程，并且理解數(shù)據(jù)結(jié)構(gòu)的含義，例如“鏈表”和“樹”。導(dǎo)言部分描寫了構(gòu)建編譯器所需的基本部分，以及l(fā)ex和yacc之間的互動(dòng)關(guān)系。后面兩章更加詳細(xì)的描寫了lex和yacc。以此為背景，我們構(gòu)建了一個(gè)經(jīng)典的計(jì)算器程序。這個(gè)計(jì)算器支持常用的算術(shù)符號(hào)和控制結(jié)構(gòu)，例如實(shí)現(xiàn)了像ifelse和while這樣的控制結(jié)構(gòu)。經(jīng)過小小的修改，我們就把這個(gè)計(jì)算器轉(zhuǎn)換成一個(gè)可以運(yùn)行在基于棧的計(jì)算機(jī)上的編譯器。后面的間節(jié)討論了在編寫編譯器是經(jīng)常發(fā)生的問題。本書中使用的例程的源代碼可以從下面列出的網(wǎng)站上下

3、載到。允許下面列出的網(wǎng)站復(fù)制本書的一部分內(nèi)容，沒有任何附加限制。例程中的源代碼可以自由的用于任何一個(gè)軟件中，而無需通過作者的授權(quán)。THOMAS?NIEMANN?波特蘭，俄勒岡州網(wǎng)站：epaperpress.com?譯者序:?找不到好的中文資料，所以自己翻譯了一個(gè)，如發(fā)現(xiàn)錯(cuò)誤，請(qǐng)不吝賜教。電子郵件：fuhuizn@hotmail.com?傅惠忠導(dǎo)言在1975年之前，編寫編譯器一直是一個(gè)非常費(fèi)時(shí)間的工作。這一年Lesk[1975]和Johson?[1975]發(fā)表了關(guān)于lex和yacc的論文。這些工具極大地簡(jiǎn)化了編寫編譯器的工作。在Aho[1

4、986]中描寫了關(guān)于如何具體實(shí)現(xiàn)lex和yacc的細(xì)節(jié)。從下列地方可以等到lex和yacc工具：●Mortice?Kern?System?(MKS)，在www.mks.com?，●GNU?flex和bison，在www.gnu.org?，●Ming，在www.mingw.org?，●Cygwin，在www.cygwin.org?，還有●我的Lex和Yacc版本，在epaperpress.com?MKS的版本是一個(gè)高質(zhì)量的商業(yè)產(chǎn)品，零售價(jià)大約是300美元。GNU軟件是免費(fèi)的。flex?的輸出數(shù)據(jù)也可以被商業(yè)版本所用，對(duì)應(yīng)的商業(yè)版本號(hào)是1.

5、24，bison也一樣。Ming和Cygwin?是GNU軟件在某些32位Windows系統(tǒng)上的移植產(chǎn)物。事實(shí)上Cygwin是UNIX操作系統(tǒng)在Windows?上的一個(gè)模擬接口，其中包括了gcc和g++?編譯器。我的版本是基于Ming的，但量是使用Visual?C++編譯的并且包含一個(gè)改善文件操作程序的小補(bǔ)丁。如果你下載我的版本，請(qǐng)記住解壓縮的時(shí)候一定要保留文件夾結(jié)構(gòu)。圖1?：編譯順序Lex為詞法分析器或掃描器生成Ｃ程序代碼。它使正則表達(dá)式匹配輸入的字符串并且把它們轉(zhuǎn)換成對(duì)應(yīng)的標(biāo)記。標(biāo)記通常是代表字符串或簡(jiǎn)單過程的數(shù)值。圖１說明了這一點(diǎn)。

6、當(dāng)Lex?發(fā)現(xiàn)了輸入流中的特定標(biāo)記，就會(huì)把它們輸入一個(gè)特定的符號(hào)表中。這個(gè)符號(hào)表也會(huì)包含其它的信息，例如數(shù)據(jù)類型（整數(shù)或?qū)崝?shù)）和變量在內(nèi)存中的位置。所有標(biāo)記的實(shí)例都代表符號(hào)表中的一個(gè)適當(dāng)?shù)乃饕怠acc為語法分析器或剖析器生成Ｃ程序代碼。Yacc使用特定的語法規(guī)則以便解釋從Lex?得到的標(biāo)記并且生成一棵語法樹。語法樹把各種標(biāo)記當(dāng)作分級(jí)結(jié)構(gòu)。例如，操作符的優(yōu)先級(jí)和相互關(guān)系在語法樹中是很明顯的。下一步，生成編譯器原代碼，對(duì)語法樹進(jìn)行一次第一深度歷遍以便生成原代碼。有一些編譯器直接生成機(jī)器碼，更多的，例如上圖所示，輸出匯編程序。圖２：用Le

7、x/Yacc構(gòu)建一個(gè)編譯器圖２顯示了Lex和Yacc使用的命名約定。我們首先要說明我們的目標(biāo)是編寫一個(gè)BASIC編譯器。首先我們要指定Lex的所有的模式匹配規(guī)則（bas.l）和Yacc的全部語法規(guī)則（bas.y?）。下面列舉了產(chǎn)生我們的編譯器，bas.exe，的命令。yacc?dbas.y?#生成y.tab.h,?y.tab.clex?bas.l#生成lex.yy.ccc?lex.yy.cy.tab.c?obas.exe#?編譯／連接Yacc讀入bas.y中的語法描述而后生成一個(gè)剖析器，即y.tab.c中的函數(shù)yyparse。bas.y

8、?中包含的是一系列的標(biāo)記聲明?！癲”選項(xiàng)使Yacc生成標(biāo)記聲明并且把它們保存在y.tab.c中。Lex?讀入bas.l中的正則表達(dá)式的說明，包含文件y.tab.h，然后生成詞匯解釋器，即文件lex.yy.c