着手。もくもく会では微妙な 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 に、で良いのか。