goyaccの難しかったところ
goyaccの難しかったところ
goyaccを読む必要があり、下記を読んで勉強した。
難しく感じた以下の項目についてメモしておく。
- ParserがLexerからどう値を受け取って、その値をどうやって識別しているのか
-
%unionには何を書くべきなのか -
%tokenと%typeと%unionと規則部の関係性
理解したいgoyaccのソースコード
k0kubunさんの記事の以下の例を対象に理解していく。
%{
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がLexerからTokenをどう受け取り、定義されたシンタックスと照らし合わせ還元していくか、というところが難しかった。これは具体的にセマンティックスタックの挙動を書いて理解した。
↓SHIFT Token{1} NUMBER という記述が表しているのは、ParserがLexerからToken{1}というトークンと、そのトークンが何であるかという識別子NUMBERを受け取っているという意味である。↓REDUCEはルールとマッチングして還元したという意味だ。
↓SHIFT Token{1} NUMBER
[Token{1}]
↓REDUCE
[NumExpr{1}]
↓SHIFT Token{+} 43(43は+のasciiコード)
[NumExpr{1}, Token{+}]
↓SHIFT Token{1}, NUMBER
[NumExpr{1}, Token{+}, Token{1}]
↓REDUCE
[NumExpr{1}, Token{+}, NumExpr{1}]
↓REDUCE
[BinOp{1+1}]
NUMBERの定義については後述するが、とにかくParserは、LexerからTokenとその種類が渡されスタックにシフトする。そしてスタックを見て規則部に書かれたシンタックスとマッチしたら還元する。
セマンティックスタックやシフト・還元の概念は速習yaccのシフトと還元を読むとよくわかった。
具体的なLexerの挙動については、k0kubunさんの記事を読んで把握した。
Lexはトークンを一つ読み、lvalにトークンリテラルを解釈した結果を入れ、トークンの種類を返すことを期待されている。
https://qiita.com/k0kubun/items/1b641dfd186fe46feb65#yyparseの引数
%unionにはセマンティックスタックに入る値の型を列挙する
%unionには何を書くべきなのかというのが最初わからなかったが、セマンティックスタックに入る可能性のある型を書けば良いということがわかった。
上のセマンティックスタックの例で、スタックには Token・NumExpr・BinOpが入っているが、それが例のgoyaccでは以下のように表現されている。
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
}
%token・%type と %unionと規則部の関係性
%union は型の列挙でしかなく、規則部は文法の定義でしかないので、この2つを紐付けてやる必要があり、それが%tokenと%typeの役割になる。
%type<unionのメンバ名> 規則部で使う名前
%token<unionのメンバ名> 規則部で使う名前
例のgoyaccのソースコードは以下のようになっている。
%union {
token Token
expr Expression
}
%type<expr> program
%type<expr> expr
%token<token> NUMBER
%type<expr> program は「規則部でprogramって書いてあるところの実態は%unionのメンバであるexprだよ」という意味だ。
難しかったのは %token<token> NUMBER だ。%type同様、「規則部でNUMBERって書いてあるところの実態は%unionのメンバであるtokenだよ」という意味なのだが他にも特殊な振る舞いがある。
まず、Lexerは基本的にはトークンの文字コードを返すということを知る必要がある。セマンティックスタックの動作例で、Lexcerは Token{+} と一緒に文字コード43をParserに渡している。
[NumExpr{1}]
↓SHIFT Token{+} 43(43は+のasciiコード)
[NumExpr{1}, Token{+}]
しかし、特殊なケースとして文字コードの代わりにNUMBERを返すケースがあるというのが %token<token> NUMBER の意味になる。いま足し算のできる電卓を作りたいので、あらゆる整数をグルーピングして扱えると便利だ。すべての整数に対して足し算のルールを書くことは難しいからだ。
そして%token<token> NUMBER はGoのソースコードで const NUMBER=54376 と変換されるので、Lexerの実装で文字コードを返す代わりにNUMBERを返すことができる。
例のLexの実装がそのようになっていることを確認する。
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
}
Discussion