goにはコンパイラ以外にもいくつか便利なツールがついてきていて、goyaccもその一つだ。yaccはパーサージェネレータで、プログラミング言語みたいな言語を読み取るためのプログラムを生成してくれる。goyaccはそのGo言語バージョンとなっている。

この文章では、簡単な言語を処理するプログラムを作りながら、goyaccを用いた構文解析の方法について説明する。

プログラム全体はdraftcode/goyacc_sampleで参照できる。文章中では抜粋しか載せないので、足りない部分はこちらをみて補って欲しい。

生成する言語

実際に字句解析器や構文解析器を作りながら説明するため、簡単な計算機のようなものを作ることにしよう。作る言語は次のような構文を持つ言語だ。

var a = 123;
var b = a + 1;
a * (b + 2 * a);

字句解析器

字句解析器は、文字列としてのソースコードからトークン列としてのソースコードへ変換するプログラムだ。

プログラムのソースコードに出てくる単語は、いくつかの種類に分けられる。例えばここで作る言語に出てくる単語は、次のどれかに分類される。

• キーワード VAR
• 識別子 IDENT
• 数値リテラル NUMBER
• 代入演算子 '='
• 終端子 ';'
• 開き括弧・閉じ括弧 '(', ')'
• 四則演算の記号 '+', '-', '*', '/'

字句解析器は、ソースコードを単語に分割して、分類分けして出力するようなプログラムだ。ここでは分類される種類のことをトークンと呼ぶ。字句解析器は先のサンプルソースを解析し、次のようなトークンの列を出力する。

[VAR, IDENT, '=', NUMBER, ';', ...]

goには構文解析器を生成するツールはついてくるが、字句解析器を生成するツールはついてこない。このため、字句解析器は他の方法で作る必要がある。字句解析器は手書きでもあまり苦労せずに作れる。次に、lexer.goから抜粋した字句解析器を示す。

type Scanner struct {
	src []rune
	offset int
	lineHead int
	line int
}

func (s *Scanner) scanIdentifier() string {
	var ret []rune
	for isLetter(s.peek()) || isDigit(s.peek()) {
		ret = append(ret, s.peek())
		s.next()
	}
	return string(ret)
}

func (s *Scanner) Scan() (tok int, lit string, pos Position) {
	s.skipWhiteSpace()
	pos = s.position()
	switch ch := s.peek(); {
	case isLetter(ch):
		lit = s.scanIdentifier()
		if keyword, ok := keywords[lit]; ok {
			tok = keyword
		} else {
			tok = IDENT
		}
	case isDigit(ch):
		tok, lit = NUMBER, s.scanNumber()
	default:
		switch ch {
		case -1:
			tok = EOF
		case '(', ')', ';', '+', '-', '*', '/', '%', '=':
			tok = int(ch)
			lit = string(ch)
		}
		s.next()
	}
	return
}

字句解析器Scanner.Scanはトークンを返す。さらにトークンに加えて、そのトークンのもともとの文字列としての表現であるリテラルと、トークンがファイルのどの位置から始まったのかという情報も一緒に返している。

Scanner.Scanはまず、Scanner.peekで現在の先頭の文字を見て、それがアルファベットだったら識別子として読み込み、数字だったら数値として読み込み、それ以外であれば記号として読み取っていく。一文字読み終わったらScanner.nextで次の文字へ進めていく。

キーワードの読み込み方

識別子を読み込むところに着目する。ここでは、普通にScanner.scanIdentifierで識別子を読み込んだ後に、少し変更を加えている。プログラミング言語では識別子とキーワードは区別される。キーワードとは、識別子の中でも特別扱いされるような単語である。例えばJavaScriptではfunctionなどが該当する。特別扱いするために、特別扱いする単語のリストkeywordsを用意しておき、それに該当していた場合は、別のトークンとして認識されるようにしている。

記号を表す定数

キーワードや識別子などは、きちんとそれを表すための定数VARやIDENTなどを定義しているが、記号については定数定義をサボっていて、runeを無理やりintに変換してそれで済ませている。もちろんきちんとADDのような定数を定義してそれを用いることはできるのだが、このようにサボる方法を使っていると、後でgoyaccで使うときに便利なので、一文字からなるトークンであればこれで済ませるとよい。

構文解析器

構文解析器は、トークン列としてのソースコードから木構造を認識するプログラムだ。

プログラミング言語は、いくつかの階層に分けてみることができる。例えば次のようなGoのプログラムを見てみる。

func f(a, b int) int {
	c := g(a)
	return h(a) + b + 2 * c
}

ここには3つの階層がある。

• 宣言: func f(a, b. int) int { ... }
• 文: c := g(a), return h(a) + b + 2 * c
• 式: g(a), h(a) + b + 2 * c

Goの言語仕様にもそれぞれDeclaration, Statement, Expressionとして、分けて記述されている。

それぞれの階層は別の階層を含む。宣言はいくつかの式を含み、式はいくつかの式を含む。このように階層構造になっているため、ソースコードは木構造として認識できる。

構文定義

goyaccのようなパーサージェネレータは、ソースコードがどのような木構造を持っているかについての記述から、構文解析器を生成するプログラムだ。今回作る言語の構文をgoyaccが認識する形で記述すると次のようなものになる。

statement
	: expr ';'
	| VAR IDENT '=' expr ';'

expr
	: NUMBER
	| IDENT
	| '-' expr
	| '(' expr ')'
	| expr '+' expr
	| expr '-' expr
	| expr '*' expr
	| expr '/' expr
	| expr '%' expr

この言語には2種類の文がある。1つは単に式を並べたもの、もう1つは変数定義である。式を並べただけの文は"1+2;"のように式に続けてセミコロンを打てば良いので、expr ';' と記述してある。もう1つの変数定義は"var a = 1+2;"のように書けば良いので、構文の定義もVAR IDENT = expr ';'としてある。このように他の階層の構文定義を利用しながら、また別の構文を定義していく。

これらの構文定義はparser.go.yに記述してある。次のコマンドを実行すると構文解析器が生成される。

$ go tool yacc -o parser.go -v parser.output parser.go.y

このコマンドによって、parser.goとparser.outputが生成される。parser.goは構文解析器で、parser.outputは構文に関する種々の情報となっている。

非終端記号と終端記号

構文定義の中には2種類の記号が出てきている。statementやexprのような、何かの階層を表す記号と、VARや+のような、実際にソースコード中に出てくるトークンだ。前者のことを非終端記号、後者のことを終端記号と呼ぶ。見てわかるとおり、先ほどの字句解析器でサボった一文字のトークンはここで生きていて、構文定義の中で終端記号として扱うことができる。

字句解析器との接続

構文定義をすることができたはいいが、このままでは何もすることができない。まず先に構文解析器が受け取る入力部分から埋めていくことにする。

構文解析器は字句解析器が出力するトークン列を使って処理を行う。パーサージェネレータに字句解析器がどのようなトークンを出力するかを認識させていくために、トークン(とその付属物)の定義を行う。構文定義であるparser.go.yから抜粋する。

%{
package calc

type Token struct {
	tok int
	lit string
	pos Position
}
%}

%union{
	tok Token
}

%token<tok> IDENT NUMBER VAR

ここで、%{から%}まではGoのソースコードとして認識される。先ほど定義した字句解析器はトークンといくつかの付属物を出力していたので、それを表す構造体を定義している。

%unionも構造体なのだが、こちらはgoyaccのほうで認識される。これはあとで何回かに分けて説明する。

%token<tok>で始まるところは、字句解析器が出力するトークン定義である。一文字の記号トークンは定義しなくても認識される。

つぎに、実際に字句解析器の呼び出しを行う部分を抜粋する。

type LexerWrapper struct {
	s *Scanner
	recentLit string
	recentPos Position
}

