『Go言語で作るインタプリタ』をTypeScriptで実装する(前編)

後編はこちら
wafuwafu13.hatenadiary.com

O'Reilly Japan - Go言語でつくるインタプリタ
を2章までTypeScriptで実装しました。

この本を手にした動機は、

• Goの文法を学習したついでに低レイヤーにも手を出したかった
• 分量的に手が出やすそうだった

TypeScriptで実装を始めた動機は、

• 2章のPratt構文解析あたりから、写経ではなく理解してないコピペで進んでいた
• デバッグしてもポインタのせいでよく分からない
• 「Go言語でつくるインタプリタ」をRustで実装しました。 - Sansan Tech Blog の影響で、このままコピペで進めていくよりも、自分の慣れている言語で実装しなおした方が理解が進む気がした

といったところです。

let文の解析を中心としてまとめていきます。
リポジトリはこちらです。
GitHub - wafuwafu13/Interpreter-made-in-TypeScript: Interpreter Written in TypeScript

環境構築

TypeScript webpack Jest ESLint Prettier を用いました。
first commit · wafuwafu13/Interpreter-made-in-TypeScript@313d7a0 · GitHub

字句解析器(レキサー)

ソースコードを入力として受け取り、出力としてそのソースコードを表現するトークン列を返します。
GoのStructをJavaScriptのclassに置き換えるとうまくいきました。

...
type Lexer struct {
	input        string 
	position     int
	readPosition int
	ch           byte
}

func New(input string) *Lexer {
	l := &Lexer{input: input}
	l.readChar()
	return l
}

func (l *Lexer) readChar() {
	if l.readPosition >= len(l.input) {
		l.ch = 0
	} else {
		l.ch = l.input[l.readPosition]
	}
	l.position = l.readPosition
	l.readPosition += 1
}
......

...
export interface LexerProps {
  input: string;
  position: number;
  readPosition: number;
  ch: string | number;
}

export class Lexer<T extends LexerProps> {
  input: T['input'];
  position: T['position'];
  readPosition: T['readPosition'];
  ch: T['ch'];

  constructor(
    input: T['input'],
    position: T['position'] = 0,
    readPosition: T['readPosition'] = 0,
    ch: T['ch'] = '',
  ) {
    this.input = input;
    this.position = position;
    this.readPosition = readPosition;
    this.ch = ch;

    this.readChar();
  }

  readChar(): void {
    if (this.readPosition >= this.input.length) {
      this.ch = 'EOF';
    } else {
      this.ch = this.input[this.readPosition];
    }
    this.position = this.readPosition;
    this.readPosition += 1;
  }
...

抽象構文木(AST)

ソースコードの内部表現として使われています。
GoではValueフィールドの型はExpressionですが、TypeScriptではNameフィールドと同様にIdentifierクラスの型を用いました。

...
type Node interface {
	TokenLiteral() string
	String() string
}

type Statement interface {
	Node
	statementNode()
}

type Expression interface {
	Node
	expressionNode()
}

type Program struct {
	Statements []Statement
}

func (p *Program) TokenLiteral() string {
	if len(p.Statements) > 0 {
		return p.Statements[0].TokenLiteral()
	} else {
		return ""
	}
}

func (p *Program) String() string {
	var out bytes.Buffer

	for _, s := range p.Statements {
		out.WriteString(s.String())
	}

	return out.String()
}

type LetStatement struct {
	Token token.Token
	Name  *Identifier
	Value Expression
}

func (ls *LetStatement) statementNode() {}

func (ls *LetStatement) TokenLiteral() string { return ls.Token.Literal }

func (ls *LetStatement) String() string {
	var out bytes.Buffer

	out.WriteString(ls.TokenLiteral() + " ")
	out.WriteString(ls.Name.String())
	out.WriteString(" = ")

	if ls.Value != nil {
		out.WriteString(ls.Value.String())
	}

	out.WriteString(";")

	return out.String()
}

type Identifier struct {
	Token token.Token
	Value string
}

func (i *Identifier) expressionNode() {}
func (i *Identifier) TokenLiteral() string { return i.Token.Literal }
func (i *Identifier) String() string { return i.Value }
...

...
export interface ProgramProps {
  statements:
    | LetStatement<LetStatementProps>[]
    | ReturnStatement<ReturnStatementProps>[]
    | ExpressionStatement<ExpressionStatementProps>[];
}

export class Program<T extends ProgramProps> {
  statements: T['statements'];

  constructor(statements: T['statements'] = []) {
    this.statements = statements;
  }
}

export interface LetStatementProps {
  token: Token<TokenProps>;
  name: Identifier<IdentifierProps>;
  value?: Identifier<IdentifierProps>;
}

export class LetStatement<T extends LetStatementProps> {
  token: T['token'];
  name?: T['name'];
  value?: T['value'];

  constructor(token: T['token']) {
    this.token = token;
  }

  tokenLiteral(): string | number {
    return this.token.literal;
  }

  string(): string {
    let statements = [];
    statements.push(this.tokenLiteral() + ' ');
    statements.push(this.name!.string());
    statements.push(' = ');

    if (this.value != null) {
      statements.push(this.value.string());
    }

    statements.push(';');

    return statements.join('');
  }
}

export interface IdentifierProps {
  token: Token<TokenProps>;
  value: string | number;
}

export class Identifier<T extends IdentifierProps> {
  token: T['token'];
  value: T['value'];

  constructor(token: T['token'], value: T['value']) {
    this.token = token;
    this.value = value;
  }

