『Go言語でつくるインタプリタ』を読んだ。構文解析〜let&return編〜

こんにちわ、んだです。

さて、前回の続きで、構文解析です。構文解析は長いので、何回かに分けて説明していきたいと思います

今回は、let&returnについてです。 nda-desu.hatenablog.com

構文解析とは？

さて、まずは構文解析とは何かについてです。

構文解析器は、字句解析が出力したトークン列をinputとして、抽象構文木（Abstract Syntax Tree、略してAST）と呼ばれるデータ構造を生成します。

図にすると、このような流れです

抽象構文木を構築する間に、構文解析は入力がプログラム言語の文法に従っているかどうかをチェックします。

つまり、プログラムの文法が正しいかどうかを確認する役割も果たしているわけですね。

こういった理由から、この作業は「構文解析」と呼ばれているわけですね。構文解析と聞くと、難しいそうな印象を受けますが、やっていることはシンプルです。

ただし、構文解析の理論の話になると難易度は上がるようです、、本書ではあくまでもインタプリタを自作することに重きを置いているため、詳細な理論には立ち入らないですが、いずれ理論的な話も理解していきたいなと思います。

構文解析 in Go

それでは実際に構文解析のコードを見ていきましょう。

// parser/parser.go

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{},
    }

    p.nextToken()
    p.nextToken()

    return p
}

func (p *Parser) nextToken() {
    p.curToken = p.peekToken
    p.peekToken = p.l.NextToken()
}

まずはp.nextToken()を2回呼び出すことで、curToken（現在のトークン）とpeekToken（その次のトークン）の両方をセットします。これでセッティングは完了です。

あとは、字句解析と同じように順番に一個ずつトークンを読んでいくだけです。

// parser/parser.go
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
}

func (p *Parser) parseStatement() ast.Statement {
    switch p.curToken.Type {
    case token.LET:
        return p.parseLetStatement()
    case token.RETURN:
        return p.parseReturnStatement()
    default:
        return nil
    }
}

やっていることは、シンプルです。

順に読んでいって、tokenTypeごとにそれぞれのparserを呼び出します。それぞれのparser内で構文解析を行い、正しいと判断されたら、ASTに追加されていくわけですね。

では、それぞれのparseLetStatement(), parseReturnStatement()の中では何が行われているのでしょうか。

順番に見ていきましょう。

式と文

letとreturnのパーサーの詳細に立ち入る前に、式と文の違いについておさえていきましょう。

その違いは非常にシンプルで、式は値を生成し、文はしないということです。

例えば、1000は式であり、この式は1000という値を生成します。一方、let x = 1000は、値を生成するわけではありません。そのため、let x = 1000は文ということになります。

この区別は、Monkey言語における区別ですが、プログラミング言語によっては、式と文の区別が異なることもあります。

letの構文

では、式と文の違いを抑えた上で、letの構文について観察してみましょう。

以下は、Monkey言語においてのlet文の有効なプログラムです。

let y = true;
let foobar = 838383;

let add = fn(a, b) { return a + b};

let文の構文は、次のような形で表現することができます

let <identifier> = <expression>;

let の次には、識別子があり、次は＝が来ます。そして、＝の右辺には式がきます。

ということで、let文と識別子の構造体はそれぞれこんな感じです。

// ast/ast.go
type LetStatement struct {
    Token token.Token
    Name  *Identifier
    Value Expression
}

type Identifier struct {
    Token token.Token
    Value string
}

letの構文解析

では、実際にletの構文解析をコードで追っていきましょう。

// parser/parser.go
func (p *Parser) parseLetStatement() *ast.LetStatement {
    stmt := &ast.LetStatement{Token: p.curToken}

    if !p.expectPeek(token.IDENT) {
        return nil
    }

    stmt.Name = &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}

    if !p.expectPeek(token.ASSIGN) {
        return nil
    }
    // TODO: 式の解析を後回しにしているため、セミコロンまで読み飛ばし
    for !p.curTokenIs(token.SEMICOLON) {
        p.nextToken()
    }

    return stmt
}

let の次には、識別子があり、次は＝が来ていることを順に確認し、OKであれば、ASTを構築しています

// TODO: 式の解析を後回しにしているため、セミコロンまで読み飛ばしとありますが、この段階では、＝の次に式が来ているかどうかは、一旦保留にしています。

returnの構文

次にreturnの構文について見ていきましょう。

以下は、Monkey言語においてのreturnの有効なプログラムです。

return 5;
return 993322;

returnの構文は、次のような形で表現することができます

return <expression>;

returnの構造体は以下のように表現できます。

// ast/ast.go
type ReturnStatement struct {
    Token       token.Token
    ReturnValue Expression
}

returnの構文解析

では、returnの構文解析をコードで追っていきましょう。

// parser/parser.go
func (p *Parser) parseReturnStatement() *ast.ReturnStatement {
    stmt := &ast.ReturnStatement{Token: p.curToken}

    p.nextToken()
    // TODO: 式の解析を後回しにしているため、セミコロンまで読み飛ばし
    for !p.curTokenIs(token.SEMICOLON) {
        p.nextToken()
    }

    return stmt
}

まだ式の解析を行なっていないため、シンプルです。ここでもやっていることは、変わらずトークンを左から読み進めていって、構文的に正しいかどうかを確認して、正しければASTを構築しています。

まとめ

今回は、letとreturnの構文解析について見てきました。

構文解析を聞くと、イメージ的には難しそうな印象を持ちますが、行なっていることはシンプルであることがわかりますし、一つ一つ読み解いていくと、よーできているなと感心しますね。

では、また続きを書いていきたいと思います。

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

んだ日記

ndaDayoの技術日記です