Senin, 02 April 2012

Grammar



Suatu kumpulan aturan (production) yang menentukan urut-urutan karakter. Suatu formal grammar adalah grammar biasa yang ditentukan dengan menggunakan notasi yang ketat.
Bahasa Pemrograman ditentukan  2 jenis Grammar :
1. Primary Grammar
Disebut juga phrase-structure grammar, menspesifikasikan bagian utama pada kompilator dan interpreter, yang disebut parser.
Grammar ini menspesifikasikan bagaimana kata-kata dalam bahasa pemrograman dapat tergabung dan membentuk program yang valid secara sintaks.
Parsing adalah istilah pada bahasa yang menggambarkan proses analisis sebuah kalimat bahasa menurut grammarnya.
2. Secondary Grammar 
Umumnya digunakan untuk menspesifikasikan bentuk yang benar, spelling dari kata-kata pada bahasa komputer  à disebut dengan grammar leksikal.
Bagian dari kompilator yang menganalisis kata-kata secara individu pada input program disebut scanner.
Ada dua kelas grammar yang berguna untuk teknologi compiler, yaitu:
(a) EBNF Grammar
EExtended Backus-Naus Form 
Metalanguage: Bahasa yang digunakan untuk mendeskripsikan bahasa lain.
Menggunakan notasi matematis, ::=, <, >, |, *, +, {, }, [, ] disebut Metasymbol.
Suatu bahasa yang dideskripsikan dalam EBNF merupakan suatu kumpulan aturan.
penggunaan simbol dalam EBNF grammar
EBNF grammar
(b) Regular Grammar
Regular Grammar disebut juga Regular Language.

 •Digunakan pada Teori Bahasa Otomata (Mesin abstrack yang menggunakan model matematika, tetapi menggunakan matematika yang benar-benar berbeda dengan matematika klasik dan kalkulus)
Bahasa pemrograman yang menggunakan aturan sintaktik bahasa regular ini antara lain: Javascript & Perl. 
Dalam hierarki-bahasa Chomsky, grammar regular adalah grammar paling restriktif yang dapat membangkitkan sebuah kalimat.
Dalam hierarki tersebut, grammar regular mempunyai kemampuan pembangkitan kalimat yang sangat minimal karena: 
1.   Sisi kiri hanya boleh berisi sebuah nonterminal, 
2.  Sisi kanan dalam setiap aturan produksinya hanya boleh berisi satu nonterminal, dan posisinya hanya boleh berada di akhiratausisi kanan rangkaian. 
Deskripsi yang lebih sederhana: parser untuk grammar ini tidak dapat mengetahui konteks pemunculan nonterminal yang tengah didefinisikan, dan hanya dapat melihat symbol terminal yang ada tepat didepannya.
Terminal Symbols, Alphabet dan Strings
Alphabet : representasi letter yang ditulis dalam huruf kecil (a,b,c,…z)
Terminal Simbol (T) : individual karakter, termasuk di dalamnya adalah alphabet {a,b,….z, 0,1,…9}
Strings : urutan simbol terbatas (sequence finite symbol)
  contoh : aba, ab12z, axy
  operasi yang dapat dilakukan pada strings : substrings, concatenation.
Non Terminal (NT) : kumpulan string alphabeth yang ada pada formal language.
  Non Terminal direpresentasikan dalam huruf  besar (A,B,….) dan diapit dengan
  tanda <..> untuk membedakannya dengan string.
Konsep T dan NT direpresentasikan dalam Produksi.
  Bentuk Umum Produksi   NT ::= string T atau NT

Derivasi & Reduksi
Derivasi merupakan uraian dari suatu Produksi.
Reduksi proses perubahan string ke dalam NT sehingga menjadi suatu grammar production.

.:: Klasifikasi Grammar ::.
Chomsky (1963) mengklasifikasikan Grammar menjadi 4 kategori :
1. Grammar Type-0
Disebut Phrase Structure Grammar atau grammar tidak terbatas
Bentuknya : a ::= ß
Dimana, a dan ß dapat berupa T atau NT, yang dapat saling bersubstitusi, karenanya tidak relevan untuk bahasa pemrograman.
 2. Grammar Type-1
Disebut Context Sensitive Grammar (CSG), produksi dari grammar ini adalah derivasi/reduksi dari particular  string yang hanya terdapat pada particular context
Bentuknya :
  a ::= apß
Dimana, p menggantikan A untuk menutupi string a dan ß .
Grammar ini-pun tidak relevan untuk bahasa pemrograman.
 3. Grammar Type-2
Disebut Context Free Grammar (CFG), grammar ini tidak membutuhkan context pengenal  atau derivasi
Bentuknya : A ::= p
Grammar ini digunakan pada ALGOL-60 dan PASCAL
 4. Grammar Type-3
