2016/08/06 13:00- cc-zemi

[次回予定]
	9/3
	8/26

[前回迄]
	tokenizer (字句解析)
		LRLA(k), LL(k) # k=0 と k>0 時は違っていて k=1 と k>1 は同じ
			複数 (k>0) の文字を先読みをして、構文解析をする
				-> 長さ k の token (字句) を 1 token 先読みすれば良い
					# tokenizer があれば、k>0 の時は k=1 と思って良い
		文字列の中から token 切り出して、Parser (構文解析) に渡す部分
			# 「token 」、複数の文字からなる「終端記号」
			#	例 : 数値(を表す文字列)、名前(を表す文字列)、区切記号(を表す文字列 [ 「/*」とか 「==」、「!=」等..])

	関係する話題
		DFA ( 決定性有限状態機械 )
		バックトラック
			-> 後回しにする(折角の夏休みに、楽しい事をしたい..)

	# 話が飛ぶが、2016/07/09 のファイルの説明をしたい
	#	-> 全く新しい章にはいったとおもって話をきいて欲しい

==

	[目的]	言語処理系を作りたい
				形式 : インタプリターとコンパイラー
					インタプリターを作ってみたい

		インタプリター
			言語処理する
				言語 : 構文規則と意味規則
					構文 : 文法を利用して、表現
						-> parser : 文法に即して、入力(文字列)を構文解析する
							# LL(k) トップダウンに(非終端記号に対応した関数を)(ほぼ)自動的作る事ができる
					意味 : その意味を「作る」プログラムで実現
						# これは、「表現の意味」に即したコードをかく

	[本日の主題]
		parser は、文法から、自動生成
			自動生成を行うプログラム binson ( と jlex ) に觝れる


	calc.l
		flex のソース ( lex のソース )
			Tokenizer の元となる記述
				この内容を flex に与えると、tokenizer として動く
					C 言語のプログラムが作られる
		記述方法
			基本は、「文字パータン」と「Token type」の対応表
				# 実際は、「Token type」ではなく、
				#	その文字バターンに対応した「C 言語の命令列」
				#		「return token-type」とすると、token が返る
			「文字パータン」
				regular expression (RE:正規表現) で記述
					RE の詳細と、FA と関係は後回し

				# RE は、unix を使いこなす上で、「必須内容」なので
				#	-> Hacker になりたい人は身に付けておく !!

		RE の基本
			!! RE は、「文字列集合(無限かもしれない)」を表す (言語表現)
			アルファベット集合 : 文字列を表現する文字の集合 (有限)
				# flex, bison では ASCII Code 文字集合が、アルファベット
				#	例 : 'a', 'b', '0', '1', '+', ...

			a	a がアルファベットの時に、これは RE で、
				{ "a" } という文字列を表す
				例 : 「1」 -> { "1" }, 「a」-> { "a" }

			[abc..]	a,b,c,... がアルファベットの時に、これは RE で、
				{ "a", "b", "c", .. } を表す
				例 : [0123456789] -> { "0", "1", .., "9" } を表す

			特に、範囲を指定するために 「-」を利用して、[a-b] ともかける
				例 : [0-9] -> { "0", .., "9" }
	
			AB	A, B が共に RE に、これは RE であり、集合としては
				A, B が表す文字列の集合をそれぞれ A, B とすると、
					AB -> { xy | x \in A, y \in B }
				となる
					例 : [a-z][0-9] -> { "a0", "a1", .., "a9", "b0", .., "z9" }
			A|B	A, B が共に RE に、これは RE であり、集合としては
				A, B が表す文字列の集合をそれぞれ A, B とすると、
					A| B -> A \cup B
				となる
					例: [a-z]|[0-9] -> { "a", "b", .., "z", "0", .., "9" }

			A*	A が RE の時に、これは RE であり、集合としては、
					A* -> { "" } | A | AA | AAA | ...
				となる
					例: [0-9]* -> { "", "0", .., "9", "00", "01", .., "000", .. }

			A+
					A+ -> AA*		
					例: [0-9]+ -> { "0", .., "9", "00", "01", .., "000", .. }

			.	[アルファベット全体]

			\	メタ記号の意味を消す
				a+ -> { "a", "aa", "aaa", .. }
				a\+ -> { "a+" }

			yytext ( char 型配列 ) には、token に対応する文字列がはいっている
			yylval token の意味(値)を入れる事ができる
				-> parser 側の意味処理の所で、参照可能

	calc.y
		bison のソース ( yacc のソース )
			parser の元となる記述
				この内容を bison に与えると、parser として動く
					C 言語のプログラムが作られる
		記述方法
			「文法」と、その非終端記号が受理された時の「意味規則」の対応

			「文法」
				非終端記号 : 文法規則 (意味規則) ;
					# cf. <abc> ::= <xyz> <uvm>     (BNF 形式)
					#	->	abc : xyz uvm ;			(yacc 形式)
					#		xyz, や uvm には終端記号や、非終端記号が現れる

			「意味」
				$n で、n 番目の「意味(値)」が取り出せて、
				$$ で、自分の「意味(値)」を計算して、設定できる
					「意味」をボトムアップに処理できる時には、簡単にかける
						! そうできない場合がある (宣言/定義)

	例題
		演算子を増やす
			'|' : bit 毎の 論理和 (bit 演算子)
				# C 言語の '|' と同じ
				#	整数値の bit 毎に 論理和を計算する
				#		例 10 | 6 -> 1010 | 0110 -> 1110 -> 14

		手順
			新しい token を入れるので、token 名を決める
				# 他の名前と重複しない、意味が判るような名前にする
				#		T_BIT_OR
			.y に token 名を登録
				演算子なので、結合規則 (強さと、左右をきめる)
					# 四則よりよわくして、かつ、左結合なので、
					#	%left T_BIT_OR
					#		を
					#	%left T_PLUS T_MINUS の上に挿入
			.l に token の識別部分を書き込む
			.y に構文の部分を考えていれる
				expression の中にいれる
			.yに 意味の部分を考えていれる
				expression の中にいれる

	課題 1
		演算子を増やす
			'&' : bit 毎の 論理積 (bit 演算子)
				# C 言語の '&' と同じ
				#	整数値の bit 毎に 論理和を計算する
				#		例 10 & 6 -> 1010 & 0110 -> 0010 -> 2
			'+-' > '&' > '|'
				#		例 OK | 10 & 6 -> 1 | (10&6) -> 1 | 2 -> 3
				#		例 NG | 10 & 6 -> (1 | 10) &6 -> 11 | 2 -> 2

	課題 2
		演算子を増やす
			'**' : べき乗
				#		[例] 2 ** 10 -> 2^10 -> 1024
			'**' > '*'
				#		[例] 2 * 2 ** 10 -> 2 * 1024 -> 2048
			'**' は、右結合
				#		[例] 3 ** 3 ** 3 -> 3 ** ( 3 ** 3 ) -> 3 ** 27

		[案 1]
		{
			int v = 1;
			int i;
			for ( i = 0; i < $3; i++ ) {
				v *= $1;
			}
			$$ = v;
		}


		[案 2]
			{ $$ = ipower($1,$3);}

			%% の後に
			int ipower ( int a, int b ) {
				int v = 1;
				int i;
				for ( i = 0; i < b; i++ ) {
					v *= a;
				}
				return v;
			}

	変数と代入文の導入

		目的
			代入文
				a=1.0	-> 変数 a に 値 1.0 を代入
			式の中での変数の値の参照
				b=a+a+a -> 変数 b に 値 3.0 が入る

		構文
			変数名は、小文字一文字 ( 'a' 〜 'z' ) に固定
				# 26 個しかもてない (自由変数名と、その処理は、宿題)
			代入文は、line の中に入るものとして、
				変数名 '=' mixed_expression
			式の中に、変数名があらわれたら、mixed_expression として扱う


		.y
			token の追加
				T_NAME (変数名) ( 'a' 〜 'z' )
					左辺値を持つ (整数型 : 0 〜 25 : 'a'-'a' 〜 'z'-'a' )
				T_EQ (代入記号) ( '=' )
		.l
			token に対応する、パターンを記述
		.y
			値を保持するための変数(配列)を用意する
				大域変数なので、先頭におく習慣
					float variable['z'-'a'+1];

			代入文 (line にいれる)
			変数の値参照 (mixed_expression に入れる) 

.l
[a-z]		{yylval.ival = *yytext - 'a'; return T_NAME;}
"="		{return T_EQ;}

.y
float variable['z'-'a'+1];	/* 変数 'a' 〜 'z' の値を保持する領域 */

%token<ival> T_INT T_NAME

%token T_EQ

	| T_NAME T_EQ mixed_expression T_NEWLINE {
	  	variable[$1]=$3;
		printf("\tResult: %c=%f\n", 'a' + $1, $3);
	} 

	  | T_NAME                               { $$ = variable[$1]; }


	課題
		小文字の 1 文字は浮動小数点数型変数だったので、
		大文字の 1 文字は整数型変数としてみる


	左辺値の役割
		[0] とかくと、a と同じ意味になるようにする
			「[左辺値]」 という表現を導入 ( C 言語では * が相当 )
				例
					[0] = 3.0
					a -> 3.0
					b= 2.0
					[1] -> 2.0

		T_L_BRA, T_R_BRA


	sin 関数
		sin という token T_SIN
			浮動小数点数 : 	sin ( 浮動小数点数 )

	課題
		cos/tan/sqrt/log 等を追加すれば、関数電卓になる