Per 2016, RMID pindah ke RMID Discord (Invite link dihapus untuk mencegah spambot -Theo @ 2019). Posting sudah tidak bisa dilakukan lagi.
Mohon maaf atas ketidaknyamanannya dan mohon kerjasamanya.

Share | 
 

 Parser Tool

Topik sebelumnya Topik selanjutnya Go down 
Parser Tool Empty2011-04-14, 12:07
PostParser Tool
#1
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
Parser Tool Vide
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://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
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)


Terakhir diubah oleh bungatepijalan tanggal 2011-04-20, 16:20, total 3 kali diubah
Parser Tool Empty2011-04-14, 12:49
PostRe: Parser Tool
#2
Vsio 
Xutix Xox
Xutix Xox
Vsio

Kosong
Posts : 2377
Thanked : 18
Engine : Multi-Engine User
Skill : Advanced
Type : Developer

Parser Tool Vide
Ini bukannya yang buat compiler itu ya? :swt:

Walah sampai diterapin di sini scriptnya =))

Btw, berarti CFGnya gimana donk yg ini? :kabur:

EDIT:

Nih ane kasih Cendol nih soalnya gile sampai diterapin di sini Teori dan Bahasa Otomatanya :hammer:
Parser Tool Empty2011-04-14, 13:13
PostRe: Parser Tool
#3
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
Parser Tool Vide
Ya, bisa jg utk bikin compiler, krn compiler termasuk parser.
Soal CFG-nya, kita harus mengubahnya sendiri ke PDA, lalu diubah lagi menjadi PDA yg deterministik (pake cara konversi NFA ke DFA).
Atau.. coba parser generator: http://www.bumblebeesoftware.com/
sapa tau bisa membantu :senyum:
Parser Tool Empty2011-04-14, 15:21
PostRe: Parser Tool
#4
TheoAllen 
♫ RMID Rebel ♫
♫ RMID Rebel ♫
TheoAllen

Kosong
Posts : 4935
Thanked : 63
Awards:




Parser Tool Vide
ga ngerti istilah script. :swt:
gunanya buat game dev apaan y?
Parser Tool Empty2011-04-14, 15:30
PostRe: Parser Tool
#5
hart 
Senior
Senior
avatar

Level 5
Posts : 805
Thanked : 38
Engine : Other
Skill : Very Beginner
Type : Developer

Parser Tool Vide
@om bunga: wah, mantap nih. teori automata dan bahasa formal nih? :shocked: tapi deskripsi, FAQ, dll, pake bahasa yang lebih awam plisss, soalnya kebanyakan member sini kan bukan scripter. Misalnya saja saya yang buta sama sekali tentang program :sembah:

@om theo: gunanya buat bikin bahasa script sendiri :kabur:
Parser Tool Empty2011-04-14, 15:39
PostRe: Parser Tool
#6
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
Parser Tool Vide
@theo
Hehe.. ya emang gitu lah krn ini buat tugasku =))
gunanya ya bikin interpreter sendiri :kabur:

@hart
Ya kurang cocok buat awam lah, jadi bahasanya ga awam juga =))
dan lebih cocok buat scripter sih, yg ingin bikin interpreter :kabur:
Parser Tool Empty2011-04-14, 17:40
PostRe: Parser Tool
#7
Vsio 
Xutix Xox
Xutix Xox
Vsio

Kosong
Posts : 2377
Thanked : 18
Engine : Multi-Engine User
Skill : Advanced
Type : Developer

Parser Tool Vide
@Bunga:

Btw, request nih.

Minta yang bisa parsing syntax simple ini:

Code:

BEGIN
END
Parser Tool Empty2011-04-16, 11:17
PostRe: Parser Tool
#8
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
Parser Tool Vide
A little update: Version 1.1 :kabur:
Added: Error handling feature. If input and top stack condition aren't recognized by PDA, parsing will be terminated and input string will be claimed to be not valid.

