Pembuatan Compiler dengan Metode Recursive Descent Parser

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 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 pengenalan 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

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 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.

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> ::= <bool_term> { T_OR <bool_term> }
<bool_term> ::= <bool_not_fact> { T_AND <bool_not_fact> }

dapat diubah ke dalam algoritma:

procedure exp()
bool_term()
while CToken = T_OR do
scan()
bool_term()
endwhile
endprocedure


procedure bool_term()
bool_not_fact()
while CToken = T_AND do
scan()
bool_not_fact()
endwhile
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. Pedefinisian 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.

a. Perancangan Parser menggunakan BNF dan Diagram Sintaks

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> ::= <term> { <add_operator> <term> }
<add_operator> ::= T_ADD | T_SUB
<term> ::= <signed_fact> { <mul_operator> <signed_fact> }
<signed fact> ::= <add_operator> <fact> | <fact>
<mul_operator> ::= T_MUL | T_DIV
<fact> ::= T_LPARENT <exp> T_RPARENT | T_NUMERIC

dimana:

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 <add_operator>

Gambar 5. Diagram sintaks dari <term>

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.

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
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"
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
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> { <add_operator> <term> }
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
'<add_operator> ::= T_ADD | T_SUB
If CToken = T_ADD Or CToken = T_SUB Then add_operator = True Else add_operator = False
End Function


Sub term()
'<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
End Sub


Sub signed_fact()
'<signed fact> ::= <add_operator> <fact> | <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()
'<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)
'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

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

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/