Golang でプログラミング言語を作る__Part22

Tuyoshi Akiyama
Aug 24, 2017 · 12 min read

前回は、組み込み関数 lent() を実装しました。

今回は、新しいタイプ、配列を言語に加えていきます。

基本的には、Go言語のスライスを使ったものになりますので、新しいData Structureを構築する必要はなさそうです。


まず最初に、lexerに配列タイプのTokenを設定する必要があります。処理の流れは、こちらの記事と同様に行っていきたいと思います。

では、次のTokenをconst内に追加します。

LBRACKET = "["
RBRACKET = "]"

また、lexer_test.goファイルのテスト入力値に [1, 2] と、配列を加えて、テストをfailさせます。

そしたら、lexerの NextToken 関数に、”[”と”]”が来た時に、それぞれのTokenタイプが設定されるようにします。

case '[':
tok = newToken(token.LBRACKET, l.ch)
case ']':
tok = newToken(token.RBRACKET, l.ch)

以上でテストがpassすることを確認したら、配列のToken化は成功です。

次は、このTokenをparserに渡していきます。


今回の配列の要素には、どのタイプの値も入るようなものに、したいと思います。

infix/prefixも、その中に含まれていきますね。

さて、parserの処理を行う際には、ASTに配列を表すノードを設定して、内部的に配列を表現するようにします。

ast/ast.go

type ArrayLiteral struct {
Token token.Token
Elements []Expression
}
func (al *ArrayLiteral) expressNode() {}
func (al *ArrayLiteral) TokenLiteral() string { return al.Token.Literal }
func (al *ArrayLiteral) String() string {
var out bytes.Buffer
// [...]

次に下の入力値を持つテストケースを作って、テストをfailさせます。

input := "[1, 2 * 2, 3 + 3]"

そのテストをpassさせる為には、 parser.go内にある、parserの初期化関数、 New にtokenLBRACKETが渡された時に配列を解析する関数を設定する必要があります。

その関数は、 先程設定した、 ast.ArrayLiteral (ASTの配列ノード)を返します。更には、そのElements(要素)フィールドには、次の関数、 parseExpressionList がアサインされます。

parser/parser.go

func (p *Parser) parseExpressionList(end token.TokenType) []ast.Expression {
list := []ast.Expression{}
if p.peekTokenIs(end) {
p.nextToken()
return list
}
p.nextToken()
list = append(list, p.parseExpression(LOWEST))
for p.peekTokenIs(token.COMMA) {
p.nextToken()
p.nextToken()
list = append(list, p.parseExpression(LOWEST))
}
if !p.expectPeek(end) {
return nil
}
return list
}

処理内容としては

  1. 次のTokenがend、つまり](RBRACKET)であった時は配列の要素listは終わりを意味するので、listを返す。
  2. さらにTokenを次に進めて、list内に要素を入れていく。
  3. 次のTokenがコンマである時、Tokenを2つすすめて、listに次の要素を入れる
  4. 最後のTokenが](RBRACKET)で終わらない時は、エラーを返す。

以上でテストがpassした時に、配列(array literal)の解析処理は完了です。

token.LBRACKETと配列の解析関数は紐付きました。


ここまでは、配列のサポートの実装となります。次は、myArray[0];のように、indexで配列の中身を取り出す機能をつけていきたいと思います。

まずは、ASTノードに配列のIndexを表すノードを設定します。

type IndexExpression struct {
Token token.Token
Left Expression
Index Expression
}
func (ie *IndexExpression) expressNode() {}
func (ie *IndexExpression) TokenLiteral() string { return ie.Token.Literal }
func (ie *IndexExpression) String() string {
var out bytes.Buffer
// [...]
]

上のLeftフィールドは myArray が、 Indexフィールドには [0] が入ります。

どちらも Expression タイプとすることで、どんな種類の値も、このフィールドに入れることができます。

次は、テストケースの作成です。次の入力値をもつテストを作成します

input := "myArray[1 + 1]"

このテストは、parserがあるTokenタイプを与えた時に、それに紐付く解析関数がよばれるかをテストします。その解析関数は、 上で設定した ast.IndexExpression が返される事を、期待されています。

更に、次の入力値を TestOperatorPrecedenceParsing のテストケースに追加して、配列の要素内で優先度(precedence)が正しく機能するかのテストも行います。

  {
"a * [1, 2, 3, 4][b * c] * d",
"((a * ([1, 2, 3, 4][(b * c)])) * d)",
},
{
"add(a * b[2], b[1], 2 * [1, 2][1])",
"add((a * (b[2])), (b[1]), (2 * ([1, 2][1])))",
},

