Prodig - Komunitas Proyek Digital
Selamat datang di ProDig!
Di sini adalah tempat untuk berbagi proyek (game, seni, program, dan situs).
Di sini Anda juga bisa mendapatkan hal lainnya seperti permainan, berbagi karya, ilmu pengetahuan, kesenangan, dan sebagainya. :)

Ayo daftar lalu langsung login tanpa perlu konfirmasi email sama sekali :D!
Prodig - Komunitas Proyek Digital

Tempat untuk berbagi proyek digital : Situs, Game, Seni, Program
 
CalendarPortalHomeRulesSearchFAQMemberlistUsergroupsRegisterLog in
Welcome to the ProDig, Guest!

 
 

 Parser Tool

View previous topic View next topic Go down 
AuthorMessage
Alissa
Ngacay Princess


Status : Ngacay :v
Posts : 424
Chips : 4172
Power : 14
Join date : 2010-09-22
Location : Antara ada dan tiada :-
Badge :

PostSubject: Parser Tool   
Thu Apr 21, 2011 6:00 pm


Parser Tool
Versi: 1.2
Tipe: Parser Engine


Pengenalan

Script ini digunakan untuk mendesain parser, yaitu sistem yang memproses dan melakukan validasi terhadap data masukan (berupa string). Parser didesain menggunakan sistem yang disebut Pushdown Automaton (PDA). Pengertian PDA dapat dilihat di bagian FAQ.

Script ini tidak menyediakan parser yang siap pakai. Anda harus mendesain sendiri parser menggunakan sistem PDA. Cara mendesain parser dan memprosesnya dapat dilihat di script yang diberikan.

NB: Sebenarnya ini ditujukan untuk memenuhi tugas kuliahku: Teori Bahasa dan Otomata.



FAQ

Q: Apa itu PDA?
A:
Wikipedia wrote:
In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data.

Q: Koq pake inggris, terjemahin donk definisinya! :swt:
A: Okay, jadinya: Dalam teori otomata, pushdown automaton (PDA) adalah otomata terhingga yang dapat menggunakan stack yang berisi data.

Q: Gimana cara menggunakannya?
A: Lihat petunjuk di script-nya dan pelajari demo-nya.

Q: Bisakah script ini digunakan di RMVX?
A: Ya, karena scriptnya tidak menggunakan Game Library.

Q: Saya orang awam nih, gimana biar bisa mendesain parser?
A: Anda harus menguasai konsep dan prinsip PDA terlebih dahulu. Dan karena PDA merupakan finite otomata, anda juga harus menguasai konsep dan prinsip finite otomata (DFA dan NFA). Berikut ini referensi yg bisa anda pelajari:
- Hopcroft, John E, et al, Introduction to Automata Theory, Languages, and Computation, Second Edition
- http://www-db.stanford.edu/~ullman/ialc.html
- http://en.wikipedia.org/wiki/Pushdown_automaton

Q: Haruskah PDA yang digunakan deterministik?
A: Ya, disarankan begitu. Jika anda menggunakan PDA nondeterministik, parser hanya akan memakai salah satu transisi.

Q: Bagaimanakah penanganan stack kosong?
A: Mungkin parsing akan menjadi kacau. Maka dari itu, desainlah PDA yang tidak mungkin menyebabkan kasus stack kosong.

Q: Saya ingin membuat parser yang bisa.. (anu) tapi ga tau/bingung untuk mendesain PDA-nya, sementara saya susah mengerti konsepnya.
A: Okay, silahkan posting request parser-mu disini. Dan saya akan memberikan PDA-nya berupa potongan script. ;)



Screenshot

Spoiler:
 
Spoiler:
 
Spoiler:
 
Spoiler:
 
Spoiler:
 


Demo

Sample untuk mendemonstrasikan:
- parser yang menerima string masukan yang diawali simbol 0 sebanyak n dan diakhiri simbol 1 sebanyak n.
- parser yang menerima string masukan yang diawali "begin", diikuti spasi, dan diakhiri "end"
- parser yang membaca string masukan dari file 'code.txt', spesifikasi parsernya adalah sebagai berikut:
Spesifikasi parser:
 
Link: http://ifile.it/toj4krc/ParserDemo.zip
Keterangan lebih lanjut tentang demo dapat dilihat di salah satu dr post-post di bawah ini.


Script

Code:
#==============================================================================
# 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://www.rpgmakerid.com
#  - 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
Add-on script for text file processing:
Code:
#==============================================================================
# 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


Credits

  • Bunga Tepi Jalan (scripting)
  • Vsio Stitched (documenting)






SIGGY KOSONG
Back to top Go down
View user profile https://bungatepijalan.wordpress.com
 

Parser Tool

View previous topic View next topic Back to top 
Page 1 of 1

Permissions in this forum:You cannot reply to topics in this forum
Prodig - Komunitas Proyek Digital  :: Education Chamber :: Programming :: RGSS-
Jump to: