VB.NETで計算機を作る（LL解析）

VB.NETで計算機を作る（LL解析）

（準備中）

今までは再帰下降パーサによる構文解析で計算機プログラムを作成してきました。
（→ひとまずの完成形はVB.netで計算機を作る（とりあえず完成形２）

再帰下降パーサもLL構文解析の一種ですが、今回はいささか酔狂でLL構文解析表による
計算機プログラムを作成したみます。

実行例

変数
rpn, rpnlist()　
姉妹サイトLL解析表での四則演算にあるrpnlistというのがこのプログラムの変数rpnlに該当し
rpnlの各要素を肘しているのがrpnlist()という配列になります。
rpnpos rpnlistのindex

宣言部と字句解析部
宣言部と字句解析部はVB.netで計算機を作る（とりあえず完成形２）
で作成したプログラムをほぼそのまま流用しています。使用する変数等の違いで多少の違いはありますが。

①のForループでは、入力文字列（記号列）を１文字づつ表示
statement.Length
文字列statementの長さを取得するのに、Lengthプロパティを使っている。　

②のForループでは、入力文字列をに分解しtokenに分解したものを表示

Imports System

Module Program
    REM    Public num_token As Integer
    Public err, rpnpos, rpnstackpos As Integer
    Public rpnlist(30), rpnstack(30) As String

    Enum type
        number
        dot
        add_op
        sub_op
        mul_op
        div_op
        pow_op
        lparen
        rparen
        space
        bad
        line_end

    End Enum

    Structure token
        Dim type As type
        Dim str As String
        Dim v As Double
    End Structure

    Public tok(20) As token

    Sub Main(args As String())
        Dim i, j, k, l, pos, isnum, rp, lp As Integer
        Dim value, v As Double
        Dim r As type
        Dim statement, stack, c, rpnl, rpnstck, calclist(20) As String

        REM     num_token = 0
        err = 0 : rp = 0 : lp = 0

        statement = Console.ReadLine()

' ①　入力文字列（記号列）を１文字づつ表示
        For i = 0 To statement.Length - 1
            Console.WriteLine("{0} : {1}", i, statement.Chars(i))
        Next

        pos = 0 : isnum = 0
        For i = 0 To statement.Length - 1
            Try
                r = checktype(statement.Chars(i))
                If (isnum = 0 Or isnum = 5) And r = type.space Then GoTo L1 : 
                If (isnum = 1 Or isnum = 3) And r = type.space Then isnum = 5 : GoTo L1 : 
                If r = type.bad Then Console.WriteLine("{0}:Bad character", i) : tok(pos).str = tok(pos).str + statement.Chars(i) : tok(pos).type = type.bad : err = 1 : Exit For
                If (isnum = 1 Or isnum = 3) And r = type.number Then tok(pos).str = tok(pos).str + statement.Chars(i) : tok(pos).v = Double.Parse(tok(pos).str) : GoTo L1
                If isnum = 1 And r = type.dot Then tok(pos).str = tok(pos).str + statement.Chars(i) : isnum = 2 : GoTo L1
                If (isnum = 1 Or isnum = 3 Or isnum = 5) And r = type.rparen Then rp = rp + 1 : pos = pos + 1 : tok(pos).str = statement.Chars(i) : tok(pos).type = r : isnum = 5 : GoTo L1
                If (isnum = 1 Or isnum = 3 Or isnum = 5) And (r = type.add_op Or r = type.sub_op Or r = type.mul_op Or r = type.div_op Or r = type.pow_op) Then pos = pos + 1 : tok(pos).str = statement.Chars(i) : tok(pos).type = r : pos = pos + 1 : tok(pos).type = type.bad : isnum = 0 : GoTo L1
                If isnum = 2 And r = type.number Then tok(pos).str = tok(pos).str + statement.Chars(i) : tok(pos).v = Double.Parse(tok(pos).str) : isnum = 3 : GoTo L1
                If isnum = 2 And r <> type.number Then err = 1 : Console.WriteLine("{0}: Bad expression", i) : Exit For
                If isnum = 3 And r = type.dot Then err = 1 : Console.WriteLine("{0}: too many dot", i) : tok(pos).type = type.bad : Exit For
                If isnum = 0 And r = type.lparen Then lp = lp + 1 : tok(pos).str = tok(pos).str + statement.Chars(i) : tok(pos).type = r : pos = pos + 1 : GoTo L1
                If isnum = 0 And r = type.number Then tok(pos).str = tok(pos).str + statement.Chars(i) : tok(pos).type = type.number : tok(pos).v = Integer.Parse(tok(pos).str) : isnum = 1 : GoTo L1
                If isnum = 0 And r = type.sub_op Then tok(pos).str = tok(pos).str + statement.Chars(i) : tok(pos).type = type.number : isnum = 1 : GoTo L1
                Console.WriteLine("{0}:Bad expression", i) : tok(pos).str = tok(pos).str + statement.Chars(i) : tok(pos).type = type.bad : err = 1 : Exit For
            Catch ex As System.FormatException
                ' (0)0のような表現で")0"がSystem.FormatExceptionを引きおこすが、rparenの処理後isnum=5にすることで解消できる。tok(pos).v = Integer.Parse(tok(pos).str)が")0"という表現を整数型にパースできないため
                err = 1
                Console.WriteLine("System.FormatException")
                Exit For
            End Try
