/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