Skip to content

Instantly share code, notes, and snippets.

@junk0612
Last active Dec 4, 2021
Embed
What would you like to do?
# 以下の BNF で表される数式が書かれたファイルを受け取り、数式をパースし、抽象構文木をJSON形式でファイルに出力します。
#
# expression ::= term | term "+" expression | term "-" expression
# term ::= factor | factor "*" term | factor "/" term
# factor ::= number | "(" expression ")"
# number ::= ("0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9")+
#
# Usage:
# $ ruby main.rb src.txt dst.json
#
class ExpressionParser
class ParseError < StandardError; end
class Node; end
class BinaryOperator < Node
def initialize(left, operator, right)
@left = left
@operator = operator
@right = right
end
def to_json
%({"operator": "#{@operator}", "left": #{@left.to_json}, "right": #{@right.to_json}})
end
end
class Integer < Node
def initialize(value)
@value = value
end
def to_json
"#{@value}"
end
end
ADD_SUB_OPERATOR = %w(+ -)
MUL_DIV_OPERATOR = %w(* /)
OPEN_PARENTHESES = '('
CLOSE_PARENTHESES = ')'
DIGIT = %w(0 1 2 3 4 5 6 7 8 9)
def initialize(expression)
@pointer = 0
@expression = expression
end
def parse
parse_expression!
end
private
def parse_expression!
left = parse_term!
return left if parse_end?
operator = pointed_character
return left unless ADD_SUB_OPERATOR.include?(operator)
@pointer += 1
right = parse_expression!
BinaryOperator.new(left, operator, right)
end
def parse_term!
left = parse_factor!
return left if parse_end?
operator = pointed_character
return left unless MUL_DIV_OPERATOR.include?(operator)
@pointer += 1
right = parse_term!
BinaryOperator.new(left, operator, right)
end
def parse_factor!
if pointed_character == OPEN_PARENTHESES
@pointer += 1
expression = parse_expression!
raise ParseError unless pointed_character == CLOSE_PARENTHESES
@pointer += 1
return expression
else
parse_number!
end
end
def parse_number!
raise ParseError unless DIGIT.include?(pointed_character)
value = pointed_character.to_i
@pointer += 1
while DIGIT.include?(pointed_character)
value *= 10
value += pointed_character.to_i
@pointer += 1
end
Integer.new(value)
end
def pointed_character
@expression[@pointer]
end
def parse_end?
@pointer == @expression.length
end
end
unless ARGV.size == 2
puts 'usage: ruby main.rb SRC DST'
exit 1
end
src_file = File.open(ARGV[0], 'r')
dst_file = File.open(ARGV[1], 'w')
expression = src_file.readline.chomp
ast = ExpressionParser.new(expression).parse.to_json
dst_file.puts ast
src_file.close
dst_file.close
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment