Plan 9とGo言語のブログ

主にPlan 9やGo言語の日々気づいたことを書きます。

Go+goyaccでシェルを実装する

Go Exported from Qiita

この記事はQiitaで公開されていました

この記事は、Go2 Advent Calendar 2017の17日目です。

特にこれといったネタがなかったので、goyaccを使ってシェルを実装してみました。

何をしたのか

Linux/macOSなどのUnix系OSには、bashやzsh、fishなどあります。これらはとてもよく出来ていて、ユーザインタフェースとして使う分にはあまり困りません。しかし、プログラムを書く言語としては、少々貧弱であったり直感的でない文法があったりして、微妙だなと思っていました。例えばスペースを含む場合、どこでクオートが必要で、どこで書いてはいけないのかを正しく行うのは難しいです。

Plan 9にはrcという、とてもCに近い文法のシェルがあって、これはプログラミング言語としてよくできています。Infernoのシェルにも、モジュールをロードするなど面白い要素があります。これらを参考に、今年はGoでプログラムを書く言語としてのシェルを実装しました。

このシェルは、プロンプトやヒストリなど、インタラクティブな機能はほとんどありません。また、最低限動作する程度なので、必要だけれど実装が終わっていない機能などはいっぱいありますが、最低限は使える状態まで実装できたかなと思います。

使い方

以下のコマンドでインストールできます。

$ go get github.com/lufia/qsh

qshを実行しても、現在はプロンプトなど一切出ませんが、1行入力すれば入力されたコマンドを実行します。終了する場合は ctl+d を入力してください。

$ qsh

ある程度は他のシェルと同じですが、Plan 9の rc と Infernoの sh を参考にしているので、少し変わった文法があります。

文法

コメント

コメントは他のシェルと同じで#から行末までを無視します。ただし、文字の途中に含まれるものはそのまま文字として扱います。

# この行は無視する
echo a#b # "a#b"と出力
echo '#E'   # "#E"と出力

コマンド実行

普通に書けばコマンドとして実行します。他と異なり、コマンド名に/を含む場合でもPATHから探して実行します。

ls -l
gitlab/users -a  # $HOME/bin/gitlab/usersを実行

PATHにサブディレクトリが作れるのはPlan 9でも多用されていますが、とても便利だと思います。

変数

変数は全て一次元のリストです。リストは(a b c)のように、カッコとスペースで表します。a=1のように書くこともできますが、これはa=(1)と等価です。また、全て大文字の変数は、自動的に環境変数として昇格するためexportする必要はありません。

ranks=(S A B C)
echo $ranks     # "S A B C"と出力

API_TOKEN=xxxx   # 全て大文字なら環境変数になる
bash -c 'echo $API_TOKEN'  # "xxx"と出力

特別に、PATHという文字を含む環境変数は、他のプロセスが参照した時に困るため、エクスポートする時に要素の区切りをfilepath.ListSeparatorへ変更しています。

PATH=(/bin /usr/bin)
echo $PATH           # "/bin /usr/bin"と出力
bash -c 'echo $PATH' # "/bin:/usr/bin"と出力

変数を使って変数を間接参照することもできます。

Jan=1
January=Jan
c=January
echo $$$c    # "1"と出力

スペースもまともに扱えます。

touch 'a b'
args=(-l 'a b')
ls $args
# ls -l 'a b'を実行

今のところ、リストから特定の要素を取り出すことはできませんが、近いうちに$a(1)のような書き方で取り出せるようにする予定です。

If文・For文

これらは、よくあるシェルと見た目は異なります。Infernoのシェル由来ですが、ifの条件ブロックには複数のコマンドを書けるので少し便利です。

for i in 1 2 3 {
    echo $i
}

if { echo a | grep -q . } {
    echo match
}

&&や||で繋げることもできます。こっちは他のシェルと同じです。

cmp -s a b && echo same  # aとbが同じ内容ならsameと出力
cmp -s a b || echo diff  # aとbが異なる内容ならdiffと出力

リダイレクト・パイプ

普通ですね。

echo hello >out   # 出力
echo hello >>out  # 追記
cat <in           # 入力
echo hello | wc   # パイプ

