『Go言語でつくるインタプリタ』を読んだ。構文解析その２前置演算子・中置演算子編

こんにちは。んだです。今回も前回に続き、構文解析についてお届けします。

前回記事 nda-desu.hatenablog.com

構文解析編は、2回目になりますが、今回は前置演算子・中置演算子の構文解析について書いていきます。

式の構文解析の難しさ
Pratt構文解析
実装
まとめ

式の構文解析の難しさ

式の構文解析は、文の構文解析と比較して難しさがあります。

一つの難しさは、優先順位の問題です。

式には演算子が含まれており、演算子には優先順位があります。

例えば、

7 * 5 + 19

という式では、7 * 5の部分が+ 19よりも先に評価される必要があります。

このような優先順位を正確に反映した構文解析を行う必要があります。

さらに、式は様々な形で表現されることがあります。

例えば、

add(x, y)
foo == bar
fn(x, y){ return x * y }

などです。式の形式に決まりがなく、自由度が高いため、その柔軟性を構文解析に反映させる必要があります。こうした問題に対して、本書では「Pratt構文解析」というアプローチを用いています。

Pratt構文解析

Pratt構文解析については、詳細については理解しきれないので説明はできませんが、本書で説明されている特徴だけ書き残しおきます。

以下は本書からの引用です。

Pratt構文解析器の考え方で重要なのは、トークンタイプごとに構文解析関数を関連づけることだ。あるトークンタイプに遭遇するたびに、対応する構文解析関数がよばれる。この関数は適切な式を構文解析し、その式を表現するASTノードを返す。トークンタイプごとに、最大２つの構文解析関数が関連づけられる。これらの関数は、トークンが前置で出現したか中置で出現したかによって使い分けられる。

これから、式の構文解析の実装をみていきますが、ここでは、「トークンタイプごとに構文解析関数を関連づける」とだけ、押さえておきましょう。

実装

それでは、実装を追っていきましょう。

ParseProgram

まずは、スタート地点であるParseProgramからです。

func (p *Parser) ParseProgram() *ast.Program {
    program := &ast.Program{}
    program.Statements = []ast.Statement{}

    for p.curToken.Type != token.EOF {
        stmt := p.parseStatement()

        if stmt != nil {
            program.Statements = append(program.Statements, stmt)
        }

        p.nextToken()
    }

    return program
}

EOFが来るまで、構文解析を進め、構文的に正しければStatementsに追加します。

parseStatement

続いて、parseStatementです。今回は、式の構文解析ですので、parseExpressionStatementが呼び出されます。

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()
    }
}

parseExpressionStatement

いよいよ、式の構文解析がスタートです。 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
}

まずは、ExpressionStatement構造体のTokenに現在のトークンをセットします。

stmt := &ast.ExpressionStatement{Token: p.curToken}

この状態で、parseExpressionを呼び出します。

parseExpression

parseExpressionは、こんな感じです。

func (p *Parser) parseExpression(precedence int) ast.Expression {
    prefix := p.prefixParseFns[p.curToken.Type]
    if prefix == nil {
        p.noPrefixParseFnError(p.curToken.Type)
        return nil
    }
    leftExp := prefix()

    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
}

まず注目すべきは、この二行です。

prefix := p.prefixParseFns[p.curToken.Type]
infix := p.infixParseFns[p.peekToken.Type]

ここでは、現在のトークンに関連づけられた関数を呼び出しています。

先程「Pratt構文解析器の特徴」の章で説明した

Pratt構文解析器の考え方で重要なのは、トークンタイプごとに構文解析関数を関連づけることだは、まさにこの部分です。

では、prefixParseFnとinfixParseFnの関連付けを行なっている場所にみてみましょう。

これは、New()で行なっています

New

ここで前置演算子と中置演算子それぞれについて、関連付けの設定しています。

func New(l *lexer.Lexer) *Parser {
    p := &Parser{
        l:      l,
        errors: []string{},
    }

    p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
    p.registerPrefix(token.IDENT, p.parseIdentifier)
    p.registerPrefix(token.INT, p.parseIntegerLiteral)
    p.registerPrefix(token.BANG, p.parsePrefixExpression)
    p.registerPrefix(token.MINUS, p.parsePrefixExpression)

    p.infixParseFns = make(map[token.TokenType]infixParseFn)
    p.registerInfix(token.PLUS, p.parseInfixExpression)
    p.registerInfix(token.MINUS, p.parseInfixExpression)
    p.registerInfix(token.SLASH, p.parseInfixExpression)
    p.registerInfix(token.ASTERISK, p.parseInfixExpression)
    p.registerInfix(token.EQ, p.parseInfixExpression)
    p.registerInfix(token.NOT_EQ, p.parseInfixExpression)
    p.registerInfix(token.LT, p.parseInfixExpression)
    p.registerInfix(token.GT, p.parseInfixExpression)

...[略]
}

では、ここまで来たら、最後は、parsePrefixExpressionとparseInfixExpressionをみていきましょう。

parsePrefixExpressionとparseInfixExpression

parsePrefixExpressionとparseInfixExpressionは、それぞれ以下のような実装です

func (p *Parser) parsePrefixExpression() ast.Expression {
    expression := &ast.PrefixExpression{
        Token:    p.curToken,
        Operator: p.curToken.Literal,
    }

    p.nextToken()

    expression.Right = p.parseExpression(PREFIX)

    return expression
}

func (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression {
    expression := &ast.InfixExpression{
        Token:    p.curToken,
        Operator: p.curToken.Literal,
        Left:     left,
    }

    precedence := p.curPrecedence()
    p.nextToken()
    expression.Right = p.parseExpression(precedence)

    return expression
}

ここで着目したい点は、２つあります。

一つ目は、parseExpressionが呼び出されていることです。

parsePrefixExpressionとparseInfixExpressionもparseExpressionから呼び出されていましたよね。しかし、呼び出された側からもparseExpressionを呼び出すという再帰になっています。

これが、Pratt構文解析器がうまく機能する１つ目のポイントだと思います。読み解いていくと、「うまくできてんなー」と興奮しました。

２つ目は、parseExpressionの引数に、優先度を渡している点です。

優先度は以下のように定義されています。

const (
    _ int = iota
    LOWEST
    EQUALS      // ==
    LESSGREATER // > or <
    SUM         // +
    PRODUCT     // *
    PREFIX
    CALL // myFunction(x, y)
)

で、この優先度をparseExpressionに渡すことで、このfor文のprecedence < p.peekPrecedence()の判定に使用されます。

for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
        infix := p.infixParseFns[p.peekToken.Type]
        if infix == nil {
            return leftExp
        }

        p.nextToken()

        leftExp = infix(leftExp)
    }

トークンタイプごとに関連付けされた構文解析関数が再帰的に呼び出され、且つ、優先度によって絶妙なタイミングでASTが組み上がっていきます。

本書の例では、

1 + 2 + 3;

を例に解説しています。

本記事では、逐次的な解説はしませんが、追ってみると「うまくできてんなー」と大変興奮しました。（再帰を追うのはしんどかった。。

まとめ

以上で、前置演算子・中置演算子編を終えますが、コードを追ってASTが組み上がることを理解した時には、嬉しかったです。何度も紙に書いては理解できず、、心折れかけましたが、なんとか辿り着けました。

僕の目標である、コンパイラ編にいくのはまだまだ先ですが、少しづつ前進していこうと思います。

僕から以上。あったかくしてねろよ。

んだ日記

ndaDayoの技術日記です