jq の簡単なクエリの紹介
.
.key
.[0]
|
goyacc を使ってみる
yacc の使い方
雛形を作る
parser.go.y というファイルを作ります。まずは . という文字列を AST にすることを目指します。大まかなコードの流れとしては Lexer.Lex() で文字列をトークンに分割し、それを Perse して AST にしていきます。ファイル全体はこちら https://github.com/zoncoen-sample/goyacc-jq-query-parser/blob/be513ae6d4bd210b8bc0c439d5140634365e1186/parser.go.y
Lexer
Lex() 関数を実装した Lexer を作ります。今回は簡略化のために、スキャナには text/scanner の Scanner を利用します（これを使えば Go の準拠のもの、例えばダブルクォートで囲まれたものを文字列トークンとして扱う、みたいなところを自分で書かないで済みます）。
. をトークンにできればよいので、そのようにコードを書きます。
type Lexer struct {
scanner.Scanner
result Filter
}
func (l *Lexer) Lex(lval *yySymType) int {
token := int(l.Scan())
if token == int('.') {
token = PERIOD
}
lval.token = Token{token: token, literal: l.TokenText()}
return token
}Parser
type Filter interface{}
type Token struct {
token int
literal string
}
type EmptyFilter struct {}.) がきたら empty_filter とみなして EmptyFilter{} を返します。最初の実装は . の対応のみなので、 filter 全体は empty_filter のみで構成されます。
%union{
token Token
expr Filter
}
%type<expr> filter empty_filter
%token<token> PERIOD
%%
filter
: empty_filter
{
\$$ = $1
yylex.(\*Lexer).result = $$
}
empty_filter
: PERIOD
{
$$ = EmptyFilter{}
}main() を実装する
main() を実装しておきます。yyParse() という関数が goyacc によって生成されるので、それに Lexer を渡して Parse するコードです。
func main() {
l := new(Lexer)
l.Init(strings.NewReader(os.Args[1]))
yyParse(l)
fmt.Printf("%#v\n", l.result)
}parser の生成
parser.go が生成されます。
\$ go tool yacc -o parser.go parser.go.y\$ go run parser.go '.'
main.EmptyFilter{}テストを書く
package main
import (
"io"
"strings"
"testing"
)
var parseTests = []struct {
text string
ast Filter
}{
{".", EmptyFilter{}},
}
func parse(r io.Reader) Filter {
l := new(Lexer)
l.Init(r)
yyParse(l)
return l.result
}
func TestParse(t \*testing.T) {
for i, test := range parseTests {
r := strings.NewReader(test.text)
res := parse(r)
if res != test.ast {
t.Errorf("case %d: got %#v; expected %#v", i, res, test.ast)
}
}
}\$ go test ./.key, .[0] の実装
func (l *Lexer) Lex(lval *yySymType) int {
token := int(l.Scan())
if token == int('.') {
token = PERIOD
}
if token == scanner.Ident {
token = STRING
}
if token == scanner.Int {
token = INT
}
if token == int('[') {
token = LBRACK
}
if token == int(']') {
token = RBRACK
}
lval.token = Token{Token: token, Literal: l.TokenText()}
return token
}empty_filter
: PERIOD
{
$$
}
key_filter
: PERIOD STRING
{
$$ = KeyFilter{Key: $2.Literal}
}
index_filter
: PERIOD LBRACK INT RBRACK
{
$$ = IndexFilter{Index: $3.Literal}
}{".key", KeyFilter{Key: "key"}},
{".[0]", IndexFilter{Index: "0"}},| の実装
| の機能を実装してみましょう。https://github.com/zoncoen-sample/goyacc-jq-query-parser/blob/b4d1b497feed99f467883e1db5270576ebe772c1/parser.go.y
if token == int('|') {
token = PIPE
}filter
...
| filter PIPE filter
{
\$$ = BinOp{Left: $1, Op: $2, Right: $3}
}conflicts という一見エラーかな？と思うメッセージがでてきます。実はこのままでもきちんと動くのですが、一体このメッセージはなんなのでしょうか？
\$ go tool yacc -o parser.go parser.go.y
conflicts: 1 shift/reduce
conflicts: shift/reduce について
'.first | .second | .third'(.first | .second) | .third として解釈すべきなのか、 .first | (.second | .third) として解釈すべきなのかが明示されておらず曖昧だ、という事になります。
| 演算子は左結合（常に左から右へと処理を進めていく）なので、%left<token> PIPE としてその事を明示してやれば、曖昧ではなくなり conflicts は出なくなります。
動作の確認
{".key | .[0]", BinOp{Left: KeyFilter{Key: "key"}, Op: Token{Token: 57351, Literal: "|"}, Right: IndexFilter{Index: "0"}}},
{".first | .second | .third", BinOp{
Left: BinOp{
Left: KeyFilter{Key: "first"},
Op: Token{Token: 57351, Literal: "|"},
Right: KeyFilter{Key: "second"}},
Op: Token{Token: 57351, Literal: "|"},
Right: KeyFilter{Key: "third"}}},