L1:         If lp < rp Then Console.WriteLine("too many rparen") : err = 1 : Exit For
        Next

        If lp <> rp Then Console.WriteLine("The number of parentheses does not match.") : err = 1
        Console.WriteLine("TOKEN")
        tok(pos + 1).type = type.line_end
        tok(pos + 1).str = "$"
' 　② tokenの表示
        For i = 0 To pos + 1
           Console.WriteLine("{0}: {1} : {2} : {3}", i, tok(i).str, tok(i).type, tok(i).v)
        Next

        If err = 1 Then Console.WriteLine("This is a bad expression")

構文解析
以下構文解析を行っている個所になります。
stackという変数は、姉妹サイト「LL解析表での四則演算」のLL解析表にあるスタックに該当します。
解析の1ステップ毎に
③　rpnl（姉妹サイト「LL解析表での四則演算」のLL解析表にあるrpnlist）の確定と作成
④　rpnstck(姉妹サイト「LL解析表での四則演算」のLL解析表にあるrpnstack）の確定と作成
⑤よりLL解析表に基づく解析を行っています。
⑤-A
stackより先頭の記号を読み込み、その記号が"$"かつ現在解析中のtoken=記号列 (tok(i))のtypeがline_endなら解析終了
⑤-B
stackの先頭の記号が"n"かつ現在解析中のtoken=記号列 (tok(i))のtypeがnumber（数値）ならstackの先頭から1文字ポップし、rpn()を呼ぶ。
また、stackの先頭記号と現在解析中のtokenの記号が同じ場合もstackの先頭から1文字ポップし、rpn()を呼ぶ
stack.Remove(0,1)とありますが、Removeというメソッドは文字列からRemoveで指定した文字を削除するメソッドです。
Remove(0,1)は先頭の文字の削除になります。
Remove(1,3)だと2文字目から3文字削除になります。
⑤-C以降、Select Case文の中で、stackの先頭の記号が"E","A","T","B","F"の場合に分けて処理を進めます。
姉妹サイト「LL解析表での四則演算」のLL解析表（表１）に基づいた処理です。

⑥　⑤-Aで構文解析が終了したら、後置記法を完成させるために、rpnstackに残っている記号（文字）を取り出し、rpnlistに追加していきます。
これで後置記法（rpnl,　rpnlist() )が完成です。

⑦後置記法に変換した後の式の表示です。

  stack = "E$"
        Console.WriteLine("Analisys")
        i = 0 : j = 0 : rpnlist(0) = ""
        While (1)
            rpnl = "" : rpnstck = ""