  tokenLiteral(): string | number {
    return this.token.literal;
  }

  string(): string | number {
    return this.value;
  }
}
...

構文解析器(パーサー)

入力データを受け取り、抽象構文木のデータ構造を構築します。
Type Guardが煩わしかったので、新たにDEFAULTトークンを定義しました。
DEFAULTトークンを定義 · wafuwafu13/Interpreter-made-in-TypeScript@42f923e · GitHub

...
func (p *Parser) parseLetStatement() *ast.LetStatement {
	stmt := &ast.LetStatement{Token: p.curToken}

	if !p.expectPeek(token.IDENT) {
		return nil
	}

	stmt.Name = &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}

	if !p.expectPeek(token.ASSIGN) {
		return nil
	}

	p.nextToken()

	stmt.Value = p.parseExpression(LOWEST)

	if p.peekTokenIs(token.SEMICOLON) {
		p.nextToken()
	}

	return stmt
}
...

...
parseLetStatement(): LetStatement<LetStatementProps> {
    const stmt: LetStatement<LetStatementProps> = new LetStatement(
      this.curToken,
    );

    if (!this.expectPeek(TokenDef.IDENT)) {
      return stmt;
    }

    stmt.name = new Identifier(this.curToken, this.curToken.literal);

    if (!this.expectPeek(TokenDef.ASSIGN)) {
      return stmt;
    }

    while (!this.curTokenIs(TokenDef.SEMICOLON)) {
      this.nextToken();
    }

    return stmt;
  }
...

テスト

Jestを用いました。
TDDを実践できたのでよかったです。

...
func TestLetStatements(t *testing.T) {
	tests := []struct {
		input              string
		expectedIdentifier string
		expectedValue      interface{}
	}{
		{"let x = 5;", "x", 5},
		{"let y = true;", "y", true},
		{"let foobar = y;", "foobar", "y"},
	}

	for _, tt := range tests {
		l := lexer.New(tt.input)
		p := New(l)
		program := p.ParseProgram()
		checkParserErrors(t, p)

		if len(program.Statements) != 1 {
			t.Fatalf("program.Statements does not contain 1 statements. got=%d",
				len(program.Statements))
		}

		stmt := program.Statements[0]
		if !testLetStatement(t, stmt, tt.expectedIdentifier) {
			return
		}

		val := stmt.(*ast.LetStatement).Value
		if !testLiteralExpression(t, val, tt.expectedValue) {
			return
		}
	}
}
...

...
describe('testLetStatement', () => {
  const tests = [
    { input: 'let x = 5;', expectedIdentifier: 'x', expectedValue: 5 },
    { input: 'let y = true;', expectedIdentifier: 'y', expectedValue: true },
    {
      input: 'let foobar = y;',
      expectedIdentifier: 'foobar',
      expectedValue: 'y',
    },
  ];

  for (const test of tests) {
    const l = new Lexer(test['input']);
    const p = new Parser(l);

    const program: Program<ProgramProps> = p.parseProgram();

    it('checkParserErrros', () => {
      const errors = p.Errors();
      if (errors.length != 0) {
        for (let i = 0; i < errors.length; i++) {
          console.log('parser error: %s', errors[i]);
        }
      }
      expect(errors.length).toBe(0);
    });

    it('parseProgram', () => {
      expect(program).not.toBe(null);
      expect(program.statements.length).toBe(1);
    });

    const stmt: LetStatement<LetStatementProps> | any = program.statements[0];

    it('letStatement', () => {
      expect(stmt.token.literal).toBe('let');
      expect(stmt.name.value).toBe(test['expectedIdentifier']);
      expect(stmt.value.value).toBe(test['expectedValue']);
    });
  }
});
...

デバッグ

Goに不慣れなため、デバッグの仕方が悪かっただけかもしれませんが、TypeScriptだと、きれいにASTの構造がデバッグできました。

Go

TypeScript

特にif文なんかでは、ASTのノードがネストされている構造が掴めたのでよかったです。

if文

感想

低レイヤーの知識はまだまだ浅いですが、入り口としてこの本に出会えたのはよかったです。
現段階ではインタプリタよりむしろ、GoとTypeScriptの文法の知識の方が身についている感覚があるので、また気が向いたら続きをしていこうと思います。
インタプリタの挙動なんて知らなくてもエンジニアにはなれると思いますが、本能的に知りたくなる、周りのみんな知っている世界線にいたい、ということでこれからも独学でやっていくと思います。

#インタプリタ

wafuwafu13 2020-08-18 11:51 読者になる

広告を非表示にする

関連記事

• 

  2023-01-08

  ArduinoでDHT11を使って室温を取得し、Mackerelに投稿する

  ELEGOO Arduino用UNO R3スターターキットに同梱されている、気…
• 2021-07-17

  『Go言語で作るインタプリタ』をTypeScriptで実装する(後編)

  前編を書いたのが約1年前なので1年間かかってしまった。wafuwaf…
• 

  2021-06-06

  mackerel-plugin-accesslogを中心にMackerelのコードを読んだ

  グラフのラベル名をいい感じにする簡単なPRを投げた時のメモ。[…
• 

  2021-06-05

  はじめてOSSに新機能追加した

  owという、Lots of built-in validationsなOSSに、BigIntのバリ…
• 

  2021-02-23

  Go の Short variable declarations と Named return va…

  go-mp4という、mp4ファイルをパースしてくれるGoで書かれたライ…

• もっと読む

コメントを書く