parser.go の ParseProgram 起点で “1 + 2 + 3” を parse するナニを掘削してみます。
あと、以下なダミーの試験をでっちあげて
func Test123Statements(t *testing.T) {
tests := []struct {
input string
firstValue interface{}
operator1 string
secondValue interface{}
operator2 string
thridValue interface{}
}{
{"1 + 2 + 3", 1, "+", 2, "+", 3},
}
for _, tt := range tests {
l := lexer.New(tt.input)
p := New(l)
program := p.ParseProgram()
stmt, ok := program.Statements[0].(*ast.ExpressionStatement)
if !ok {
}
t.Errorf("%s", stmt.Expression)
}
}
dlv で確認しつつ、なのかどうか。
$ dlv test -- -test.run Test123Statements
(dlv) b Test123Statements
とりあえず New(l)
が吐き出した Parser なオブジェクトの一部が以下です。
(dlv) p p
*monkey/parser.Parser {
l: *monkey/lexer.Lexer {
input: "1 + 2 + 3",
position: 3,
readPosition: 4,
ch: 32,},
errors: []string len: 0, cap: 0, [],
curToken: monkey/token.Token {Type: "INT", Literal: "1"},
peekToken: monkey/token.Token {Type: "+", Literal: "+"},
ParseProgram に step in してみます。
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
}
curToken が EOF になるまで繰り返し、の中で 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()
}
}
LET でも RETURN でもないので 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
}
LOWEST を渡す形で parseExpression が呼び出されます。その中では
- INT (p.curToken の状態) な prefixParseFns (parseIntegerLiteral) を取り出して呼び出し
- parseIntegerLiteral は *ast.IntegerLiteral を戻す
- 値 (p.curToken.Literal) を int に変換して Value 属性に設定
- parseIntegerLiteral の戻りは leftExp に設定される
という前処理の後に繰り返しが開始されています。繰り返しが続くための条件として
- p.peekToken が token.SEMICOLON ではない
- precedence は p.peekPrecedence() より小さい
となっています。peekPrecedence の定義は以下。
func (p *Parser) peekPrecedence() int {
if p, ok := precedences[p.peekToken.Type]; ok {
return p
}
return LOWEST
}
次、の優先度なので現時点では + の優先度になります。とりあえず繰り返しの中には入ることがわかります。繰り返し部分を以下に引用します。
for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
infix := p.infixParseFns[p.peekToken.Type]
if infix == nil {
return leftExp
}
p.nextToken()
leftExp = infix(leftExp)
}
return leftExp
- に対応する infixParseFns は parseInfixExpression になっています。というか現時点では infixParseFns にはこれのみが設定されていますね。そして、この手続きは基本的に *ast.InfixExpression を戻しています。また、呼び出し前に Token を次にすすめていますね。現時点で以下な状態?
1 + 2 + 3
^ ^
parseInfixExpression の定義を順に引用します。
expression := &ast.InfixExpression{
Token: p.curToken,
Operator: p.curToken.Literal,
Left: left,
}
戻すオブジェクトを初期設定して (curToken は + で、left は 1 な *ast.IntegerLiteral です)
precedence := p.curPrecedence()
p.nextToken()
次の Token にすすめて (優先度、も次のもの (+ の優先度ですね) にしています) いるので現状以下。
1 + 2 + 3
^ ^
で、parseExpression 呼び出し、なのか。
expression.Right = p.parseExpression(precedence)
で、parseExpression の中のループには入らない、のか。そして leftExp は *ast.IntegerLiteral が設定されて戻る、と。
ちょいタイム
これまでの、というとこでは以下な順で手続き呼び出してて
- ParseProgram
- parseStatement
- parseExpressionStatement
- parseExpression
- parseInfixExpression
から parseExpression 呼び出し、だったのか。戻す expression としては
- Token は + (簡略表現)
- Operator も + (簡略表現)
- Left は 1 な *ast.IntegerLiteral
- Right は 2 な *ast.IntegerLiteral
になるのですね。で、戻ってきた parseExpression の中の leftExp に上の expression が設定されて Token が進みます。
1 + 2 + 3
^ ^
で、再度 parseInfixExpression 呼び出し、なんすね。作成される InfixExpression は
- Token は +
- Operator は +
- Left は上の InfixExpression
で、優先度と Token が再設定されています。
1 + 2 + 3
^ ^
ここでループ判定は prececence も p.peekPrecedence() の戻りは同じ、になる、から 3 な *ast.IntegerLiteral が戻って Right に設定されて終わり、なのかな (prefixParseFns で作ったソレが設定される)。
もう一度整理
最初からコールグラフを整理。
- ParseProgram
- parseStatement
- parseExpressionStatement
- parseExpression
parseExpression では一度 prefixParseFns な手続きを呼び出して先頭の要素を処理して leftExp に格納している事に注意。
- parseInfixExpression
- parseExpression
この時点で (1 + 2) な式ができあがって parseInfixExpression から脱出。残りを処理するために再度 parseInfixExpression が呼び出されるのか。
今週のもくもくで
S 式を parse する実装について検討してみます。