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