Algoritma dan Pemrograman 1 (*), Farhah, 12110612, 1KA31 (BAB 2)

Kode Mata Kuliah : IT011302
PTA 2010/2011

Bab 2

Sintaksis

Bahasa Mesin  adalah bentuk terendah pada komputer/ jenis komputer yang digunakan. 

Penerjemah Bahasa Mesin agar mesin (komputer) dapat dimengerti apa yang diinginkan oleh manusia yaitu :

1. Interpreter

2. Compiler.

    Contoh : Cobol, Pascal, Fortran, dll.

Sintaks : kumpulan aturan yang mendefinisikan suatu bentuk bahasa. 

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

1. Aturan Lexical (Scanner) 

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

     a) mengidentifikasi semua besaran yang membangun suatu bahasa

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

     c) menentukkan jenis dari token-token

     d) menangani tabel simbol

     e) scanner di desain untuk mengenali keyword, operator, identifier

     

2. Aturan Sintaksis (Parser)

     Tugas-tugas Syntax Analyzer (Parser) :

     a) bertugas memeriksa kebenaran dan urutan dari token-token yang terbentuk oleh Lexical Analysis.

     b) pengelompokkan token-token kedalam class syntax (bentuk sintaks), seperti prosedur, statement dan expression.

     c) grammar dipakai oleh syntax analyzer untuk menentukkan struktur dari program sumber.

    d) proses pendeteksian (pengenalan token) disebut dengan parsing, maka syntax analyzer sering disebut dengan parser

    e) pohon sintaks yang dihasilkan digunakan semantic analyzer yang bertugas untuk menentukkan maksud dari  program sumber. misalnya operator penjumlahan maka semantic analyzer akan mengambil aksi apa yang harus dilakukan. 

Parsing atau Proses Penurunan

Parsing : berasal dari sebuah kalimat adalah konstruksi atau pembentukkan pohon sintaks untuk kalimat tersebut. 

Parsing dapat dilakukan dengan cara :

1. Penurunan Terkiri (leftmost derivation) : simbol variabel yang paling kiri diturunkan (tuntas) dahulu.

2. Penurunan Terkanan (rightmost derivation) : simbol yang paling kanan diturunkan (tuntas) dahulu. 

Konsep dan Notasi Bahasa

- Alfabet : himpunan hingga yang tidak kosong (hampa) dari symbol. 

- Bahasa : himpunan hingga ataupun tak hingga dari kalimat atau kumpulan kalimat. 

- Tata Bahasa / 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 bahaasa, yaitu menjadi empat class yang disebut dengan Hierarki Chomsky.

Hierarki Chomsky 

1) Unrestricted Grammar (UG) 

     Ciri-ciri : Tipe 0 / Unrestricted : tidak ada batasan pada aturan produksi

                       Abc -> De

2) Context Sensitive Grammar (CSG)

     Ciri-ciri : Tipe 1 / Context Sensitive : panjang string ruas kiri harus < (lebih kecil) atau = (sama dengan) ruas kanan.

                       Ab -> DeF

                       CD -> eF

3) Context Free Grammar (CFG)

     Ciri-ciri : Tipe 2 / Context Free : ruas kiri haruslah tepat satu symbol variabel, yaitu simbol non terminal.

                       B -> CDeFg

                       D -> BcDe

4) Regular Grammar (RG)
     Ciri-ciri : Tipe 3 / Regular : ruas kanan hanya memiliki maksimal satu symbol non terminal dan diletakkan paling kanan.

     
                       A -> e

                       A -> efg

                       A -> efgH

                       C -> D

Aturan Produksi :

1. Dinyatakan dalam bentuk α -> β, α menghasilkan atau menurunkan β.

2. Simbol α untuk ruas kiri, sedangkan simbol β untuk ruas kanan. 

3. Simbol-simbol dapat berupa terminal dan non terminal dimana non terminal dapat diturunkan menjadi simbol yang lainnya.

4. Umumnya, simbol terminal disimbolkan dengan huruf kecil (a,b,c, dsb) sedangkan untuk simbol non terminal dengan huruf besar (A,B,C, dsb).

5. Contoh aturan produksi :

    T -> a, T menghasilkan a

    E -> T | T + E, E menghasilkan T atau E menghasilkan T + E.

Derifasi : Proses pembentukkan kalimat di grammar. 

Contoh : Derifasi untuk aaabaaa, adalah :

                 S -> aCa

                    -> aaCaa

                    -> aaaCaaa

                    ->aaabaaa