구문분석기 racc

racc 는 yacc 의 루비 버전이다.

calc.y

# 연산자 - *
# - 가 * 보다 우선순위가 높다
# - 는 우결합성

class CalcParser
# 연산자 우선 순위
    prechigh
        right '-' # 우결합
        left  '*' # 좌결합
    preclow

rule
    target: exp
       | {result = 0} # result 는 val[0]
    exp: exp '-' exp { result -= val[2] }
       | exp '*' exp { result *= val[2] }
       | NUMBER
end

# header, inner, footer 은 파일에 그대로 추가되는 부분이다.
---- header
require 'English'
---- inner
def parse(str) # 스캐너를 사람이 만들어야 한다.
    @q = []
    until str.empty?
        case str
        when /\A\s+/
        when /\A\d+/
            @q.push [:NUMBER, Regexp.last_match[0].to_i] # 위에 터미널인 NUMBER 가 심볼로 되어 있다.
        when /\A.|\n/o
            s = Regexp.last_match[0]
            @q.push [s, s]
        end
        str = Regexp.last_match.post_match
    end
    @q.push [false, '$end']
    do_parse
end

def next_token
    @q.shift
end

---- footer
parser = CalcParser.new
puts
puts 'type "q" to quit.'
puts
while true
    puts
    print '? '
    str = gets.chop!
    break if /q/i =~ str
    begin
        puts "= #{parser.parse(str)}" # 위에 정의한 parse 메소드가 실행된다.
    rescue ParseError
        puts $ERROR_INFO
    end
end

$ racc calc.y
$ ruby1.9.1 calc.tab.rb

-가 *보다 우선순위가 높고 -를 우결합으로 해놓았기 때문에 이렇게 계산이 된다.

1-3-2*2 = (1-(3-2)) * 2 = 0
4-1*1-2 = (4-1) * (1-2) = -3
7-5*2 = (7-5)*2 = 4
2*4-5 = 2*(4-5) = -2