Script:
Code:
#==============================================================================
# Parser Tool by Bunga Tepi Jalan
# Version 1.1
#==============================================================================
# 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
#
#==============================================================================
# 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://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
  attr_reader :alphabets
  #--------------------------------------------------------------------------
  # * 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,alphabets=[])
    @state_start = state_start
    @sym_start = sym_start
    @states_final = states_final
    @states = Array.new
    @alphabets = alphabets
  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) &&
          (@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

Demo updated too.. with new appearance and additional parser sample: BEGIN-END validation.
Link: http://ifile.it/oe7lvgb/ParserDemo.zip

@Vsio
Permintaan dikabulkan, silakan liat di demo update-annya :kabur:
Parser Tool Empty2011-04-16, 11:26
PostRe: Parser Tool
#9
Vsio 
Xutix Xox
Xutix Xox
Vsio

Kosong
Posts : 2377
Thanked : 18
Engine : Multi-Engine User
Skill : Advanced
Type : Developer

Parser Tool Vide
Wah mantap lah, Btj :D

Btw, itu dalam bahasa C kan? :D

Btw, yuk lanjut lagi tubes compilernya XD
Parser Tool Empty2011-04-16, 12:32
PostRe: Parser Tool
funkyee 
Newbie
Newbie
funkyee

Level 5
Posts : 61
Thanked : 0
Engine : RMVX
Skill : Intermediate
Type : Writer

Parser Tool Vide
wow kk bunga keren...ne scripter advanced yaaa....
sepertinya selain googling PDA harus ningkatin minat belajar script...
Jadiii...badan script n jenisnya memang beragam yak... tapi ini kompatibel di VX n XP kan yaa??
:D
Parser Tool Empty2011-04-16, 12:38
PostRe: Parser Tool
Vsio 
Xutix Xox
Xutix Xox
Vsio

Kosong
Posts : 2377
Thanked : 18
Engine : Multi-Engine User
Skill : Advanced
Type : Developer

Parser Tool Vide
Btw, pas aku coba, kok langsung dianggap malware ya? :swt:
Parser Tool Empty2011-04-16, 12:49
PostRe: Parser Tool
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
Parser Tool Vide
Hehe, mo belajar scripting juga yah? :D
Yang penting, menguasai dasar2 algoritma/pemrograman, dan syntax bahasa Ruby.
Btw, kl mo request PDA yang bisa sesuatu, silakan aja ;)

ini kompatibel di VX n XP kan yaa?? << ya iyalah, sesuai yg ditulis di FAQ, coba aja :D
Parser Tool Empty2011-04-16, 12:51
PostRe: Parser Tool
Vsio 
Xutix Xox
Xutix Xox
Vsio

Kosong
Posts : 2377
Thanked : 18
Engine : Multi-Engine User
Skill : Advanced
Type : Developer

Parser Tool Vide
Btw, request lagi :hammer:

Minta PDA yang bisa compiling.

Speknya bisa dilihat di soal tubes I TBO. :kabur:
Parser Tool Empty2011-04-19, 14:04
PostRe: Parser Tool
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
Parser Tool Vide
Phew~ setelah sekian lama susah payahnya bikin parser sesuai request Vsio buat tugas TBO... :swt:
Ini dia update terbarunya: Version 1.2
- Input character condition "_" in state transition functions used as wildcard that represents any input
- Parsers are defined in "Parsers" module
- Text Reader add-on for retrieving string from file named 'code.txt' located in the game directory (included in demo)
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://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
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
Demo updated too.. with new additional parser sample: simple program code validation. A sample valid code included in demo.
Link: http://ifile.it/toj4krc/ParserDemo.zip
Parser Tool Empty2011-04-19, 14:06
PostRe: Parser Tool
Vsio 
Xutix Xox
Xutix Xox
Vsio

Kosong
Posts : 2377
Thanked : 18
Engine : Multi-Engine User
Skill : Advanced
Type : Developer

Parser Tool Vide
Walah, ini sampai dikonversi semua dari bahasa C ke Ruby nih? =))

Mantap lah! =))

