學(xué)過編譯原理的朋友肯定都接觸過LEX這個(gè)小型的詞法掃描工具. 但是卻很少有人真正把LEX用在自己的程序里. 在構(gòu)造專業(yè)的編譯器的時(shí)候,常常需要使用到lex和yacc. 正是因?yàn)檫@兩個(gè)工具,使得我們編寫編譯器,解釋器等工具的時(shí)候工作變得非常簡單.不過話說回來,會(huì)使用lex和yacc的人也確實(shí)不簡單. Lex和yacc里面牽涉到一系列的編譯原理的理論知識(shí),不是簡單地看看書就能搞懂的. 本文只是簡單地介紹一下lex和yacc的使用方法.相關(guān)編譯理請查看本科教材.
國內(nèi)大學(xué)教材里面對于lex和yacc的介紹很少,有些根本就沒有,不過在國外的編譯原理教材介紹了很多. 按照學(xué)科的分類,國內(nèi)大學(xué)本科里面開的<<編譯原理>>教程只是講解編譯的原理,并不講解實(shí)踐. 而對于實(shí)踐方面則是另外一門學(xué)科<<編譯技術(shù)>>. 關(guān)于編譯技術(shù)的書籍在國內(nèi)是少之又少. 前不久, 聽說上海交大的計(jì)科內(nèi)部出版過編譯技術(shù)的教材.可惜我們這些人就無法得見了. 還好,機(jī)械工業(yè)出版社引進(jìn)了美國 Kenneth C.Louden所著的經(jīng)典著作<<編譯原理及實(shí)踐>>中,比較詳細(xì)地介紹lex和yacc的使用.
Lex屬于GNU內(nèi)部的工具,它通常都是gcc的附帶工具. 如果你使用的Linux操作系統(tǒng),那么肯定系統(tǒng)本身就有lex和yacc,不過yacc的名字變成了bison. 如果你使用的Windows操作系統(tǒng),那么可以到cygwin或者GNUPro里面找得到. 網(wǎng)上也有windows版本lex和yacc,大家可以自己去找一找.
本文一共有兩篇,一篇是介紹lex,另一篇是介紹yacc. Lex和yacc搭配使用, 我們構(gòu)造自己的編譯器或者解釋器就如同兒戲. 所以我把本文的名字叫做黃金組合.
本文以flex( Fase Lex)為例,兩講解如何構(gòu)造掃描程序.
Flex可以通過一個(gè)輸入文件,然后生成掃描器的C源代碼.
其實(shí)掃描程序并不只用于編譯器 .比如編寫游戲的腳本引擎的時(shí)候,我看到很多開發(fā)者都是自己寫的掃描器,其算法相當(dāng)落后(完全沒有DFA的概念化), 甚至很多腳本引擎開發(fā)者的詞法掃描器都沒有編寫,而是在運(yùn)行過程中尋找token(單詞). 在現(xiàn)代的計(jì)算機(jī)速度確實(shí)可以上小型的腳本引擎在運(yùn)行中進(jìn)行詞法掃描, 但是作為一個(gè)合格的程序員, 或者說一個(gè)合格的計(jì)算機(jī)本科畢業(yè)生而來說, 能夠運(yùn)用編譯原理與技術(shù)實(shí)踐,應(yīng)該是個(gè)基本要求.
如果要說到詞法分析的掃描器源代碼編寫, 其實(shí)也很簡單, 會(huì)C語言的人都會(huì)寫. 可是Kenneth Louden在<<編譯原理及技術(shù)>里面,花了50多頁,原因就是從理論角度,介紹標(biāo)準(zhǔn)的,可擴(kuò)展的,高效的詞法掃描器的編寫. 里面從正則表達(dá)式介紹到DFA(有窮自動(dòng)機(jī)),再到NFA(非確定性有窮自動(dòng)機(jī)),最后才到代碼的編寫. 以自動(dòng)機(jī)原理編譯掃描器的方法基本上就是現(xiàn)在詞法掃描器的標(biāo)準(zhǔn)方法, 也就是Lex使用的方法. 在Lex中,我們甚至不需要自己構(gòu)造詞法的DFA, 我們只需要把相應(yīng)的正則表達(dá)式輸入, 然后lex能夠?yàn)槲覀冏约荷?/span>DFA,然后生成源代碼,可謂方便之極.
本文不講DFA, lex的輸入是正則表達(dá)式, 我們直接先看看正則表達(dá)式方面知識(shí)就可以了.
1.正則表達(dá)式(regular expression):
對于學(xué)過編譯原理的朋友來說,這一節(jié)完全可以不看.不過有些東西還是得注意一下,因?yàn)樵?/span>flex中的正則表達(dá)式的使用有些具體的問題是在我們的課本上沒有說明的.
先看看例子:
例1.1
name Tangl_99
這就是定義了name這個(gè)正則表達(dá)式,它就等于字符串Tangl_99.所以,如果你的源程序中出現(xiàn)了Tangl_99這個(gè)字符傳,那么它就等于出現(xiàn)一次name正則表達(dá)式.
例1.2
digit 0|1|2|3|4|5|6|7|8|9
這個(gè)表達(dá)式就是說,正則表達(dá)式digit就是0,1,2,…,9中的某一個(gè)字母.所以無論是0,2,或者是9…都是屬于digit這個(gè)正則表達(dá)式的.
“|”符號(hào)表示”或者”的意思.
那么定義正則表達(dá)式 name Tangl_99|Running,同樣的,如果你的源程序中出現(xiàn)了Tangl_99或者Running,那么就等于出現(xiàn)了一次name正則表達(dá)式.
例1.3
one 1*
“*”符號(hào)表示”零到無限次重復(fù)”
那么one所表示的字符串就可以是空串(什么字符都沒有), 1, 11, 111, 11111, 11111111111, 11111111…等等.總之,one就是由0個(gè)或者N個(gè)1所組成(N可以為任意自然數(shù)).
與”*”相同的有個(gè)”+”符號(hào).請看下面的例子1.4
例1.4
realone 1+
“+”符號(hào)表示”1到無限次重復(fù)”
那么realone和one不同的唯一一點(diǎn)就是,realone不包含空串,因?yàn)?/span>”+”表示至少一次重復(fù),那么realone至少有一個(gè)1.所以realone所表達(dá)的字符串就是1,11,111, 1111, 11111…,等等.
例1.5
digit [0-9]
letter [a-zA-Z]
這里的digit等于例1.2中的digit,也就是說,a|b|c就相當(dāng)于[a-c].
同理,letter也就是相當(dāng)于 a|b|c|d|e|f|…|y|z|A|B|C|D…|Z 不過注意的一點(diǎn)就是,你不能把letter寫成[A-z],而必須大寫和小寫都應(yīng)該各自寫出來.
例1.6
notA [^A]
“^”表示非,也就是除了這個(gè)字符以外的所有字符
所以notA表示的就是除了A以外的所有字符.
下面讓我們來看看一些一般高級程序語言中常用的綜合例子.
digit [0-9]
number {digit}+
letter [a-zA-Z_]
digit前面多次提起過,就是0-9的阿拉伯?dāng)?shù)字.number就是所有的數(shù)字組合,也就是整數(shù).
Letter前面也提起過,唯一不同的就是多了一個(gè)下劃線.因?yàn)橐话阄覀兊?/span>C語言中容許有下劃線來表示定義的變量名,所以我也把下劃線當(dāng)成英語字母來處理了.
這里number中使用上面定義的digit正則表達(dá)式.在lex中,用{digit}就是表示正則表達(dá)式digit.
newline [\n]
whitespace [ \t]+
newline就是提行的意思.這里我們使用的是\n這個(gè)符號(hào),它和C語言中表示提行號(hào)一致.問題是大家可能要問到為什么要使用[]符號(hào).因?yàn)樵?/span>lex中,如果你使用[],那么里面表示的肯定就是單個(gè)字符號(hào),而不會(huì)被理解成”\”和”n”兩個(gè)字符.
Whitespace就是空格符號(hào)的意思.一般的高級程序語言中有兩種,一種就是簡單的空格,還有一種就是\t制表符.使用了”+”符號(hào),就表示了這些空白符號(hào)的無限組合.
聯(lián)系客服
