goyaccで構文解析を行う

go toolにはyaccというものがある。
これはunixの言語処理系で広く使われるyaccというパーサジェネレータのGoバージョンである。
本稿はその使い方を説明するチュートリアルである。

対象読者

goyaccを使う - Qiitaという記事があって、これはgoのyaccを使って簡単な言語の構文解析をして使い方を説明している。
しかし、yaccについての基本的な説明が完全ではなく(例えば%%とか)、yaccを触ったことがない人には若干難しい。
従って、私のようなGoの文法は理解しているがyaccを使ったことがない人向けにごく簡単な使い方を説明する。

参考資料

yacc - The Go Programming Languageが公式のドキュメントっぽいが、これもyaccの文法自体は他に任せている。
RHGの速習yaccがとても参考になると思う。
本稿はあくまで取っ付き易いチュートリアルにしかしないつもりなので、あとでこちらを参照されたい。

困ったときはsrc/cmd/yaccを読むと理解が深まる。

とりあえず動かしてみる

まずは足し算をパースしてみる。
文法としては以下のようになる。

program
    : expr

expr
    : NUMBER
    | expr '+' expr

ようするに+で連結された式１つを全体のプログラムとして扱う。

parser.go.y

%{
package main

import (
    "fmt"
    "text/scanner"
    "os"
    "strings"
)

type Expression interface{}
type Token struct {
    token   int
    literal string
}

type NumExpr struct {
    literal string
}
type BinOpExpr struct {
    left     Expression
    operator rune
    right    Expression
}
%}

%union{
    token Token
    expr  Expression
}

%type<expr> program
%type<expr> expr
%token<token> NUMBER

%left '+'

%%

program
    : expr
    {
        $$ = $1
        yylex.(*Lexer).result = $$
    }

expr
    : NUMBER
    {
        $$ = NumExpr{literal: $1.literal}
    }
    | expr '+' expr
    {
        $$ = BinOpExpr{left: $1, operator: '+', right: $3}
    }

%%

type Lexer struct {
    scanner.Scanner
    result Expression
}

func (l *Lexer) Lex(lval *yySymType) int {
    token := int(l.Scan())
    if token == scanner.Int {
        token = NUMBER
    }
    lval.token = Token{token: token, literal: l.TokenText()}
    return token
}

func (l *Lexer) Error(e string) {
    panic(e)
}

func main() {
    l := new(Lexer)
    l.Init(strings.NewReader(os.Args[1]))
    yyParse(l)
    fmt.Printf("%#v\n", l.result)
}

を、parser.go.yという名前で保存し、go tool yacc -o parser.go parser.go.y; go run parser.go "1+2"などとしてみてほしい。

$ go tool yacc -o parser.go parser.go.y; go run parser.go "1+2"
main.BinOpExpr{left:main.NumExpr{literal:"1"}, operator:43, right:main.NumExpr{literal:"2"}}

となっただろうか。

go tool yacc

go tool yaccはyaccファイルをgoのソースに変換するコマンドである。
-oオプションでそのgoのファイル名を指定する。
動作確認の際は毎度これでgoのコードを生成しないといけない。
y.outputというファイルも生成されるが、本稿では説明しない。

yacc全体の見方

yaccは%%で全体を3分割する。

%{
ヘッダ
%}
%union ....
%token ....
%type ....
%left ....

%%
規則部
%%
ユーザ定義部

規則部に文法を書くとその文法のパースをするfunc(yyLexer) int型の関数yyParseを作ってくれる。(parser.go参照)
規則部全体がyyParse関数のテンプレートだと思って良い。

ヘッダとユーザ定義部には好き放題goのコードを書くことができる。どちらに何を書いても同じである。
普通に考えたらyyParseをラップする関数を書くべきで、この例ではmain()である。

残りの%union,%token,%type,%leftについて説明する。

%union

文法の構成要素はyyParse内で全てyySymType型の変数にいれる。このyySymTypeの宣言が%unionである。
トークン、式、文など全てを区別しつつ全てyySymTypeにいれるために、yySymTypeはstructとして定義される。
規則部の$$ =(後述)はyyVAL.expr =と変換され(yyVALはyySymType型)、トークンや式の代入先にyySymTypeのメンバが使われていることがわかる。

メモリ節約のためにCではunionが使われているから%unionなのだと思うが、Goにはunionがないため実体はstructである。

%token, %type

%tokenと%typeで規則部に出てくる文法の構成要素を宣言しなければならない。
%typeは非終端記号(プログラム、式、文)、%tokenは終端記号(数字や変数のリテラル)のために使う。

%type<unionのメンバ名> 規則部で使う名前
%token<unionのメンバ名> 規則部で使う名前

のように宣言する。

%left, %right, %nonassoc

演算子の結合の方向を決定する。
たとえば、%left '+'と書いておくと、+が左結合になるため1+2+3は(1+2)+3と解釈されるが、
%right '+'とすると1+(2+3)となり、%nonassoc '+'だとエラーになる(3つ以上つなげた時にエラーにしたい場合に使われる)。

%token, %type, %left等は後ろに書くほど結合の優先順位が高くなる。
この例では、最も親要素であるprogramを一番最初に、その子となるexprをその次に、exprの構成要素となる演算子をその次に宣言している。
四則演算を書く場合は、

%left '+' '-'
%left '*' '/'

