電卓機能の実装．自由文脈文法の設計とその構文解析

calc-parser.rb

puts  <<"EOS"
.
start program...
.
----------------------------------------
# 文脈自由文法の説明

##  自由文脈文法 G = (V, T, P, S)を考える
 * V:非終端記号の有限集合
 * T:終端記号の有限集合
 * P:書き換え規則
 * S:開始記号

## 以下のように定義する
 * V:{E,D,C} #Eは<式>,Dは<項>,Cは<因子>
 * T:{<整数>,+,-,*,/,(,)}
 * P:E -> D|E+D|E-D  # <式> = <項> or <式>+<項> or <式>-<項>
 *   D -> C|D*C|D/C  # <項> = <因子> or <項>*<因子> or <項>/<因子>
 *   C -> <整数>|(E) # <因子> = <整数> or (<式>)
 * S:{E}
--------------------------------------
#  プログラムの操作説明

 * {1,2,3,4,5,6,7,8,9,0,+,-,*,/,(,)}を使った数式を入力してください
 * 半角スペースはあっても無くても大丈夫です
 * "exit"と入力すると終了します
.
EOS

# 字句解析
def lexical_analyser(str)
	puts "--字句解析開始--"
	tokens = str.split(/\s*(\+|\-|\*|\/|\(|\)|\D|\s)\s*/).reject{|w|w=="" or w==" "}
	puts "--"
	puts tokens
	puts "--"
	tokens.each do |w|
		case w
		when (/^(0|[1-9]\d*)$/) then
			puts w + ":整数"
		when /(\+|\-|\*|\/)/ then
			puts w + ":演算子"
		when /(\(|\))/ then
			puts w + ":括弧"
		else
			puts w + ":定義されていない文字"
			tokens = nil
			break
		end
	end
	puts "--"
	puts "--字句解析終了--"
	return tokens
end

# 括弧の対応関係のチェック
def check_bracket(arr)
	puts "--"
	puts "--括弧対応関係検査開始--"

	bracket_count = []
	arr.each do |w|
		case w
		when "(" then
			puts "("
			bracket_count << "("
		when ")" then
			puts ")"
			bracket_count.pop
		end
	end
	puts "--括弧対応関係検査終了--"
	puts "--"

	unless arr.find{|w|w=="(" or w==")"} then
		puts "括弧は存在しない"
		return true
	end

	if bracket_count.length == 0 then
		puts "括弧は対応してる"
		return true
	else
		puts "括弧の対応関係がおかしい"
		return false
	end
end

# 式に対する規則適用
def parse_exp(arr, depth)
	(depth*4).times do
		print "\s"
	end
	puts "<式>?" + arr.to_s

	if arr == nil then
		(depth*4).times do
			print "\s"
		end
		puts "Error"
		return nil
	end

	# E -> Dの適用
	result_e_rule1 = parse_term(arr, depth+1)
	result_e_rule2 = nil
	result_e_rule3 = nil
	if result_e_rule1 != nil then
		return result_e_rule1
	else
		bracket_count = []
		separate_poses = []
		arr.each_with_index do |w,index|
			case w
			when "("
				bracket_count << "("
			when ")"
				bracket_count.pop
			when "+"
				if bracket_count.length == 0 then
					separate_poses << index
				end
			when "-"
				if bracket_count.length == 0 then
					separate_poses << index
				end
			else
			end
		end


		if separate_poses.length == 0 then
			(depth*4).times do
				print "\s"
			end
			puts "Error"
			return nil
		else
			# 考えられうる+,-の組み合わせについて
			# E -> E+D or E-D の適用
			separate_poses.each do |pos|
				# 演算子の前半
				previous_val = parse_exp(arr.slice(0,pos), depth+1)
				if previous_val != nil then
					# 演算子の後半
					follow_val = parse_term(arr.slice(pos+1, arr.length), depth+1)
					if follow_val != nil then
						# 演算子に応じて計算
						case arr[pos]
						when "+"
							result_e_rule2 = previous_val.to_f + follow_val.to_f
							(depth*4).times do
								print "\s"
							end
							puts "OK"
							return result_e_rule2
						when "-"
							result_e_rule3 = previous_val.to_f - follow_val.to_f
							(depth*4).times do
								print "\s"
							end
							puts "OK"
							return result_e_rule3
						end
					end
				end
			end
			# +,-の全ての組み合わせで規則が適用できないならエラー
			(depth*4).times do
				print "\s"
			end
			puts "Error"
			return nil
		end
	end