'　③rpnl（rpnlist)
            For j = 0 To rpnpos
                rpnl = rpnl + rpnlist(j) + " "
            Next
' ④rpnstck(rpnstack)
            For j = 0 To rpnstackpos
                rpnstck = rpnstck + rpnstack(j) + " "
            Next
'　⑤
            Console.WriteLine("{0}: {1}: {2}: {3}", tok(i).str, stack, rpnl, rpnstck)

            c = stack.Chars(0)
            If (c = "$" And tok(i).type = type.line_end) Then Exit While   '⑤-A
            If (c = "n" And tok(i).type = type.number) Or (c = tok(i).str) Then stack = stack.Remove(0, 1) : rpn(i) : i += 1 : GoTo L2   '⑤-B
'⑤-C
            Select Case c
                Case "E"
                    If (tok(i).type = type.number) Or (tok(i).type = type.lparen) Then stack = "TA" + stack.Remove(0, 1) Else err = err + 10 : Exit While
                Case "A"
                    If (tok(i).type = type.add_op) Then stack = "+TA" + stack.Remove(0, 1) : GoTo L2
                    If (tok(i).type = type.sub_op) Then stack = "-TA" + stack.Remove(0, 1) : GoTo L2
                    If (tok(i).type = type.rparen) Or (tok(i).type = type.line_end) Then stack = stack.Remove(0, 1) : GoTo L2
                    err = err + 10 : Exit While
                Case "T"
                    If (tok(i).type = type.number) Or (tok(i).type = type.lparen) Then stack = "FB" + stack.Remove(0, 1) Else err = err + 10 : Exit While
                Case "B"
                    If (tok(i).type = type.add_op) Or (tok(i).type = type.sub_op) Then stack = stack.Remove(0, 1) : GoTo L2
                    If (tok(i).type = type.mul_op) Then stack = "*FB" + stack.Remove(0, 1) : GoTo L2
                    If (tok(i).type = type.div_op) Then stack = "/FB" + stack.Remove(0, 1) : GoTo L2
                    If (tok(i).type = type.rparen) Or (tok(i).type = type.line_end) Then stack = stack.Remove(0, 1) : GoTo L2
                    err = err + 10 : Exit While
                Case "F"
                    If (tok(i).type = type.number) Then stack = "n" + stack.Remove(0, 1) : GoTo L2
                    If (tok(i).type = type.lparen) Then stack = "(E)" + stack.Remove(0, 1) : GoTo L2
                    err = err + 10 : Exit While
            End Select


L2:
        End While

'　⑥後置記法を完成させるための最後の処理
       For i = rpnstackpos To 0 Step -1
            rpnlist(rpnpos + 1) = rpnstack(i)
            rpnl = rpnl + rpnlist(rpnpos + 1) + " "
            rpnpos = rpnpos + 1
        Next

'　⑦　後置記法に変換後の表示
        For k = 0 To rpnpos
            Console.WriteLine(rpnlist(k))
        Next
        Console.WriteLine(rpnl)

⑧からの3行はエラーがあった場合の処理です。
エラーがあった場合は演算を実施せず終了します。
⑨からが演算部です。

 '　⑧エラーがある場合は演算を実施せず終了
        If (err Mod 10) = 1 Then Console.WriteLine("Error on tokenization") : GoTo L3
        If err >= 10 Then Console.WriteLine("Error on calculation") : GoTo L3
        If lp <> rp Then Console.WriteLine("The number of parentheses does not match.") : GoTo L3

