Parser Tool

#==============================================================================
# Parser Tool by Bunga Tepi Jalan
# Version 1.2
#==============================================================================
# Copyrighted by Bunga Tepi Jalan.
#  * Don't forget to credit me if you want to use this work
#  * You are free to Share - to copy, distribute and transmit the work
#  * You are free to Remix - to adapt the work
#  * You may not use this work for commercial purposes
#
# Credits
#  Vsio Stitched (documenting)
#==============================================================================
# Information:
#  This script provides a tool for parsing, using Pushdown Automaton (PDA).
#  Note that it doesn't provide a ready-to-use parser. You have to
#  initialize and design PDA with following code:
#
#    $pda = PDA.new(start_state,first_stack_symbol,set_of_final_states)
#    $pda.add_state(state_number,input_condition,symbol_tobe_popped,
#      next_state,symbols_tobe_pushed)
#    . . .
#
#  Note that the PDA must be deterministic (only single state transitions and
#  no epsilon transitions). To give string of input sequence and start
#  parsing, just call:
#
#    $pda.startPDA(input_string)
#
#  And then perform parsing process:
#
#    until $pda.isDone
#      # <process>
#      $pda.proceed
#    end
#
#  Parsing done. Use $pda.isValid to see if the input string is valid.
#
#
#  To learn about PDA, see/visit below:
#    - Hopcroft, John E, et al, Introduction to Automata Theory, Languages,
#      and Computation, Second Edition, ch 6.
#    - http://www-db.stanford.edu/~ullman/ialc.html
#    - http://en.wikipedia.org/wiki/Pushdown_automaton
#
# If you find any bugs or you have any suggestions, please report them via
# e-mail (listra92@gmail.com), or either my blog or these forums:
#  - http://bungatepijalan.wordpress.com
#  - http://rmid.forumotion.net
#  - http://prodig.forumotion.net
#==============================================================================

#==============================================================================
# ** PDA
#------------------------------------------------------------------------------
#  This class represents a Pushdown Automaton (PDA). The PDA must be
#  deterministic (only single state transitions and no epsilon transitions)
#  in order to be used as a parser.
#==============================================================================

class PDA
  attr_reader :state_current
  attr_reader :string_input
  attr_reader :stack
  attr_reader :string_input_pointer
  #--------------------------------------------------------------------------
  # * Initialization
  #    state_start      : start state (an index number)
  #    sym_start        : start stack symbol
  #    states_final      : set/array of final states
  #--------------------------------------------------------------------------
  def initialize(state_start,sym_start,states_final)
    @state_start = state_start
    @sym_start = sym_start
    @states_final = states_final
    @states = Array.new
  end
  #--------------------------------------------------------------------------
  # * Start Parsing
  #    string_input      : input string to be parsed
  #--------------------------------------------------------------------------
  def startPDA(string_input)
    @string_input = string_input
    @string_input_pointer = 0
    @state_current = @state_start
    @stack = [@sym_start]
    @error_flag = false
  end
  #--------------------------------------------------------------------------
  # * Add State
  #    state_num        : state's index number
  #    char_input        : input character condition
  #    sym_popped        : stack symbol to be popped from stack
  #    state_next        : next state's index number
  #    string_pushed    : set of stack symbols (or string) to be pushed
  #                        into stack
  #--------------------------------------------------------------------------
  def add_state(state_num,char_input,sym_popped,state_next,string_pushed)
    # Adds a state and its transition function
    @states.push(State.new(state_num,char_input,sym_popped,state_next,string_pushed))
  end
  #--------------------------------------------------------------------------
  # * Proceed to Next State
  #--------------------------------------------------------------------------
  def proceed
    if (@string_input_pointer<@string_input.length)
      @error_flag = true
      for i in 0..@states.length-1
        if (@string_input[@string_input_pointer,1] == @states[i].char_input || @states[i].char_input == "_") &&
          (@state_current == @states[i].state_num) &&
          (@stack[@stack.length-1] == @states[i].sym_popped)
          # Sets current state to next state
          @state_current = @states[i].state_next
          # Pop last symbol from stack
          @stack.pop
          # Push new symbols
          j = @states[i].string_pushed.length-1
          while j>=0
            @stack.push(@states[i].string_pushed[j,1])
            j = j-1
          end
          @error_flag = false
          break
        end
      end
      # Mark error flag and terminate parsing if current condition isn't in
      # state transition list
      if @error_flag
        @string_input_pointer = @string_input.length-1
      end
      # Advance input string traversal position
      @string_input_pointer = @string_input_pointer+1
    end
  end
  #--------------------------------------------------------------------------
  # * Is Parsing Done?
  #--------------------------------------------------------------------------
  def isDone
    # Parsing is done when parser has finished traversing input string
    return @string_input_pointer >= @string_input.length
  end
  #--------------------------------------------------------------------------
  # * Is Input String Valid?
  #--------------------------------------------------------------------------
  def isValid
    # Input string is valid if stack remains start symbol and current state
    # is final state
    return !@error_flag && (@stack.length == 1) && (@stack[0] == @sym_start) && (@states_final.index(@state_current) != nil)
  end
  #--------------------------------------------------------------------------
  # * Print Current State
  #--------------------------------------------------------------------------
  def printCurrentState
    string_input_rem = @string_input[@string_input_pointer,@string_input.length-@string_input_pointer]
    print("Current state: #{@state_current}\nCurrent stack contents: #{@stack}\nRemaining input string: #{string_input_rem}")
  end
