學(xué)過編譯原理的朋友肯定都接觸過
LEX
這個小型的詞法掃描工具
.
但是卻很少有人真正把
LEX
用在自己的程序里
.
在構(gòu)造專業(yè)的編譯器的時候
,
常常需要使用到
lex
和
yacc.
正是因?yàn)檫@兩個工具
,
使得我們編寫編譯器
,
解釋器等工具的時候工作變得非常簡單
.
不過話說回來
,
會使用
lex
和
yacc
的人也確實(shí)不簡單
. Lex
和
yacc
里面牽涉到一系列的編譯原理的理論知識
,
不是簡單地看看書就能搞懂的
.
本文只是簡單地介紹一下
lex
和
yacc
的使用方法
.
相關(guān)編譯理請查看本科教材
.
國內(nèi)大學(xué)教材里面對于
lex
和
yacc
的介紹很少
,
有些根本就沒有
,
不過在國外的編譯原理教材介紹了很多
.
按照學(xué)科的分類
,
國內(nèi)大學(xué)本科里面開的
<<
編譯原理
>>
教程只是講解編譯的原理
,
并不講解實(shí)踐
.
而對于實(shí)踐方面則是另外一門學(xué)科
<<
編譯技術(shù)
>>.
關(guān)于編譯技術(shù)的書籍在國內(nèi)是少之又少
.
前不久
,
聽說上海交大的計科內(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
可以通過一個輸入文件
,
然后生成掃描器的
C
源代碼
.
其實(shí)掃描程序并不只用于編譯器
.
比如編寫游戲的腳本引擎的時候
,
我看到很多開發(fā)者都是自己寫的掃描器
,
其算法相當(dāng)落后
(
完全沒有
DFA
的概念化
),
甚至很多腳本引擎開發(fā)者的詞法掃描器都沒有編寫
,
而是在運(yùn)行過程中尋找
token(
單詞
).
在現(xiàn)代的計算機(jī)速度確實(shí)可以上小型的腳本引擎在運(yùn)行中進(jìn)行詞法掃描
,
但是作為一個合格的程序員
,
或者說一個合格的計算機(jī)本科畢業(yè)生而來說
,
能夠運(yùn)用編譯原理與技術(shù)實(shí)踐
,
應(yīng)該是個基本要求
.
如果要說到詞法分析的掃描器源代碼編寫
,
其實(shí)也很簡單
,
會
C
語言的人都會寫
.
可是
Kenneth Louden
在
<<
編譯原理及技術(shù)
>
里面
,
花了
50
多頁
,
原因就是從理論角度
,
介紹標(biāo)準(zhǔn)的
,
可擴(kuò)展的
,
高效的詞法掃描器的編寫
.
里面從正則表達(dá)式介紹到
DFA(
有窮自動機(jī)
),
再到
NFA(
非確定性有窮自動機(jī)
),
最后才到代碼的編寫
.
以自動機(jī)原理編譯掃描器的方法基本上就是現(xiàn)在詞法掃描器的標(biāo)準(zhǔn)方法
,
也就是
Lex
使用的方法
.
在
Lex
中
,
我們甚至不需要自己構(gòu)造詞法的
DFA,
我們只需要把相應(yīng)的正則表達(dá)式輸入
,
然后
lex
能夠?yàn)槲覀冏约荷?/span>
DFA,
然后生成源代碼
,
可謂方便之極
.
本文不講
DFA, lex
的輸入是正則表達(dá)式
,
我們直接先看看正則表達(dá)式方面知識就可以了
.
1.
正則表達(dá)式
(regular expression):
對于學(xué)過編譯原理的朋友來說
,
這一節(jié)完全可以不看
.
不過有些東西還是得注意一下
,
因?yàn)樵?/span>
flex
中的正則表達(dá)式的使用有些具體的問題是在我們的課本上沒有說明的
.
先看看例子
:
例
1.1
name????? Tangl_99
這就是定義了
name
這個正則表達(dá)式
,
它就等于字符串
Tangl_99.
所以
,
如果你的源程序中出現(xiàn)了
Tangl_99
這個字符傳
,
那么它就等于出現(xiàn)一次
name
正則表達(dá)式
.
例
1.2
digit??????? 0|1|2|3|4|5|6|7|8|9
這個表達(dá)式就是說
,
正則表達(dá)式
digit
就是
0,1,2,…,9
中的某一個字母
.
所以無論是
0,2,
或者是
9…
都是屬于
digit
這個正則表達(dá)式的
.
“|”
符號表示
”
或者
”
的意思
.
那么定義正則表達(dá)式
name?? Tangl_99|Running,
同樣的
,
如果你的源程序中出現(xiàn)了
Tangl_99
或者
Running,
那么就等于出現(xiàn)了一次
name
正則表達(dá)式
.
例
1.3
one?????? 1*
“*”
符號表示
”
零到無限次重復(fù)
”
那么
one
所表示的字符串就可以是空串
(
什么字符都沒有
), 1, 11, 111, 11111, 11111111111, 11111111…
等等
.
總之
,one
就是由
0
個或者
N
個
1
所組成
(N
可以為任意自然數(shù)
).
與
”*”
相同的有個
”+”
符號
.
請看下面的例子
1.4
例
1.4
realone??? 1+
“+”
符號表示
”1
到無限次重復(fù)
”
那么
realone
和
one
不同的唯一一點(diǎn)就是
,realone
不包含空串
,
因?yàn)?/span>
”+”
表示至少一次重復(fù)
,
那么
realone
至少有一個
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]
“^”
表示非
,
也就是除了這個字符以外的所有字符
所以
notA
表示的就是除了