end

# 項に対しての規則適用
def parse_term(arr, depth)
	(depth*4).times do
		print "\s"
	end
	puts "<項>?" + arr.to_s

	if arr == nil then
		(depth*4).times do
			print "\s"
		end
		puts "Error"
		return nil
	end

	# D -> Cの適用
	result_d_rule1 = parse_factor(arr, depth+1)
	result_d_rule2 = nil
	result_d_rule3 = nil
	if result_d_rule1 != nil then
		return result_d_rule1
	else
		bracket_count = []
		separate_poses = []
		arr.each_with_index do |w,index|
			case w
			when "("
				bracket_count << "("
			when ")"
				bracket_count.pop
			when "*"
				if bracket_count.length == 0 then
					separate_poses << index
				end
			when "/"
				if bracket_count.length == 0 then
					separate_poses << index
				end
			end
		end


		if separate_poses.length == 0 then
			(depth*4).times do
				print "\s"
			end
			puts "Error"
			return nil
		else
			# 考えられうる*,/の組み合わせについて
			# D -> D*C or D/C の適用
			separate_poses.each do |pos|
				# 演算子の前半
				previous_val = parse_term(arr.slice(0,pos), depth+1)
				if previous_val != nil then
					# 演算子の後半
					follow_val = parse_factor(arr.slice(pos+1, arr.length), depth+1)
					if follow_val != nil then
						# 演算子に応じて計算を区別
						case arr[pos]
						when "*"
							result_d_rule2 =  previous_val.to_f * follow_val.to_f
							(depth*4).times do
								print "\s"
							end
							puts "OK"
							return result_d_rule2
						when "/"
							result_d_rule3 =  previous_val.to_f / follow_val.to_f
							(depth*4).times do
								print "\s"
							end
							puts "OK"
							return result_d_rule3
						end
					end
				end
			end
			#　*,/の全ての組み合わせで規則が適応できない場合はエラー
			(depth*4).times do
				print "\s"
			end
			puts "Error"
			return nil
		end
	end
end

# 因子に対する規則適用
def parse_factor(arr, depth)
	(depth*4).times do
		print "\s"
	end
	puts "<因子>?" + arr.to_s

	case arr.length
	# []は終了
	when 0
		(depth*4).times do
			print "\s"
		end
		puts "Error"
		return nil
	# 数値かどうか
	when 1
		if arr[0] =~ /^\d+$/ then
			(depth*4).times do
				print "\s"
			end
			puts "OK"
			return arr[0]
		else
			(depth*4).times do
				print "\s"
			end
			puts "Error"
			return nil
		end
	# (<式>)かどうか
	else
		if (arr[0] == "(") and (arr[arr.length-1] == ")") then
			(depth*4).times do
				print "\s"
			end
			puts "OK"
			return parse_exp(arr.slice(1, arr.length-2), depth+1)
		else
			(depth*4).times do
				print "\s"
			end
			puts "Error"
			return nil
		end
	end

end

# 構文解析
def parser(arr)
	puts "---構文解析開始---"
	ast_node = parse_exp(arr, 0)
	puts "---構文解析終了---"
	if ast_node != nil then
		puts "構文解析成功した"
	end
	return ast_node
end

# 構文木の表示
def show_ans(arr)
	puts "答え:" + arr.to_s
end

# メイン処理
while true
	puts ""
	puts "数式を入力して下さい(\"exit\"で終了します)"
	print ">"
	str = STDIN.gets
	break if str.chomp == "exit"

	splitted_str = lexical_analyser(str.chomp)
	if splitted_str == nil then
		puts "字句解析に失敗しました"
		next
	end

	if check_bracket(splitted_str)  == false then
		next
	end

	parsed_arr = parser(splitted_str)
	if parsed_arr == nil then
		puts "構文解析に失敗しました"
		next
	end

	show_ans(parsed_arr)

end

puts <<"EOS"
.
good bye...
.
EOS