func (l *LexerWrapper) Lex(lval *yySymType) int {
	tok, lit, pos := l.s.Scan()
	if tok == EOF {
		return 0
	}
	lval.tok = Token{tok: tok, lit: lit, pos: pos}
	l.recentLit = lit
	l.recentPos = pos
	return tok
}

func (l *LexerWrapper) Error(e string) {
	log.Fatalf("Line %d, Column %d: %q %s",
		l.recentPos.Line, l.recentPos.Column, l.recentLit, e)
}

func Parse(s *Scanner) {
	l := LexerWrapper{s: s}
	if yyParse(&l) != 0 {
		panic("Parse error")
	}
}

goyaccはLexとErrorというメソッドを定義した構造体を字句解析器として認識する。先ほど作った字句解析器とインターフェースを合わせるために、ラッパーを噛ませて利用する。

Lexは*yySymTypeという値を受け取っている。この型はgoyaccが定義する型で、実際はあとで説明するとした%unionである。Lexはトークンを表すintを返し、その付随物(リテラルやポジション)を*yySymTypeに入れることを想定しているので、そのよう定義してある。また、エラーハンドリングのために、最後に渡したリテラルなどを別途保存して利用している。

このラッパーを利用してgoyaccが定義するyyParseに渡すことでLexが呼び出されていき、構文解析が始まる。yyParseは0を返すと正常終了でそうでない場合はエラーとなる。

抽象構文木を返すようにする

このまま動かすこともできて、きちんと構文が認識されればParseは何もせず返ってきて、構文エラーがあるとpanicで終了する。しかし、ここではもうちょっと意味のある値を返すようにしたい。ここでは抽象構文木を返すようにしてみよう。

抽象構文木はast.goで定義してある。例えば変数定義の文に対応する抽象構文木は次のようになる。

type VarDefStatement struct {
	VarName string
	Expr Expression
}

このように後々の処理で必要になる情報だけ取り出して、それを構文解析器が返してくれればよい。つまり、変数定義の文を認識したら、それに対応するようにVarDefStatementを作って、それを返してくれるようにしたい。

goyaccは各非終端記号・終端記号に対して「こういう値を返す」ということを定義することができる。%unionの定義あたりを次のようにする。

%union{
	statements []Statement
	statement Statement
	expr Expression
	tok Token
}

%type<statements> statements
%type<statement> statement
%type<expr> expr
%token<tok> IDENT NUMBER VAR

%unionは「こういう値を返す」の「こういう値」を合わせた構造体になる。そして、%type<...>や%token<...>で「この非終端記号・終端記号は%unionの中のこのフィールドに代入できる値を返す」ということを定義できる。

次に「こういう値」を実際に作るために、構文定義の方を整えていく。VarDefStatementを作る部分を抜粋して示す。

statement
	: VAR IDENT '=' expr ';'
	{
		$$ = &VarDefStatement{VarName: $2.lit, Expr: $4}
	}

中括弧で囲まれた部分はGoのソースコードになる。ただし、$$や$2などの特別な変数が使える。

$$はその構文の返り値を現す変数である。例えばstatementは%unionの中のstatementフィールドに代入できる値を返すとしたので、$$はStatement型の変数になる。ここではVarDefStatementを作って、それを代入している。

$2のような変数は構文定義中に出てくるトークン列の値になる。例えばこの変数定義では次のように特殊変数が定義される。

• $1(VAR): Token
• $2(IDENT): Token
• $3('='): Token
• $4(expr): Expression
• $5(';'): Token

このようにほかの構文の値を参照できるので、これを用いて新しく値を作っていくことになる。例えばvar a = 1 + 2;のような文を考える。この中で1 + 2の部分はexprで処理されて、その中で$$に適切なExpression型の値が代入される。そうすると今度はstatementで変数定義の文として認識されたときに、さっきexprで$$に代入された値が、今度は$4として現れて使えるようになる。そして、また$$に代入されたStatement型の値は、別のどこかの構文定義で$3みたいな形で現れる。これを続けていくことで、読み込ませたトークン列全体が一つの値になるまで変換されていく。

