Formal language的啟發

前言：
這個學期四個課，我都很想上。因為都是很精彩的課程。
後來，得知OS是只上最後幾課，擔心沒辦法跟上而放棄。
而Formal language看起來很數學，我後來也放棄了。
之後，有去旁聽了幾次，覺得formal language雖然很數學，但是應該要學的。
後悔已經來不及啦。
我只旁聽到DFA及GNFA，不過只有DFA有聽懂。
那DFA能夠做什麼哩？我想他如果可以辨認「有規則的字串」，
我想可以利用 state machine 的特性，在 log 裡面，辨認「有規則的長句子」。
DFA 是  deterministic finite automaton 的縮寫。它與 deterministic finite state machine 一樣，都是 finite state machine
你可以參閱 http://en.wikipedia.org/wiki/Deterministic_finite_state_machine
因為字串，送進 DFA 之後，只有 accept 及 not accept 兩個結果。
我的理解是，對於要辨認 log，在遇到 accept 的句子之後，還要繼續辨認下一個句子，
寫成可以辨認多個句子的應該不叫 DFA。雖然外表會長很像。我只會用較寬鬆的定義，叫他是一個 finite state machine。
比較精確的，我不知道要叫什麼。
如果把程式是一個 finite state machine，可以利用 transition ，在適當的 transtion 發出適當 event ，
就像 XML 裡的 SAX parser 一樣，我們專心處理每個 event 就可以有結果了。
也因此，event 的設計會是一個考量點。
現在來看看，我們要辨認的是什麼東西。

主題
我們要辨認的，是半導體產業中，用來與機台溝通的 message，很可惜的是，雖然有 SML 的定義，
但當 message 顯示在 log 裡，這個部份卻沒有規範。所以每一家的 log 雖然長得都很像，但是不一定完全一樣。
那些不一樣，就會造成困擾。這個問題這裡沒有要解決，雖然它是一個問題。
最簡單的解決方式就是對不同長相的，就都寫一個。(離題了)

04/01/29 15:05:15 (5005) Received Primary Message...
04/01/29 15:05:15     <S6F11 W
04/01/29 15:05:15         <L[3/1]
04/01/29 15:05:15             <U4[1/1] 3>
04/01/29 15:05:15             <U4[1/1] 1001>
04/01/29 15:05:15             <L[1/1]
04/01/29 15:05:15                 <L[2/1]
04/01/29 15:05:15                     <U4[1/1] 905>
04/01/29 15:05:15                     <L[2/1]
04/01/29 15:05:15                         <A[16/1] "2004012915072111">
04/01/29 15:05:15                         <U1[1/1] 1>
04/01/29 15:05:15                     >
04/01/29 15:05:15                 >
04/01/29 15:05:15             >
04/01/29 15:05:15         >
04/01/29 15:05:15     >
04/01/29 15:05:15 Received (GEM compliant) Event Report . (S6F11: length = 47)
04/01/29 15:05:15 (5005) Sending Reply Message...
04/01/29 15:05:15     <S6F12
04/01/29 15:05:15         <B[1/1] 0x00>
04/01/29 15:05:15     >

以上面這段 message 來說，我們不要每行前面的時間日期，只要 message 的內容。
一個 message <L[3/1] 到 Received (GEM compliant) Event Report 前面第二行那一個 >
我設計的 state machine 的圖如下：

Option Explicit
Dim c_s As String

Event ListBegin(l As Long)
Event ListEnd()
Event PError(ErrorName As String)
Event ItemFind(Name As String, Value As String, Length As Long, isArray As Boolean)



Function init(s As String)
c_s = s
End Function

Function action()
If Len(c_s) = 0 Then
    RaiseEvent PError("SourceEmpty")
End If


Dim ItemName As String
Dim ItemValue As String
Dim ItemIsArray As Boolean

