PEMROGRAMAN BAB II (SINTAKSIS)

Bab II

Sintaksis

Bahasa mesin adalah bentuk terendah pada komputer. Kita dapat berhubungan langsung dengan bagian-bagian yang ada didalam komputer seperti bit, register dan sangat primitif. Bahasa mesin tidak lebih dari urutan bit-bit 0 dan 1.

Bagaimana dengan orang yang tidak mengerti bahasa mesin?

Bahasa mesin adalah jenis mesin komputer yang digunakan. Bagaimana jika jenis komputer mengalami perubahan?

Oleh karena itu manusia berusaha menciptakan suatu bahasa yang dapat dimengerti baik oleh manusia maupun oleh komputer, yang disebut dengan bahasa tingkat tinggi. Dari bahasa tingkat tinggi ke bahasa mesin dibutuhkan sesuatu untuk menterjemahkan agar mesin (komputer) mengerti apa yang diinginkan oleh manusia, yaitu :

1. Interpreter
2. Compiler

Contoh : Cobol, Pascal, Fortran, dll

Untuk membuat penterjemah seperti compiler perlu dibuat standar atau tata bahasa atau aturan, seperti manusia berkomunikasi mempunyai tata bahasa agar lawan bicara dapat mengerti yang dibicarakan. Demikian juga untuk menterjemahkan kedalam bahasa mesin (komputer) harus dibuat suatu aturan agar komputer mengerti apa yang diinginkan oleh manusia melalui program yang dibuatnya.

Sintaks

Sintaks merupakan kumpulan aturan yang mendefinisikan suatu bentuk bahasa. Sintaks mendefinisikan bagaimana suatu kata dikombinasikan menjadi suatu statement yang benar sehingga dapat disusun suatu program yang dapat berjalan dengan benar.

Sintaks dari bahasa pemrograman didefinisikan dengan dua kumpulan aturan, yaitu :

• Aturan Lexical /Lexical Analysis (Scanner)
• Aturan Sintaksis / Syntax Analyzer (Parser)

Konsep dan Notasi Bahasa

• Alfabet : himpunan hingga yang tidak kosong (hampa) dari symbol. Symbol anggota dari alfabet dinamakan huruf atau karakter atau token.

Contoh : ∑1 = {a, b, c, .., z}      ∑2 = {α, β, γ, δ}

Contoh alfabet pada Basic : 26 huruf besar, 26 huruf kecil, 10 angka, dan symbol khusus seperti : ‘(‘, ‘)’, ‘.’, ‘+’ dsb

• Bahasa : merupakan himpunan hingga ataupun tak hingga dari kalimat atau kumpulan kalimat.
• Tata Bahasa atau Grammar : sekumpulan dari himpunan variabel-variabel, symbol-symbol terminal, symbol non terminal, symbol awal yang dibatasi oleh aturan-aturan produksi.

• Tahun 1956 – 1959 Noam Chomsky melakukan penggolongan tingkatan dalam bahasa, yaitu menjadi 4 class yang disebut dengan hirarki Chomsky.

• Tahun 1959 Backus memperkenalkan notasi formal baru untuk sintaks bahasa yang lebih spesifik

• Peter Naur (1960) merevisi metode dari sintaks yang sekarang dikenal dengan BNF(Backus Nour Form)

Contoh :

S = sentence, v = verb, o = object, A = article, s = subject phrase, N = noun, vp = verb phrase, Np = noun phrase

S → SpVp    Vp → Vo     Np → AN

Sp → AN     o → Np

Kalimat : The cat ate a mouse

Contoh tata bahasa sederhana :

<program>         →     BEGIN <stat_list> END

<Stat_list>       →     <stat>│ <stat>; <stat_list>

<stat>            →     <var> :=<expression>

<expression>      →     <term> │ <term><op1><expression>

<term>            →     <factor> │<factor><op2><term>

<factor>          →     <var> │ <constant>

<var>             →     A│ B │..│Z

<op1>             →     +│ - │=

<op2>             →     ^│ * │/

<constant>        →     <real_number> │ <integer_part>

<real_number>     →     <integer_part> │ <fraction>

<integer_part>    →     <digit> │ <integer_part> <digit>