end

#==============================================================================
# ** State
#------------------------------------------------------------------------------
#  This class represents a state and its transition function.
#==============================================================================
class State
  attr_accessor :state_num
  attr_accessor :char_input
  attr_accessor :sym_popped
  attr_accessor :state_next
  attr_accessor :string_pushed
  #--------------------------------------------------------------------------
  # * Initialization
  #    state_num        : state's index number
  #    char_input        : input character condition
  #    sym_popped        : stack symbol to be popped from stack
  #    state_next        : next state's index number
  #    string_pushed    : set of stack symbols (or string) to be pushed
  #                        into stack
  #--------------------------------------------------------------------------
  def initialize(state_num,char_input,sym_popped,state_next,string_pushed)
    @state_num = state_num
    @char_input = char_input
    @sym_popped = sym_popped
    @state_next = state_next
    @string_pushed = string_pushed
  end
end

#==============================================================================
# Text Reader by Bunga Tepi Jalan
#==============================================================================
# Instructions:
#  - Use either CharReader or TextReader class.
#  - If you use CharReader, use code below to process the text:
#
#  $cr = CharReader.new
#  $cr.start("file.txt")
#  begin
#    #process
#    $cr.adv
#  end until $cr.eof
#  #final process
#
#  - If you use TextReader, use code below to process the text:
#
#  $tr = TextReader.new
#  $tr.start("file.txt")
#  begin
#    #process
#    $tr.adv
#  end until $tr.cw == ""
#  #final process
#==============================================================================

#==============================================================================
# ** CharReader
#------------------------------------------------------------------------------
#  This class read a file by character.
#==============================================================================
class CharReader
  attr_reader :cc
  attr_reader :cc1
  #--------------------------------------------------------------------------
  # * Initialization
  #--------------------------------------------------------------------------
  def initialize
  end
  #--------------------------------------------------------------------------
  # * Start Reading
  #--------------------------------------------------------------------------
  def start(filename)
    begin
      @myFile = File.open(filename,"r+")
      @cc = ""
      if !eof
        @cc = @myFile.read(1)
      end
      @cc1 = ""
    rescue
    end
  end
  #--------------------------------------------------------------------------
  # * Advance Reading
  #--------------------------------------------------------------------------
  def adv
    begin
      if eof
        @myFile.close
        @cc1 = @cc
        @cc = ""
      else
        @cc1 = @cc
        @cc = @myFile.read(1)
      end
    rescue
    end
  end
  #--------------------------------------------------------------------------
  # * End Of File?
  #--------------------------------------------------------------------------
  def eof
    return @cc == nil
  end
end

#==============================================================================
# ** TextReader
#------------------------------------------------------------------------------
#  This class read a file by word. Words are separated by spaces and newlines.
#  Here newlines are also words.
#==============================================================================

class TextReader
  attr_reader :cw
  attr_reader :cw1
  #--------------------------------------------------------------------------
  # * Initialization
  #--------------------------------------------------------------------------
  def initialize
    @cr = CharReader.new
  end
  #--------------------------------------------------------------------------
  # * Ignore Blanks
  #--------------------------------------------------------------------------
  def ignore_blank
    while !eof && (@cr.cc==" " || @cr.cc=="\t")
      @cr.adv
    end
  end
  #--------------------------------------------------------------------------
  # * Start Reading
  #--------------------------------------------------------------------------
  def start(filename)
    @cr.start(filename)
    @cw = ""
    ignore_blank
    write_word
  end
  #--------------------------------------------------------------------------
  # * Advance Reading
  #--------------------------------------------------------------------------
  def adv
    ignore_blank
    write_word
  end
  #--------------------------------------------------------------------------
  # * Write Word
  #--------------------------------------------------------------------------
  def write_word
    i = 0
    @cw1 = @cw
    @cw = ""
    if !eof
      begin
        @cw = @cw+@cr.cc
        @cr.adv
      end while (!eof && @cr.cc!=" " && @cr.cc!="\t" && !((@cr.cc[0]==13 || @cr.cc[0]==10) && (@cr.cc1[0]>=33 && @cr.cc1[0]<=126)) && @cr.cc1[0]!=10)
    end
  end
  #--------------------------------------------------------------------------
  # * End Of File?
  #--------------------------------------------------------------------------
  def eof
    return @cr.eof
  end
end