モジュール

少し実験的な機能も入れてみました。load命令で、Goで実装した関数を呼び出せます。Goのpluginパッケージを使って、シェルの機能を拡張するものです。

まずGoで以下のようなプラグインを実装します。

package main

var SampleModule = map[string]string{
    // Hello関数をhelloという名前でシェルから呼び出せるようにする
    "hello": "Hello",
}

func Hello(args []string) ([]string, error) {
    a := make([]string, 0, len(args)+1)
    a = append(a, "hello")
    return append(a, args...), nil
}

このとき、ファイル名はsnake_caseで付けてください。また、モジュールの名前(上記の場合はSampleModule)は、ファイル名をCamelCaseにして、末尾に Module を付けたものになります。上記例は、ファイル名がsample.goなので、モジュール名はSampleModuleです。sys_util.go の場合は SysUtilModule になります。

モジュールの実装ができたら、プラグインとしてコンパイルします。Go 1.9.2現在、Linuxしかサポートされていません。

$ go build -buildmode=plugin sample.go

これで sample.so が生成できるので、シェルからロードして使いましょう。モジュールは${name}で呼び出します。

load sample          # プラグインの読み込み
echo ${hello world}  # "hello world"と出力

実装について

簡単にですが、実装について説明します。言語を実装する場合、ざっくり以下のフェーズを実装する必要があります。

他にも、最適化を行う場合もありますし、コード生成を行わずにツリーを直接実行する場合もありますが、単純な言語でない限りはコード生成を行ったほうが便利だと思います。

今回はgoyaccを使ったので、それを前提に書きます。goyacc自体の説明は、以下の記事を参考にしてください。

または、ANSI以前のC言語ですが、UNIXプログラミング環境にもyaccを使って計算機を作る章があり、とてもわかりやすいのでオススメです。

注意事項

全部書くと長くなるので、以下のコードは、雰囲気を知ってもらうために色々と省略して書いています。実際に動作するコードが見たい場合はリポジトリのコードを参照してください。

字句解析

字句解析は、言語のトークンを分割するものです。例えば以下の場合。

if { true } {
    echo a is $a | wc
}

これは次のように分割します。

type Node struct {
    Type int
    Str  string
}

Node{Type: IF}
Node{Type: '{'}
Node{Type: WORD, Str: "true"}
Node{Type: '}'}
Node{Type: '{'}
Node{Type: '\n'}
Node{Type: WORD, Str: "echo"}
Node{Type: WORD, Str: "a"}
Node{Type: WORD, Str: "is"}
Node{Type: '$'}
Node{Type: WORD, Str: "a"}
Node{Type: '|'}
Node{Type: WORD, Str: "wc"}
Node{Type: '\n'}
Node{Type: '}'}

ただし、goyaccを使う場合、字句解析のインターフェイスが決められていて、1回の呼び出しでは1つだけトークンを(lvalに詰めて)返すように実装しなければなりません。インターフェイスは以下の通りです。

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

そのため、1文字読んで、区切りだったら戻しておいて次の呼び出しに使うことがよくあります。Goでは、text/scannerが用意されていて便利そうだったのですが、Scanner.Nextはまだ返すべき文字が残っていても入力を読むまで待ってしまうため、微妙に使いづらかったです。代わりに、io.RuneScannerを満たすbufio.Readerを使うといいでしょう。

初期のLex()は以下のような雰囲気です。yySymType型については構文解析のところで説明します。

const EOF = -1

type Lexer struct {
    f   io.RuneScanner
    buf bytes.Buffer
}

func (l *Lexer) Lex(lval *yySymType) int {
    l.buf.Reset()
    var c rune
    for {
        c, _, err := l.f.ReadRune()
        if err != nil {
            return EOF
        }
        if c != ' ' && c != '\t' {
            break
        }
    }
    switch c {
    case EOF:
        return -1
    case '$', '{', '}', '\n', '|':
        return int(c)
    case '\'':
        // 省略
    default:
        l.buf.WriteRune(c)
        for {
            c, _, err := l.f.ReadRune()
            if err != nil {
                break
            }
            if c == EOF || unicode.IsSpace(c) || c == '$' || c == '{' || ... {
                l.f.UnreadRune()
                break
            }
            l.buf.WriteRune(c)
        }
        lval.tree = &Node{Type: WORD, Str: l.buf.String()}
        return WORD
    }
}