<fraction>        →     <digit> │ <digit> <fraction>

<digit>           →     0 │ 1 │ .. │ 9

Contoh :

      Begin

            A := 1;

            B := A + 2

      End.

Hirarki Chomsky

Keterangan Gambar :

• Tipe 0 / Unrestricted : tidak ada batasan pada aturan produksi

Abc → De

• Tipe 1 / Context sensitive : panjang string ruas kiri harus < (lebih kecil) atau = (sama dengan) ruas kanan

Ab → DeF

CD → eF

• Tipe 2 / Context Free Grammar : ruas kiri haruslah tepat satu symbol variabel, yaitu simbol non terminal

B → CDeFg

D → BcDe

• Tipe 3 / Regular : ruas kanan hanya memiliki maksimal satu symbol non terminal dan diletakkan paling kanan sendiri

A → e

A → efg

A → efgH

C → D

Aturan Produksi

• Aturan produksi dnyatakan dalam bentuk α → β, α menghasilkan atau menurunkan β
• α symbol-symbol untuk ruas kiri,  β symbol-symbol untuk ruas kanan
• Symbol-symbol dapat berupa terminal dan non terminal dimana non terminal dapat diturunkan menjadi symbol yang lainnya
• Umumnya symbol terminal disymbolkan dengan huruf kecil (a,b,c, dsb), sedangkan untuk symbol non terminal disymbolkan dengan huruf besar (A,B,C, dsb)
• Contoh aturan produksi :

T → a, T menghasilkan a

E → T │ T + E, E menghasilkan T atau E menghasilkan T + E

Sebuah grammar didefinisikan dengan 4 tupel :

      G = (V_N, V_T, S, Q) dimana

VT dan VN : himpunan symbol terminal dan symbol non terminal

S : suatu elemen tertentu dari VN, yang disebut symbol start

Q : subhimpunan hingga yang tidak kurang dari relasi(V_TυV_N)*(V_TυV_N)* atau secara umum sebuah elemen (α, β) dari Q ditulis sebagai α → β dan disebut produksi.

Dari 4 tingkatan bahasa maka kita akan membahas tentang Context Free Grammar.

Context Free Grammar (CFG) sangat penting didalam penggambaran dan penterjemahan bahasa pemrograman.

Derifasi : proses pembentukan kalimat di grammar

Grammar Context Free merupakan pembentuk bahasa Context Free

Contoh : L (G₃) = {Aⁿbaⁿ │ n > = 1}

Dimana : G₃ = ({S,C}, {a,b}, S, Q), dengan Q adalah produksi

            S → aCa

C → aCa

C → b

Derifasi untuk a³ba³ atau aaabaaa, adalah :

            S → aCa

              → aaCaa

              → aaaCaaa

              → aaabaaa

Notasi BNF (Backus – Nour Form)

Aturan produksi dapat dinyatakan dengan notasi BNF

BNF menggunakan abstraksi untuk struktur sintaks

      ::=   identik dengan symbol →

      │     sama dengan atau

< >   pengapit symbol non terminal

      { }   pengulangan dari 0 sampai n kali

Contoh :

      Aturan Produksi sebagai berikut :   E → T │ T + E │ T – E

                                          T → a

      Notasi BNF              :     E ::= <T> │ <T> + <E> │ <T> - <E>

                                    T ::= a

Tanda untuk non terminal (<>) yang ruas kiri bersifat optional

Fase-fase proses kompilasi adalah sebagai berikut :

Aturan Lexical atau Lexical Analysis (Scanner)

Berhubungan dengan bahasa, sering disebut dengan scanner, bertugas sebelum proses syntax Analyzer dan Intermediate Code dilakukan dimana tugas Lexical Analysis ini mendekomposisi program sumber menjadi bagian-bagian kecil.

Tugas-tugas Aturan Lexical atau Lexical Analysis secara detil adalah :

a. mengidentifikasi semua besaran yang membangun suatu bahasa

b. mentransformasikan ke token-token (symbol terminal dari teori bahasa automata)

c. menentukan jenis dari token-token

d. menangani kesalahan

e. menangani tabel symbol

f. scanner di desain untuk mengenali keyword, operator, identifier

