この記事は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
echo ' #E '
コマンド実行
普通に書けばコマンドとして実行します。他と異なり、コマンド名に/ を含む場合でもPATH から探して実行します。
ls -l
gitlab/users -a
PATH にサブディレクト リが作れるのはPlan 9 でも多用されていますが、とても便利だと思います。
変数
変数は全て一次元のリストです。リストは(a b c)のように、カッコとスペースで表します。a=1のように書くこともできますが、これはa=(1)と等価です。また、全て大文字の変数は、自動的に環境変数 として昇格するためexportする必要はありません。
ranks =( S A B C)
echo $ranks
API_TOKEN =xxxx
bash -c ' echo $API_TOKEN '
特別に、PATH という文字を含む環境変数 は、他のプロセスが参照した時に困るため、エクスポートする時に要素の区切りをfilepath.ListSeparatorへ変更しています。
PATH =( /bin /usr/bin)
echo $PATH
bash -c ' echo $PATH '
変数を使って変数を間接参照することもできます。
Jan =1
January =Jan
c =January
echo $$$c
スペースもまともに扱えます。
touch ' a b '
args =( -l ' a b ' )
ls $args
今のところ、リストから特定の要素を取り出すことはできませんが、近いうちに$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
cmp -s a b || echo 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" ,
}
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 }
実装について
簡単にですが、実装について説明します。言語を実装する場合、ざっくり以下のフェーズを実装する必要があります。
他にも、最適化を行う場合もありますし、コード生成を行わずにツリーを直接実行する場合もありますが、単純な言語でない限りはコード生成を行ったほうが便利だと思います。
今回は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の定義は
wordが1回だけ登場するsimpleに続いてwordが登場する
のどちらかである、と読みます。じゃあwordとは何なのかというと、
Lex()が$を返したトーク ンに続いて word が登場する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
}
ツリー図
こういったツリーが完成したら構文解析 は終わりです。
コード生成
最後にコード生成です。今回はシェルなので、マシン語 にコンパイル する必要はありません。なので前の章で作成したツリーをそのまま実行してもいいのですが、個人的には、ループやユーザ定義関数などの実装を予定しているならコード生成を行ったほうが扱いやすいと思います。
今回実装したシェルでは、ls $optは以下のように内部コードへ変換します。
MARK
PUSH ls
PUSH opt
VAR
SIMPLE
if文の場合は少し複雑になります。以下はif { cmp -s a b } { echo ok }の場合です。
MARK
PUSH cmp
PUSH -s
PUSH a
PUSH b
SIMPLE
IF
GOTO end
MARK
PUSH echo
PUSH ok
SIMPLE
end :
こういった内部コードは、構文解析 で作成したツリーがあれば比較的簡単に実装できます。
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 以下にサブディレクト リを作れるとか、色々と好みの実装ができたかなという気持ちです。まだ足りない部分は一杯あるので、継続して開発していきます。
