Goのioで頻出するio.Reader/Writer あと解析処理

久しぶりにGoで IO を扱うプログラムを書いた。全然ダメだったので振り返った。辛い。ついでに字句解析・構文解析に使える道具もまとめておく。

基本

io.Reader 関連で便利なものを並べる。書かないけど stringsパッケージは目を通して覚えておく。

io.Pipe()

io.Reader, io.Writer のそれぞれを受け取る関数をつなげたい時に便利。システムの PIPE(2) ではないためそこまで重くない。

1
2


pr, pw := io.Pipe()
defer pw.Close()

どちらをクローズしても良いのだけど、書き込み側で閉じるのが丁寧だと思う。読み取り側から終了を通知したい時は context でキャンセルする。(古いバージョンのGoなら終了用のチャンネルを使う)

io.TeeReader()

io.Reader から読み込みながら裏で io.Writer に書き込める。

1
2


file, _ := os.Create("tmp.txt")
tr := io.TeeReader(os.Stdin, file)

bytes.NewBuffer, NewBufferString

便利な bytes.Buffer を作る。

1
2
3
4
5
6
7


	buf := bytes.NewBuffer([]byte{})
	bufStr := bytes.NewBufferString("")
  buf.Write([]byte{'a'})
  buf.WriteString("b")
  buf.WriteByte('c')
	buf.String()
	bufStr.String()

strings.Builder

strings.Builder が bytes.Buffer 置き換えとして1.10から追加されていた。

1
2
3
4


builder := &strings.Builder{}
fmt.Fprintf(builder, "%s\n", 10)
fmt.Fprintf(builder, "%s\n", 12)
fmt.Println(builder.String())

文字列処理

ここからは字句解析と構文解析のまわりについてメモする。はじめにそれぞれの選択肢を列挙して、その後ろでそれぞれのリンクや具体例の節をつづける。

構文解析の選択肢

既存の便利なツールがある。

字句解析の選択肢

lex のportツールを使う
- golex
標準パッケージを使い回す
自作
- イテーレーティブに自作
- Lexical Scanningで自作

ref.

Lexical Scanningって状態マシンの状態を関数で実装してcoroutineとして回すLuaのパターンに似てると思った。

fmt.Scannerを使う

goyaccのメモ

goyaccはyaccのgo版のツールで本体では使わなくなったので拡張扱いに格下げされている。最近はトップダウン型が主流みたいだけどこれはyaccはボトムアップ型。計算機になる単純な定義をテンプレートとして準備することにした。

構文解析器を実装するには Lexer と構文規則を定義しないとならない。 yaccファイルだと補完などしにくいのでLexerの定義は同一パッケージ内の別ファイルで書く。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


package main

import (
	"text/scanner"
)

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)
}

ここでは Lexer を text/scanner で実装している。真面目な文法で if などをトークンとして扱いたい時は scanner.Ident の一部を l.TokenText() を元に分岐させて実装する。もちろん他の方法で Lexer を定義してかまわない。

yacc ファイルはこんな感じ。

%{
package main

import (
    "io"
)

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

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

%union{
    token Token
    expr  Expression
}

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

%left '+' '-'
%left '*' '/' '%'
%left '(' ')' '<' '>' '{' '}' '[' ']'

%%

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

expr
    : NUMBER
    {
        $$ = NumExpr{literal: $1.literal, token: $1.token}
    }
    | '<' expr '>'
    { $$ = $2 }
    | '(' expr ')'
    { $$ = $2 }
    | '{' expr '}'
    { $$ = $2 }
    | '[' expr ']'
    { $$ = $2 }
    | 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} }

%%

func parse(r io.Reader) *Lexer {
	l := new(Lexer)
	l.Init(r)
	yyParse(l)
	return l
}

これらを準備したら下のようにして parser.go を生成する。

1
2


go get golang.org/x/tools/cmd/goyacc
goyacc -o parser.go parser.go.y

PEG

Parsing Expression Grammar(PEG)は再帰下降構文解析器を生成する。構文はBNFっぽいけど先頭から順に検証されるため文法が曖昧にならない。 goでは pointlander/pegが有名どころ。

1

$ go get github.com/pointlander/peg

!. がEOFを表す。

GolangとPEGで作る言語処理系 vol.1が雰囲気掴むのによかった。

Antlr

OSXで使うには下でいける。

1
2


$ brew install antlr
$ go get github.com/antlr/antlr4/runtime/Go/antlr

Antlrは昔からある再帰降下型パーサジェネレータ。木文法も取り扱えることになってたがv4を読むとなさそう。代わりにListener,Visitorがある。

大昔(v3)時代に少し遊んだ記憶がある。v4の今ではGoもターゲットに選べる。

Goの場合、package名は antlr 実行時にコマンドオプションで渡す。

1

