NFA的3种编码优劣,你喜欢怎么做?JAVA去掉了goto你喜欢吗?

instemast

(1)没有状态，用一层层if和while
(2)用状态变量和switch...case
(3)用goto跳转至某状态

首先，从思维逻辑上，我不喜欢(1)。
(1)可以说是把清晰的思维倒退会杂乱的硬编码。
手头有本书，也批评了(1)，前者用的是(2)

有意思的是，在我购买清华大学出版社的《编译原理》的之前，
我用的是近似于方法(2)的方法，虽然那时候还不知道DFA。

那本书上讲解了DFA，但是却用(1)这种方法。。。orz

DFA可以说是一个特殊的图灵机！ （虚线实线的问题先不考虑）
这种图灵机不允许在“边”上面进行 指针p 的左右移动。
只允许在“顶点”（某状态）上面统一进行。
实际上是一种简单化，可以认为，所有“边”都把指针向后移动。

RpgDIY写的比较早，没有用到真正规范的NFA。

在Kashier中，我写了一个NFA的变体，允许在“边”上决定 p 向左还是向右移动1字节。
我是为了从光标位置开始，最快搜索一个LRC歌词中的时间值。搜索方向可以变化。
当时考虑了一个NFA变体。实际上现在看来是一个货真价实的图灵机。而且十分简洁。
（代码先不慌写）

最近觉得，实际上 1,2 方法都不好。
(2)从逻辑上说 (2) 是分常好的方法！但是，性能呢？ 每次循环都必须做大量 case 判断。。。
有人说用函数指针数组，但是，进栈出栈会消耗很多时间。
函数指针是什么？不就是是代码段的地址吗，实际上用 goto 就可以搞定了。
（参见隔壁的“OBJ模型文件格式解析”）

是不是很快呢？ 可能你会中伤我说“怎么能这样用goto呢！”
但据我所知，C++还是有goto的。而且图灵机也应该这么做 （拿 IP 当我们的state寄存器）

但JAVA居然去掉了goto...orz

不过话说回来，从goto角度来说，(1)比(2)好多了，速度快，因为 if 不就是用跳转实现的吗。

。。我发誓下次决不手工编码了。。一定要用自动分析机。。草稿纸上画的图都要吐了。。

instemast

翻看Kashier代码，实际上我用了2个词法分析机。一次是找出 [] 中的数字，但不判断是否为合法的time。
这么做是有原因的。因为同样允许用户按 F5 在 "Go" 对话框里输入time字符串。
找出了[]中的数字之后，填写到 Go 对话框里，然后进行时间值的分析。

'找出光标附近的中的数字位置的图灵机。

