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.

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