トップレベルの値を返す

ここまででトークン列から構造を抜き出して、それを今度は値に変換していくというところまで出来た。最後に出来た値をParseを呼び出した側に返したい。しかし残念なことに、Parseが呼び出すyyParseはエラーがあったかどうかの整数値しか返してくれない。

最後に出来た値を返すようにするには、ちょっとトリッキーなことをしなければいけない。その部分を抜粋して示す。

statements
	: statement statements
	{
		$$ = append([]Statement{$1}, $2...)
		if l, isLexerWrapper := yylex.(*LexerWrapper); isLexerWrapper {
			l.statements = $$
		}
	}

今作っている言語は最終的にプログラムは[]Statement型の値になるように変換していく。これはその部分の構文定義になる。通常のように$$という変数に値を代入しているが、それ以外にも何かを行っている。

この構文定義で書ける{...}の部分では$$や$2以外にもyylexという変数を使うことができる。この変数はyyParseに与えた字句解析器が入っている。そこで、字句解析器の中に最終的に返すべき値をコッソリ保存しておき、最後にその値を返すようにする。保存できるようにするために、LexerWrapperの定義を少し変えておく。

type LexerWrapper struct {
	s *Scanner
	recentLit string
	recentPos Position
	statements []Statement
}

func Parse(s *Scanner) []Statement {
	l := LexerWrapper{s: s}
	if yyParse(&l) != 0 {
		panic("Parse error")
	}
	return l.statements
}

新しくstatementsというフィールドが出来ており、Parseではそこに保存された値を取ってきて無理やり返している。

別の方法: グローバル変数で返す

グローバル変数を用意して、それを経由して最終的な値を返すようにするという方法もある。しかし、goyaccはグローバル変数に依存しないようなプログラムを生成してくれるので、最後の最後でグローバル変数に依存してしまうのも、あまり良くない気がする。この字句解析器に値を埋め込んでしまう方法もかなり汚い方法だとは思うが、少なくとも構文解析器自体のリエントラント性は保つことができる。

落とし穴: スタックの値の参照を返してはいけない

goyaccの内部では%unionの構造体のスライスを用いて各構文の値を保持している。なので$$は常にzero-valueであるわけではなく、前に使用した値が入っていたりする。逆に言えば$$に入れた値は構文解析が進む中で書き換えられる可能性がある。よって、例えば&$3のように構造体中の値の参照を利用してはいけない。

C言語だと、そもそもこういった参照を取ろうとしたときに「変なことをやっている」という感覚があるのだが、Goだと一見スタックに乗っていそうな値でも、参照を取って返すことができる。goyaccのアクション部分でそれをやると、変なバグを埋め込むことになる。$4のような記号は、変数に見えて実は違うので注意したい。

評価器

字句解析器によって、文字列がトークン列に分解されるのを見た。また構文解析器によってトークン列が抽象構文木に変換されるのを見た。ここまでで、goyaccの使い方としては終わりなのだが、中途半端になってしまうので、簡単な評価器を作った。ソースコード中のevaluator.goを参照されたい。評価器は特に特別なことを行っておらず、素朴に式の評価を行っているだけである。

まとめ

小さな言語処理系の作成過程を通して、goyaccの使い方について説明した。しかし説明しきれていない部分もある。

• goyaccが入力として受け取るファイルの構成
• 演算子の優先順位
• 抽象構文木の定義

これらを補うために、この文章を書くうえで参考にしたものを紹介していく。また、より興味がある人に向けて、どのような情報があるのかを紹介する。

• 普通のyacc

  goyaccは単にyaccのGoバージョンというだけなので、普通のyaccの知識がだいたいそのまま使える。普通のyaccについては速習yaccが参考になる。