あとは、必要に応じてプログラムを分割するようなコードを書けばいいです。この辺りのコードはqsh/lex.goで実装しました。

構文解析

次に、字句解析で分割したトークンを使って、言語のツリーを作ります。このフェーズは主にgoyaccで行います。YaccはBNFに近い記法を使って、言語の文法を定義するものです。例えばシェルで1つのコマンドを表すコードは以下のようなものになります。

%term IF
%term WORD
%left IF
%left '|'
%%
prog:
    {
        return 1
    }
|   line '\n'
    {
        Compile($1)
        return 0
    }

line:
    cmd
|   cmd ';' line    { $$ = New(LIST, $1, $3) }

cmd:
|   IF block block  { $$ = New(IF, $2, $3) }
|   simple
|   cmd '|' cmd     { $$ = New(PIPE, $1, $3) }

block:
    '{' body '}'    { $$ = New(BLOCK, $2, nil) }

body:
    cmd
|   cmd ';' cmd     { $$ = New(LIST, $1, $3) }
|   cmd '\n' cmd    { $$ = New(LIST, $1, $3) }

simple:
    word
|   simple word     { $$ = New(LIST, $1, $2) }

word:
    '$' word        { $$ = New(VAR, $2, nil) }
|   WORD

これは、name: rule { code } | rule...のような書き方になっています。ruleにマッチした場合はcodeが実行されます。慣れるまでは読みづらいかもしれませんが、例えばsimpleの定義は

  1. wordが1回だけ登場する
  2. simpleに続いてwordが登場する

のどちらかである、と読みます。じゃあwordとは何なのかというと、

  1. Lex()が$を返したトークンに続いて word が登場する
  2. Lex()がWORDを返したトークン

のどちらか、という定義になっています。

ルールの読み方

例えばlsですが、まずはLex()が単語を読んでWORDを返します。そのため、wordの2番目のルールにマッチして、次からはwordとして扱われるようになります。wordはsimpleの1番目のルールにもマッチします。そのため、順に遡っていって、最終的にはlineとして扱われます。'\n'があれば、プログラムとして満たしているのでパーサは終わります。

次に、ls $optなど2つ以上のトークンで構成される場合ですが、まずlsがsimpleとして扱われます。次の$optは、Lex()で分割したトークンとしては'$'とWORDであり、これはwordの1番目のルールにマッチするのでwordです。そのため、simpleに続いてwordが登場するパターンとなり、simpleの2番目のルールにマッチしてsimpleです。

3つ以上続く場合も同じですね。

トークン

上のYaccコードで、$$とか$1のような書き方がありましたが、これは%unionで定義した型のメンバー変数が対応しています。

%union {
    tree *Node
}
%type<tree> line block body assign
%type<tree> cmd simple word
%type<tree> WORD

例えば以下の場合、

word:
    '$' word    { $$ = New(VAR, $2, nil) }
|   WORD        { $$ = $1 }

まずはWORDのルール。字句解析の章でLex()の引数にyySymTypeという型が使われていましたが、これはYaccのコードで%unionを使って定義した型そのものです。この記事で書いたLex()は、lval.treeにポインタを代入していました。また、$1などは%type<X>のルールによってメンバー変数に置き換えられるので、Lex()が代入したlval.treeの値が$1として参照できるようになっています。

$$は、別のルールからwordを参照した場合に、何を値とするかを設定するものです。$$が何も設定されなければ、$1の値が暗黙的に使われます。WORDのルールで$1(実際はLex()で設定した値)がそのまま$$になるため、'$' word {}の中で書かれた$2はそのままLex()の結果です。

構文解析の開始

Yaccで記述したパーサは、yyParse(l *yyLexer)関数を呼ぶと実行されます。yyParse()は内部的にl.Lex()を必要なだけ呼び出し、プログラムを満たせばyyParse()を抜けます。上記の場合はprogを満たした時点で(simpleに続けて'\n'が入力されたら)関数を抜けます。

