AP - Sintaksis ( UAS )

Sintaksis

Bahasa mesin adalah bentuk terendah pada komputer. Agar komputer mengerti bahasa kita kita membutuhkan :

• Interpreter
• Compiler

Contoh : cobol , Pascal, Fortran, dll .

Sintaks

Sintaks merupakan kumpulan aturan yang mendefinisikan suatu bentuk bahasa . ada 2 aturan sintaks dari bahasa pemograman :

• Aturan Lexical / Lexical Analysis ( Scanner )
• Aturan Sintaksis / Sintax Alayzer ( Parser )

Konsep dan Notasi Bahasa

Ø  Alfabet : himpunan yang tidak kosong ( hampa ) dari simbol .

Contoh alfabet pada Basic : 26 huruf besar, 26 huruf kecil, 10 angka, dan simbol khusus .

Ø  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 menjadi 4 yang dikenal sebagai 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, sp = subject phrase, N = noun, vp = verb phrase, Np = noun phrase

S -> SpVp             Vp -> Vo              Np ->AN

Sp -> AN              o -> Np    

            

Hirarki Chomsky

Tingkatan dari 0 - 3 :

0. UG ( Unrestricted Grammer )                     = tidak ada batasan pada aturan produksi
1. CSG ( Context Sensitive Grammer )         = panjang string ruas kiri harus <= dengan ruas kanan
2. CFG ( Context Free Grammer )                  = ruas kiri adalah 1 variable, yaitu simbol non terminal
3. RG ( Regular Grammer )                                                = ruas kanan hanya memiliki maksimal satu simbol non

   terminal .

Aturan Produksi

• Aturan produksi dinyatakan dalam bentuk α → β, α menghasilkan atau menurunkan β .
• α symbol – symbol untuk ruas kiri, β symbol symbol untuk ruas kanan
• symbol berupa terminal dan nonterminal
• symbol nonteriman disymbolkan huruf besar (A,B,C dst ) dan symbol terminal di symbolkan huruf kecil ( a,b,c, dst )

G = ( VN, VT , S, Q )

sebuah grammer didefinisikan dengan 4 tupel :

               

VT dan VN           : himpunan symbol terminal dan symbol nonterminal

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

Q                             : subhimpunan hinggal yang tidak kurang dari relasi

Notasi BNF ( Backus – Nour Form )

Aturan produksi dapat dinyatakan dengan notasi BNF

BNF menggunakan abstraksi untuk struktur sintaks

Aturan Lexical atau Lecixal Analysis ( Snanner )

Tugas – tugas aturan lexical :

• mengidentifikasi semua besaran yang membangun suatu bahasa
• mentransformasikan ke token token ( symbol terminal dari teori bahasa automata )
• menentukan jenis dari token token
• menangani kesalahan
• menangani tabel symbol
• scanner didesain untuk mengenali keyword, operator, identifier

token seperti konstanta, nama variable, reserved word, dan operator .

contoh :

Statement : Fahrenheit := 32 + celcius * 1.8

Maka akan diterjemahkan kedalam token token sebagai berikut :

Identifier                             → Fahrenheit

Operator                             → :=

Integer                                 → 32

Operator penjumlah      → +

Identifier                             → celcius

Operator perkalian          → *

Real / float                          → 1.8

Syntaz Analyzer ( Parser )

• bertugas memeriksa kebenaran dan urutan dari token token yang terbentuk oleh Lexcial Analysis
• Pengelompokan token token kedalam class syntax sebagai prosedur, statement, dan expression
• Grammar dipakai oleh sintax analyzer untuk menentukan stuktur dari program sumber
• Proses pendektesian disebut dengan parsing, maka sering disebut dengan parser
• Pohon sintaks yang dihasilkan digunakan untuk semantic analyzer yg bertugas untuk menentukan maksud dari program sumber .

Parsing atau Proses penurunan

Dapat dilakukan dengan cara :

• Penurunan terkiri            : symbol variabel paling kiri diturunkan dahulu
• Penurunan terkanan      : symbol variabel paling kanan diturunkan dahulu

Contoh :

 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

Ada 3 hal yang perlu diperhatikan :

1. Waktu eksekusi
2. Penanganan kesalahan
3. Penanganan kode

Parsing digolongkan menjadi :

v  Top Down

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

Metode ini meliputi :

o   Backtrack / back up : Brute Force

§  Memilih produksi sendiri mulai dari kiri

§  Meng-expand symbol nonterminal sampai pada symbol terminal

§  Bila terjadi kesalahan maka dilakukan back track

§  Algoritma ini membuat pohon parsing secara topdown

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

v  Recursive Descent Parser

o   Salah satu cara untuk mengaplikasikan bahasa context free

o   Symbol terminal maupun symbol vaiabelnya sudah bukan sebuah karakter

o   Besar leksikal sebagai symbol terminalnya, besaran syntax sebagai symbol variablenya / non terminalnya

o   Dengan cara penurunan secara rekursif untuk semua variabel dari awal sampai ketemu terminal

o   Tidak pernah mengambil token secara mundur ( back tracking )

o   Beda dengan turing yang selalu maju dan mundur dalam melakukan parsing .

v  Botom Up

Memulai pada daun dan bergerak ke atas menuju akar dimulai dengan diberikannya sebuah untai, kemudian kita mencoba untuk mencapai symbol start Grammar .