antlr  -Dlanguage=Go -package main Calc.g4

公式のGetting Startedで雰囲気を掴める。とりあえず計算機の例を書いた。Makefileも作ってる。

文法については下の3つのドキュメントでかなりの部分を知れる。

字句解析のトークン・ルールは大文字で始める、構文解析は小文字で始める。文字・数値・アンダースコアが使える。また token 句で明示的にトークンを定義して構文解析のコールバックなどで利用したりできる。

Lexerの channel() は識別されたトークンをどこに流すか? を定める。Goをターゲットにした生成コードを確認すると下みたいにデフォルトチャンネルとコメント用チャンネルが定義されていた。

1
2
3


var lexerChannelNames = []string{
    "DEFAULT_TOKEN_CHANNEL", "HIDDEN",
}

PaserにはLexerを渡さずTokenStreamを渡すのだがTokenStreamの生成関数で利用するチャンネルを指定する。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


package main

import (
        "fmt"

        "github.com/antlr/antlr4/runtime/Go/antlr"
)

func main() {
    input := antlr.NewInputStream("(12+3)*4")
    lexer := NewCalcLexer(input)
    stream := antlr.NewCommonTokenStream(lexer, 0)

    p := NewCalcParser(stream)
}

この antlr.NewCommonTokenStream(lexer,0) の0が lexerChannelNames []String のインデックスに対応していてここでは "DEFAULT_TOKEN_CHANNEL" となっている。

構文解析ルールでは{}をルールに埋め込むことでアクションを設定できる。左の内容がマッチした時点で実行される。基本的にターゲットのコードを書くけど特殊な変数が4つ(text, start, stop, ctx)用意されていて $text のように参照できる。他にルール内に var_name= でラベルを貼ることでルールの一部でマッチした箇所のctxを参照できる。その場合も $var_name で参照する。詳しくはantlr4/actions.mdに書かれている。

ちなみに $start, $stop はToken型で定義はantlr4/token.goにある。 $ctx の型はここだけど変更するレシーバ関数は呼ばない方が良さそう。

構文解析中に意味解析を利用することもできる。まず準備として局所変数を定義したり記号表を準備し、前述のアクションでそれらに変更を加えておく。そしてParserルール内に {}? を使うことで意味解析を利用した構文解析を行うことが出来る。かなり複雑な文法(文脈自由でない文法)を扱うのに使えるらしい。この述部は字句解析でも使える。

ちなみに意味解析をASTを処理する別ステージに分けてしまえば構文解析で述語を使わなくて済むはず。 Paser, Lexerは github.com/antlr/antlr4/runtime/Go/antlr に定義された型を経由してやり取りする。

Paserは antlr.Paser というインタフェースを満たしていて antlr.BaseParser をコンポジットしている。

Java をターゲットにした場合 grun というコマンドがパーサーをシミュレートしてASTを可視化してくれる。

-visitor -listener というオプションを指定することでvisitorやlistenerインタフェースも生成される。GoのインタフェースはそれぞれParseTreeListener,ParseTreeVisitor。

Listenerは構文解析の各ルールにEnter,Exitに対するイベントハンドラ集で構文解析器に渡して使う。一方で Visitor は構文解析の結果、構築されるコンテキスト(構文木のノード)に渡して使う。構文解析器でパースしてトップレベルのコンテキストに渡して使う。 antlrのアクション中で渡すことも出来るが、インタフェース定義は構文定義から生成されるのでインタフェースが生成される前にインタフェースを満たすコードを書かないとならず不自然な実装になる。

text.Scanner

目的によってはtext/scanner.ScannerをLexerに使える。フラグと渡せる関数によって挙動を少し変えられる。

1
2


sc := &scanner.Scanner{}
sc.Init(bytes.NewBufferString("[ 10, 20 ] * 4*"))

挙動の変更に使うフィールドは Mode uint, Whitespace uint64, IsIdentRune func(ch rune, i int) bool の3つ。

Mode はスキャン対象を選択しコメントをスキャンする場合にコメントをスキップするか選ぶ。選べる対象はscannerの定数定義を確認する。

1
2
3
4
5
6


sc.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanChars | scanner.ScanComments
// e.g.)
//     ScanInts -> recognize 20
//     ScanCharts -> recognize 'c'
//     ScanStrings -> recognize "string"
//     ScanRawStrings -> recognize `raw string`

Whitespace は空白文字として扱う対象を指定する。仕組上、ASCIIの64より小さい値しか対象にできない。 scannerの定数定義にあるように GoWhitespace で '\t', ‘\n’, ‘\r’, ' ‘ を空白文字として扱ってる。

1
2
3
4
5
6


  const GoWhitespace = 1<<'\t' | 1<<'\n' | 1<<'\r' | 1<<' '

  // Scan()の中で使われている箇所
	for s.Whitespace&(1<<uint(ch)) != 0 {
		ch = s.next()
	}