Public Sub btGo_MouseUp(Button As Integer, Shift As Integer, x As Single, y As Single)
    gFrmMain.txKashi.SetFocus
    If Not (x >= 0 And x <= btGo.Width And y >= 0 And y <= btGo.Height) Then Exit Sub
    If Not gMedia.GetIsOpened Then Exit Sub
    If (Button And 1) = 0 Then Exit Sub
    Dim txKashi As RichTextBox
    Set txKashi = gKashi.GettxKashi
    Dim ascii As Integer
    Dim i As Long
    i = txKashi.SelStart + 1
    Dim leng As Long
    leng = Len(txKashi.text)
    Dim state As Integer
    state = 0
    Dim LArcPos As Long, RArcPos As Long
    Dim IsSeccessful As Boolean
    Dim counter As Long
    Do
        If i >= 1 And i <= leng Then
            ascii = Asc(Mid(txKashi.text, i))
        End If
        If state = 0 Then
            If i < 1 Then 'head
                IsSeccessful = False
                Exit Do
            ElseIf i > leng Then 'end
                state = 3
                i = i - 1
                GoTo Continue
            ElseIf (ascii >= CHAR_0 And ascii <= CHAR_9) Or ascii = CHAR_DOT Or ascii = CHAR_COLON Then
                i = i - 1
                GoTo Continue
            ElseIf ascii = CHAR_LARC Then
                LArcPos = i
                state = 1
                i = i + 1
                GoTo Continue
            ElseIf ascii = CHAR_RARC Then
                RArcPos = i
                state = 2
                i = i - 1
                GoTo Continue
            ElseIf ascii = 10 Or ascii = 13 Then
                state = 3
                i = i - 1
                GoTo Continue
            Else
                state = 3
                i = i - 1
                GoTo Continue
            End If
        ElseIf state = 1 Then
            If i > leng Then 'end
                state = 3
                i = i - 2
                GoTo Continue
            ElseIf (ascii >= CHAR_0 And ascii <= CHAR_9) Or ascii = CHAR_DOT Or ascii = CHAR_COLON Then
                i = i + 1
                GoTo Continue
            ElseIf ascii = CHAR_LARC Then
                state = 3
                i = i - 2
                GoTo Continue
            ElseIf ascii = CHAR_RARC Then
                RArcPos = i
                IsSeccessful = True
                Exit Do
            ElseIf ascii = 10 Or ascii = 13 Then
                state = 3
                i = i - 2
                GoTo Continue
            Else
                state = 3
                i = i - 2
                GoTo Continue
            End If
        ElseIf state = 2 Then
            If i < 1 Then 'head
                IsSeccessful = False
                Exit Do
            ElseIf (ascii >= CHAR_0 And ascii <= CHAR_9) Or ascii = CHAR_DOT Or ascii = CHAR_COLON Then
                i = i - 1
                GoTo Continue
            ElseIf ascii = CHAR_LARC Then
                LArcPos = i
                IsSeccessful = True
                Exit Do
            ElseIf ascii = CHAR_RARC Then
                RArcPos = i
                i = i - 1
                GoTo Continue
            ElseIf ascii = 10 Or ascii = 13 Then
                IsSeccessful = False
                Exit Do
            Else
                state = 3
                i = i - 1
                GoTo Continue
            End If
        ElseIf state = 3 Then
            If i < 1 Then 'head
                IsSeccessful = False
                Exit Do
            ElseIf (ascii >= CHAR_0 And ascii <= CHAR_9) Or ascii = CHAR_DOT Or ascii = CHAR_COLON Then
                i = i - 1
                GoTo Continue
            ElseIf ascii = CHAR_LARC Then
                i = i - 1
                GoTo Continue
            ElseIf ascii = CHAR_RARC Then
                RArcPos = i
                state = 2
                i = i - 1
                GoTo Continue
            ElseIf ascii = 10 Or ascii = 13 Then
                IsSeccessful = False
                Exit Do
            Else
                i = i - 1
                GoTo Continue
            End If
        End If
Continue:
        counter = counter + 1
        If counter > 9999 Then
            IsSeccessful = False
            Exit Do
        End If
    Loop
    Dim tmp As String
    If IsSeccessful Then
        tmp = Mid(txKashi.text, LArcPos + 1, (RArcPos - 1) - (LArcPos + 1) + 1)
    End If
    Dim ret As Boolean
    Dim pSeconds As Double
    If (Shift And KEYSHIFT) = 0 Then
        ret = gFrmInputTime.InputTime(tmp, pSeconds)
        If Not ret Then Exit Sub 'canceled by user by such pressing Esc
    Else
        If tmp = "" Then Exit Sub '???s???????e?L?X?g???????
        pSeconds = TimeToSeconds(tmp)
        If pSeconds = TIMETEXT_ILLEGAL Then Exit Sub
    End If
    gMedia.SeekMedia pSeconds
    mLastTime = gMedia.GetCrrtPos
End Sub

'分析时间字符串用的是下面的代码（完整的！）用了个NFA