上の2つのテストがfailするのを確認します。ここでエラー文に、prefix関数が設定されていません、が出力されます。

が、今回このIndexExpressionは、prefixではなく、infix関数に紐つけていきたいと思います。

myArray[0]の場合、left+operator+rightは、”myArry” +“[“ + “0]”として扱います。

parser/parser.go

// this code should be implemented in New function
p.registerInfix(token.LBRACKET, p.parseIndexExpression)
func (p *Parser) parseIndexExpression(left ast.Expression) ast.Expression {
exp := &ast.IndexExpression{Token: p.curToken, Left: left}
p.nextToken()
exp.Index = p.parseExpression(LOWEST)
if !p.expectPeek(token.RBRACKET) {
return nil
}
return exp
}

上の解析関数に加えて、INDEXの優先度を設定する必要があります。token.LBRACKETにINDEXw紐つけます。

const (
_ int = iota
// [...]
INDEX // array[index]
)
var precedences = map[token.TokenType]int{
// [...]
token.LBRACKET: INDEX,
}

上の処理を終え、テストがpassするのを確認したら、parsing(解析)処理がつくられました。


次は、evaluator(評価)機能を作っていきます。

object/object.go

type Array struct {
Elements []Object
}
func (ao *Array) Type() ObjectType { return ARRAY_OBJ }
func (ao *Array) Inspect() string {
var out bytes.Buffer
elements := []string{}
for _, e := range ao.Elements {
elements = append(elements, e.Inspect())
}
out.WriteString("[")
out.WriteString(strings.Join(elements, ", "))
out.WriteString("]")
return out.String()
}

上の処理で、配列を包むオブジェクトの設定を終えたら、次はevaluatorのテストケースを作ります。

evaluator/evaluator_test.go

func TestArrayLiterals(t *testing.T) {
input := "[1, 2 * 2, 3 + 3]"
evaluated := testEval(input)
result, ok := evaluated.(*object.Array)
if !ok {
t.Fatalf("object is not Array got=%T (%+v)", evaluated, evaluated)
}
if len(result.Elements) != 3 {
t.Fatalf("array has wrong num of elements got=%d", len(result.Elements))
}
testIntegerObject(t, result.Elements[0], 1)
testIntegerObject(t, result.Elements[1], 4)
testIntegerObject(t, result.Elements[2], 6)
}

前に作ったヘルパー関数、 testIntegerObject がかなり便利ですね。Statement(式)の最終的な値をテストする役割を果たしています。

次にテストをfailさせ、evaluatorのtop-level解釈関数、 Eval に配列を表すノードが渡された時の処理、下のコードを加えます。

case *ast.ArrayLiteral:
elements := evalExpressions(node.Elements, env)
if len(elements) == 1 && isError(elements[0]) {
return elements[0]
}
return &object.Array{Elements: elements}

最後に、このテストがpassしたら、配列の実装は終了です。配列の要素のインデックスにも、同様に実装することができます。

また、前回作った組み込み関数 len() に加えて、新しく配列を操作する関数を追加しました。

その中の一つ、 rest について見ていきます。

evaluator/builtins.go

var builtins = map[string]*object.Builtin{// [...]"rest": &object.Builtin{
Fn: func(args ...object.Object) object.Object {
if len(args) != 1 {
return newError("wrong number of arguments, got=%d, want=1", len(args))
}
if args[0].Type() != object.ARRAY_OBJ {
return newError("argument to `rest` must be ARRAY, got %s", args[0].Type())
}
arr := args[0].(*object.Array)
length := len(arr.Elements)
if length > 0 {
newElements := make([]object.Object, length-1, length-1)
copy(newElements, arr.Elements[1:length])
return &object.Array{Elements: newElements}
}
return NULL
},
},
}

処理内容としては、次の通りになります。

  1. restが呼ばれた時に、 object.Builtin が返されます
  2. 1のオブジェクトの内容は一つの引数をもつ関数であり、その引数のタイプが配列オブジェクトでない場合、エラーを出します。
  3. 引数の配列を、オブジェクト配列をインスタンス化して、包み込みます。
  4. 上のオブジェクトの要素数が一つ以上あることを確認して
  5. 新しい要素をlenとcapをそれぞれ、length-1に設定して
  6. 一つ目の要素を抜き取った残りの要素を、5の要素にいれ
  7. それをもつ、配列オブジェクトを返しています。

以上で、配列タイプの実装を終えました。

次はHashタイプ(map)を持たせる、機能をつけていきます

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade