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.
|
|
| 2011-04-14, 12:07 | Parser Tool |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| Parser Tool Versi: 1.2 Tipe: Parser Engine PengenalanScript 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. FAQQ: 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! 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:
DemoSample 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:
Sebuah parser untuk mengenali apakah sintaks sebuah program sederhana itu benar atau tidak. Aplikasi akan membuka file yang berisi sintaks program dan kemudian memeriksa apakah semua sintaks pada program tersebut valid atau tidak. Jika tidak valid maka aplikasi akan mengeluarkan informasi baris yang menyebabkan ketidakvalidan sintaks program.
Program sederhana yang dimaksud hanya memiliki algoritma, tanpa pernyataan kamus atau judul program. Tipe variabel hanya integer dan operasi terhadap variabel hanya berupa operasi matematika untuk integer. Sintaks algoritma yang dimiliki program terdiri atas: 1. Begin – end sebagai batas awal dan akhir dari program 2. If – then {begin end} 3. If – then – {begin end} – else {begin end} 4. Repeat – until 5. While – do {begin end} 6. Kondisi (dengan operator: <, >, <=, >=, =, <>) Contoh: a >= b 7. Assignment (hanya operasi matematika untuk integer yaitu +, -, *) Contoh: a = b + c 8. Input (variabel) Contoh: input(z) 9. Output (variabel) atau Output (operasi matematika) Contoh: output(z) 10. Komentar yang ditandai dengan kurung buka (“{“) dan kurung tutup (“}”)
Keterangan selengkapnya: 1. Apabila terdapat sintaks error, maka program hanya memunculkan line keberapa yang error dan cukup hanya menelusuri 1 error saja. Jika program bisa mengeluarkan pesan error (error pada line berapa dan kesalahannya apa) dianggap bonus. 2. Jika program bisa menangani letak komentar seperti i{komentar}f (a < b), maka dianggap bonus. 3. Nama variabel tidak boleh diawali angka serta tidak boleh merupakan kata kunci yang telah didefinisikan pada bahasa (seperti if, while) 4. Bahasa case insensitive. 5. Untuk kata kunci seperti if (...), while (...), input (...), output (...), wajib menggunakan spasi. Contoh : input (a), bukan input(a). 6. Conditional statement wajib menggunakan kurung. Contoh : if (a<b), bukan if a=b. 7. Assignment variabel bisa berupa angka. Contoh : a = 5. 8. Assignment variabel juga bisa berupa ekspresi aritmatika yang panjang seperti a=(1+2)*(4-3) 9. Setelah program berakhir (diakhiri dengan end yang berasal dari begin penanda awal program) tidak boleh terdapat sampah. Contoh yang salah: Begin Input(z) end (ini adalah sampah) 10. Untuk tipe integer yang sesuai dengan spesifikasi integer (hanya mampu mencakup integer 32 bit) dianggap bonus. Integer yang dimaksud adalah signed integer. 11. Tokenisasi statement hanya boleh dalam 1 baris. Contoh salah : a = b. 12. Satu baris hanya boleh berisi satu perintah Contoh salah: If (a=5) then begin a=a+1 output (a) end 13. Indentasi tab tidak diperhatikan. 14. Tidak ada pengecekan apakah suatu variabel sudah didefinisikan sebelumnya atau belum apabila variabel tersebut akan digunakan.
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 |
| | | 2011-04-14, 12:49 | Re: Parser Tool |
---|
Vsio Xutix Xox
Posts : 2377 Thanked : 18 Engine : Multi-Engine User Skill : Advanced Type : Developer
| | | | 2011-04-14, 13:13 | Re: Parser Tool |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| 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 |
| | | 2011-04-14, 15:21 | Re: Parser Tool |
---|
TheoAllen ♫ RMID Rebel ♫
Posts : 4935 Thanked : 63
Awards:
| ga ngerti istilah script. gunanya buat game dev apaan y? |
| | | 2011-04-14, 15:30 | Re: Parser Tool |
---|
hart Senior
Posts : 805 Thanked : 38 Engine : Other Skill : Very Beginner Type : Developer
| @om bunga: wah, mantap nih. teori automata dan bahasa formal nih? 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 @om theo: gunanya buat bikin bahasa script sendiri |
| | | 2011-04-14, 15:39 | Re: Parser Tool |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| | | | 2011-04-14, 17:40 | Re: Parser Tool |
---|
Vsio Xutix Xox
Posts : 2377 Thanked : 18 Engine : Multi-Engine User Skill : Advanced Type : Developer
| @Bunga:
Btw, request nih.
Minta yang bisa parsing syntax simple ini:
- Code:
-
BEGIN END
|
| | | 2011-04-16, 11:17 | Re: Parser Tool |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| A little update: Version 1.1 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 |
| | | 2011-04-16, 11:26 | Re: Parser Tool |
---|
Vsio Xutix Xox
Posts : 2377 Thanked : 18 Engine : Multi-Engine User Skill : Advanced Type : Developer
| | | | 2011-04-16, 12:32 | Re: Parser Tool |
---|
funkyee Newbie
Posts : 61 Thanked : 0 Engine : RMVX Skill : Intermediate Type : Writer
| 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?? |
| | | 2011-04-16, 12:38 | Re: Parser Tool |
---|
Vsio Xutix Xox
Posts : 2377 Thanked : 18 Engine : Multi-Engine User Skill : Advanced Type : Developer
| Btw, pas aku coba, kok langsung dianggap malware ya? |
| | | 2011-04-16, 12:49 | Re: Parser Tool |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| | | | 2011-04-16, 12:51 | Re: Parser Tool |
---|
Vsio Xutix Xox
Posts : 2377 Thanked : 18 Engine : Multi-Engine User Skill : Advanced Type : Developer
| Btw, request lagi
Minta PDA yang bisa compiling.
Speknya bisa dilihat di soal tubes I TBO. |
| | | 2011-04-19, 14:04 | Re: Parser Tool |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| Phew~ setelah sekian lama susah payahnya bikin parser sesuai request Vsio buat tugas TBO... 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 |
| | | 2011-04-19, 14:06 | Re: Parser Tool |
---|
Vsio Xutix Xox
Posts : 2377 Thanked : 18 Engine : Multi-Engine User Skill : Advanced Type : Developer
| Walah, ini sampai dikonversi semua dari bahasa C ke Ruby nih?
Mantap lah!
*Thanks Reputation Point sent* |
| | | 2011-04-19, 16:12 | Re: Parser Tool |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| Sori, ada yang lupa 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:
Sebuah parser untuk mengenali apakah sintaks sebuah program sederhana itu benar atau tidak. Aplikasi akan membuka file yang berisi sintaks program dan kemudian memeriksa apakah semua sintaks pada program tersebut valid atau tidak. Jika tidak valid maka aplikasi akan mengeluarkan informasi baris yang menyebabkan ketidakvalidan sintaks program.
Program sederhana yang dimaksud hanya memiliki algoritma, tanpa pernyataan kamus atau judul program. Tipe variabel hanya integer dan operasi terhadap variabel hanya berupa operasi matematika untuk integer. Sintaks algoritma yang dimiliki program terdiri atas: 1. Begin – end sebagai batas awal dan akhir dari program 2. If – then {begin end} 3. If – then – {begin end} – else {begin end} 4. Repeat – until 5. While – do {begin end} 6. Kondisi (dengan operator: <, >, <=, >=, =, <>) Contoh: a >= b 7. Assignment (hanya operasi matematika untuk integer yaitu +, -, *) Contoh: a = b + c 8. Input (variabel) Contoh: input(z) 9. Output (variabel) atau Output (operasi matematika) Contoh: output(z) 10. Komentar yang ditandai dengan kurung buka (“{“) dan kurung tutup (“}”)
Keterangan selengkapnya: 1. Apabila terdapat sintaks error, maka program hanya memunculkan line keberapa yang error dan cukup hanya menelusuri 1 error saja. Jika program bisa mengeluarkan pesan error (error pada line berapa dan kesalahannya apa) dianggap bonus. 2. Jika program bisa menangani letak komentar seperti i{komentar}f (a < b), maka dianggap bonus. 3. Nama variabel tidak boleh diawali angka serta tidak boleh merupakan kata kunci yang telah didefinisikan pada bahasa (seperti if, while) 4. Bahasa case insensitive. 5. Untuk kata kunci seperti if (...), while (...), input (...), output (...), wajib menggunakan spasi. Contoh : input (a), bukan input(a). 6. Conditional statement wajib menggunakan kurung. Contoh : if (a<b), bukan if a=b. 7. Assignment variabel bisa berupa angka. Contoh : a = 5. 8. Assignment variabel juga bisa berupa ekspresi aritmatika yang panjang seperti a=(1+2)*(4-3) 9. Setelah program berakhir (diakhiri dengan end yang berasal dari begin penanda awal program) tidak boleh terdapat sampah. Contoh yang salah: Begin Input(z) end (ini adalah sampah) 10. Untuk tipe integer yang sesuai dengan spesifikasi integer (hanya mampu mencakup integer 32 bit) dianggap bonus. Integer yang dimaksud adalah signed integer. 11. Tokenisasi statement hanya boleh dalam 1 baris. Contoh salah : a = b. 12. Satu baris hanya boleh berisi satu perintah Contoh salah: If (a=5) then begin a=a+1 output (a) end 13. Indentasi tab tidak diperhatikan. 14. Tidak ada pengecekan apakah suatu variabel sudah didefinisikan sebelumnya atau belum apabila variabel tersebut akan digunakan.
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:
Begin input ( z ) { menerima masukan z berupa nilai integer } while ( z < 999 ) do begin if ( z < 10 ) then begin a = z * 2 output ( a ) end else begin output ( z * 10 ) end input ( z ) end end
|
| | | 2011-04-20, 15:59 | Re: Parser Tool |
---|
Vsio Xutix Xox
Posts : 2377 Thanked : 18 Engine : Multi-Engine User Skill : Advanced Type : Developer
| Akhirnya yang dalam versi bahasa pemrograman C dipost di sini
*siapin * |
| | | 2011-04-20, 16:02 | Re: Parser Tool |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| Ini dia parser request-nya Vsio dlm versi bahasa C-nya (yg buat tugas) Cara pakenya? tinggal masukin nama file yg ingin divalidasi dengan parser ini. Link: http://ifile.it/u57oxcm/mpda.rar
Enjoy |
| | | 2011-04-20, 20:41 | Re: Parser Tool |
---|
Vsio Xutix Xox
Posts : 2377 Thanked : 18 Engine : Multi-Engine User Skill : Advanced Type : Developer
| Asiklah tadi demo tubes sukses
Compiler algoritma sederhana sukses di bahasa C dan Ruby
*Thanks Reputation Point sent* |
| | | | Re: Parser Tool |
---|
Sponsored content
| | | | Similar topics | |
|
Similar topics | |
| |
Halaman 1 dari 1 | |
| Permissions in this forum: | Anda tidak dapat menjawab topik
| |
| |
Latest 10 Topics | [Web Novel] Gloria Infidelis 2016-11-17, 21:27 by LightNightKnight
[Announcement] Forum baru untuk RMID 2016-08-25, 16:39 by TheoAllen
Where I'm Wrong ? 2016-07-24, 16:10 by ReydVires
flakeheartnet's Resources part III 2016-07-08, 14:30 by flakeheartnet
Keira's Art Warehouse 2016-06-28, 19:27 by KeiraBlaze
Theo Core Time System + Bingung 2016-06-27, 16:24 by Lockin
Error Script, Maybe ? 2016-06-27, 16:20 by Lockin
Nusaimoe @ RMID Lounge 2016-06-21, 05:02 by Jihad Bagas
Call Random Battle 2016-06-15, 17:04 by Lockin
Flakeheartnet Resources Part II [come back gift] 2016-06-07, 15:51 by flakeheartnet
|
Statistics
|
Members: [ 4947 ]
Topics: [ 8258 ]
Posts: [ 112606 ]
Newest member: [ https://rmid.forumotion.net/u4968 ]
|
|
|
|
|
|