/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