Minggu, 27 Januari 2013

AP - Sintaksis ( UAS )

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 :
  1. UG ( Unrestricted Grammer )                     = tidak ada batasan pada aturan produksi
  2. CSG ( Context Sensitive Grammer )         = panjang string ruas kiri harus <= dengan ruas kanan
  3. CFG ( Context Free Grammer )                  = ruas kiri adalah 1 variable, yaitu simbol non terminal
  4. 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 .

This entry was posted in

0 komentar:

Posting Komentar