構文解析と抽象構文木 - シェルもどきをgoで自作する #9

おさらい

これまで

• シェルってなに？コマンドラインインタプリタってなに？ - シェルもどきをgoで自作する#1
• コマンドと引数の分解、環境変数PATHから探索、外部コマンドと内部コマンド - シェルもどきをgoで自作する #2
• 字句解析その1 - シェルもどきをgoで自作する #3
• 字句解析その2 - シェルもどきをgoで自作する #4
• リダイレクションってなに？ - シェルもどきをgoで自作する #5
• リダイレクションの種類 - シェルもどきをgoで自作する #6
• リダイレクションの構文 - シェルもどきをgoで自作する #7
• コマンドプロセスを作成する際のファイルディスクリプタの操作 - シェルもどきをgoで自作する #8

シェルもどき「oreshell」を自作している。
現状のoreshellはリダイレクションを行うとエラーになるのでリダイレクションできるように修正する。
前回はファイルディスクリプタ操作部分の実装を検討した。

今回はリダイレクション対応に合わせた字句解析器の修正と「構文解析器」の実装、動作確認。

字句解析器の修正

今回までに行った字句解析についての説明はコチラ。

リダイレクションに対応するために、リダイレクション文字、ファイルディスクリプタ番号、リダイレクション先ファイル名の切り出してトークンの羅列を作成できるように字句解析器を修正する。

修正内容の細かい説明は省略。
注意する点は以下の通り。

• コマンド引数(ファイル名など)とリダイレクション文字の間にスペースが入らない場合がある。(区切りは空白文字だけではない)
  • 例
  ​​$ ls a b c d>list
  

  「d」「>」「list」の間に空白はないがそれぞれ別トークンとなる。
• ファイルディスクリプタ番号はその次の文字がリダイレクション文字の時だけ、ファイルディスクリプタ番号として扱う。
  • 例
  ​​$ ls 3 2 1>list
  

  「3」「2」はコマンド引数(ここではファイル名)、「1」はファイルディスクリプタ番号としてトークンになる。

「構文解析器の実装」ってあるけど「構文解析」ってなに？

一般的なインタプリタは、その入力に対して

1.字句解析
2.構文解析
3.評価

を順に処理を行う。
それぞれの処理を「字句解析器」「構文解析器」「評価器」が行う。
それぞれの出力(結果)が次の処理の入力となる。
関係を以下に図で示す。

構文解析では、「字句解析の結果が定義した構文のとおりであるかどうか」を調べ、構文通りであれば「抽象構文木」と呼ばれるデータ構造を作成する。評価では、抽象構文木が表すデータ構造に基づいて実際の処理の実行を行う。

oreshellの字句解析結果の例はコチラ。
oreshellのリダイレクションの構文はコチラ。

■構文解析とは

プログラミング言語やマークアップ言語などのコンピュータ言語で書かれた文を構成要素に分解し、要素間の関係を元に特定のデータ構造に変換する操作を構文解析という。
e-words

■抽象構文木とは

抽象構文木（英: abstract syntax tree、AST）は、通常の構文木（具象構文木あるいは解析木とも言う）から、言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した（抽象した）木構造の木である。
wikipedia

■構文木とは

構文木（こうぶんぎ）とは、構文解析の経過や結果（またはそれら両方）を木構造で表したもの。
wikipedia

今回の抽象構文木

今回のoreshellリダイレクション対応では以下の図ような抽象構文木が必要になる。

goで書くと以下の通り。

package ast

type Direction int

const (
	IN Direction = iota
	OUT
)

type Redirection struct {
	Direction Direction
	FdNum     int
	FilePath  string
}

type CommandSuffix struct {
	Args         []string
	Redirections []Redirection
}

type SimpleCommand struct {
	CommandName   string
	CommandSuffix CommandSuffix
}

構文解析器(パーサ)の実装

リダイレクション対応するために上記のような抽象構文木を作成する構文解析器を実装する。
実装の細かい説明は省略。

今回パーサを作ってみて「こうしておいたほうが結局楽だな」と思った点は以下の通り。

• できる限りツリーの各ノード毎にパーサを個別に準備し、ツリーを下りながらパーサを再帰的に呼び出すように作る。
• 字句解析結果からトークン要素を取り出すときは、Peekできると便利。Peekとは次の要素を取り出さずに「覗き見」する処理のこと。いま手に持っている要素をどのように扱うかは次の要素の正体がわからないと決められないことがある。

実装完了

字句解析、構文解析を呼び出している様子

		// 入力文字列をトリム
		trimedL := strings.Trim(string(line), " ")
		if len(trimedL) == 0 {
			continue
		}

		// 字句解析
		l := lexer.Lex(trimedL)
		// 構文解析
		simpleCommand, err := parser.ParseSimpleCommand(l)
		if err != nil {
			fmt.Fprintln(os.Stderr, err)
			continue
		}
		log.Logger.Printf("simpleCommand: %v\n", simpleCommand)

		// 先頭の単語に該当するコマンドを探して実行する
		// 内部コマンドか？
		internalCommand, ok := internalCommands[simpleCommand.CommandName]
		if ok {
			// 内部コマンドを実行
			err = internalCommand(simpleCommand)
		} else {
			// 外部コマンドを実行
			err = execExternalCommand(simpleCommand)
		}

ソースコード

リダイレクション対応したoreshellの実行例

実装が完了したので動作確認する。

$ go run main.go
(ore) > echo "abc" > abc.txt
(ore) > cat abc.txt
abc
(ore) > ls abc.txt 1>list def.txt 2>errlist
(ore) > cat list
abc.txt
(ore) > cat errlist
ls: 'def.txt' にアクセスできません: そのようなファイルやディレクトリはありません
(ore) > ls abc.txt ghi.txt>list 2> errlist
(ore) > cat list
abc.txt
(ore) > cat errlist
ls: 'ghi.txt' にアクセスできません: そのようなファイルやディレクトリはありません
(ore) > cat < list
abc.txt
(ore) > cat <abc.txt>abc2.txt
(ore) > cat abc2.txt
abc