'　⑨
        Console.WriteLine("Caluculation")

        k = 0 : l = 0

        For i = 0 To rpnpos
            If rpnlist(i) = "+" Then
                v = Double.Parse(calclist(k - 2)) + Double.Parse(calclist(k - 1))
                calclist(k - 2) = v.ToString() : k = k - 1
                Console.WriteLine(v)
            End If

            If rpnlist(i) = "-" Then
                v = Double.Parse(calclist(k - 2)) - Double.Parse(calclist(k - 1))
                calclist(k - 2) = v.ToString()
                k = k - 1
                Console.WriteLine(v)
            End If


            If rpnlist(i) = "*" Then
                v = Double.Parse(calclist(k - 2)) * Double.Parse(calclist(k - 1))
                calclist(k - 2) = v.ToString()
                k = k - 1
                Console.WriteLine(v)
            End If

            If rpnlist(i) = "/" Then
                v = Double.Parse(calclist(k - 2)) / Double.Parse(calclist(k - 1))
                calclist(k - 2) = v.ToString()
                k = k - 1
                Console.WriteLine(v)
            End If

            If rpnlist(i) <> "+" And rpnlist(i) <> "-" And rpnlist(i) <> "*" And rpnlist(i) <> "/" Then calclist(k) = rpnlist(i) : k = k + 1

            REM           For l = 0 To k
            REM           Console.Write("{0}:", calclist(l))

            REM        Next
            REM    Console.WriteLine()

        Next

        value = v

        Console.WriteLine("value: {0}", value)

L3:

    End Sub

後置記法への変換
プロシージャrpn()は、構文解析中（⑤-B）に呼び出され、後置記法への変換の処理を行う。

Sub rpn()
変数jはrpnlistのカウント用、kはrepstackのカウント用です。
⑩　tokenのtypeが数値だった場合は、rpnlist()に入れる
⑪　tokenのtypeが"("左括弧だった場合は、rpnstack()に入れる

以下、tokenが"+",-","*","/",")"だった場合の処理は「LL解析表での四則演算」の後置記法への置き換えルール
に記した処理をそのままコードにしています。

最後にrpnposの値とrpnstackposの値を設定したいます。

  Sub rpn(ByVal i As Integer)
        Static j As Integer = 0
        Static k As Integer = 0
        Dim l As Integer
        Console.WriteLine(tok(i).str)
        If (tok(i).type = type.number) Then rpnlist(j) = tok(i).str : j = j + 1  '⑩
        If (tok(i).type = type.lparen) Then rpnstack(k) = tok(i).str : k = k + 1  '⑪

        If (tok(i).type = type.add_op) Or (tok(i).type = type.sub_op) Then

            While (1)
                If k = 0 Then Exit While
                If rpnstack(k - 1) = "(" Then Exit While
                If (rpnstack(k - 1) = "+") Or (rpnstack(k - 1) = "-") Or (rpnstack(k - 1) = "*") Or (rpnstack(k - 1) = "/") Then rpnlist(j) = rpnstack(k - 1) : j = j + 1 : rpnstack(k - 1) = "" : k = k - 1

            End While
            rpnstack(k) = tok(i).str : k = k + 1
        End If

        If (tok(i).type = type.mul_op) Or (tok(i).type = type.div_op) Then

            While (1)
                If k = 0 Then Exit While
                If rpnstack(k - 1) = "(" Or rpnstack(k - 1) = "+" Or rpnstack(k - 1) = "-" Then Exit While
                If rpnstack(k - 1) = "*" Or rpnstack(k - 1) = "/" Then rpnlist(j) = rpnstack(k - 1) : j = j + 1 : rpnstack(k - 1) = "" : k = k - 1

            End While
            rpnstack(k) = tok(i).str : k = k + 1
        End If

        If tok(i).type = type.rparen Then

            While (1)
                If k = 0 Then err = err + 10 : Exit While
                If rpnstack(k - 1) = "(" Then rpnstack(k - 1) = "" : k = k - 1 : Exit While
                If rpnstack(k - 1) = "+" Or rpnstack(k - 1) = "-" Or rpnstack(k - 1) = "*" Or rpnstack(k - 1) = "/" Then rpnlist(j) = rpnstack(k - 1) : j = j + 1 : rpnstack(k - 1) = "" : k = k - 1
            End While


        End If
        rpnpos = j - 1 : rpnstackpos = k - 1
        REM        Console.WriteLine("{0}, {1}", rpnpos, rpnstackpos)
    End Sub