PEMBUATAN KOMPILER DENGAN METODE PARSING BERUPA RECURSIVE DESCENT PARSER

PEMBUATAN KOMPILER DENGAN METODE PARSING BERUPA RECURSIVE DESCENT PARSER Drs. Tedy Setiadi, M.T. dan Basit Adhi Prabowo Program Studi Teknik Infomatika Universitas Ahmad Dahlan Jl. Prof. Soepomo, S.H., Janturan, Yogyakarta Abstrak Komputer merupakan sebuah mesin digital yang diciptakan oleh manusia untuk melakukan proses-proses intelektual yang dapat dilakukan secara mekanis oleh manusia. Manusia dapat melakukan interaksi secara efektif dengan menggunakan media bahasa. Manusia melakukan komunikasi dengan bahasa manusia, sedangkan komputer hanya menerima dan memahami bahasa mesin. Bahasa pemrograman menjembatani komunikasi antara manusia dengan komputer. Alat yang digunakan sebagai sarana untuk melakukan komunikasi dengan bahasa pemrograman adalah kompiler. Kompiler akan memeriksa sintaks dari kode sumber dengan parser, kemudian kode sumber diterjemahkan ke dalam bahasa mesin. Recursive descent parser adalah parser dengan metode top-down yang memiliki ciri secara rekursif menurunkan semua variabel dari awal sampai bertemu terminal dan tidak pernah mengambil token secara mundur (no back track). Recursive descent parser yang digunakan adalah LL(1), yaitu parser yang tidak mengandung rekursi kiri. Kata kunci:

kompiler, recursive descent parser, bahasa pemrograman

Pendahuluan Manusia dapat melakukan interaksi secara efektif dengan menggunakan media bahasa. Bahasa memungkinkan penyampaian gagasan dan pemikiran. Bahasa pemrograman adalah bahasa yang dibuat agar manusia dapat melakukan komunikasi dengan mesin. Bahasa pemrograman menjembatani antara pemikiran manusia yang sering tidak terstruktur dengan mesin yang memerlukan kepastian untuk melakukan eksekusi. Bahasa pemrograman harus memiliki konstruksi yang dapat merefleksikan gagasan dan independen dari komputer yang dipergunakan. Bahasa pemrograman seperti ini sering disebut dengan bahasa tingkat tinggi. Bahasa tingkat tinggi lebih mudah untuk dipelajari karena bahasa yang digunakan lebih dekat dengan bahasa manusia dan tidak membutuhkan latar belakang mengenai perangkat keras. Gagasan untuk perancangan bahasa pemrograman bisa berasal dari bahasa alami (natural language), matematika, dan bahasa pemrograman yang sudah ada. Konstruksi yang diturunkan dari bahasa alami berguna untuk kejelasan dan kemudahan pembacaan. Sebuah instruksi akan mengerjakan mirip dengan arti sesungguhnya dari instruksi tersebut dalam bahasa alami. Matematika telah banyak digunakan untuk aturan-aturan yang terdapat pada bahasa pemrograman, khususnya untuk ekspresi aritmatika dan notasi matematika. Notasi digunakan untuk mempersingkat kode program dan mempermudah pemrogram dalam pembuatan dan pembacaan ulang program. Bahasa pemrograman yang sudah ada dapat digunakan sebagai patokan dalam perancangan bahasa pemrograman. Namun, diperlukan ketelitian pada waktu menggunakannya karena bahasa yang sudah ada tersebut bisa saja memiliki suatu kesalahan yang cukup fatal. Bahasa yang digunakan sebagai referensi dapat juga lebih dari satu bahasa pemrograman karena setiap bahasa pemrograman memiliki kelebihan dan kekurangannya masing-masing. Pengembangan sebuah kompilator merupakan pekerjaan yang tidak sederhana. Sebuah bahasa yang terlalu kompleks akan menyulitkan pembuatan kompilator untuk bahasa tersebut. Kebanyakan pemrogram menginginkan bahasa yang sederhana, tetapi kesederhanaan dapat pula berarti kekurangan di sisi lainnya. Kesederhanaan tidak dapat dicapai dengan keterbatasan struktur dan tidak dapat dicapai dengan generalitas

1

yang tidak terbatas. Kesederhanaan dapat dicapai dengan melakukan pembatasan tujuan, perhatian pada keterbacaan, pendefinisian yang baik, dan konsep yang sederhana. Sintaks adalah susunan kalimat dan grammar[3]. Sintaks dianalisis oleh suatu mesin yang disebut dengan parser. Parser bertugas menganalisis token yang dihasilkan pada proses scan sesuai dengan grammar. Recursive Descent Parser (RDP) adalah salah satu cara untuk mengaplikasikan bahasa bebas konteks untuk melakukan analisis sintaksis suatu source code. Ciri dari RDP yang menonjol adalah secara rekursif menurunkan semua variabel dari awal sampai bertemu terminal dan tidak pernah mengambil token secara mundur (no back track). Ciri lain dari RDP adalah sangat bergantung pada algoritma scan dalam mengambil token. RDP juga dapat dikombinasikan dengan Predictive Parser. Predictive Parser (PP) adalah parser yang menggunakan prediksi untuk mengoptimalkan kerja dari parser. Parser model ini juga akan mengecilkan terjadinya rekursi kiri atau salah interpretasi. Prinsip dari predictive parser adalah mengelompokkan produksi sesuai dengan pola yang ada sehingga aturan produksi tertentu sudah diprediksikan penurunannya. Tinjauan Pustaka I Made Wiryana[4] menyebutkan bahwa teknik kompilasi telah lama diberikan di lingkungan pendidikan tinggi bidang komputer di Indonesia. Pembahasan dalam mata kuliah ini biasanya berkisar pada teori otomata, teori kompilasi, teori grammar. Praktek teknik kompilasi pun telah diberikan di lingkungan laboratorium, walau biasanya masih terbatas pada demonstrasi hal teori, ataupun sekedar pengen alan kompiler yang ada atau banyak digunakan. Beberapa universitas telah mulai memperkenalkan penggunaan perangkat pembangun kompiler. Firrar Udirartatmo[3] mengemukakan bahwa dalam lingkungan pemrograman komputer, bahasa pemrograman bertindak sebagai sarana komunikasi antara manusia dan permasalahannya dengan komputer yang dipakai untuk membantu memperoleh penyelesaian. Suatu solusi untuk suatu masalah akan menjadi lebih mudah bila bahasa pemrograman yang digunakan lebih dekat dengan permasalahan tersebut. Teori Sebuah kompiler umumnya memiliki dua tugas pokok, yaitu fungsi analisis dan fungsi sintesis. Tugas dari fungsi analisis adalah melakukan dekomposisi program sumber menjadi bagian-bagian dasarnya, sedangkan fungsi sintesis memiliki tugas melakukan pembangkitan dan optimasi program objek. Model sebuah kompiler dapat dilihat pada gambar 1. Source Code

Object Code

ANALYSIS Lexical Analyzer (Scanner)

Syntactic Analyzer (Parser)

SYNTHESIS Semantic Analyzer Intermediate code Generator

Intermediate code

Code Generator

Code Optimizer

Symbol Table

Gambar 1. Model kompiler Program sumber merupakan deretan simbol-simbol yang memuat konstruksi bahasa yang mendasar seperti nama variabel, label, konstanta, keyword, dan operator. Scanner membaca setiap karakter kode sumber dan

2

memisahkan teks ke dalam token-token. Token digunakan oleh parser untuk menganalisis sintaks sesuai dengan grammar yang telah dirancang. Selanjutnya, semantic analyzer menentukan maksud dari program sumber dan menentukan aksi yang harus dilakukan. Analisis semantik bisa menghasilkan intermediate form dari program sumber yang berguna untuk memudahkan dalam pembuatan code generator dan code optimizer. Keluaran dari semantic analyzer diberikan ke code generator untuk ditranslasikan ke dalam bahasa assembly atau ke dalam bahasa mesin. Keluaran dari code generator diberikan ke code optimizer. Proses ini bertujuan untuk menghasilkan program objek yang lebih efisien. Di dalam perancangan sebuah parser dikenal dua buah notasi, yaitu BNF dan diagram sintaks. BNF adalah notasi yang dapat digunakan untuk memberikan definisi formal dari bahasa pemrograman. Diagram sintaks memberikan gambaran yang jelas mengenai BNF yang telah dirancang dalam bentuk grafis. Diagram sintaks menggunakan simbol pada gambar 2.

: Simbol variabel : Simbol terminal Gambar 2. Simbol yang digunakan dalam diagram sintaks Di dalam proses kompilasi, analisis sintaksis menggunakan parser merupakan bagian front end dari model kompilasi. Karakteristik dari parser top-down hanya membutuhkan beberapa baris untuk mengakomodasi bahasa yang telah dirancang dan sangat cocok dengan BNF, simbol variabel direpresentasikan dengan sebuah prosedur, misalnya: <exp> ::= { T_OR } ::= { T_AND } dapat diubah ke dalam algoritma: procedure exp() procedure bool_term() bool_term() bool_not_fact() while CToken = T_OR do while CToken = T_AND do scan() scan() bool_term() bool_not_fact() endwhile endwhile endprocedure endprocedure Penurunan secara rekursif dapat terlihat dari kedua algoritma. Prosedur bool_term dipanggil oleh prosedur exp. Di dalam prosedur bool_term juga terjadi pemanggilan prosedur, yaitu prosedur bool_not_fact. Pemanggilan prosedur tersebut terjadi berulang-ulang (rekursif) dan terjadi penurunan (descent). Rekursi (penurunan) terjadi sampai menemui simbol terminal (token). Masalah utama dalam penggunaan rekursi adalah rekursi yang tidak berhenti. Oleh karena itu, diperlukan kehati-hatian dalam pemakaian rekursi. Predictive parser diperlukan untuk menekan atau menghilangkan kemungkinan terjadinya hal tersebut. Pembahasan Tahap-tahap penelitian yang dilakukan dalam penelitian ini adalah: 1. Pendefinisian Kebutuhan Pendefinisian kebutuhan meliputi penentuan perangkat lunak, penentuan perangkat keras yang sesuai dengan perangkat lunak dan aplikasi yang hendak dibuat serta data-data yang diperlukan untuk membuat aplikasi. Aplikasi ini hanya membutuhkan 3 elemen dari elemen-elemen kompiler yang ada, yaitu parser, scanner dan code generator. Hal ini bisa dilakukan karena bahasa yang dirancang tidak memerlukan deklarasi variabel (memerlukan tabel informasi) dan optimasi kode (memerlukan kode antara), sedangkan analisis semantik sudah ada secara implisit di dalam parser. 2.

Perancangan Perancangan merupakan tahap awal dari suatu aplikasi program untuk menghasilkan sistem yang baik. Perancangan dibuat sebagai landasan implementasi untuk mempermudah pembuatan aplikasi. Perancangan meliputi perancangan parser (BNF dan diagram sintaks), perancangan scanner (FA) dan desain aplikasi.

3

a.

Perancangan Parser menggunakan BNF dan Diagram Sintaks Kode sumber pada kompiler memerlukan BNF dan diagram sintaks agar pembuat program mudah dalam membuat program. Adapun beberapa rancangan BNF dari kompiler yang dibuat adalah sebagai berikut: <simple_exp> ::= { } ::= T_ADD | T_SUB ::= <signed_fact> { <mul_operator> <signed_fact> } <signed fact> ::= | <mul_operator> ::= T_MUL | T_DIV ::= T_LPARENT <exp> T_RPARENT | T_NUMERIC di mana: T_ADD = ’+’ T_SUB = ’-‘ T_MUL = ’*’ T_DIV = ’/‘ T_LPARENT = ’(‘ T_RPARENT = ’)’ T_ANGKA = ’0’..’9’ sedangkan beberapa rancangan berupa diagram sintaks dari kompiler yang dibuat dapat dilihat pada gambar 3, 4 dan 5.

