常常看到別人寫的程式裡面有
return token === TokenType.EQUAL;
這跟
return token == TokenType.EQUAL;
有什麼不同？
依據http://www.w3schools.com/js/js_comparisons.asp的說明
=== is exactly equal to (value and type)
所以
x = 5
x===5 is true
x==="5" is false
那我推測
x == 5 is true
x == “5” 應該是 true。
一般資料都說，遞迴下降的程式寫法，就是為每個非終端符號寫一個 function 來做 parse。
這裡提醒一些小事項。
(1) 準備兩個function，一個 accept，一個 expect。(註1)
def accept(s):
global sym
if sym[0] == s:
print 'accept',sym
getsym()
return True
return False
def expect(s):
if accept(s):
return True
print "expect: unexpected symbol"
global sym
print sym
sym = None
return False
這些會有幾個用途：
(a)處理可省略項目的 rule，例如：
<host_type_msg> ::= eap_log_1 [xml_transaction]
accept 的意思是，如果傳入參數，是預期的就回 True，input 往下移動一個。
如果不是預期的，就回 False。呼叫的人看到回傳是 False 不停止動作。
expect 的意思是，如果傳入參數，是預期的就回 True，input 往下移動一個。
如果不是預期的，就回 False。呼叫的人看到回傳是 False 則停止動作。
所以 host_type_msg 的 parse function 寫成
def host_type_msg():
if expect("eap_log_1"):
accept("xml_transaction")
return True
else:
return False
(b)accept可當做look ahead的測試工具，例如：
<secs_msg_item> ::= secs_item_a
| secs_item_u
| secs_item_b
| secs_item_bool
| secs_item_f
| secs_item_i
| secs_list_start [secs_comment] {<secs_msg_item>} secs_list_end
secs_msg_item 的 parse function 裡面可寫成
if accept("secs_item_a"):
return True
elif accept("secs_item_u"):
return True
....省略
elif accept("secs_list_start"):
accept("secs_comment")
....省略
(2)每個 parse function 要回傳 True 或 False。
基本上，可以不用每個 parse function 都加。
但是有「出現0次或多次」這種規則的 parse function，需要回傳值才知道什麼時候要停下來。
因為這個規則的程式會轉換成迴圈，parse成功，才需要再 parse 否則就要停。
例如：
{<secs_msg_item>}
會轉成
r = secs_msg_item()
while r == True:
r = secs_msg_item()
(3)因為以下的規則，必須使用 look ahead。
<desc> ::= <secs_msg_name> colon <secs_SxFy_sym>
| normal_word {normal_word}
<secs_msg_name> ::= normal_word
因為 secs_msg_name() 的呼叫結果是 expect("normal_word")
在看到 input 的 normal_word 時，無法決定要呼叫 secs_msg_name()
還是 expect("normal_word")，可是往下看一個 input 若是 colon 就呼叫 secs_msg_name()，
否則呼叫 accept("normal_word")。
把 grammar 跟程式兩個互相比較，你就會知道有多直覺(前提是寫一些方便函數)
========================================================
<msg> ::= timestamp <secs_type_msg>
| timestamp <host_type_msg>
--------------------------------------------------------
def msg():
print 'msg()'
if expect("timestamp"):
if sym[0]=="eap_log_1":
host_type_msg()
else:
secs_type_msg()
print 'msg() complete'
========================================================
<host_type_msg> ::= eap_log_1 {xml_transaction}
--------------------------------------------------------
def host_type_msg():
print 'host_type_msg()'
expect("eap_log_1")
accept("xml_transaction")
========================================================
<secs_type_msg> ::= <desc> secs_comment <secs_msg>
--------------------------------------------------------
def secs_type_msg():
print 'secs_type_msg()'
desc()
accept("secs_comment")
secs_msg()
========================================================
<desc> ::= <secs_msg_name> colon <secs_SxFy_sym>
| normal_word {normal_word}
--------------------------------------------------------
def desc():
print 'desc'
global input_index
_sym = lookahead()
if _sym[0]=="colon":
secs_msg_name()
expect("colon")
secs_SxFy_sym()
else:
r = accept("normal_word")
while r == True:
r = accept("normal_word")
========================================================
<secs_SxFy_sym> ::= secs_SxFy {<secs_w_bit>}
--------------------------------------------------------
def secs_SxFy_sym():
print 'secs_SxFy_sym()'
expect("secs_SxFy")
secs_w_bit()
========================================================
<secs_msg_name> ::= normal_word
--------------------------------------------------------
def secs_msg_name():
print 'secs_msg_name()'
expect("normal_word")
========================================================
<secs_w_bit> ::= normal_word
--------------------------------------------------------
def secs_w_bit():
print 'secs_w_bit'
accept("normal_word")
========================================================
<secs_msg> ::= {<secs_msg_body>} secs_end
--------------------------------------------------------
def secs_msg():
print 'secs_msg()'
if accept("secs_end"):
pass
else:
secs_msg_body()
accept("secs_end")
========================================================
<secs_msg_body> ::= <secs_msg_item> {secs_comment }
--------------------------------------------------------
def secs_msg_body():
print 'secs_msg_body()'
secs_msg_item()
accept("secs_comment")
========================================================
<secs_msg_item> ::= secs_item_a {secs_comment}
| secs_item_u {secs_comment}
| secs_item_b {secs_comment}
| secs_item_bool {secs_comment}
| secs_item_f {secs_comment}
| secs_item_i {secs_comment}
| secs_list_start {secs_comment} {<secs_msg_item>} secs_list_end
--------------------------------------------------------
def secs_msg_item():
print 'secs_msg_item()'
if accept("secs_item_a"):
accept("secs_comment")
return True
elif accept("secs_item_u"):
accept("secs_comment")
return True
elif accept("secs_item_b"):
accept("secs_comment")
return True
elif accept("secs_item_bool"):
accept("secs_comment")
return True
elif accept("secs_item_f"):
accept("secs_comment")
return True
elif accept("secs_item_i"):
accept("secs_comment")
return True
elif accept("secs_list_start"):
accept("secs_comment")
r = secs_msg_item()
while r == True:
r = secs_msg_item()
expect("secs_list_end")
return True
else:
return False
========================================================
相信有仔細看程式的人會注意到，怎麼 accept 就只是把 input 接受而已，
怎麼沒有 output ？
對的，再來就是要產生 parser 的 output，通常是長成 tree，
叫做 contrete syntax tree 或 parse tree 或 parsing tree。
或者是abstract syntax tree(把 parse tree 中，將來不需要用到的資訊去除)。
這兩種 tree 的差異，我認為只是相對的。程式可以控制你想表現的是哪一種 tree。
所以重點是要把 parse 的結果表現成 tree，讓後續的動作能利用。
當然把所有accept 的 token 都呈現的 tree 是 parse tree。
我們先從這裡開始。
問題是這樣出現的：
我在 windows xp 底下的 cmd 環境，用 ftp 指令連到 AIX 環境。
put 檔案之後，要改遠端的檔案的讀寫權限為 755。
直接再下 chmod 755 檔案
會出現 invalid command。
先用 remotehelp 查一下，有支援 SITE，而且 SITE 也支援 CHMOD，但直接下 site chmod 755 檔案 也失敗。
後來看到 http://www.net527.cn/a/caozuoxitong/Linux/2011/0203/16360.html
這裡試了一些 quote 或是 literal 的組合還是失敗。
但是，從這裡出發是對的，他應該少試了我成功的組合。
quote site chmod 755 檔案
quote 及 literal 都是傳送指令，我猜一定要加上 SITE 才能讓遠端執行遠端允許的指令，
加上要執行的指令後，也一定要把該指令的參數加上去，
不加完整的話，只下 quote site chmod
遠端也只回傳 500 ‘CHMOD’: command nto understood，
還以為遠端不支援呢。
這次有找到新的參考，是國內大學(註1)的講義，因此把一些英文名詞換成中文來寫。
文章也比較順眼一點。
parser 的工作是語法分析(syntactic analysis)，要完成這項工作，
需要兩個先決條件，一個是字彙分析(lexical analysis)的結果，
一個是文法(grammer)已經設計完畢。文法是由一組推導(derivation)所形成。
用白話一點的方式來說，parser的工作就是
找出字彙分析(lexical analysis)的結果是由哪些推導、依據什麼順序產生的。
找出這些推導及順序，記錄下來這些推導及順序，
就是所謂的建立 parse tree 了。
字彙分析(lexical analysis)的結果，之前已經有提過。
所以現在要來看一下文法的表示方式。
在一般的編譯器課程裡，大多使用的是 BNF 的表示方式(註2)。
之前的課本提到的方式則是CNF(註3)。
BNF 的表示方式的元素有(1)終端符號、(2)非終端符號、(3)指定符號、(4)選擇符號。
一個推導(derivation)規則，可以表示成
<符號> ::= __expression__
其中，<符號> 這是指非終端符號，所有的非終端符號都用 < > 括起來。
::= 這是指定符號，用來將表示式分成左邊跟右邊。
| 這個是選擇符號。
其他出現的符號，都算是終端符號。
在指定符號的左邊，只能出現非終端符號，
在指定符號的右邊，叫做 expression，因為他可以是所有符號的組合。
一個推導規則表示，在左邊的非終端符號，可以被替換右邊的 expression。
因為這個操作規則，只出現在右邊的符號，永遠不能被替換，
不能再被推導的符號叫做終端符號。
選擇符號是用來分隔不同的選擇。
一個綜合範例：
<A> ::= <B> | <C> + <D>
<A> <B> <C> <D> 是四個終端符號
+ 是終端符號
| 是分隔符號
這個規則，就是表示<A> 可以被替換成 <B> 或著是 <C> + <D>
一般而言，一組推導之中，列在最上面的那一個與別人不太一樣。
因為推導過程需要開始，而最開始的非終端符號就需要寫在最上面。
有了文法，就需要有尋找推導規則的方法，這個方法叫做剖析方法(parse)
有分成LL及LR兩大類。
LL = parse from left construct leftmost derivation
LR = parse from left construct rightmost derivation
因為文法的表示方式，可以表達到 context-free 語言，
而單純的 LL 及 LR 的尋找方法無法涵蓋整個 context-free 語言。
因此，大多的實作上，都要使用到LL(1) 或 LALR 來滿足實際需求。
選擇 LL 或是 LR 對於文法的設計，也會有一點點的影響。
例如使用 LL 方法的時候會遇到的 left recursion 的問題，
就要在設計文法的時候避開。
簡單講完文法設計的原則，就來試試設計自己的文法。
字彙分析(lexical analysis)的結果要回頭看一下 scanner 那篇的最後。
我設計文法如下：
<msg> ::= timestamp <desc> secs_comment <secs_msg> | timestamp eap_log_1 xml_transaction | timestamp eap_log_1
<desc> ::= <secs_msg_name> colon secs_SxFy <secs_w_bit> | <secs_msg_name> colon secs_SxFy
<secs_msg_name> ::= normal_word
<secs_w_bit> ::= normal_word
<secs_msg> ::= <secs_msg_body> secs_end | secs_end
<secs_msg_body> ::= <secs_msg_item> secs_comment | <secs_msg_item>
<secs_msg_item> ::= secs_item_a | secs_item_u | secs_item_b | secs_item_bool | secs_item_f | secs_item_i | secs_list_start secs_comment <secs_msg_item> secs_list_end | secs_list_start <secs_msg_item> secs_list_end | secs_list_start secs_comment secs_list_end | secs_list_start secs_list_end
接下來挑選最符合人的思考的剖析方法叫做遞迴-下降方法，屬於LL類型。
因為這個方法想法直接，用程式來實作時非常直覺，
據說 c# 的 parser 也是用這種方法寫的。
在設計文法的時候儘量把同一個非終端符號寫在一行，
接下來檢查幾個項目，減少實作上的問題：
(1)檢查一下有無 left recursion 問題。
left recursion 的問題是就文法中，左邊的符號跟右邊的第一個符號一樣，
例如：
<a> ::= <a> + <b>
或是
<a> ::= <a> + c
(2)檢查文法中，有無需要「選擇」，
例如以下的文法，不先偷看一下，沒辦法知道選哪一個推導：
<desc> ::= <secs_msg_name> colon secs_SxFy <secs_w_bit> | <secs_msg_name> colon secs_SxFy
所以LL(0)是不太可能的。
如果希望LL(1)就能夠剖析，還是需要再改寫
<desc> 可以有兩個選擇，這兩個選擇前面都一樣，只差在尾巴，
一個有<secs_w_bit>，一個沒有。要先偷看的話，是要看到 4 個之後。
所以改寫成
<desc> ::= <secs_msg_name> colon <secs_SxFy_sym>
<secs_SxFy_sym> ::= secs_SxFy | secs_SxFy <secs_w_bit>
同理：
<msg> ::= timestamp <secs_type_msg>| timestamp <host_type_msg>
<secs_type_msg> ::= <desc> secs_comment <secs_msg>
<host_type_msg> ::= eap_log_1 | eap_log_1 xml_transaction
(3)把「出現0次或1次」、「出現0次或多次」、「出現1次或多次」的關係整理一下。
這一步需要用到多一點的BNF變種，{ 出現0次或多次 }、[出現0次或1次]，
這樣寫在實作時也方便參考。
例如：
<secs_msg> ::= <secs_msg_body> secs_end | secs_end
改成
<secs_msg> ::= {<secs_msg_body>} secs_end
整理完的文法如下：
<msg> ::= timestamp <secs_type_msg>
| timestamp <host_type_msg>
<secs_type_msg> ::= <desc> secs_comment <secs_msg>
<host_type_msg> ::= eap_log_1 {xml_transaction}
<desc> ::= <secs_msg_name> colon <secs_SxFy_sym>
| normal_word {normal_word}
<secs_SxFy_sym> ::= secs_SxFy {<secs_w_bit>}
<secs_msg_name> ::= normal_word
<secs_w_bit> ::= normal_word
<secs_msg> ::= {<secs_msg_body>} secs_end
<secs_msg_body> ::= <secs_msg_item> {secs_comment }
<secs_msg_item> ::= secs_item_a {secs_comment}
| secs_item_u {secs_comment}
| secs_item_b {secs_comment}
| secs_item_bool {secs_comment}
| secs_item_f {secs_comment}
| secs_item_i {secs_comment}
| secs_list_start {secs_comment} {<secs_msg_item>} secs_list_end
接下來就可以開始把 parser 的程式寫出來
(註1)：http://www.nhu.edu.tw/~ycliaw/Teaching/9901/SP/05_Compiler.pdf
(註2)：http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form
(註3)：http://en.wikipedia.org/wiki/Chomsky_normal_form
前面提到 scanner 的工作，是詞法分析，
針對這項工作，要依序解釋每個詞意義，也就是轉換成 token。
token 將是 parser 處理時的最小單位，scanner 的這項工作做不好，parser 也很難做得好。
因此 scanner 與 parser 通常是排在一起，因為相依性很高。
----------------------
程式的設計路線通常是跟實作路線反過來，我們在設計的過程會先想到需求，
把需求從抽象到實際從上到下一一描述出來，
而實作的時候，卻要由下往上一一實作，才能組合回去。
物件導向的程式語言，是可以幫上一點忙，一開始設計抽象物件，
但是程式要能夠跑起來，物件實作還是要寫好才會能夠動。
寫文章要講求思考脈絡又要講求實作順序，還真的傷腦筋。
----------------------
接下來要為 scanner 準備好它所需要的 function 及 class，
包含字串辨認及字串確定兩個工作。
scanner 要做的字串辨認工作，
要準備 Token 類別來儲存「字串辨認定義」、「字串辨認結果」的資訊及「字串辨認」的操作。
字串辨認結果，要包含字串類別，字串值。
舉一個 timestamp 的 Token 類別來說
Token 定義是 regular express 的 '[0-9]+-[0-9]+-[0-9]+-[0-9]+:[0-9]+:[0-9]+ '
Token 名字是 "timestamp"
Token 的 test 方法，會比對來源字串是否符合 pattern。
如果辨認成功，token.reg 為 true，token.value 為所要的值
因為要連續辨認，所以 test 的回傳值是一個新的 token 物件。
原來的物件留著下一次比對用。
為了輸出的時候，知道 Token 是在檔案的第幾個 byte 及第幾行，
也多兩個欄位 Token.cur_pos 及 Token.cur_line 來儲存訊息。
有人會想用 regular express，但是在 MIT 課程裡有特別提到
它無法應付 recursive，這是什麼意思呢？
我認為是這樣的。
例如，我們有兩個 token，一個是 timestamp token，及 number token。
在 log 裡，2011-06-22-07:56:06 會辨認到一個 timestamp token，及數個 number token。
依照最長辨認的原則，應該是選擇 timestamp token。
那要找到這裡面的年，月，日…等等的 number token，就沒辦法把它分開。
只得把它辨認為 number token，也就是把 timestamp token 的定義拿掉。
在 scanner 階段就無法區分 number token 是否為年，月，日…等等。
要等到 parser 階段才能決定。
但是，若辨認工作是自己實作特殊的 DFA 或 NFA，就可以自行增加 stack、queue 或 tape 等等不同的操作，
提供特殊辨認及輸出。例如處理 non-regular language，{a{n}b{n}}，
只要在 DFA 裡面加一個變數記一下看到a有幾次，就可用程式的方法解決這個問題。
這個問題想到這裡就好，因為我們目前只求「大部 分解」因此，
timestamp token 裡面的年，月，日…等等就先不理會。
我個人認為若有必要，可以用二次 scan 來解決。
目標是先把大區塊標顏色，token 切太細，parser 的規則就會變多。
如果 token 切很細，parser 的規則又不想寫很多，那標出來的顏色就是花花緣緣的。
這是一個「資源取捨」問題。
因應各種辨認的問題，我們設計的 Token 類別實際上是個抽象類別。
如果是可以用 regular express 辨認的，就用 Token_RE 類別，
它的實例化方法需要一個 regular express，它的 test 方法就是該 regular express 來辨認。
另外，我們會遇到 XML transaction，因此特別寫了一個 Token_XML 類別，
把 root element <Transaction> 整個視為一個 xml transaction token。
在我們的範例 log，我就定了 16 個 token，實際有用到的是 15 個。
NULL_TOKEN = 0 ### 沒用到
TIMESTAMP_TOKEN = 1
SPACE_TOKEN = 2
NWORD_TOKEN = 3
COLON_TOKEN = 4
SECSSTREAMFUNCTION_TOKEN = 5
SECSCOMMENT_TOKEN = 6
WHITESPACE_TOKEN = 7
SECSEND_TOKEN = 8
SECSLISTSTART_TOKEN = 9
SECSITEMA_TOKEN = 10
SECSLISTEND_TOKEN = 11
EAPLOG1_TOKEN = 12
XMLTRANSACTION_TOKEN = 14
SECSITEMU_TOKEN = 15
SECSITEMB_TOKEN =16
SECSITEMBOOL_TOKEN = 17
這 15 個 token 裡 XMLTRANSACTION_TOKEN 是 Token_XML。其他都是 Token_RE，
Token_RE 的 test 方法，我偷懶用了 python 的 re module 的 match。
因為每次傳入的都是要從頭開始比，所以是 match 而不是 search。
class Token_RE(Token_abs):
### 省略部份
def test(self,source):
r = self.p_compile.match(source)
if r == None:
self.reg = False
self.value = ""
a = Token_RE(self.token_name,self.token_index,self.re_pattern)
a.reg = self.reg
a.value = self.value
return a
else:
self.reg = True
if len(r.groups())>0:
self.value = r.groups(0)[0]
else:
self.value = r.group()
a = Token_RE(self.token_name,self.token_index,self.re_pattern)
a.reg = self.reg
a.value = self.value
return a
scanner 主要工作在 read 方法，大部分的實作都是執行一次 read 方法，就傳回一個 token。也就是在這裡就要做字串確定的工作。
在執行 read 方法之前，要把 log 讀進來，指定給 source 這個變數。
在執行 read 方法的時候，scanner 把 source 給 15 個 token 比對，找出比對成功的。
然後選擇比對結果最長的一個 token 當成辨認結果。
接下來，把 source 切掉已辨認的部份，剩下未辨認的部份。
傳回辨認結果之前，要順手把 cur_pos 及 cur_line 算完記下來，下次要用，
也要把值存進 token 裡，讓呼叫的人知道。
然後才是把 token 傳回去。
read 方法回傳 None 的情況有三個，代表 scanner 要停止辨認。
一個是 source 長度為零，因為上次辨認最後了。
一個是所有的 token 都沒有辨認到。
最後一個就是辨認結果的字串長度為零，這是一個很特別的狀況，也要停止辨認。
因為 regular express 有使用到 star operation 的時候，
也就是比對到 empty string 的狀況。
依照 scanner 的設計，empty string 長度為零，
source 等於沒有進行切除已辨認的動作，
下次 read 方法再執行時， source 還是原來的 source，
辨認結果還會是一樣的 empty string。
因此針這個情況要停下來，以免進入無窮迴圈。
class Scanner:
### 省略部份
def Read(self):
if len(self.source) == 0:
return None
r = []
for i in self.tokens_info:
r.append( i.test(self.source) )
r2 = []
resultlength=[]
for i in r:
if i.reg == True:
r2.append(i)
resultlength.append(len(i.value))
print ' match:%s' % i
if len(resultlength) == 0:
print 'source a:%s' % self.source[:30]
print 'pos:%s' % self.cur_pos
print 'no match!!!!'
return None
maxlen = max(resultlength)
if maxlen == 0:
print 'source a:%s' % self.source[:30]
print 'pos:%s' % self.cur_pos
print 'no match!!!!'
return None
self.source = self.source[maxlen:]
#print 'source b:%s' % self.source[:30]
#print "new:%s\nold:%s" % (self.source[:40],self._keepsource[:40])
#print r2
for i in r2:
if len(i.value) == maxlen:
i.cur_pos = self.cur_pos
i.cur_line = self.cur_line
r3 = i
self.cur_pos += maxlen
line_object = re.findall("\\n",i.value)
self.cur_line += len(line_object)
break
return r3 #r2[0]
scanner 使用方法，就是加入 token 定義，設定 source 的內容，
執行 read 方法直到回傳為 None。
每一次拿到的 token，裡面的資訊都有 token 的名字、內容、位置及行號。
接下來就是交給 parser 處理。
### token 定義
re_1 = '[0-9]+-[0-9]+-[0-9]+-[0-9]+:[0-9]+:[0-9]+'
lex_timestamp = Token_RE("timestamp",TIMESTAMP_TOKEN, re_1)
### 其餘省略
### 加入 token 定義
s = Scanner()
s.AddTokenDefinition(lex_timestamp)
### 其餘省略
### 設定 source 內容
s.SetSource(source)
### 讀取 token
r = s.Read()
while r != None:
count += 1
if r.token_index != 2 and r.token_index != 7: ### 不想印出空白及分行
print ' result(%s):%s' % (count,r)
因為還沒有想到 parser 要怎麼辦，所以先把 token 全寫到檔案裡，用三個連續分行符號分開。像這樣：
tokens(1):timestamp,1,True,0,0,2011-06-22-07:56:06
tokens(3):normal word,3,True,20,0,AYT_Host
tokens(4):colon,4,True,28,0,:
tokens(6):secs SxFy,5,True,30,0,'S1F1'
tokens(8):normal word,3,True,37,0,W
tokens(10):secs comment,6,True,39,0,/* Name=AreYouThere_Host Dir=2 Header=[00 00 81 01 00 00 00 01 BA A3] Rcvd=2 Time=07:56:06 TID=28848 */
tokens(12):secs end,8,True,143,1,.
tokens(14):timestamp,1,True,145,2,2011-06-22-07:56:06
tokens(16):normal word,3,True,165,2,OLD
tokens(17):colon,4,True,168,2,:
在 MIT 的課程「6.035 電腦語言工程(SMA 5502),2005秋季課程」(註1)提到
課程裡要完成的 5 項工作，連接起來就會完成一個編譯器。
這 5 項工作是
掃描器和解析器、
語義檢查器、
代碼生成器、
資料流程優化器、
指令優化器
編譯器的工作裡，一開始是 scanner 及 parser (掃描器和解析器)。
scanner 的工作是把一連串的字元(character)，轉換成一連串的token。(註2)(註3)
stream of characters --> stream of tokens
sequence fo tokens 是compiler所在乎的部份。
<---
(註1)：http://www.myoops.org/main.php?act=course&id=1946
(註2)：來源：http://www.myoops.org/twocw/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-035Fall-2005/EF1122A1-77A5-49CA-8BF6-EF6C9AC64F42/0/2scanerparsr_prj.pdf
(註3)：token 的定義是可被當成處理的單元，它是由一連串的字元(sequence of character)所組成。
---->
parser 的工作是把一連串的token轉換成語言中的entities。
且把language的結構建構出來，通常的表達方式是樹狀結構。
在scanner及parser所產生的結果，可以用來替原始碼上色(註4)。
<----
(註4)：http://www.cnblogs.com/Ninputer/archive/2011/06/07/2074632.html
---->
從字元轉換成 token 需要辨認recognize。
這個層級通常在regular language的範圍內。因此使用 DFA，NFA 的方式來實作。
或者利用現成的 regular expression 模組來做，但是無法處理 recursive。
所以自己寫 DFA/NFA 來處理是必須要會的。
例如一般程式語言會有保留字，及變數id。
這兩個是不同的意義，遇到保留字要做的事與遇到變數要做的事是不同的。
像是在c++語言裡面
string string1;
DFA，NFA做的工作是辨認，有一個 string 的字出現在第0個位置，是保留字。
有一個 string1 的字出現在第7個位置，是變數id
因為規則不同，所以需要兩個 DFA/NFA 來處理。
而一般的程式語言，會需要很多的意義。例如：
保留字
變數id
註解
常數
空白
分行
...
之前課本(註5)學寫的 DFA/NFA 的能力，是等待輸入結束後，
看最後一個state留在哪裡來判斷是否有被辨視到。
而對應於整串的程式語言，就不能等輸入結束後才來判斷。
針對這樣的需求，DFA/NFA 需要被修正。
需求是輸入還沒結束前，就判斷是否有辨認到屬於哪個類別。
並且在多個辨認都成立的狀況下，選擇最長辨認。
舉前面的例子，當一看到 string 的時候就當做辨認到 string 的話，
string string1 會被認為兩個 string 的保留字及一個 1 的常數。
因此， DFA/NFA 要一直辨視到失敗為止，
然後檢查最後一個 accept 的 state 是否存在。
若存在，才能算是正確的辨認。
<---
(註5)：introduction to the theory of computation
--->
一個來自MIT上課程中，說明的 scanner 的工作應該是做到以下的轉換：
語言範例：
class Program {
// uninformative comment
void main() {
callout("printf", "%d", 42);
}
}
轉換結果：(原始結果沒有換行，為了排版才換行)
CLASS IDEN("Program") LBRACE VOID IDEN("main") LPAREN RPAREN LBRACE
CALLOUT LPAREN STR("printf") COMMA STR("%d") COMMA NUM(42) RPAREN
SEMI RBRACE RBRACE
在這個講義中，有趣的是，本來要用手寫的 scanner，後來可用 JLex 產生。
到了 parser 的階段，parse algorithm 有幾種，分類的方法也有好幾種。
按照處理 input 及 derivation 的方向來分，傳統的有 LL，LR。
按照組成 tree 的順序來分，有 top-down 及 bottom-up。
按照處理 transition 的方法來分，有 tabular 及 non-tabular。(註6)
按照 parser code 是誰寫的有分，hand-made 及 generator。
<----
(註6)：http://people.few.eur.nl/pijls/parsing.pdf
---->
LL parser指的是從左邊開始處理字元(parse from left)，
從左邊開始建構(construct leftmost derivation)，
它自然就是屬於 top-down parser。
這種的 parser 可以使用 recursive descent，程式碼可用人來寫。
也可以轉化 grammer 成 parsing table 來查詢。
parsing table 可用手工或是用 generator 產生。
LL recursive descent 這種方法可以處理的 language
只是 context-free language 的一部份子集而不是全部，
因此有強化版本的 LL(k)版本，這種方法，會先偷看下 k 個輸入來判斷 state，
大多教科書舉例都是 LL(1) 的。
但是 LL(k) 仍然無法滿足所有的 context-free language。
(再延申下去還有LL(*)，使用 regular expression 檢查下個 input)
兩種 LL parser 在製作 grammer 的時候，要注意 left recursion 的問題，
有固定的方法重排 grammer 以解決這個問題。
否則會出現 conflicts 的問題。
因為 LL 的 parser 處理邏輯非常直覺，教學上常會拿來當作範例，
容易用人來寫，也比較容易被人看懂。
(當然也有用 parser generator 產生的 LL parser。)
另一種傳統是 LR parser，從左邊開始處理字元(parse from left)，
從右邊開始建構(construct rightmost derivation)，
是屬於 bottom-up parser。
這種的 parser 可以使用 recursive ascent
但是大多數的實作上都是使用 generator 產生 parsing table，
所以大多數的是 tabular parser。
LR 在不進行偷看動作(lookahead)的時候(也就是 LR(0))，處理的 language 就比較廣，
但是還是會遇到無法處理的 grammer。
LR 的 parser 的程式碼相對比較複雜，比較難用人來寫，
同時 parser 的錯誤與 grammer 的錯誤比較難分別，
在 parse input 的時候可以產生比較清楚的錯誤訊息，但是難在 parser 要判斷發生哪種錯誤。(註7)
<----
(註7)：http://en.wikipedia.org/wiki/LR_parser
---->
不是資訊科系出身的我，非常敬畏compiler。
因為要看得懂人寫的東西，是非常困難的，
而compiler就是能夠看得懂。
這次研究的開頭是因為看到 google 啟動一個 traceur 的計畫。
這個計畫要介紹給大家 google 對於 javascript 語言的進化的規劃。
讓大家了解，新的 javascript 會有什麼新的語法及功能、
新的語法帶來什麼方便。
這個計畫，寫了一個 javascript to javascript 的轉換，
把新語法對應到舊語法。而且這工作是用 javascript 寫的。
這很可愛！
擴展一個語言的新功能，是重寫 compiler，這很正常。
可以用原來的語言再寫一個新的 compiler，這就有點可愛，不覺得嗎？
這一類的情況也不是只發生在這裡。
gnu 的 c/c++ compiler，python 的 pypy，也都是這一類的東西。
compiler 是一個很大的題目，陳公覺得我很無聊。
花這個時間能做出個 compiler 又怎樣？
是啊，以一個人來說，做出來的 compiler 應該也只是個玩具。
在這次研究中，我個人是希望，至少，
前面的 scanner + parser 階段，
可以開發個工具來 parse 工作上的 log，替 log 上色。
這個工具是吃 config 的，所以才要用到 compiler 的技術。
就不用每次換 log 都要重寫一次。
至於後續的部份，那就再看看囉。