contoh :

Besaran Lexical : (tergantung program)

• Identifier dapat berupa keyword seperti if, else, begin .. end (pada Pascal) , integer (Pascal), int float (pada C)
• Konstanta : besaran yang berupa bilangan bulat (integer), bilangan pecahan(float / real), Boolean (true/false), string, dll
• Operator : operator aritmatika (+, -, *, /), operator logika(< = >)
• Delimiter : berguna bagi pemisah atau pembatas, seperti kurung buka, kurung tutup, titik, koma, titik dua, titik koma, white_space
• White_space : pemisah yang diabaikan oleh program, seperti : enter, spasi, ganti baris dan akhir file

Program sumber merupakan input dari penganalis leksikal ala scanner. Analisis leksikal mempunyai tujuan untuk memisahkan naskah program sumber yang masuk menjadi bagian leksikografis terkecil atau Token seperti konstanta, nama varibel, reserved word dan operator.

Scanner biasanya berinteraksi dengan parser melalui salah satu dari 2 cara berikut. Yang pertama, scanner dapat mengolah program sumber secara terpisah, sebagai satu fasa sebelum Parser mulai bekerja. Kemudian token disimpan dalam sebuah file atau dalam sebuah file besar. Cara kedua melibatkan antara Parser dan Scanner yang saling berinteraksi, scanner dipanggil oleh parser bila token berikut dalam program sumber diperlukan.

Token hasil pekerjaan scanner biasanya disajikan dalam bentuk Bilangan Penyajian internal berupa bilangan bulat (integer) yang unik.

Contoh :

Nama variabel           1     operator perkalian      8

Konstanta               2     operator pembagian      9

Label                   3     tanda baca koma         10

Keyword                 4     tanda baca titik dua    11

Operator penambahan     5     tanda baca titik koma   12

Operator penugasan      6     dan lain-lain

Operator pengurangan    7

Token tersebut disimpan dalam suatu tabel label serta nama variabel akan dimasukkan kedalam tabel identifier, sedangkan konstanta dimasukkan ke tabel konstanta dan suatu token yang tidak berkaitan dengan label (seperti operator) maka lokasinya adalah 0 (nol).

Lexical Analysis, contoh :

Statement : Fahrenheit := 32 + celcius * 1.8

Maka akan diterjemahkan ke dalam token-token sebagai berikut :

Identifier              → Fahrenheit

Operator                → :=

Integer                 → 32

Operator penjumlahan    → +

Identifier              → celcius

Operator perkalian      → *

Real / float            → 1.8

Statement : Jumlah A = A + B

                   GOTO KERJA

Buatlah tabel untuk penyajian Token :

Token       Bilangan Penyajian Internal   Lokasi      Keterangan

Jumlah                  3                   1            Label

  :                     11                  0         Delimiter

  A                     1                   2         Identifier

  =                     6                   0         Assignment

  A                     1                   2         Identifier

  +                     5                   0   Operator Penjumlahan

  B                     1                   3         Identifier

 GOTO                   4                   0        Reserved word

 KERJA                  1                   4         Identifier

Syntax Analyzer (Parser)

• Bertugas memeriksa kebenaran dan urutan dari token-token yang terbentuk oleh Lexical Analysis
• Pengelompokan token-token kedalam class syntax (bentuk sintaks), seperti prosedur, statement dan expression
• Grammar dipakai oleh syntax analyzer untuk menentukan struktur dari program sumber
• Proses pendeteksian (pengenalan token) disebut dengan parsing, maka syntax analyzer sering disebut dengan parser
• Pohon sintaks yang dihasikan digunakan untuk semantic analyzer yang bertugas untuk menentukan maksud dari program sumber, misalnya operator penjumlahan maka semantic analyzer akan mengambil aksi apa yang harus dilakukan

Parsing atau Proses Penurunan

Parsing dari sebuah kalimat adalah konstruksi atau pembentukan pohon sintaks untuk kalimat tersebut.

Parsing dapat dilakukan dengan cara :

• Penurunan terkiri (Leftmost derivation) : symbol variabel yang paling kiri diturunkan (tuntas) dahulu
• Penurunan terkanan (Rightmost derivation) : symbol yang paling kanan diturunkan (tuntas) dahulu