IsIdentRune は Mode に ScanIdents (識別子)を含めて初めて使われる。スキャン中に今の文字を識別子に含めるか判断する。

例えば下のように設定すると rune が文字(カテゴリL)かアンダースコアか先頭を除く数字である場合に識別子の一部だと判断している。色々とカスタマイズできるが識別子はハイフンで終わらないといった規則を表現できない。

1
2
3
4
5
6


sc.IsIdentRune = func(ch rune, i int) bool {
    if ch == '_' || unicode.IsLetter(ch) || unicode.IsDigit(ch) && i > 0 {
        return true
    }
    return false
}

unicodeパッケージ

rune のカテゴリ判断などに便利なのがunicodeパッケージ。パッケージ定数やパッケージ変数を眺めると文字コードやカテゴリについて知りたくなる。

go/scanner

go/scannerを流用するのも手として考えられる。token.Tokenが認識されるので、これで記述できるなら楽。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103


const (
    // Special tokens
    ILLEGAL Token = iota
    EOF
    COMMENT

    // Identifiers and basic type literals
    // (these tokens stand for classes of literals)
    IDENT  // main
    INT    // 12345
    FLOAT  // 123.45
    IMAG   // 123.45i
    CHAR   // 'a'
    STRING // "abc"

    // Operators and delimiters
    ADD // +
    SUB // -
    MUL // *
    QUO // /
    REM // %

    AND     // &
    OR      // |
    XOR     // ^
    SHL     // <<
    SHR     // >>
    AND_NOT // &^

    ADD_ASSIGN // +=
    SUB_ASSIGN // -=
    MUL_ASSIGN // *=
    QUO_ASSIGN // /=
    REM_ASSIGN // %=

    AND_ASSIGN     // &=
    OR_ASSIGN      // |=
    XOR_ASSIGN     // ^=
    SHL_ASSIGN     // <<=
    SHR_ASSIGN     // >>=
    AND_NOT_ASSIGN // &^=

    LAND  // &&
    LOR   // ||
    ARROW // <-
    INC   // ++
    DEC   // --

    EQL    // ==
    LSS    // <
    GTR    // >
    ASSIGN // =
    NOT    // !

    NEQ      // !=
    LEQ      // <=
    GEQ      // >=
    DEFINE   // :=
    ELLIPSIS // ...

    LPAREN // (
    LBRACK // [
    LBRACE // {
    COMMA  // ,
    PERIOD // .

    RPAREN    // )
    RBRACK    // ]
    RBRACE    // }
    SEMICOLON // ;
    COLON     // :

    // Keywords
    BREAK
    CASE
    CHAN
    CONST
    CONTINUE

    DEFAULT
    DEFER
    ELSE
    FALLTHROUGH
    FOR

    FUNC
    GO
    GOTO
    IF
    IMPORT

    INTERFACE
    MAP
    PACKAGE
    RANGE
    RETURN

    SELECT
    STRUCT
    SWITCH
    TYPE
    VAR
)

golex: LexのGo版を書いてる方がいる

modernc.org/golex ってツールがある。

Golex is a lex/flex like (not fully POSIX lex compatible) utility

とのこと。

マクロ定義	用途
%yyc	現在の文字に対応するマクロ
%yyn	次の文字に移動する処理に対応するマクロ
%yyb	行の先頭かどうかを論理値で返すマクロ (正規表現の’^re’的なものに有用)
%yyt	現在のlexerのステートをintで返すマクロ

examplesが参考になるが、 lex コマンドのように字句解析関連コードがそのまま生成されるだけなので、ヘッダパート内 %{, %} の箇所で関数定義を開いておき、フッタ部分で閉じないといけないなど、少し読みにくくなりそう。

素でLexerを書く: Lexical Scanning

公式の字句解析生成器はないし golex も少し使いにくい。既存のライブラリに使える字句解析器が見つからなかった場合、構文解析も必要な場合は PEG, Antlr が候補になるが自分で書くのも考えられる。

Lexerの状態を stateFunc として定義して処理したトークンをchan経由で提供するパターン。

実装例

素でLexerを書く: 逐次的

素朴に書く。力技で書く感じ。実際これでも良いらしい。安定しちゃったらメンテナンス少ないから多少汚くても良いよとのこと。

実装例

masu-mi's blog(dirty pages)

Search

Recent Posts

主に2023年をふりかえる

Goチャンネルをwatchする

VyOSでVRRPとSTP

RaspberryPiでスイッチ配下をブロードバンドルーターに繋げた

VTYSHでstaticルートを設定した時の動き

VyOSのconfigureの出自

VyOSでVXLAN

VyOSでVLAN

VyOSでIPIP

VyOSでIPSec

Tags

基本