Attribute VB_Name = "TimeCalc"
Option Explicit
Public Const CHAR_0 = 48           ' 0
Public Const CHAR_9 = 57           '9
Public Const CHAR_DOT = 46         ' .
Public Const CHAR_COLON = 58       ' :
Public Const CHAR_LARC = 91    ' [
Public Const CHAR_RARC = 93    ' ]
Public Const TIMETEXT_ILLEGAL = -1
Private Type WORD
    wVal As String
    wType As Integer
End Type
Private Const WTYPE_HMS = 1 'number of hour/min/second
Private Const WTYPE_MS = 2 'millisecond
Private Const WTYPE_E = 3 '??
Private Const WTYPE_ERROR = 4
Public Function SecondsToTime(sec As Double, houred As Boolean, msn As Byte) As String
    Dim intsec As Long
    Dim ms As String
    Dim s As Long
    Dim h As Long
    Dim m As Long
    Dim tmp As Long
    intsec = Int(sec)
    h = Int(intsec / 3600)
    tmp = intsec Mod 3600
    m = Int(tmp / 60)
    s = tmp Mod 60
    If h > 0 Or houred Then
        SecondsToTime = Format(h, "00") + ":"
    End If
    SecondsToTime = SecondsToTime + Format(m, "00") + ":" + Format(s, "00")
    If msn > 0 Then
        ms = Format(sec - intsec, "." + String(msn, "0"))
        If Left(ms, 1) <> "." Then '?@format?????????????P?D?O?O????I
            ms = "." + String(msn, "9")  ' ????l??h.999?h????B
        End If
        SecondsToTime = SecondsToTime + ms
    End If
End Function
Public Function TimeToSeconds(text As String) As Double
    Dim index As Integer
    index = 1
    Dim tmp(1 To 4) As WORD
        
    If index > Len(text) Then
        TimeToSeconds = 0
        Exit Function
    End If
   
    tmp(1) = GetWord(text, index)
    If tmp(1).wType = WTYPE_ERROR Then
        TimeToSeconds = TIMETEXT_ILLEGAL
        Exit Function
    End If
    If index > Len(text) Then
        If tmp(1).wType = WTYPE_HMS Then
            TimeToSeconds = CDbl(tmp(1).wVal)
            Exit Function
        ElseIf tmp(1).wType = WTYPE_MS Then
            TimeToSeconds = CDbl("0." + tmp(1).wVal)
            Exit Function
        ElseIf tmp(1).wType = WTYPE_E Then
            TimeToSeconds = 0
            Exit Function
        End If
    End If
   
    tmp(2) = GetWord(text, index)
    If tmp(2).wType = WTYPE_ERROR Then
        TimeToSeconds = TIMETEXT_ILLEGAL
        Exit Function
    End If
    If index > Len(text) Then
        If tmp(2).wType = WTYPE_HMS Then
            TimeToSeconds = CDbl(tmp(1).wVal) * 60 + CDbl(tmp(2).wVal)
            Exit Function
        ElseIf tmp(2).wType = WTYPE_MS Then
            TimeToSeconds = CDbl(tmp(1).wVal + "." + tmp(2).wVal)
            Exit Function
        End If
    End If
   
    tmp(3) = GetWord(text, index)
    If tmp(3).wType = WTYPE_ERROR Then
        TimeToSeconds = TIMETEXT_ILLEGAL
        Exit Function
    End If
    If index > Len(text) Then
        If tmp(3).wType = WTYPE_HMS Then
            TimeToSeconds = CDbl(tmp(1).wVal) * 3600 + CDbl(tmp(2).wVal) * 60 + CDbl(tmp(3).wVal)
            Exit Function
        ElseIf tmp(3).wType = WTYPE_MS Then
            TimeToSeconds = CDbl(tmp(1).wVal) * 60 + CDbl(tmp(2).wVal + "." + tmp(3).wVal)
            Exit Function
        End If
    End If
   
    tmp(4) = GetWord(text, index)
    If tmp(4).wType = WTYPE_ERROR Then
        TimeToSeconds = TIMETEXT_ILLEGAL
        Exit Function
    End If
    If index > Len(text) Then
        If tmp(4).wType = WTYPE_HMS Then
            TimeToSeconds = TIMETEXT_ILLEGAL
            Exit Function
        ElseIf tmp(4).wType = WTYPE_MS Then
            TimeToSeconds = CDbl(tmp(1).wVal) * 3600 + CDbl(tmp(2).wVal) * 60 + CDbl(tmp(3).wVal + "." + tmp(4).wVal)
            Exit Function
        End If
    End If