Gambar 3. Diagram sintaks dari <simple_exp>

Gambar 4. Diagram sintaks dari

Gambar 5. Diagram sintaks dari b.

Perancangan Scanner menggunakan FA Dalam memeriksa sintaks dari kode sumber, parser membutuhkan bantuan scanner untuk memberikan token dari sintaks. Berdasarkan BNF dan diagram sintaks yang telah dibuat, maka dapat dirancang sebuah scanner dengan rancangan seperti pada gambar 6.

4

T_ADD

+

T_SUB

T_MUL

* q0

/

)

T_DIV

(

T_LPARENT

T_RPARENT

0..9 T_TAMBAH

Gambar 6. Rancangan scanner berupa Finite Automata

3.

Implementasi a. Scanner Berikut ini adalah implementasi dari FA Scanner: Option Explicit 'inisialisasi token Enum Token T_NUMERIC = 0 T_ADD T_SUB T_MUL T_DIV T_RPARENT T_LPARENT T_EOF T_UNKNOWN End Enum 'inisialisasi Const TAB_ = 9 Const LINEFEED_ = 10 Const CARRIAGE_RETURN_ = 13 Const SPACE_ = 32 Const EOF_SIGN = "#" Private keySymbol() As Variant Dim lst As ListItem Dim CTokenType As String Sub Reset() 'reset posisi pita ke posisi awal Index = 0

5

LineNumber = 1 CC = "" BOF = True EOF = True ReDim errorTrap(0) End Sub Sub getCh() 'pita maju satu karakter If CC <> EOF_SIGN Then Index = Index + 1 CC = Mid(theRtf.Text, Index, 1) If CC <> EOF_SIGN Then EOF = False Else EOF = True Else EOF = True End If End Sub Sub Initialize(ByRef Rtb As Object) ‘inisialisasi awal Set theRtf = Rtb isAnyError = False Reset If Len(Rtb) <> 0 Then EOF = False End Sub Sub skipComment() ‘mengabaikan komentar If CC = "{" Then Do getCh Loop Until CC = "}" Or EOF If Not EOF Then getCh Scan End If End If End Sub Sub Scan() 'kode scanner Dim indexKey As Integer Dim isAllow As Boolean Identifier = "" If BOF Then getCh BOF = False End If While Not EOF Select Case CC Case Chr(TAB_), Chr(LINEFEED_), Chr(SPACE_): getCh Case Chr(CARRIAGE_RETURN_) getCh LineNumber = LineNumber + 1 Case "#" CToken = T_EOF Case "0" To "9" Do Select Case CC Case "0" To "9"

6

isAllow = True Identifier = Identifier & CC getCh Case Else: isAllow = False End Select Loop Until Not isAllow Or EOF CToken = T_NUMERIC CTokenType = "numerik" GoTo addToken Case "+" applyToken T_ADD, "operator penjumlahan" getCh GoTo addToken Case "-" applyToken T_SUB, "operator penjumlahan" getCh GoTo addToken Case "*" applyToken T_MUL, "operator perkalian" getCh GoTo addToken Case "/" applyToken T_DIV, "operator perkalian" getCh GoTo addToken Case "(" applyToken T_LPARENT, "delimiter" getCh GoTo addToken Case ")" applyToken T_RPARENT, "delimiter" getCh GoTo addToken Case "{" skipComment Exit Sub Case "}" setError 2 getCh Scan Exit Sub Case Else setError 1 applyToken T_UNKNOWN, "tidak diketahui" getCh GoTo addToken End Select Wend CToken = T_EOF Exit Sub addToken: With frmUtama.ListView3 No = No + 1 Set lst = .ListItems.Add(, , No) lst.SubItems(1) = CTokenType lst.SubItems(2) = Identifier

7

End With End Sub Sub applyToken(ByVal theToken As Token, kindOfToken As String) ‘memasukkan informasi tentang token ke dalam tabel simbol CToken = theToken CTokenType = kindOfToken Identifier = CC End Sub b.

Parser dan object code Pembuatan object code dalam bentuk bahasa assembly disisipkan ke dalam implementasi notasi BNF untuk mempermudah pembuatan program . Object code yang disisipkan di tandai dengan pemanggilan sub “writeAssemblyCode”. Berikut ini adalah implementasi dari BNF yang telah dibuat dan pembuatan object code: Option Explicit Sub simple_exp() '<simple_exp> ::= { } term While add_operator writeAssemblyCode "PUSH AX" Select Case CToken Case T_ADD Scan term writeAssemblyCode "POP tempAX" & gantiBaris & "ADD AX, tempAX" Case T_SUB Scan term writeAssemblyCode "POP tempAX" & gantiBaris & "balikAX2tempAX" & gantiBaris & "SUB AX, tempAX" End Select Wend End Sub Function add_operator() As Boolean ' ::= T_ADD | T_SUB If CToken = T_ADD Or CToken = T_SUB Then add_operator = True Else add_operator = False End Function Sub term() ' ::= <signed_fact> { <mul_operator> <signed_fact> } signed_fact While mul_operator writeAssemblyCode "PUSH AX" Select Case CToken Case T_MUL Scan signed_fact writeAssemblyCode "POP tempAX" & gantiBaris & "MUL tempAX" Case T_DIV Scan signed_fact writeAssemblyCode "POP tempAX" & gantiBaris & "balikAX2tempAX" & gantiBaris & "DIV tempAX" End Select Wend

8

End Sub Sub signed_fact() '<signed fact> ::= | If add_operator Then If CToken = T_SUB Then Scan fact writeAssemblyCode "negatifAX" Else fact End If End Sub Function mul_operator() As Boolean '<mul_operator> ::= T_MUL | T_DIV If CToken = T_MUL Or CToken = T_DIV Then mul_operator = True Else mul_operator = False End Function Sub fact() ' ::= T_LPARENT <exp> T_RPARENT | T_NUMERIC If CToken = T_LPARENT Then Scan simple_exp Match T_RPARENT, 101 Else If Not (CToken = T_NUMERIC) Then setError 102 Else writeAssemblyCode "MOV AX, " & Identifier Scan End If End If End Sub Sub startParsing(ByRef Rtb As Object) 'prosedur awal untuk memulai proses parsing Initialize Rtb writeAssemblyCode "negatifAX MACRO ;mengalikan AX dengan -1" & gantiBaris(True) & "MOV BX, -1" & gantiBaris & "MUL BX" & gantiBaris & "ENDM" & gantiBaris(False) writeAssemblyCode " ;start definisi program exe" & gantiBaris & ".MODEL SMALL" & gantiBaris & ".STACK 200h" & gantiBaris & ".DATA" & gantiBaris & ".CODE" & gantiBaris & "program:" & gantiBaris & "MOV AX, CS ;segmen data" & gantiBaris & "MOV DS, AX ;pada exe DS tak otomatis terinisialisasi" & gantiBaris & " ;end definisi program exe" & gantiBaris & "JMP programUtama" & gantiBaris & " ;start deklarasi variabel serbaguna" & gantiBaris & "tempAX DW ?" & gantiBaris & "temp DW ?" & gantiBaris & "temporary DW ?" & gantiBaris & "lastFor DW ?" & gantiBaris & "T_ENTER EQU 0Dh ; konstanta karakter <Enter>" & gantiBaris & "Buffer DB 30,?,30 DUP(?)" & gantiBaris & "true_str DB 'true'" & gantiBaris & "false_str DB 'false'" & gantiBaris & " ;end deklarasi variabel serbaguna" & gantiBaris writeAssemblyCode "programUtama:" Scan simple_exp writeAssemblyCode "end_program:" & gantiBaris & "MOV AX, 4C00h ;Servis kembali ke OS" & gantiBaris & "INT 21h" & gantiBaris & "END program" End Sub Sub writeAssemblyCode(theCode As String) 'menulis string ke dalam richTextBox sehingga kode assembly langsung dapat dilihat frmUtama.RichTextBox2.Text = frmUtama.RichTextBox2.Text & theCode & gantiBaris End Sub Sub Match(theToken As Token, errNumIfNotMatch As Byte)

9

'memeriksa token saat ini If CToken = theToken Then Scan Else setError errNumIfNotMatch End Sub Function gantiBaris(Optional isPL As Variant) As String 'memberi nomor baris pada kode assembly sekaligus ganti baris barisAssembly = barisAssembly + 1 If Not IsMissing(isPL) Then If isPL Then isPrcLn = True procedureLine = 0 Else isPrcLn = False End If End If gantiBaris = vbTab & " ;; " & barisAssembly If isPrcLn Then procedureLine = procedureLine + 1 gantiBaris = gantiBaris & " : " & procedureLine End If gantiBaris = gantiBaris & vbCrLf End Function c.

Tampilan Program Pada program ini terdapat 3 bagian yang berisi teks, yaitu source code (tempat untuk mengetikkan baris program), tabel informasi dan assembly code. Program ini akan menghasilkan sebuah file aplikasi (*.exe) jika baris program sukses dikompilasi seperti pada gambar 7 dan program ini akan menghasilkan pesan kesalahan jika baris program tidak sukses dikompilasi seperti pada gambar 8.

Gambar 7. Tampilan program sewaktu kode sumber sukses dikompilasi

10

Untuk menghasilkan sebuah file aplikasi diperlukan TASM (Turbo Assembly). Adapun kode untuk memanggil TASM adalah sebagai berikut: Private Sub Command2_Click() Dim dTaskID As Double, path As String, file As String RichTextBox2.SaveFile App.path & "\tempCode.asm", rtfText path = Chr(34) & App.path & "\runtasm.bat" & Chr(34) dTaskID = Shell(path, vbNormalFocus) enableExecute False End Sub dimana file “runtasm.bat” dibuat melalui sub “buatFile” berikut ini: Sub buatFile() Dim nofile As Integer nofile = FreeFile() If Exists(App.path & "\runtasm.bat") Then Kill App.path & "\runtasm.bat" Open App.path & "\runtasm.bat" For Output As #nofile Print #nofile, Chr(34) & App.path & "\tasm" & Chr(34) & " tempCode.asm" Print #nofile, "tlink /t tempCode" Print #nofile, "tlink tempCode" Print #nofile, "del *.map" Print #nofile, "del *.obj" Close #nofile nofile = FreeFile() If Exists(App.path & "\show.bat") Then Kill App.path & "\show.bat" Open App.path & "\show.bat" For Output As #nofile Print #nofile, Chr(34) & "C:\WINDOWS\TCG_HELP\%1" & Chr(34) Close #nofile End Sub

Gambar 8. Tampilan program sewaktu kode sumber tidak sukses dikompilasi

11

Kesimpulan 1. Pembuatan kompiler merupakan masalah yang kompleks karena di dalam kompiler sendiri terdapat beberapa proses yang memiliki karakteristik dan masalah masing-masing. 2. Recursive descent parser mudah untuk diimplementasikan tetapi memerlukan kehati-hatian dalam perancangannya Saran 1. Grammar dari bahasa pemrograman dapat diperluas dan ditambah dengan struktur yang lebih kompleks, seperti: penambahan prosedur dan fungsi dengan parameter, floating point, string, array, I/O file, kontrol pemilihan case, tipe data user defined, struct, class dan sebagainya 2. Menambahkan error recovery dan error repair. 3. Menambahkan optimasi sebelum diubah ke dalam object code atau optimasi object code yang dihasilkan. Daftar Pustaka [1] Crenshaw, Jack W., Ph.D., 1988, LET'S BUILD A COMPILER!, http://www.etekchalmers.se/~e8johan/compiler/ [2] Prabowo, Basit Adhi, 2006, Pembuatan Kompiler dengan Metode Recursive Descent Parser, Skripsi S1, Universitas Ahmad Dahlan Yogyakarta [3] Utdirartatmo, Firrar, 2005, Teknik Kompilasi, Graha Ilmu, Yogyakarta [4] Wiryana, I Made, Compiler Construction, http://www.wiryana.pandu.org/

12