# 字句解析その1 - シェルもどきをgoで自作する #3

## おさらい
シェルもどき「[oreshell](https://github.com/jyami/oreshell)」を自作している。

前々回、前回
- [シェルってなに？コマンドラインインタプリタってなに？ - シェルもどきをgoで自作する#1](https://hackmd.io/@jyami/HJzohRn2D)
- [コマンドと引数の分解、環境変数PATHから探索、外部コマンドと内部コマンド - シェルもどきをgoで自作する #2](https://hackmd.io/@jyami/HyeSkkThP)

シェルは入力した文字列を読み取って、コマンドと引数群に分割してプロセス生成に渡している。


## 現在の実装では入力文字列を単純に空白で分割している

$ cp hoge age

上記のコマンド文字列の入力を分割した結果は以下の通り。


## ファイル名/パス名が空白文字を含んでいる場合はどうする？

コマンドの引数として「(space)oge」、「h(space)ge」というファイル名を扱いたいときはどうする？


ファイル名/パス名に空白文字を含んでいる場合は、現在の実装である「単純に空白で区切る」では期待した分割をすることができない。
期待した分割をするためには、コマンドと引数群の区切りの空白文字と、ファイル名/パス名に含まれる空白文字とを区別する必要がある。

## エスケープ処理

一般的なシェルでは、

- バックスラッシュ : 対象文字の直前にバックスラッシュをつける
- クォーテーション(シングル、ダブル) : 対象文字列リテラルをクォーテーションで「くくる」。

を使って、ファイル名/パス名(文字列リテラル)の空白文字と、コマンドと引数群の区切りとの見分けをつけている。
これをエスケープ処理と呼ぶ。エスケープの対象となった文字を[エスケープ文字](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%B9%E3%82%B1%E3%83%BC%E3%83%97%E6%96%87%E5%AD%97
)と呼ぶ。

(エスケープによって文字列リテラルとして扱える対象は空白文字だけはないが、細かい説明はここではしない。)

「(space)oge」、「h(space)ge」というファイル名を扱いたい場合のコマンドライン文字列の入力の例は以下の通り。

$ cp \ oge "h ge"

## 文字のエスケープを考慮したコマンドと引数群の分割は？

ファイル名/パス名の空白文字と、コマンドと引数群の区切りとの見分けをつける指定方法はわかった。
では、今回作っているシェルでは、上記の文字列をどのようにして分割してプロセス生成に渡したらよいのか？


## 字句解析

文字のエスケープを考慮したコマンドと引数群の分割を行うためには、単純に空白で分割するのではなく、もうちょっと手の込んだ分割を行う必要がある。
インタプリタ/コンパイラではこの「もうちょっと手の込んだ分割」を「字句解析」と呼んでいる。

■字句解析とは

> プログラムの文字の並び、文字列を　意味のある単語（これをトークンと言います。）に分ける処理を行います。これを字句解析と いいます。
[参照](https://www.is.s.u-tokyo.ac.jp/vu/96/cad/compiler.html#jiku)

字句解析では、入力した文字列を「トークン」と呼ばれる意味のある単語に分割する。
このトークンには後々の処理がしやすいように種別をつけておく。


ここでは、トークンに以下の種別をつけておく。
- コマンドと引数群の区切りの空白文字
- 文字列リテラル
- バックスラッシュ付きの文字列リテラル
- クオートでくくった文字列リテラル
- バックスラッシュ、クォートの無い文字列リテラル
- 入力文字列全体の終端(EOF)

トークンに分割した後、その種別を参照しながら「その他の処理」を行った後にプロセス生成を行う。


## 字句解析器

字句解析を実現するプログラム(またはプログラムの一部の機能)を「字句解析器(lexer)」と呼ぶ。
lexerはステートマシンで設計/実装することがよくある。
[go言語の偉い人](https://ja.wikipedia.org/wiki/%E3%83%AD%E3%83%96%E3%83%BB%E3%83%91%E3%82%A4%E3%82%AF)がステートマシンを使って実装している例があるので、今回はそれを真似する。

参考
- https://www.youtube.com/watch?v=HxaD_trXwRE
- https://talks.golang.org/2011/lex.slide#1
- https://github.com/golang/go/blob/master/src/text/template/parse/lex.go

### 文字のエスケープを考慮した字句解析のステートマシン

以下は今回設計した字句解析器の状態遷移図である。

[*] --> lexText
lexText : EOFを見つけたら、EOFトークンを切り出して終了する。
lexText --> [*]

lexText -> lexWhitespace : 空白文字を見つけた
lexWhitespace : 空白以外の文字が見つかる\nまでの間の1個以上の空白を\nトークンとして切り出して\nlexTextに戻る。
lexWhitespace --> lexText

lexText --> lexEscapeChar : バックスラッシュ文字を見つけた
lexEscapeChar : バックスラッシュ文字と\nその次の文字を\nトークンとして切り出して\nlexTextに戻る。
lexEscapeChar -> lexText
lexEscapeChar --> lexError

lexText --> lexQuotedString : クォーテーション文字を見つけた
lexQuotedString -> lexText
lexQuotedString : 次のクォーテーション文字\nまでの間の文字列を\nトークンとして切り出して\nlexTextに戻る。
lexQuotedString --> lexError

lexText --> lexString : バックスラッシュ文字、\nクォーテーション文字、\n空白文字以外\nの文字を見つけた
lexString : バックスラッシュ文字、\nクォーテーション文字、\n空白文字、EOF\nが見つかるまでの間の文字列\nをトークンとして切り出して\nlexTextに戻る。
lexString -> lexText

上記ステートマシンは以下のように入力文字列の上を
P : 文字読み取りポインタ
S : トークン開始位置
の2つを文字列終端へと少しづつずらしながらトークンを切り出して動作する。


ステートマシンが文字読み取りポインタとトークン開始位置を使ってトークン切り出す動作の解説は次回。