/var/log/messages

Aug 20, 2018 - 3 minute read - Comments - programming

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

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 する実装について検討してみます。

scheme 実装 Gremlin Sessions

comments powered by Disqus