一般的な言語の場合は、yyParse()を1回だけ呼び出せばよいこともありますが、シェルの場合はコマンド実行が終わっても次の入力を待つ必要があります。yyParse()は文法エラーなどがあった場合に非ゼロを返すので、エラーになるまで何度も繰り返すようにしました。

var l Lexer
f := bufio.NewReader(os.Stdin)
l.Init(f)
for yyParse(&l) == 0 {
}

Yaccでreturnすると、その値がyyParse()の戻り値として返るため、文法は正しいけどエラーにしたい場合などは、この方法を使うこともできます。

prog:
    {
        return 1
    }
|   line '\n'
    {
        return 0
    }

最終的に、字句解析のところで書いた以下のコードは、

if { true } {
    echo a is $a | wc
}

yyParse()の結果このようなツリーになります。

type Node struct {
    Type  int
    Str   string
    Left  *Node
    Right *Node
}

f:id:lufiabb:20200328205019p:plain
ツリー図

こういったツリーが完成したら構文解析は終わりです。

コード生成

最後にコード生成です。今回はシェルなので、マシン語にコンパイルする必要はありません。なので前の章で作成したツリーをそのまま実行してもいいのですが、個人的には、ループやユーザ定義関数などの実装を予定しているならコード生成を行ったほうが扱いやすいと思います。

今回実装したシェルでは、ls $optは以下のように内部コードへ変換します。

# ls $opt
MARK       # 新規スタックを作成する
PUSH ls    # lsという文字をスタックにpush
PUSH opt   # optという文字をスタックにpush
VAR        # 1つ取り出して変数参照; 結果をスタックに入れる
SIMPLE     # スタックに溜まっているリストを実行

if文の場合は少し複雑になります。以下はif { cmp -s a b } { echo ok }の場合です。

# if { cmp -s a b } {
#     echo ok
# }
MARK       # 新規スタックを作成する
PUSH cmp   # cmpという文字をスタックにpush
PUSH -s    # -sという文字をスタックにpush
PUSH a     # aという文字をスタックにpush
PUSH b     # bという文字をスタックにpush
SIMPLE     # スタックに溜まっているリストを実行
IF         # 実行結果が正常終了なら1つ飛ばす(GOTOをスキップ)
GOTO end   # endラベルへジャンプ
MARK       # 新規スタックを作成する
PUSH echo  # echoという文字をスタックにpush
PUSH ok    # okという文字をスタックにpush
SIMPLE     # スタックに溜まっているリストを実行
end:       # endラベル; ls aがエラーならここに飛ぶ

こういった内部コードは、構文解析で作成したツリーがあれば比較的簡単に実装できます。

type Cmd struct {
    pc int
}

type Code struct {
    steps []func(cmd *Cmd)
}

func (c *Code) emit(f func(cmd *Cmd)) {
    c.steps = append(c.steps, f)
}

func build(c *Code, p *Node) {
    if p == nil {
        return
    }
    switch p.Type {
    case WORD:
        c.emit(Push(p.Str))
    case SIMPLE:
        c.emit(Mark)
        build(c, p.Left)
        c.emit(Simple)
    case LIST:
        build(c, p.Left)
        build(c, p.Right)
    case BLOCK:
        build(c, p.Left)
    case VAR:
        c.emit(Mark)
        build(c, p.Left)
        c.emit(Var)
    case IF:
        build(c, p.Left)
        c.emit(If)
        var end Label
        c.emit(Goto(&end))
        build(c, p.Right)
        end.pos = len(c.steps)
    }
}

以上で完成です。あとはコード生成が終わったCode.stepsを順番に実行していけば、それらしい動きをすると思います。

最初にも書きましたが、動作する完全なコードはリポジトリのコードを参照してください。

おわりに

今回、12月の頭からシェルを実装しはじめて、だいたい動作するかなというところまでで50コミット2,000行くらいでした。スペースの扱いとか、変数の間接参照とか、PATH以下にサブディレクトリを作れるとか、色々と好みの実装ができたかなという気持ちです。まだ足りない部分は一杯あるので、継続して開発していきます。