♥ 學習筆記Learning 程式語言 Coding

[程式] 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://www.csie.ntnu.edu.tw/~ghhwang/course.html –> “lex 說明”lex 簡易手冊”
Reference book: lex & yacc (2nd Edition) lex & yacc by John Levine, Tony Mason, Doug Brown, O’Reilly. –> 總圖借得到

 

Lemon

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

Lex and Yacc

–> 有圖解動畫,另外稍微了解一下 Yacc 有助於撰寫 Lemon 的語法規則

About the author

蕾咪

蕾咪,來自台東,卻不定期旅居歐洲的工程師女孩,身兼作家、部落客、創業家等多重身份。畢業於台大電子所,曾在義大利商與美商擔任研發工程師;走訪世界後,發現對台灣有段割捨不了的愛,讓我們一起努力成為想要的自己吧!:) 合作邀稿請聯繫:ramihaha@gmail.com

Leave a Comment