Dim l As Long
Dim st As Integer
Dim i As Long
Dim checkString As String
st = 1
l = 0
For i = 1 To Len(c_s)
    checkString = Mid(c_s, i, 1)
    Select Case st
        Case 1
            If checkString = "<" Then
                st = 2
            End If
        Case 2
            If checkString = "L" Then
                st = 3
                l = l + 1
                RaiseEvent ListBegin(l)
            End If
            If checkString = "I" Then
                ItemName = checkString
                st = 4
            End If
            If checkString = "U" Then
                ItemName = checkString
                st = 4
            End If
            If checkString = "A" Then
                ItemName = checkString
                st = 4
            End If
            If checkString = "B" Then
                ItemName = checkString
                st = 4
            End If
            If checkString = "F" Then
                ItemName = checkString
                st = 4
            End If
            If st = 2 Then st = 1
        Case 3
            If checkString = ">" Then
                st = 5
                l = l - 1
                RaiseEvent ListEnd
            End If
            If checkString = "<" Then
                st = 2
            End If
        Case 4
            If checkString = "1" Or checkString = "2" Or checkString = "4" Or checkString = "8" Then
                st = 41
                ItemName = ItemName & checkString
            End If
            If checkString = "[" Then
                st = 42
            End If
            If checkString = "O" Then
                st = 401
                ItemName = ItemName & checkString
            End If
        Case 401
            If checkString = "O" Then
                st = 402
                ItemName = ItemName & checkString
            End If
        Case 402
            If checkString = "L" Then
                st = 403
                ItemName = ItemName & checkString
            End If
        Case 403
            If checkString = "E" Then
                st = 404
                ItemName = ItemName & checkString
            End If
        Case 404
            If checkString = "A" Then
                st = 405
                ItemName = ItemName & checkString
            End If
        Case 405
            If checkString = "N" Then
                st = 41
                ItemName = ItemName & checkString
            End If
        Case 41
            If checkString = "[" Then
                st = 42
            End If
        Case 42
            If checkString = "]" Then
                st = 43
            End If
        Case 43
            If checkString = " " Then
                st = 44
            End If
            If checkString = ">" Then
                st = 6
                RaiseEvent ItemFind(ItemName, "", 0, False)
            End If
        Case 44
            st = 45
            ItemValue = checkString
        Case 45
            If checkString = ">" Then
                st = 6
                RaiseEvent ItemFind(ItemName, ItemValue, Len(ItemValue), False)
            Else
                ItemValue = ItemValue & checkString
            End If
        Case 5
            If checkString = "<" Then
                st = 2
            End If
            If checkString = ">" Then
                st = 5
                l = l - 1
                RaiseEvent ListEnd
            End If
        Case 6
            If checkString = "<" Then
                st = 2
            End If
            If checkString = ">" Then
                st = 6
                l = l - 1
                RaiseEvent ListEnd
            End If
    End Select
Next

End Function
結論
這個程式，可以忽略每行的時間，也忽略掉，每個 item 的長度與大小。(也就是[X/Y]裡面的數值。)
也沒有找出 stream function 的編號，單純只有內容。
如果 item 是 array 也會忽略。還不是非常完整的。
其中 state 非常多，因為一個 state 只看一個字元，一次只有一個 activate state，所以 state 必須很多。
程式及圖看起來就很複雜，要改就不容易。
目前，主要的幫助針對一個 message 來做轉換格式給另一個 parser (HostDeveloper (R))來做處理。
動作是人工剪下一個 message ，補上 stream function，再餵給另一個 parser。
雖然只是減少了其他修剪的需要，但省下不少時間。
雖然只是一個 parser，但是它可以用來做格式轉換、trace log，一舉兩得，只要配合不同的事件處理方式即可。


討論
因為我只學了DFA，它就只有一個 state 是 activate，所以我的 state machine 也只有一個 activate state，造成圖看來還滿複雜的。
尤其是遇到要比對某些字串的時候，會多很多 state，來負責辨認。
你會發現，像這種要改 state machine，很可怕。每個有影響到的 state 及 transition，都要考慮好。
寫成程式，更難看得懂。據說，有程式可以把畫好的state machine 變成程式碼，要是有的話，那真是太方便啦！

以目前的這段程式，可以改善的地方有：
1、辨認 stream function，如此就可以多個 SECS message 同時辨認。
2、要加上，SECS message 的 array 形態辨認。
3、state 的描述要更嚴謹，以免錯誤辨認。

而可以延伸的方向有：
1、寫出多個 active state 的 state machine，例如 NFA
2、把每個 state 分開在不同的程式片段中(例如，把 state 包裝成一個物件)，可提高程式的 reuse 的機會。
3、改以每一行來做辨認的基本單位，也許會加快程式執行。


最後
其實我應該先去看看人家 xml parser 的 SAX parser 怎麼做的才對。

本文授權為 CC。
創作者介紹
創作者 betaparticle的部落格 的頭像
betaparticle

betaparticle的部落格

betaparticle 發表在 痞客邦 留言(0) 人氣( 288 )

▲top

請先 登入 以發表留言。

Recommended

你可能也喜歡

為你精選 3 篇值得延伸閱讀的內容

載入推薦文章中...
目前沒有推薦文章