• Goの標準パッケージ

  抽象構文木などをどう定義していくかについては、Goの標準パッケージであるgo/astが参考になる。ここで扱った言語処理系でも、go/astパッケージを参考にして抽象構文木を定義した。また、字句解析器もgo/scannerパッケージを参考にして作成した。goのソースコード中のsrc/pkg/go/astやsrc/pkg/go/scannerが該当する。

• goyaccコマンド

  goyacc自体も実はGoで書かれている。このプログラムは結構小さく、1つのファイルで3500行弱に収まっている。中でどのような処理を行っているのか、出力されるソースコードはどういう構成になっているのか、どのような定義が認識されるのかといったことについて簡単に知ることができる。src/cmd/yaccがソースコードになる。同じディレクトリにサンプルソースが置いてあるので、そちらも参照したい。

• goの処理系

  goの処理系自体もパーサージェネレータを利用して構文解析器を作っている。goはyaccではなくBisonを使っているのだが、ファイル構成自体はあまり変わらない。src/cmd/gc/go.yが構文定義ファイルになる。

• エラーメッセージ生成

  goの処理系では面白いことに、yaccが生成するparser.outputのようなファイルから構文エラーのメッセージを自動生成している。src/cmd/gc/bisonerrorsがエラーメッセージを生成するスクリプトになる。冒頭にこのエラーメッセージを生成する方法のベースとなった論文が参照されている。Generating LR syntax error messages from examples

• 書籍など

  有名どころだとThe Dragon Bookとか最新コンパイラ構成技法だが、分厚いのであまり読む気に慣れない。(後者はまだ読める気がする。)

  字句解析や構文解析だけに絞って、より詳しく知りたいのであれば、背景にあるのはオートマトン理論なので、大学の情報系のシラバスをみてそこら辺の教科書なりを見れば概要はつかめる。

  もっと真面目なコンパイラの作り方であれば、MinCamlの解説や東大のコンパイラ演習あたりの資料あたりが参考になりそう。ちょっと外れるが、型推論とかについてゲーム感覚で演習をやりたいのであれば、プログラミング言語の基礎概念の演習システムがよい。

• 演習など

  現在はDSLだったらRubyなどを使って内部DSLを書いたり、YAMLとかにのせて済ませたほうが楽なので、いちいち構文解析をして言語をつくることも無いだろう。それでもいくつか言語処理系をつくってみたいのであれば、例えば今回の計算機をベースに次のようなことができるだろう。

  • Goのようなセミコロン自動挿入
  • 関数定義・関数呼び出しの導入
  • ifやforなどの制御文の導入
  • VMコードや他言語へのコンパイル

  VMなどは自分で適当な命令をもつ機械を定義して、それが実行できる形に変更してやればよい。今はJVM上で動く言語が流行りだが、JVMも命令セットは簡単なのですこし学んでみればclassファイルにコンパイルできる。JasminというJVMアセンブラがあるので、それを利用すると楽にできるだろう。JVM自体について学ぶにはProgramming for the Java Virtual Machineが詳しく書いてあり、読みやすかった。

  より小さい構文解析だけに絞って演習をしてみたいのであれば、プログラミングコンテストの構文解析系の問題を解いてみるのがよいだろう。Aizu Online Judgeにある構文解析カテゴリの問題が手軽で良い。しかし、プログラミングコンテストで出される構文解析の問題は再帰下降構文解析ですぐ解けてしまうので、あまり面白くないかもしれない。再帰下降構文解析の方法については構文解析 Howtoという文章を書いたので、そちらを参照されたい。

• 関数型言語の世界

  関数型言語における構文解析はまた別の世界にいっている。例えばHaskellの入門書では頻繁に構文解析の問題を取り扱っているように思える。ICFPあたりの論文を探していれば、いくつか構文解析に関する論文が見つかるはずなので、それらを読むとYaccとは違うアプローチをとっていて面白いと思うはずだ。タイトルが煽っていて面白いのでYacc is deadを読んでみるといいかもしれない。