2016/07/16 13:00- CC-semi

[前回]
	# 「言語」とは ?
	#	「表現規則(Syntax)」+「意味規則(Semantics)」

	X 言語の処理系
		X 言語で記述された「表現(プログラム)」の意味を求める
			「意味」... 不問

			インタープリターは、対応する「動作」を行う
				「意味」=「動作」(表現を解釈して、意味を作りだす)
				通訳(「動作」の結果を人間に伝えるために、「表現」する)
					「逐次(インタラクティブ処理)」に動作する

			コンパイラは、対応する「(普通は、別の言語で記述された)表現」に変更
				「意味」=「(別)表現」(結果として得られた表現はまた解釈が必要)
				翻訳
					「一挙(バッチ処理)」に動作する

	処理系が行う作業
		「セマンティクスギャップ(Symatics Gap) を埋める」という作業
			コンパイラーの場合は、変換先の言語レベルが高ければ、
				コンパイルする言語のレベルが高くても(セマンティクスギャップが
				小さいので..)、作るのは、むずかしくはない

			例 : C 言語の整数式を計算する言語
				-> C 言語のプログラムに変換するコンパイラーを作った
					ほぼ、入力、まるまる出力にコピーするだけ
						本質的な部分(式を解釈して実行する)は、C コンパイラーに丸投げした

==

	式を計算するインタープリターを作りたい	
		# 「式の評価」: 大概、どんな言語でも必要
		#		どんな言語を自作しても、無駄にならない
		# インタープリター : コンパイラーと違って、誤魔化しがきかない
		#		処理系の中身をしっかりと把握できる

	「式」言語
		対象となる言語を定める
			言語 : 構文規則 + 意味規則(意味)
				意味 : 整数値 ( + エラー )
					# 意味は、大概、なんらかの単純(構造を持たない)集合になる事が多い
				構文規則 : 言語の文法
					意味規則 : 表現から意味を定める関数
						# 構文に対応して構造的に意味関数を定める事が多い

					抽象的な例
						偶奇言語(P) : (簡単) 構文 : 0 1 の並び
								 	  	  意味 : { 0, 1 }
										  意味規則 : 1 が偶数回でたら 0 そうでなければ 1

			「式言語[0]」の構文規則 (BNF)
				<文> ::= <行>'\n'
				<行> ::= <式> ';' | ';'
				<式> ::= <整数値>
				<整数値> ::= '0' | '1' | ... | '9'	/* 一桁 */

			式言語[0] の文の例
					  1;\n
					  3;\n

			式言語[0] の文でない例
					  1\n
					  3 ;\n

			「式言語[0]」の意味規則 ( 整数値をいれたらその整数値[の出力]を意味とする )
					# 意味集合は { 0 〜 9 } までの整数値
					# 動作は、それを画面に出力する

				<文> ::= <行>'\n'
					/* <行> で、整数値が取り出せるので、その値を出力する */

				<行> ::= <式> ';' | ';'
					/* <式> で整数値が取り出せるので、その値を自分の値とする
						か、空の時は、0 とする */

				<式> ::= <整数値>
					/* <整数値> が整数値を取り出すので、それが式の値 */

				<整数値> ::= '0' | '1' | ... | '9'	/* 一桁 */
					/* 文字が表す、一桁の数 */

			式言語[0] の文の場合の実行例
					  1;\n
						result = 1
					  3;\n
						result = 3

			式言語[0] の文でない場合の実行例
					  1\n
						Syntax Error
					  3 ;\n
						Syntax Error

			パーサのプログム(関数)に、「意味の処理」を行う部分を追加
				意味は、関数の値として、やり取りされる

		処理系を作る言語を定める
			C でやる

	ungetch 関数
		一旦、よみこんだ文字を、元に戻す
			# 元に戻す文字は、読み込んだ文字でなくても良い
	
		<説明>
			getchar() によって、stdin (標準入力) から、一文字ずつ取り出す
			事ができる。しかし、読みすぎた時に、元に戻す必要があれば、
			読み込んだ文字を、ungetc ( ch, stdin ) とする事により、
			「読み込んだ事を取り消す」事ができる
				この機能を利用する事により「先読み」が可能になる。

	exp-000
		下降型 (Top Down) パーサー
				# 「パーサー」: 言語処理系の一部で、構文行う部分のプログラム
			プログラムの構文解析は、上から下 (Top Down)に進む
				選択肢が複数ある場合は、先読みをして、どちらにするかを
				判定して行う
					LL(k) : Left to Right k Lookup (左から右に k 文字先読み)
						# exp-000 は LL(1) 型 (1 文字先読みをしている)
						# LL(0) < LL(1) = LL(k) (k>0)
						#	この形でパーサが作れるような言語の種類
						#	例 : exp-000 は LL(1)
						#	例 : 偶奇言語は LL(0)
		LL(k) 型の言語であれば、パーサーの作成は楽
			基本的に、文法にそって、プログラムを作ればよい
				-> 機械化できる -> パーサージェネレータが作れる

==

			「式言語[1]」の構文規則 (BNF)
				<文> ::= ε|  <文> <行>'\n /* 複数行に対応 */
				<行> ::= <式> ';' | ';'
				<式> ::= <整数値>
				<整数値> ::= <整数値> <数字> | ε
				<数字> ::= '0' | '1' | ... | '9'

			「式言語[2]」の構文規則 (BNF)
				<文> ::= ε|  <文> <行>'\n /* 複数行に対応 */
				<行> ::= <式> ';' | ';'
				<式> ::= <整数値> | <整数値> '+' <式>
				<整数値> ::= <整数値> <数字> | ε
				<数字> ::= '0' | '1' | ... | '9'