Disebut Linier atau RegularGrammar, dimana dapat berupa single terminal simbol dan terminal  simbol atau kebalikannya
Bentuknya : A ::= t B | t  atau A ::= B t | t
Bentuk ini banyak dijumpai pada bahasa pemrograman.
CFG (Context Free Grammar)
CFG ditemukan untuk membantu menspesifikasikan bahasa manusia dan ternyata sangat cocok untuk mendefinisikan bahasa komputer, menyederhanakan penerjemahan bahasa komputer dan aplikasi-aplikasi pengolahan string lainnya.
CFG digunakan untuk menspesifikasikan struktur sintaks bahasa pemrograman serta beragam basis data.
CFG adalah sekumpulan berhingga variabel yang juga disebut nonterminal atau kategori sintaks, dimana masing-masing mempresentasikan bahasa. Bahasa-bahasa yang direpresentasikan dengan variabel-variabel itu yang dideskripsikan secara rekursif dalam bentukan lain dan symbol-simbol primitif disebut terminal. Aturan-aturan yang berhubungan dengan variabel-variabel itu disebut produksi.

Semantic


Semantic adalah Mendefinisikan arti dari program yang benar secara syntax dari bahasa tersebut.
Semantic suatu bahasa pemrograman mempunyai banyak potensial / keunggulan, beberapa diantara nya adalah :
Standarisasi bahasa pemrograman.
   Banyak usaha yang dilakukan untuk menstandarisasi bahasa pemrograman seperti FORTRAN, COBOL, dan PL/1, untuk lebih memudahkan programmer menggunakannya.
Referensi untuk user.
  Programmer membutuhkan suatu dokumentasi yang pasti supaya user dapat mengoperasikan program yang dibuat dengan baik.
Pembuktian dari program yang benar.
  Secara matematis, program tidak mungkin bekerja dan berjalan jika tidak ada semantic. 
Referensi untuk implementor.
  Semantic akan mencegah suatu gaya bahasa yang tidak kompetibel yang diwujudkan dalam suatu implementasi berbeda walaupun dengan bahasa yangsama.
Implementasi otomatis
  Suatu tool/alat dapat secara otomatis membuatu translasi bahasa yang melebihi parsing. Hal ini dapat dilakukan jika semantic sudah dirumuskan.
Pemahaman yang lebih baik dari desain bahasa.
  Jika suatu rumusan semantic sulit untuk di deskripsikan secara formal maka rumusan semantic tersebut juga akan sulit digunakan oleh programmer.
Dua alasan mengapa perlu memahami suatu desain bahasa pemrograman dengan lebih baik, yaitu :
1) Memahami dengan lebih baik suatu desain bahasa pemrograman, berarti mambantu menguasai dan menggunakan bahasa tersebut.
2) Memahami dengan lebih baik suatu disain bahasa pemrograman secara detail, membantu programmer untuk memperbaiki proses pengembangan program menjadi lebih baik
Teknik-Teknik Pendeskripsian Semantic Bahasa Pemrograman :
 Operational Semantic :: Pendekatan ini mendefinisikan suatu mesin buatan (Abstract) dengan instruksi-instruksi primitif, tidak perlu realistik, tetapi cukup sederhana supaya tidak muncul kesalahpahaman.Deskripsi semantic dari bahasa pemrograman menentukan suatu translasi kekode.
Denotational Semantic :: Pada pendekatan ini, diberikan suatu fungsi yang memetakan program-program komputer yang ditunjuk kedalam bentuk nilai-nilai abstrak secara matematika (angka, nilai, kebenaran, fungsi matematika, dan sebagainya).
Axiomatic Semantic :: Pada pendekatan ini didefinisikan suatu tindakan program yang dibangun dengan property logika yang menyimpan status computer sebelum dan sesudah eksekusi.
Algebraic Semantic :: Pada pendekatan ini dipertimbangkan suatu objek komputasi yang menjadi syarat-syarat dalam aljabar multi-sorted. Program meng-implementasikan fungsi yang dapat diwujudkan dengan suatu persamaan di antara syarat-syarat tersebut.  
Structured Operational atau Natural Semantic :: Seperti dalam pengambilan keputusan secara alamiah dengan logika. Program diberi suatu arti dari aturan yang diturunkan yang menggambarkan penilaian gagasan suatu bahasa.
Penerapan Semantic
Misal :
  int nilai[10]
  Semantic akan menentukan deklarasi diatas akan menyebabkan ruang sebanyak 10 elemen integer yang diberikan kepada variabel nilai.
Contoh :
  if (a > b) max = a; else max = b;
  Ekspressi a > b harus di evaluasi, dan tergantung dari nilai ini, satu dari dua statemen di belakangnya akan dieksekusi.
  Aturan syntax memberikan bentuk pada statemen tersebut di mana dengan tepat meletakkan tanda “;” sehingga aturan semantic dapat mengartikannya dengan benar.