パソコン活用研究5番街（Visual
Basic、Excel(VBA)、BASIC プログラミング研究）
VB.NETで計算機を作る（LR解析）
（準備中）
今までに再帰下降パーサによる構文解析で計算機プログラムを作成してきました。
（→ひとまずの完成形はVB.netで計算機を作る（とりあえず完成形２）
その次にはいささか酔狂でLL構文解析表による計算機プログラムを作成してみました。
→VB.netで計算機を作る(LL解析）
今回はLR解析表を使った四則演算の計算機を作ってみることにしますが、
使えるのは加算と乗算だけです。一応( )は使えます。
実行例
スタックの表記の意味は姉妹サイト「構文解析（上昇解析）」をご参照下さい。
変数
token型構造体として、tok(), stack()をグローバル変数として宣言しています。
tok()は読み込み記号列用の変数、stack()はスタック用です。
宣言部と字句解析部
宣言部と字句解析部はVB.netで計算機を作る（とりあえず完成形２）やVB.netで計算機を作る(LL解析）
で作成したプログラムをほぼそのまま流用しています。使用する変数等の違いで多少の違いはありますが。
Enum typeにstateを追加しています。
①のForループでは、入力文字列（記号列）を１文字づつ表示
statement.Length
文字列statementの長さを取得するのに、Lengthプロパティを使っている。
②のForループでは、入力文字列をに分解しtokenに分解したものを表示
Imports System
Module Program
REM Public num_token As Integer
Public err, cnt As Integer
Enum type
number
dot
add_op
sub_op
mul_op
div_op
pow_op
lparen
rparen
space
bad
line_end
state
End Enum
Structure token
Dim type As type
Dim str As String
Dim v As Double
End Structure
Public tok(30), stack(30) As token
Sub Main(args As String())
Dim i, j, pos, isnum, rp, lp As Integer
Dim value As Double
Dim r As type
Dim statement, stck, 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 = "$"
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") : GoTo L3
構文解析と演算
以下構文解析を行っている個所になります。
stack 姉妹サイト構文解析（上昇解析）の解析表のスタックに該当するものです。token型の構造体なので、メンバ変数としてtype,str,vを
持っています。
LR解析表を2次元の配列にしたりすると、LR解析表を使っている感がよくでてくると思いますが、ここではLR解析表の内容をSelect
Caseとif文で
直接ブレイクダウンして処理しています。
stckというのが状態を表す変数です。
stckの値により、Select Caseで場合分けしていますが、これがLR解析表の状態に該当します。
各状態の中で、if文でtok(i)により処理を分岐させています。tok(i)は次に読まれる記号を保持しています。
シフトの処理、還元の処理はそれぞれ関数shufy(), reduce()を呼んで処理しています。
変数iはtok()のindexとして使用
グローバル変数cntはstackのtopを表す変数として使っています。
関数shift()からの戻り値は次に読み込むtokuのindexを返し、関数reduce()からの返り値は、還元処理で削除するスタックの記号列の数です。
よってcnt=cnt-reduce() は還元処理後のstackのtopを示すことになります。
LR解析の場合は、解析しながら演算も同時進行していますので、解析が終了したときには、演算結果も出ており
stack(1).vに結果が保持されています。
演算は還元処理の時、すなわち関数reduce()で行われています。
このあたり、グローバル変数を使ったり、関数の戻り値を使ったりしょぼいコードの書き方になってますので、ご注意下さい。
stack(0).type = type.state : stack(0).str = "0"
stck = stack(0).str
' cntはstackのtop iは読み込んでいるtokのindex
i = 0
cnt = 0
' Console.ReadLine()
While (1)
For j = 0 To cnt
Console.Write("{0}", stack(j).str)
Next
Console.WriteLine(" : {0}", tok(i).str)
' Console.ReadLine()
Select Case stck
Case "0"
If tok(i).type = type.number Then i = shift(i, "5") : stck = "5" : Console.WriteLine("s5") : Continue While
If tok(i).type = type.lparen Then i = shift(i, "4") : stck = "4" : Console.WriteLine("s4") : Continue While
Case "1"
If tok(i).type = type.add_op Then i = shift(i, "6") : stck = "6" : Console.WriteLine("s6") : Continue While
If tok(i).type = type.line_end Then Exit While
Case "2"
If tok(i).type = type.add_op Then Console.WriteLine("r2") : cnt = cnt - reduce(cnt, 2) : stck = goto_table(cnt) : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = stck : Continue While
If tok(i).type = type.mul_op Then i = shift(i, "7") : stck = "7" : Console.WriteLine("s7") : Continue While
If tok(i).type = type.rparen Then Console.WriteLine("r2") : cnt = cnt - reduce(cnt, 2) : stck = goto_table(cnt) : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = stck : Continue While
If tok(i).type = type.line_end Then Console.WriteLine("r2") : cnt = cnt - reduce(cnt, 2) : stck = goto_table(cnt) : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = stck : Continue While
Case 3
If (tok(i).type = type.add_op) Or (tok(i).type = type.mul_op) Or (tok(i).type = type.rparen) Or (tok(i).type = type.line_end) Then Console.WriteLine("r4") : cnt = cnt - reduce(cnt, 4) : stck = goto_table(cnt) : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = stck : Continue While
Case 4
If tok(i).type = type.number Then i = shift(i, "5") : stck = "5" : Console.WriteLine("s5") : Continue While
If tok(i).type = type.lparen Then i = shift(i, "4") : stck = "4" : Console.WriteLine("s4") : Continue While
Case 5
If tok(i).type = type.number Then i = shift(i, "5") : stck = "5" : Console.WriteLine("s5") : Continue While
If (tok(i).type = type.add_op) Or (tok(i).type = type.mul_op) Or (tok(i).type = type.rparen) Or (tok(i).type = type.line_end) Then Console.WriteLine("r6") : cnt = cnt - reduce(cnt, 6) : stck = goto_table(cnt) : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = stck : Continue While
Case 6
If tok(i).type = type.number Then i = shift(i, "5") : stck = "5" : Console.WriteLine("s5") : Continue While
If tok(i).type = type.lparen Then i = shift(i, "4") : stck = "4" : Console.WriteLine("s4") : Continue While
Case 7
If tok(i).type = type.number Then i = shift(i, "5") : stck = "5" : Console.WriteLine("s5") : Continue While
If tok(i).type = type.lparen Then i = shift(i, "4") : stck = "4" : Console.WriteLine("s4") : Continue While
Case 8
If tok(i).type = type.add_op Then i = shift(i, "6") : stck = "6" : Console.WriteLine("s6") : Continue While
If tok(i).type = type.rparen Then i = shift(i, "11") : stck = "11" : Console.WriteLine("s11") : Continue While
Case 9
If (tok(i).type = type.add_op) Or (tok(i).type = type.rparen) Or (tok(i).type = type.line_end) Then Console.WriteLine("r1") : cnt = cnt - reduce(cnt, 1) : stck = goto_table(cnt) : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = stck : Continue While
If tok(i).type = type.mul_op Then i = shift(i, "7") : stck = "7" : Console.WriteLine("s7") : Continue While
Case 10
If (tok(i).type = type.add_op) Or (tok(i).type = type.mul_op) Or (tok(i).type = type.rparen) Or (tok(i).type = type.line_end) Then Console.WriteLine("r3") : cnt = cnt - reduce(cnt, 3) : stck = goto_table(cnt) : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = stck : Continue While
Case 11
If (tok(i).type = type.add_op) Or (tok(i).type = type.mul_op) Or (tok(i).type = type.rparen) Or (tok(i).type = type.line_end) Then Console.WriteLine("r5") : cnt = cnt - reduce(cnt, 5) : stck = goto_table(cnt) : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = stck : Continue While
End Select
End While
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")
value = stack(1).v
Console.WriteLine("value: {0}", value)
関数shift() と関数reduce()
関数shift()は読み込んだ記号をスタックに追加していくという処理になります。
cnt = cnt + 1 : stack(cnt) = tok(i)
数値の場合はスタックの記号を
非終端記号"n"にしておきます。
If stack(cnt).type = type.number Then stack(cnt).str = "n"
更に新たな状態をスタックに追記し、その状態（変数i）をReturnします。
i = i + 1 : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = r
Function shift(ByVal i As Integer, ByVal r As String) As Integer
cnt = cnt + 1 : stack(cnt) = tok(i)
If stack(cnt).type = type.number Then stack(cnt).str = "n"
i = i + 1 : cnt = cnt + 1 : stack(cnt).type = type.state : stack(cnt).str = r
Return i
End Function
Function reduce(ByVal cnt As Integer, ByVal r As Integer) As Integer
Dim v As Double
Select Case r
Case 1
v = stack(cnt - 5).v + stack(cnt - 1).v
stack(cnt - 5).v = v
cnt = cnt - 5
Return 5
Case 2
stack(cnt - 1).str = "E"
cnt = cnt - 1
Return 1
Case 3
v = stack(cnt - 5).v * stack(cnt - 1).v
stack(cnt - 5).v = v
cnt = cnt - 5
Return 5
Case 4
stack(cnt - 1).str = "T"
cnt = cnt - 1
Return 1
Case 5
v = stack(cnt - 3).v
stack(cnt - 5).str = "F"
stack(cnt - 5).v = v
stack(cnt - 5).type = type.number
Return 5
Case 6
stack(cnt - 1).str = "F"
cnt = cnt - 1
Return 1
End Select
End Function
goto表
r 還元された後のスタックにある状態
Function goto_table(ByVal cnt As Integer) As String
Dim r As String
r = stack(cnt - 1).str
Select Case r
Case "0"
If stack(cnt).str = "E" Then r = "1"
If stack(cnt).str = "T" Then r = "2"
If stack(cnt).str = "F" Then r = "3"
Case "4"
If stack(cnt).str = "E" Then r = "8"
If stack(cnt).str = "T" Then r = "2"
If stack(cnt).str = "F" Then r = "3"
Case "6"
If stack(cnt).str = "T" Then r = "9"
If stack(cnt).str = "F" Then r = "3"
Case "7"
If stack(cnt).str = "F" Then r = "10"
End Select
Console.WriteLine("goto ->{0} ", r)
Return r
End Function
字句解析のための関数checktype() とEnd Module
ここはVB.netで計算機を作る（とりあえず完成形２）
のものをそのまま流用しています。
このプログラムは加算と乗算だけなので、"-"やら"/"などは字句解析に不要ですが
そのまま残してあります。（今後の万が一拡張するときのため）
最後の1行はこのモジュールの終了をあらわすEnd Module
Function checktype(ByVal t As String) As Integer
If IsNumeric(t) = True Then Return type.number
If t = "." Then Return type.dot
If t = "+" Then Return type.add_op
If t = "-" Then Return type.sub_op
If t = "*" Then Return type.mul_op
If t = "/" Then Return type.div_op
If t = "^" Then Return type.pow_op
If t = "(" Then Return type.lparen
If t = ")" Then Return type.rparen
If t = " " Then Return type.space
Return type.bad
End Function
End Module
ＴｏｐＰａｇｅ > Visual BasIc＆Ｅｘｃｅｌ活用研究目次