Contoh : ingin dihasilkan string aabbaa dari

        Context free language :     S → aAS │ a

A → SbA │ ba

Penurunan kiri                      Penurunan kanan

S  → aAS                            S  → aAS

   → aSbAS                             → aAa

   → aabAS                             → aSbAa

   → aabbaS                            → aSbbaa

   → aabbaa                            → aabbaa

Metode Parsing

Pada metode parsing ada tiga hal yang perlu diperhatikan, yaitu :

1. waktu eksekusi
2. penanganan kesalahan
3. penanganan kode

Parsing digolongkan menjadi :

1. Top Down

Penelusuran dari root ke leaf atau dari symbol awal ke symbol terminal

Metode ini meliputi :

1. Backtrack / back up : Brute Force

·         Memilih produksi mulai dari kiri

·         Meng-expand symbol non terminal sampai pada symbol terminal

·         Bila terjadi kesalahan (string tidak sesuai) maka dilakukan backtrack

·         Algoritma ini membuat pohon parsing secara top-down, yaitu dengan cara mencoba segala kemungkinan untuk setiap non terminal

Back Up : pengulangan suatu produksi dengan alternatif produksi yang lain, bila produksi yang digunakan tidak sesuai dengan symbol input.

Contoh :

Grammar :   1.    S → aAd

2.       S → aB

3.       A → b

4.       A → c

5.       B → ccd

6.       B → ddc

S, A dan B adalah symbol non terminal dengan S adalah symbol start. Sementara itu a, b, c dan d adalah symbol terminal

Latihan :

Membentuk pohon sintaks bagi untai accd dengan menggunakan metode Brute Force.

tidak sesuai dengan untaitidak sesuai dengan untai accd, maka diperlukan Back Up untuk pilihan produksi A yang lain

Sama seperti diatas hanya Back Up untuk pilihan produksi S karena

produksi A sudah tidak ada pilihan

Namun teknik Parsing Top Down tidak selalu dapat bekerja pada setiap CFG. Misalnya pada CFG yang mengandung variabel bersifat rekursif kiri (mengandung minimal satu non terminal rekursif kiri), maka akan terjadi loop yang tak hingga. Untuk menanganinya maka CFG tersebut harus dihilangkan terlebih dahulu rekursif kirinya. (tidak dibahas)

Contoh rekursif :

      S → Sab │ Sbd

      S → aAc

      A → Ab │ ∑

Parsing : Recursive Descent Parser

Parsing dengan Recursive Descent Parser

• Salah satu cara untuk mengaplikasikan bahasa context free
• Symbol terminal maupun symbol variabelnya sudah bukan sebuah karakter
• Besaran leksikal sebagai symbol terminalnya, besaran syntax sebagai symbol variabelnya / non terminalnya
• Dengan cara penurunan secara rekursif untuk semua variabel dari awal sampai ketemu terminal
• Tidak pernah mengambil token secara mundur (back tracking)
• Beda dengan turing yang selalu maju dan mundur dalam melakukan parsing

Parsing Bottom Up

Teknik Bottom Up adalah dengan memulai pada daun dan bergerak ke atas menuju akar dimulai dengan diberikannya sebuah untai, kemudian kita mencoba untuk mencapai symbol start Grammar.

Latihan 1 :

Diberikan sebuah grammar yang menyajikan operasi aritmatika sederhana meliputi penambahan(+), pengurangan(-), perkalian(*), dan pembagian (/)

Symbol diartikan sebagai suatu nama variabel atau identifier :

V_N = { C, T, F}, V_T = (i, *, /, +, -, (,)}, S = E

Dengan produksi :

F → i       T → T / F         T →  F            E →  E + T

F → (E)     E → T             T →  T * F        E →  E – T

Berikan derifasi untuk ekspresi sebagai berikut :

i + i, i – i / i, i * (i + i), i * i + i

Latihan 2 :

Buatlah pohon sintaks dari kalimat :

• A monkey climbs a tree → gramatikal dan semantik benar
• The banana ate a cat → gramatikal benar, semantik salah

Download disini : Indowebster