経験は何よりも饒舌

10年後に真価を発揮するかもしれないブログ 

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

後編はこちら
wafuwafu13.hatenadiary.com


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

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

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

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

といったところです。

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


環境構築

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

字句解析器(レキサー)

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

...
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の構造がデバッグできました。

f:id:wafuwafu13:20200818112246p:plain
Go
f:id:wafuwafu13:20200818112429p:plain
TypeScript

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

f:id:wafuwafu13:20200818112849p:plain
if文

感想

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