/var/log/messages

Aug 19, 2018 - 4 minute read - Comments - programming

scheme 実装

着手。もくもく会では微妙な lexer をでっち上げたところで timeup でした。

もう少し

repl まで実装。がしかし、なんとなく微妙感があります。まず、リテラル式のあたりが微妙。とりあえず

(quote xxx)

という形を、ですね。

とりあえず

手元にある R5RS をもとに色々すすめようと思っています。

cons および dot を追加

そしてそろそろ parse の作戦を練らないと。とりあえず元の parser が

  • 始点は ParseProgram で token が続く限り parseStatement を呼び出す
  • 現時点の状態では parseStatement から let または return あるいはそれ意外の式、という形で分岐してそれぞれを parse

ってなってますね。現状の想定では即値ではない場合には式の始まりは “(” 一択で良いはず。parseSStatement とかにしておけば良いのかな。

とりあえず即値の試験を書きます。ってこれは元ネタの TestIntegerLiteralExpression を流用できるのかな。ひとまず ast なナニを確認します。とりあえず以下とのこと。

package ast

type Node interface {
	TokenLiteral() 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 ""
	}
}

で、parser の最初の状態が以下?

package parser

import (
	"fmt"
	"scheme_interpreter/ast"
	"scheme_interpreter/lexer"
	"scheme_interpreter/token"
	"strconv"
)

type Parser struct {
	l      *lexer.Lexer
	errors []string

	curToken  token.Token
	peekToken token.Token
}

func New(l *lexer.Lexer) *Parser {
	p := &Parser{
		l:      l,
		errors: []string{},
	}

	// Read two tokens, so curToken and peekToken are both set
	p.nextToken()
	p.nextToken()

	return p
}

func (p *Parser) nextToken() {
	p.curToken = p.peekToken
	p.peekToken = p.l.NextToken()
}

func (p *Parser) ParseProgram() *ast.Program {
	return nil
}

忘れてました。以下な試験をスデにでっちあげております。

package parser

import (
	"fmt"
	"scheme_interpreter/ast"
	"scheme_interpreter/lexer"
	"testing"
)

func TestIntegerLiteralExpression(t *testing.T) {
	input := "5"

	l := lexer.New(input)
	p := New(l)
	program := p.ParseProgram()
	checkParserErrors(t, p)

	if len(program.Statements) != 1 {
		t.Fatalf("program has not enough statements. got=%d",
			len(program.Statements))
	}
	stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
	if !ok {
		t.Fatalf("program.Statements[0] is not ast.ExpressionStatement. got=%T",
			program.Statements[0])
	}

	literal, ok := stmt.Expression.(*ast.IntegerLiteral)
	if !ok {
		t.Fatalf("exp not *ast.IntegerLiteral. got=%T", stmt.Expression)
	}
	if literal.Value != 5 {
		t.Errorf("literal.Value not %d. got=%d", 5, literal.Value)
	}
	if literal.TokenLiteral() != "5" {
		t.Errorf("literal.TokenLiteral not %s. got=%s", "5",
			literal.TokenLiteral())
	}
}

func checkParserErrors(t *testing.T, p *Parser) {
	errors := p.Errors()
	if len(errors) == 0 {
		return
	}

	t.Errorf("parser has %d errors", len(errors))
	for _, msg := range errors {
		t.Errorf("parser error: %q", msg)
	}
	t.FailNow()
}

とりあえず、parseProgram を何とかしないと試験にパスしない。

func (p *Parser) ParseProgram() *ast.Program {
	program := &ast.Program{}
	program.Statements = []ast.Statement{}

	for !p.curTokenIs(token.EOF) {
		stmt := p.parseStatement()
		if stmt != nil {
			program.Statements = append(program.Statements, stmt)
		}
		p.nextToken()
	}

	return program
}

次は parseStatement 手続き。とりあえずそのまんまコピします。

func (p *Parser) parseStatement() ast.Statement {
	switch p.curToken.Type {
	case token.LET:
		return p.parseLetStatement()
	case token.RETURN:
		return p.parseReturnStatement()
	default:
		return p.parseExpressionStatement()
	}
}

現時点でここは token.LPAREN とそれ以外、を想定しています。次は parseExpressionStatement ですね。元ネタは以下な定義。

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

	stmt.Expression = p.parseExpression(LOWEST)

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

	return stmt
}

ast.ExprssionStatement は未定義。ここはパクれるはずなので元ネタを使います。

type ExpressionStatement struct {
	Token      token.Token // the first token of the expression
	Expression Expression
}

