#
# parser.rb
#
#   Copyright (c) 1999 Minero Aoki <aamine@dp.u-netsurf.ne.jp>
#
#   This program is free software.
#   You can distribute/modify this program under the terms of
#   the GNU Lesser General Public License version 2 or later.
#

unless defined? ParseError then
  class ParseError < StandardError; end
end


module Racc


class Parser

  private


  begin
    require 'racc/cparse'   # def _c_parse
    Racc_Main_Parsing_Routine = :_c_parse
  rescue LoadError
    Racc_Main_Parsing_Routine = :_rb_parse
  end
  # Racc_Main_Parsing_Routine = :_rb_parse


  def next_token
    raise NotImplementError, "#{self.type}#next_token must be defined"
  end


  def do_parse
    t = self.type
    unless t::Racc_debug_parser then
      @yydebug = false
    end
    @yydebug = @yydebug ? true : false

    send( Racc_Main_Parsing_Routine,
          t::Racc_action_table,
          t::Racc_action_table_ptr,
          t::Racc_goto_table,
          t::Racc_goto_table_ptr,
          t::Racc_reduce_table,
          t::Racc_token_table,
          t::Racc_shift_n,
          t::Racc_reduce_n,
          false )
  end


  def _rb_parse( action_table, action_ptr, goto_table, goto_ptr,
                 reduce_table, token_table, shift_n, reduce_n,
                 in_debug )
    #
    # local variables
    #

    state    = [ 0 ]
    curstate = 0

    tstack = []
    vstack = []

    atmp = tok = val = t = nil
    read_next = true

    act = i = ii = nil

    errstatus = 0
    nerr = 0

    t_def = -1   # default token
    t_end = 0    # $end
    t_err = 1    # error token

    #
    # LR parsing algorithm main loop
    #

    while true do

      if read_next then
        if t != t_end then
          atmp = next_token
          tok = atmp[0]
          val = atmp[1]
          t = (token_table[tok] or t_err)

          read_next = false
        end
      end

      i = action_ptr[curstate]
      while true do
        ii = action_table[i]
        if ii == t or ii == t_def then
          act = action_table[i+1]
          break
        end
        i += 2
      end

      if act > 0 and act < shift_n then
        #
        # shift
        #

        if errstatus > 0 then
          errstatus -= 1
        end

        tstack.push t if @yydebug
        vstack.push val

        _shift( t, tstack ) if @yydebug

        curstate = act
        state.push curstate

        read_next = true

      elsif act < 0 and act > -reduce_n then
        #
        # reduce
        #

        curstate = _do_reduce( action_table, action_ptr,
                               goto_table, goto_ptr, reduce_table,
                               state, curstate, vstack, tstack,
                               act )
        state.push curstate

      elsif act == shift_n then
        #
        # accept
        #

        _accept if @yydebug
        break

      elsif act == -reduce_n then
        #
        # error
        #

        case errstatus
        when 0
          nerr += 1
          on_error t, val, vstack
        when 3
          if t == t_end then
            return nil
          end
          read_next = true
        end
        errstatus = 3

        while true do
          i = action_ptr[curstate]
          while true do
            ii = action_table[i]
            if ii == t_def then
              break
            end
            if ii == t_err then
              act = action_table[i+1]
              break
            end
            i += 2
          end

          break if act != -reduce_n

          return nil if state.size < 2
          state.pop
          vstack.pop
          tstack.pop if @yydebug
          curstate = state[-1]
        end

        if act > 0 and act < shift_n then
          #
          # err-shift
          #
          tstack.push t_err if @yydebug
          vstack.push nil

          _shift( t_err, tstack ) if @yydebug

          curstate = act
          state.push curstate
          
        elsif act < 0 and act > -reduce_n then
          #
          # err-reduce
          #
          curstate = _do_reduce( action_table, action_ptr,
                                 goto_table, goto_ptr, reduce_table,
                                 state, curstate, vstack, tstack,
                                 act )
          state.push curstate

        elsif act == shift_n then
          #
          # err-accept
          #
          _accept if @yydebug
          break

        else
          raise RuntimeError, "[Racc Bug] wrong act value #{act.inspect}"
        end

      else
        raise RuntimeError, "[Racc Bug] unknown action #{act.inspect}"
      end

      _print_state( curstate, state ) if @yydebug
    end

    vstack[0]
  end


  def on_error( t, val, vstack )
    raise ParseError, "\nunexpected token #{val.inspect}"
  end


  def _do_reduce( action_table, action_ptr,
                  goto_table, goto_ptr, reduce_table,
                  state, curstate, vstack, tstack,
                  act )
    i = act * -3
    ii = nil
    len       = reduce_table[i]
    reduce_to = reduce_table[i+1]
    method_id = reduce_table[i+2]
    void_array = []

    tmp_t = tstack[ -len, len ] if @yydebug
    tmp_v = vstack[ -len, len ]
    tstack[ -len, len ] = void_array if @yydebug
    vstack[ -len, len ] = void_array
    state[ -len, len ]  = void_array

    # tstack must be renewed AFTER method calling
    vstack.push( (method_id == :_reduce_none) ?
                     tmp_v[0] : send(method_id, tmp_v, vstack, tmp_v[0]) )
    tstack.push reduce_to

    _reduce( tmp_t, reduce_to, tstack ) if @yydebug

    i = goto_ptr[state[-1]]
    while true do
      ii = goto_table[i]
      if ii == reduce_to or ii == 0 then
        curstate = goto_table[i+1]
        break
      end
      i += 2
    end

    curstate
  end


  # for debugging output

  def _shift( tok, tstack )
    print 'shift   ', _token2str(tok), "\n"
    _print_tokens( tstack, true )
    print "\n\n"
  end

  def _accept
    print "accept\n\n"
  end

  def _reduce( toks, sim, tstack )
    print 'reduce '
    if toks.size == 0 then
      print ' <none>'
    else
      _print_tokens( toks, false )
    end
    print ' --> '; puts _token2str(sim)
        
    _print_tokens( tstack, true )
    print "\n\n"
  end

  def _print_tokens( toks, bla )
    print '        [' if bla
    toks.each {|t| print ' ', _token2str(t) }
    print ' ]' if bla
  end

  def _print_state( curstate, state )
    puts  "goto    #{curstate}"
    print '        ['
    state.each {|st| print ' ', st }
    print " ]\n\n"
  end

  def _token2str( tok )
    unless ret = self.type::Racc_token_to_s_table[tok] then
      raise RuntimeError, "[Racc Bug] can't convert token #{tok} to string"
    end
    ret
  end

end


end   # module Racc