*Thanks Reputation Point sent*
Parser Tool Empty2011-04-19, 16:12
PostRe: Parser Tool
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
Parser Tool Vide
Sori, ada yang lupa :kabur:
Khususnya untuk contoh parser terakhir sesuai request dr Vsio, bagi yang belum sempat download demo atau tidak mengerti cara kerjanya, ane kasi penjelasannya, sesuai di spesifikasi tugasku:
Spesifikasi parser:
Berikutnya implementasinya di RGSS/RGSS2:
- Buat slot script baru di bawah "PDA" dan isi dengan:
Code:
module Parsers
  $pda3 = PDA.new(0,"Z",[1])
  # begin
  $pda3.add_state(0,"b","Z",1,"neZ")
  $pda3.add_state(1,"b","b",1,"ne")
  # newline
  $pda3.add_state(1,"n","e",1,"e")
  $pda3.add_state(1,"n","n",1,"")
  # assignment
  $pda3.add_state(1,"V","e",1,"=Ene")
  $pda3.add_state(1,"V","l",1,"=En")
  $pda3.add_state(1,"=","=",1,"")
  $pda3.add_state(1,"V","E",2,"")
  $pda3.add_state(1,"I","E",2,"")
  $pda3.add_state(2,"V","E",2,"")
  $pda3.add_state(2,"I","E",2,"")
  # advanced expressions
  $pda3.add_state(1,"(","E",2,"E)")
  $pda3.add_state(2,"(","E",2,"E)")
  $pda3.add_state(2,"+","n",2,"En")
  $pda3.add_state(2,"-","n",2,"En")
  $pda3.add_state(2,"*","n",2,"En")
  $pda3.add_state(2,"+",")",2,"E)")
  $pda3.add_state(2,"-",")",2,"E)")
  $pda3.add_state(2,"*",")",2,"E)")
  $pda3.add_state(2,"+","K",2,"EK")
  $pda3.add_state(2,"-","K",2,"EK")
  $pda3.add_state(2,"*","K",2,"EK")
  $pda3.add_state(2,")",")",2,"")
  $pda3.add_state(2,"n","n",1,"")
  # input & output proc
  $pda3.add_state(1,"i","e",1,"(V)ne")
  $pda3.add_state(1,"o","e",1,"(E)ne")
  $pda3.add_state(1,"i","l",1,"(V)n")
  $pda3.add_state(1,"o","l",1,"(E)n")
  $pda3.add_state(1,"V","V",1,"")
  $pda3.add_state(1,"(","(",1,"")
  $pda3.add_state(1,")",")",1,"")
  # control statements
  $pda3.add_state(1,"f","e",1,"(EKE)tnbnle")
  $pda3.add_state(1,"f","l",1,"(EKE)tnbnl")
  $pda3.add_state(1,"l","l",1,"nbn")
  $pda3.add_state(1,"w","e",1,"(EKE)dnbne")
  $pda3.add_state(1,"w","l",1,"(EKE)dnbn")
  $pda3.add_state(1,"r","e",1,"nbnu(EKE)ne")
  $pda3.add_state(1,"r","l",1,"nbnu(EKE)n")
  $pda3.add_state(2,"=","K",2,"")
  $pda3.add_state(2,"!","K",2,"")
  $pda3.add_state(2,">","K",2,"")
  $pda3.add_state(2,"<","K",2,"")
  $pda3.add_state(2,"G","K",2,"")
  $pda3.add_state(2,"L","K",2,"")
  $pda3.add_state(2,"t","t",1,"")
  $pda3.add_state(2,"d","d",1,"")
  $pda3.add_state(1,"u","u",1,"")
  $pda3.add_state(1,"n","l",1,"")
  # comment
  $pda3.add_state(1,"{","n",1,"}n")
  $pda3.add_state(2,"{","n",1,"}n")
  $pda3.add_state(1,"{","e",1,"}ne")
  $pda3.add_state(1,"{","l",1,"}n")
  $pda3.add_state(1,"}","}",1,"")
  $pda3.add_state(1,"_","}",1,"}")
  # end
  $pda3.add_state(1,"e","e",1,"")
 
  def self.pda3_getInputChar
  begin
    input_char = " "
    if $tr.cw == "\n"
      input_char = "n"
    end
    if $tr.cw.downcase == "begin"
      input_char = "b"
    elsif $tr.cw.downcase == "end"
      input_char = "e"
    elsif $tr.cw.downcase == "if"
      input_char = "f"
    elsif $tr.cw.downcase == "then"
      input_char = "t"
    elsif $tr.cw.downcase == "else"
      input_char = "l"
    elsif $tr.cw.downcase == "repeat"
      input_char = "r"
    elsif $tr.cw.downcase == "until"
      input_char = "u"
    elsif $tr.cw.downcase == "while"
      input_char = "w"
    elsif $tr.cw.downcase == "do"
      input_char = "d"
    elsif $tr.cw.downcase == "input"
      input_char = "i"
    elsif $tr.cw.downcase == "output"
      input_char = "o"
    elsif $tr.cw.downcase == "("
      input_char = "("
    elsif $tr.cw.downcase == ")"
      input_char = ")"
    elsif $tr.cw.downcase == "="
      input_char = "="
    elsif $tr.cw.downcase == "+"
      input_char = "+"
    elsif $tr.cw.downcase == "-"
      input_char = "-"
    elsif $tr.cw.downcase == "*"
      input_char = "*"
    elsif $tr.cw.downcase == "{"
      input_char = "{"
    elsif $tr.cw.downcase == "}"
      input_char = "}"
    elsif $tr.cw.downcase == "<>"
      input_char = "!"
    elsif $tr.cw.downcase == ">"
      input_char = ">"
    elsif $tr.cw.downcase == "<"
      input_char = "<"
    elsif $tr.cw.downcase == ">="
      input_char = "G"
    elsif $tr.cw.downcase == "<="
      input_char = "L"
    else
      i = 0
      if ($tr.cw[i] >= 48 && $tr.cw[i] <= 57) || $tr.cw[i,1] == "-"
        iNt = 0
        if $tr.cw[i,1] != "-"
          iNt = $tr.cw[i]-48
        end
        input_char = "I"
        for i in 1..$tr.cw.length-1
          if $tr.cw[i]<48 || $tr.cw[i]>57
            input_char = " "
            break
          else
            if $tr.cw[0,1] == "-"
              iNt = iNt*10-($tr.cw[i]-48)
            else
              iNt = iNt*10+($tr.cw[i]-48)
            end
          end
        end
        if iNt<-32768 || iNt>32767
          input_char = " "
        end
      elsif ($tr.cw[i,1].downcase[0] >= 97 && $tr.cw[i,1].downcase[0] <= 122) || $tr.cw[i,1] == "_"
        input_char = "V"
        for i in 1..$tr.cw.length-1
          if ($tr.cw[i,1].downcase[0]<97 || $tr.cw[i,1].downcase[0]>122) && $tr.cw[i,1] != "_" && ($tr.cw[i]<48 || $tr.cw[i]>57)
            input_char = " "
            break
          end
        end
      end
    end
    $input_string = $input_string+input_char
  rescue
    p "dsf"
  end
  end
  def self.pda3_process
    $pda3.startPDA($input_string)
    $game_variables[1] = 1
    if ($input_string[$pda3.string_input_pointer,1]=="n")
      $game_variables[1] += 1
    end
    until $pda3.isDone
      if $game_switches[1]
        $pda3.printCurrentState
      end
      $pda3.proceed
      if ($input_string[$pda3.string_input_pointer,1]=="n")
        $game_variables[1] += 1
      end
    end
    if $game_switches[1]
      $pda3.printCurrentState
    end
  end
