PHPのハッシュテーブルを見るの記事で表題通り、PHPのハッシュテーブルを見て、ハッシュテーブルに関数を登録するところを見ようとしたが、共同体の記述の解釈で断念でした。
一旦、ハッシュテーブル周りを見るのは保留にして、バーチャルマシン(VM)を含む機械がコードを解釈して実行する箇所を見ることにする。
上記のコードを解釈して実行する過程はコンパイラもしくはインタプリタによって、人が書いたコードを機械が解釈できる形式に翻訳して実行する。
コードを翻訳して実行の過程の細かい言葉は全て一旦置いといて、下記の課題を設ける事にする。
文字列で「5 * 8 ÷ (3 + 5)」を読み込んだ時に「5」を出力すること
上記の計算を行う場合、最初に(3 + 5)の箇所を計算して「8」の結果を得る。
この結果を元に「5 * 8 ÷ 8」の計算を左から順に行うことで「5」の結果を得ることが出来る。
この時、計算の過程が左から順に行っているわけではないということに注意が必要で、コンピュータに数式を計算させる場合は逆ポーランド記法を利用するとのこと。
この課題をこなすにあたって、「5 * 8 ÷ (3 + 5)」には、
5 * 8 ÷ ( 3 + )
という要素にバラす事を最初に行う必要がある。
これらの各要素を字句(トークン)と呼び、字句解析という手法を用いて行われる。
最初に超簡易的な字句解析器(レキサー)を作成してみる。
言語はメモリを意識していきたいので、PHPではなくGo言語で進める。
とその前に字句解析器で必要なデータ構造のスタックとキューを先に触れておく。
スタックに関してWikipediaにわかりやすい図があるので引用すると、
Maxtremus - 投稿者自身による作品, CC0, リンクによる
データを蓄積出来る配列があって、その配列に値を上に積み重ねるように格納(Push)していく。
値を取り出す(Pop)時は、後入れ先出しの規則に基づき、最後に入れた値から取り出す。
このデータの扱い方は前述した逆ポーランド記法で重宝するが、詳細は一旦置いといて、実際のコード作成に移る。
この手の内容は慣れないので、作成したコードはぎこちないかもしれないけれども、そこはご愛嬌でスルーしてください。
最初にディレクトリ構造は下記の通り
stack
├── main.go
└── stack
└── stack.go
先にstack/stack.goの方のコードは下記のように作成した。
stack/stack.go
package stack
import "log"
var top int = 0
const capacity int = 10
//スタック用の配列を作成
func New() []int {
return make([]int, capacity)
}
//データの挿入(push)
func Push(s []int, x int) {
if top >= cap(s) {
log.Fatal("スタックはオーバーフローしました")
}
s[top] = x
top++
}
//データの取り出し(pop)
func Pop(s []int) int {
if top == 0 {
log.Fatal("スタックは空で、値の取り出しを失敗しました")
}
top--
x := s[top]
s[top] = 0
return x
}
このコードを用いて、スタックにPushとPopを試してみる。
main.go
package main
import (
"fmt"
"./stack"
)
func main() {
//スタック用のスライスを作成する
s := stack.New()
//スタック用スライスに値を挿入する
stack.Push(s, 1)
stack.Push(s, 4)
stack.Push(s, 6)
fmt.Println("スタックに３個の値を入れた")
fmt.Println(s)
//値を取り出す
i := stack.Pop(s)
fmt.Println("スタックから最後に入れた値を取り出した")
fmt.Println(i)
fmt.Println("現在のスタックの状況")
fmt.Println(s)
fmt.Println("再びスタックに値を二つ入れてみる")
stack.Push(s, 3)
stack.Push(s, 5)
fmt.Println("現在のスタックの状況")
fmt.Println(s)
}
実行結果は
go run main.go スタックに３個の値を入れた [1 4 6 0 0 0 0 0 0 0] スタックから最後に入れた値を取り出した 6 現在のスタックの状況 [1 4 0 0 0 0 0 0 0 0] 再びスタックに値を二つ入れてみる 現在のスタックの状況 [1 4 3 5 0 0 0 0 0 0]
用意したコードでは意図通りの動作になったかな？
事前にたくさんのケースを加えたテストコードを作る必要があるけれども、今回は端折る。