End Function
Private Function GetWord(ByRef pStr As String, ByRef pIndex As Integer) As WORD
    Dim state As Integer
    Dim char As String * 1
    Dim ascii As Integer
    state = 0
    GetWord.wVal = ""
    Do
        If pIndex <= Len(pStr) Then
            char = Mid(pStr, pIndex)
            ascii = Asc(char)
        End If
        Select Case state
        Case 0:
            If pIndex > Len(pStr) Then
                GetWord.wType = WTYPE_E
                Exit Function
            ElseIf ascii >= CHAR_0 And ascii <= CHAR_9 Then
                GetWord.wVal = GetWord.wVal + char
                state = 1
                GoTo Continue
            ElseIf ascii = CHAR_DOT Then
                state = 4
                GoTo Continue
            ElseIf ascii = CHAR_COLON Then
                state = 2
                GoTo Continue
            Else
                GetWord.wType = WTYPE_ERROR
                Exit Function
            End If
        Case 1:
            If pIndex > Len(pStr) Then
                GetWord.wType = WTYPE_HMS
                Exit Function
            ElseIf ascii >= CHAR_0 And ascii <= CHAR_9 Then
                GetWord.wVal = GetWord.wVal + char
                GoTo Continue
            ElseIf ascii = CHAR_DOT Then
                GetWord.wType = WTYPE_HMS
                Exit Function
            ElseIf ascii = CHAR_COLON Then
                GetWord.wType = WTYPE_HMS
                Exit Function
            Else
                GetWord.wType = WTYPE_ERROR
                Exit Function
            End If
        Case 2:
            If pIndex > Len(pStr) Then
                GetWord.wType = WTYPE_ERROR
                Exit Function
            ElseIf ascii >= CHAR_0 And ascii <= CHAR_9 Then
                GetWord.wVal = GetWord.wVal + char
                state = 3
                GoTo Continue
            Else
                GetWord.wType = WTYPE_ERROR
                Exit Function
            End If
        Case 3:
            If pIndex > Len(pStr) Then
                GetWord.wType = WTYPE_HMS
                Exit Function
            ElseIf ascii >= CHAR_0 And ascii <= CHAR_9 Then
                GetWord.wVal = GetWord.wVal + char
                GoTo Continue
            ElseIf ascii = CHAR_DOT Then
                GetWord.wType = WTYPE_HMS
                Exit Function
            ElseIf ascii = CHAR_COLON Then
                GetWord.wType = WTYPE_HMS
                Exit Function
            Else
                GetWord.wType = WTYPE_ERROR
                Exit Function
            End If
        Case 4:
            If pIndex > Len(pStr) Then
                GetWord.wType = WTYPE_MS
                Exit Function
            ElseIf ascii >= CHAR_0 And ascii <= CHAR_9 Then
                GetWord.wVal = GetWord.wVal + char
                GoTo Continue
            Else
                GetWord.wType = WTYPE_ERROR
                Exit Function
            End If
        End Select
Continue:
        pIndex = pIndex + 1
    Loop
End Function

instemast

Kashier以前在 Ja 语言的BBS帖过，
最新版地址是，http://esnips.com/web/kashier/

lingjingqiu

你不用跳转表用什么goto....

instemast

lingjingqiu: Re:NFA的3种编码优劣,你喜欢怎么做?JAVA去掉了goto你喜欢吗?

你不用跳转表用什么goto....

用goto的话时间复杂度为 O(n^0)