func (es *ExpressionStatement) statementNode()       {}
func (es *ExpressionStatement) TokenLiteral() string { return es.Token.Literal }
func (es *ExpressionStatement) String() string {
	if es.Expression != nil {
		return es.Expression.String()
	}
	return ""
}

あと、parseExpression が未定義? そろそろ scheme に合わせた修正が必要になってくるはず。parseExpressionStatement の以下の部分は

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

token.RPAREN なのかな。

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

あと、parseExpression は簡単に考えたいので即値限定で実装してやれ。

とりあえず RPAREN で始まっていない場合、即値ってことで良いのかな。てことは

func (p *Parser) parseStatement() ast.Statement {
	switch p.curToken.Type {
	case token.LET:
		return p.parseLetStatement()
	case token.RETURN:
		return p.parseReturnStatement()
	default:
		return p.parseExpressionStatement()
	}
}

は default な分岐でとりあえず parseIntegerLiteral 呼んでいいのかな。なんか違うな。このインタプリタの方法だと式のパースは

  • token に対応する prefixParseFn を取得して呼び出して leftExp にセット
  • 次の token が SEMICOLON ではなくて precedence が次の、より小さい? 場合に次の token の infixParseFn を取り出して、token を次に進めて
  • infixParseFn に leftExp を渡して呼び出して戻りを leftExp にセット

という形になってます (たぶん書き方微妙)。元ネタで prefixParseFns に設定されているのは

  • IDENT
  • INT
  • BANG
  • MINUS
  • TRUE
  • FALSE
  • LPAREN
  • IF
  • FUNCTION

prefix という意味で scheme 的にあり得るのは

  • IDENT
  • INT
  • LPAREN

に加えて quote なのかどうか (ただし現時点では ' は想定していない)。とりあえずこうしてやれ

func (p *Parser) parseStatement() ast.Statement {
	switch p.curToken.Type {
	case token.INT:
		return p.parseIntegerLiteral()
	case token.IDENT:
		return p.parseIdentifier()
	default:
		return p.parseSExpressionStatement()
	}
}

なんというか酷い。あと、parseIntegerLiteral と parseIdentifier は元ネタ流用。

やはり色々酷い

上記だと ast.Expression に wrap されてない形になるな。

紆余曲折の後

試験にパスしている。parseStatement が以下な定義になってます。

func (p *Parser) parseStatement() ast.Statement {
	switch p.curToken.Type {
	case token.INT:
		stmt := &ast.ExpressionStatement{Token: p.curToken}
		stmt.Expression = p.parseIntegerLiteral()
		return stmt
	case token.IDENT:
		stmt := &ast.ExpressionStatement{Token: p.curToken}
		stmt.Expression = p.parseIdentifier()
		return stmt
	default:
		return p.parseSExpressionStatement()
	}
}

微妙。リファクタします。

func (p *Parser) parseStatement() ast.Statement {
	return p.parseExpressionStatement()
}

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

	switch p.curToken.Type {
	case token.INT:
		stmt.Expression = p.parseIntegerLiteral()
	case token.IDENT:
		stmt.Expression = p.parseIdentifier()
	default:
		stmt.Expression = p.parseSExpressionStatement()
	}

	return stmt
}

func (p *Parser) parseSExpressionStatement() ast.Expression {
	return nil
}

識別子

TestIdentifierExpression 追加。これもパス。ようやく S 式なナニが書けるのかどうか。ast てきには SExpression ってナニを追加すべきなのかどうか。と言いつつ結局こうなりました。

	default:
		stmt.Expression = p.parseExpression()
	}

	return stmt
}

func (p *Parser) parseExpression() ast.Expression {
	return nil
}

で、どうするかと言うと

  • 式の parse においては先頭の LPAREN は除去 (nextToken する)
  • prefixParseFn します
  • 括弧閉じるまで sufixParseFn します

prefix はとりあえず

  • define
  • let
  • lambda
  • quote
  • cons

あたりにしておきます。そろそろ真面目に parse しないと駄目なのか。

例えば

quote が一番簡単かな。あと、S 式って意味では演算子の優先度とかスルーでいいのかな。quote の場合は引数一つってことでいいのか。

  • program.Statements は 2
  • quote なので二番目の式は parse しない
  • あら? トークンにもしなくて良いのかな

てことは lexer 修正必要なのか。ちょっと備忘までポイントを箇条書きにしときます。

  • NextToken の分岐な default にて quote な処理を入れる
  • isQuote な手続き追加
  • Literal 属性にデータを入れる (データとしては括弧始まりなら S 式でそれ以外なら即値と見る)

ってなってれば quote の場合はそのまま Literal が Value に、で良いのか。

再帰下降構文解析器 再帰下降構文解析器 (2)

comments powered by Disqus