のようにすると、隣り合う物同士は優先順位が同じで、後に書かれた*と/の優先順位が+と-より高くなる。

yyParseの引数

先ほど、yyParseはfunc(yyLexer) int型であると述べた。
公式のドキュメントにも書いてある、

type yyLexer interface {
    Lex(lval *yySymType) int
    Error(e string)
}

というインターフェースを満たした型を渡さないといけない。lexerとは字句解析器のことである。
Lexはトークンを一つ読み、lvalにトークンリテラルを解釈した結果を入れ、トークンの種類を返すことを期待されている。
Errorはsyntax errorが起きた時のコールバックである。

この例では、goの標準ライブラリtext/scannerのScannerというgoの字句解析器をラップしたLexer型を使っている。

トークンの種類

本稿では字句解析のやり方については説明しない。(goyaccを使う - Qiitaの方を参照)
が、構文解析への接続部分は説明する。

一つ前で「トークンの種類」と言ったが、これは「演算子の文字コード」か「終端記号の識別定数」である。
%token<token> NUMBERという宣言をすると、const NUMBER = 57346に変換される。
Lexは、'+'のような文字コードか、NUMBERのような%tokenで宣言した定数を返せば良い。
(text/scannerは数字リテラルを読み込むとscanner.Intを返すが、LexでこれをNUMBERに変えている)

規則部の書き方

長くなったが、yaccの説明はこれが最後である。
規則部は、BN記法に似た規則で書かなければならない。
Goのコードを書く部分以外は普通のyaccと同じなので、詳細は速習yaccを見て欲しい。

まず、

program
    : expr

expr
    : NUMBER
    | expr '+' expr

のように書く。
そして、各文法規則が解釈された際のコールバックを定義する。

program
    : expr
    {
        コールバック
    }

expr
    : NUMBER
    {
        コールバック
    }

    | expr '+' expr
    {
        コールバック
    }

このコールバックでは、$$というメタ変数にその文法を解釈した結果を入れることを期待されている。
前述した通り、$$は%unionのメンバのいずれかを指している。
expr(%type<expr> expr)のコールバックであればyySymType.expr、NUMBER(%token<token> NUMBER)のコールバックであればyySymType.tokenとなる。

このスコープでは$$の他に、$1, $2 ... のようなメタ変数と、yyParseの引数(このyylex引数を使う)やローカル変数が参照できる。
$1、$2には文法の右辺に相当するyySymTypeのメンバの型の値が入っている。
すなわち、expr '+' exprのコールバックでは最初のexprが$1、'+'が$2、最後のexprが$3に入っている。

これらを好きな型(この例では、NumExpr、BinOpExpr)でラップして$$にいれることで、独自の構文解析を行う。
yaccではASTのroot要素を一番上に書くことになっており、一番上の文法規則のコールバック(すなわち、プログラム全体の解釈が終了した時のコールバック)で、yylex.resultに全体の結果を入れている。

文法の拡張

四則演算ができるように拡張する。

-%left '+'
+%left '+', '-'
+%left '*', '/'

 %%

 program
    : expr
    {
        $$ = $1
        yylex.(*Lexer).result = $$
    }

 expr
    : NUMBER
    {
        $$ = NumExpr{literal: $1.literal}
    }
    | expr '+' expr
    {
        $$ = BinOpExpr{left: $1, operator: '+', right: $3}
    }
+   | expr '-' expr
+   {
+       $$ = BinOpExpr{left: $1, operator: '-', right: $3}
+   }
+   | expr '*' expr
+   {
+       $$ = BinOpExpr{left: $1, operator: '*', right: $3}
+   }
+   | expr '/' expr
+   {
+       $$ = BinOpExpr{left: $1, operator: '/', right: $3}
+   }

1+2*3を入力にすると、

$ go tool yacc -o parser.go parser.go.y; go run parser.go "1+2*3"
main.BinOpExpr{left:main.NumExpr{literal:"1"}, operator:45, right:main.BinOpExpr{left:main.NumExpr{literal:"2"}, operator:42, right:main.NumExpr{literal:"3"}}}

となり、*の結合の優先度が正しく解釈されていることがわかる。
ほぼパースのためのプログラムを書くことなく、最小限の労力で文法を拡張できた。非常に便利。

意味解析

単なる四則演算だが、l.resultはまがりなりにもASTである。
構文解析をしただけでは面白く無いので、最後にこれの意味解析をして終わりにする。

+func Eval(e Expression) int {
+   switch e.(type) {
+   case BinOpExpr:
+       left := Eval(e.(BinOpExpr).left)
+       right := Eval(e.(BinOpExpr).right)
+
+       switch e.(BinOpExpr).operator {
+       case '+':
+           return left + right
+       case '-':
+           return left - right
+       case '*':
+           return left * right
+       case '/':
+           return left / right
+       }
+   case NumExpr:
+       num, _ := strconv.Atoi(e.(NumExpr).literal)
+       return num
+   }
+   return 0
+}

 func main() {
    l := new(Lexer)
    l.Init(strings.NewReader(os.Args[1]))
    yyParse(l)
-   fmt.Printf("%#v\n", l.result)
+   fmt.Printf("%d\n", Eval(l.result))
 }

$ go tool yacc -o parser.go parser.go.y; go run parser.go "14/2-2*3"
1

最終的なコードはこちら。
お疲れ様でした。