end
- Implementasi parser ini dapat dilihat pada contoh berikut ini:
Spoiler:
- Buatlah file baru dgn nama 'code.txt' dan isi dengan code program sesuai spesifikasi yang dikatakan diatas. Berikut ini contoh kode yang valid untuk parser tersebut:
Spoiler:
Parser Tool Empty2011-04-20, 15:59
PostRe: Parser Tool
Vsio 
Xutix Xox
Xutix Xox
Vsio

Kosong
Posts : 2377
Thanked : 18
Engine : Multi-Engine User
Skill : Advanced
Type : Developer

Parser Tool Vide
Akhirnya yang dalam versi bahasa pemrograman C dipost di sini :banana:

*siapin 8)*
Parser Tool Empty2011-04-20, 16:02
PostRe: Parser Tool
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
Parser Tool Vide
Ini dia parser request-nya Vsio dlm versi bahasa C-nya (yg buat tugas) :kabur:
Cara pakenya? tinggal masukin nama file yg ingin divalidasi dengan parser ini.
Link: http://ifile.it/u57oxcm/mpda.rar

Enjoy ;)
Parser Tool Empty2011-04-20, 20:41
PostRe: Parser Tool
Vsio 
Xutix Xox
Xutix Xox
Vsio

Kosong
Posts : 2377
Thanked : 18
Engine : Multi-Engine User
Skill : Advanced
Type : Developer

Parser Tool Vide
Asiklah tadi demo tubes sukses :banana:

Compiler algoritma sederhana sukses di bahasa C dan Ruby :banana:

*Thanks Reputation Point sent*
Parser Tool Empty
PostRe: Parser Tool
Sponsored content 




Parser Tool Vide
 

Parser Tool

Topik sebelumnya Topik selanjutnya Kembali Ke Atas 

Similar topics

+
Halaman 1 dari 1

Permissions in this forum:Anda tidak dapat menjawab topik
RPGMakerID :: Scripts & Event Systems :: RMXP Scripts-