2016/11/05 13:00- compiler seminer

[テーマ]
	自分言語の設計と、その処理系を作る
		Compiler Compiler ( Parser Generator ) の使い方
			bison (GNU 版 yacc : Yet Another Compiler Compiler)
				構文解析 ( Parser ) を作る
					Token 列から文法に即した構文を認識する

			flex (GNU 版 lex : Lexical Analayser Genereator)
				字句解析 ( Tokenizer ) を作る
					文字列内から Token(字句) を認識して、
					文字列を Token 列に変更する

		# 共に、言語 ( = 文字列の集合 ) を認識 ( 与えたれた文字列が、
		#	その言語に含まれているかどうかを判断する事 ) するプログラム
		#		flex は、第三言語のクラスの言語 ( 正規表現の言語 )
		#		bison は、第ニ言語の一部のクラスの言語 ( LRLA(k) の言語 )
		#
		# [目的] 与えられた文字列が、特定の言語の要素かどうかを判定したい
		#			「集合を定める」事が目的
		#	言語のクラス分け(上は下に含まれる)
		#		3 : Regulaer Language (正規言語) のクラス
		#		2 : Context Free Language  (文脈自由言語) のクラス
		#		1 : Context Senstive Language (文脈依存言語) のクラス
		#		0 : 全ての言語のクラス
		#
		# [表現] (言語は一般に無限集合なので直接は表現できないから)
		#		有限で言語を表現する方法 : 文法(とか、表現)
		#	文法のクラス分け(上は下に含まれる)
		#		RE : Regulaer Expression (正規表現) のクラス
		#		CFG : Context Free Grammar (文脈自由言語) のクラス
		#		CSG : Context Senstive Grammar (文脈依存言語) のクラス
		#
		# [プログラム] 言語を認識するプログラム
		#		3 の場合は、FAT を作る、2 の場合は、PDAM を作る
		#	言語を認識する機械
		#		3 : FAM ( 有限状態マシン )
		#		2 : PDAM ( Push Down マシン )
		#		1 : ?
		#		0 : TM ( チュリーリングマシン : 万能 )


	言語を作るとは
		文法(あるいは、言語表現) を与えて、言語(文字列の集合)を決める
			=> 構文規則
				binson/flex が構文解析をやってくれる
					構文要素に対応した、文字列を認識してくれる
		文法表現に対応した意味を考える
			=> 意味規則(計算/動作規則)
				binson/flex から得た、構文要素に対応して、
				「意味」を作る規則を考える
		例:
			calc
				式言語(表現)から、数(意味)を作る (計算機)
					calc 「1+2:表現 -> 3:意味」

[前回]
	言語を作るにあたって、(bison/flex を利用する)例が欲くて、
		電卓(calc の元の版)を紹介した
			-> 色々拡張をした
				変数
				IF 構文
				ユーザ定義関数
					-> 万能言語と、そのインタープリターができた

		1. bison/flex に慣れた
		2. 文法規則と、意味規則を拡張しながら幾つか体験した
		3. 結果的にインタープリターの書き方は、一通りやった
			特に、parser に「構文木」を作らせ、eval (評価器)で、
			その意味を定める ( 「構文規則」と「意味規則」を分離した)
				# ユーザ定義関数を実現するために、「表現」の再利用の
				# 仕組みが必要だった..

	ユーザ定義関数が導入されて万能性ができた
		# IF 構文 + 再帰呼び出し

	!!! 一通り、「自分言語を作り処理系を作成する」という目的は実現できた

[続き]
	インタープリターはできた
		次(こそ)は、コンパイラー
			# 式言語を拡張したので、いまいち、言語設計という気分がしない
			#	今度は、普通(?)のプログラミング言語を作りたい
			#		-> 多分、 C 言語風になる

		[アプローチ]
			a. 本物の CPU (i386) の Code を作るリアルなコンパイラー
				利点 : 本当に、実用になる
				方針 : 既存システム ( GNU の環境 ) を間借りする				
				欠点 : CPU の勉強が必要
			b. 仮想 CPU を考えて、そのコンパイラー
				利点 : 自分で、すきにできる
				方針 : all-in-one で全てのものを作る
				欠点 : おもちゃになると悲しい

	前回の相談で、b. でやる
		# 前回、CPU をつくってみた

==

[今回]
	CPU の設計
		# いきなり、全部でなく、すこずつ機能を追加しながらやる
		## 学習が目的なので、シンプル(解り易)さ重視

		[基本設計]
			16 bit Word CPU にする
				memory は、16 bit = 2 byte = 1 word にして、2^16 のサイズ
					# word が 2 byte なので、文字列は、C 言語と異る
					# その代りに、日本語の「文字」が扱えるようになる
					#	文字コードは utf-8 ( 内部的には ?? )