[程式] lex 基本概念-Theory

以下出自此網頁！http://epaperpress.com/lexandyacc/ 此為雷米的學習筆記，幫助健忘的雷米記憶！
lex與yacc常常在資工系的編譯器（Compiler）作為概念教學的輔助學習語言。
雷米編譯器（compiler）課沒有學到這東東，之後寫程式需要創建剖析器（parser）才了解到這東西。

lex theory 理論

在編譯器第一個階段，先將輸入的字串轉成Token。
在正規的表示方式中，我們可以有一些判別樣式給lex，讓他可以產生程式碼去掃描與比對輸入的字串。
每個樣式的輸入給lex都有關連的動作，通常一個動作回傳一個token，用來表示符合的字串，之後可以被parser利用。最原始的情況，我們會簡單的印出這些符合的字串而不是去回傳一個token value。

雷米碎碎念：
以上的廢話簡單的說就是，你的input會被切成一堆token，
切的方法就是從你在lex定義的樣式（pattern）去掃描比對，
然後比對到的字串會回傳一個個token value回來。

底下表示一個簡單的樣式（pattern），由一個正規表示法來敘述，它可以掃描識別碼（identified）。
Lex會讀取這些樣式（pattern），並且產生成C source code用來做字彙分析。

letter(letter|digit)* -> 這＝ ” = 最好是這樣看得懂啦！這裡開始是在介紹pattern的寫法。

這個pattern會去比對一個字串的型別（characters）讓他變成單獨的字元，可由0到多個letter或digits組成。這個範例表示了運算過程允許的正規表示法。

repetition, expressed by the “*” operator -> 重複，請用＊表示
alternation, expressed by the “|” operator ->交替，請用｜表示
concatenation ->可串連

雷米碎碎念：慧根太低！Q___Q 看到這才懂letter是指字母，而digits是指數字，看懂了。（跪）

任何的正規表示式，都可以用一個有限狀態機（FSA）來表示。
我們可以用狀態圖來表示FSA，並且在狀態之間傳送。
有一個開始狀態和一個以上的終止狀態或接收狀態。

在上圖中，狀態0是開始狀態，狀態2是接收狀態。當型別被讀取產生了轉換從一個狀態到另一個狀態。當第一個字母被讀到轉換到狀態1，我們維持狀態1繼續讀取多個字母或數字，當我們讀到不同的型別時，我們轉換到狀態2。任何的有限狀態機（FSA）可以被表示為一個電腦程式。舉例來說，這三態機是可以簡單的被編程為…

start:  goto state0
state0: read c
if c = letter goto state1
goto state0
state1: read c
if c = letter goto state1
if c = digit goto state1
goto state2
state2: accept string

這是被用在lex上的技術。正規表示法被lex轉換成一個電腦程式以模擬有限狀態機。

Using the next input character and current state the
next state is easily determined by indexing into a computer-generated state table.
雷米碎碎念：這句話太神奇了，導致雷米需要一點時間消化，be continued…這樣<(___ ___)>

現在我們了解到lex的限制。舉例來說，lex不能被用來判別巢狀的結構像是括號。

巢狀結構必須被結合成一個堆疊（stack）來處理。
當我們遇到左括號”(“，我們將它放進堆疊（stack）裡。
當我們遇到右括號”)” ，我們把它放在堆疊的最上層，配對後將其從堆疊中取出（pop）。

雷米碎碎念：
話說，遇到那種很機車錯誤很多的input file時，剖析器（parser）忽略括號可能好一點Orz|||
不過對一個普通的編譯器（Compiler）來說，檢查括號有沒有對稱是很基本的一件事。

然而，lex 只有許多狀態並做狀態間的轉換。
因為它沒有堆疊（stack）所以不適合去分析巢狀結構。

雷米碎碎念：原文的以下就變成了Yacc廣告時間了！

Yacc 擴充有限狀態機（FSA）具有堆疊（stack）可簡單的建構括號。使用正確的工具來完成工作非常的重要，Lex是一個很好的字串比對工具，Yacc適合用來做更多具有挑戰性的任務。

[Reference] 感謝電機系學弟C.H.Lee提供參考資料，您的大恩大德小的沒齒難忘！！！

Lex

http://flex.sourceforge.net/manual/ –> 官方的使用手冊

http://epaperpress.com/lexandyacc/ –> Lex 入門

http://www.csie.ntnu.edu.tw/~ghhwang/course.html –> “lex 說明”、“lex 簡易手冊”

Reference book: lex & yacc (2^nd Edition) by John Levine, Tony Mason, Doug Brown, O’Reilly. –> 總圖借得到

http://www.cs.rug.nl/~jjan/vb/lextut.pdf –> A Lex Tutorial

http://oz.nthu.edu.tw/~d947207/chap10_lex.ppt

Lemon

http://www.sqlite.org/src/doc/trunk/doc/lemon.html –> 官方版本 (最完整)

http://jetsnote.blogspot.com/2009/11/lemon-parser-user-guide.html –> 中文版 (比較不完整)

http://freshmeat.net/articles/lemon-parser-generator-tutorial –> example

Lex and Yacc