ANALISA SINTAKS

Analisa sintaks

Bahasa program merupakan suatu wahana untuk menuangkan pikiran manusia yang dapat dimengerti oleh mesin komputer sehingga bernilai guna. Suatu bahasa program akan terikat aturan dari paradigma bahasa. Ada berbagai macam paradigma bahasa : Prosedural, Fungsional, Deklaratif, Object Oriented, Konkuren. Paradigma yang diajarkan dalam Matakuliah Algoritma dan Pemrograman ini adalah paradigma prosedural.
Belajar bahasa program hanya belajar tentang sintak (aturan) dari bahasa sedangkan belajar memprogram akan tercakup beberapa hal yang didalamnya terkandung tentang belajar bahasa program itu sendiri. Yang harus diperhatikan oleh mahasiswa yang sedang belajar memprogram, yaitu :
• Simulasi , sensibilitas terhadap masalah dan kemungkinan solusi. Kegiatan dilakukan di kelas, melalui permainan. Contoh : Mengurutkan tinggi badan mahasiswa dari tinggi ke pendek atau sebaliknya. Permainan dapat dilakukan secara manual maupun dengan komputer.
• Analisis masalah secara lebih formal dan membuat spesifikasi dan algoritma dalam notasi yang ditetapkan. Mahasiswa harus menuliskan solusi algoritmiknya dalam notasi standar di kelas. Penulisan notasi algoritmik bertujuan untuk menyeragamkan pemahaman tentang algoritma program yang terbebas dari sintak (aturan) penulisan bahasa program .
• Menulis program, yaitu menterjemahkan notasi algoritmik ke dalam sintak bahasa program.
• Debugging dan menguji coba program. Hal ini bertujuan untuk mendapatkan program yang benar. Program dikatakan benar jika terbebas dari salah lojik dan sintak bahasa. Secara ideal mahasiswa hanya diberi kesempatan untuk me-run program sebanyak 2 kali : pertama untuk membersihkan program dari kesalahan sintak dan kedua untuk mendapatkan program benar. Pada tahap ini diharapkan tidak terjadi kesalahan lojik jika analisa benar.
• Mengamati peristiwa eksekusi, perlu dilakukan untuk meningkatkan kepercayaan bahwa jika analisa benar maka sisa pekerjaan menjadi mudah. Pada pemrograman prosedural, aspek ini penting untuk memahami fenomena eksekusi dan perubahaan nilai suatu struktur data.
• Membaca program : orang akan dapat menulis dengan baik kalau sering membaca. Hal ini juga berlaku dalam memprogram. Kegiatan yang dapat dilakukan di kelas adalah dengan saling tukar menukar teks algoritma, dan saling mengkritik algoritma teman. Mahasiswa harus berlatih sendiri pada kegiatan belajar bersama.
• Membuktikan kebenaran program secara formal , satu-satunya hal yang menjamin kebenaran, tetapi kontradiktif dan sulit diterapkan dalam kehidupan sehari-hari. Program yang hanya lima baris pembuktiannya bisa sehalaman, sehingga seringkali tidak pernah diterapkan dalam aplikasi nyata. Aktifitas ini dicakup dalam matakuliah Analisis Algoritma.

Masalah bahasa pemrograman

Memilah bilangan menjadi 3 bagian, yaitu wilayah negatif , nol dan positif. Wilayah negatif akan dicirikan oleh suatu aturan jika bilangan yang diinputkan dari keyboard adalah lebih kecil dari nol ( dalam bahasa Matematik “bilangan 0 “ sedangkan wilayah nol adalah bilangan samadengan nol ( yaitu bilangan yang bukan bagian dari “bilangan > 0 dan bilangan < 0”).

1.1. Spesifikasi :
Input : suatu nilai bertipe integer yang ditampung dalam variabel “Bil”
Proses : memilah klasifikasi bilangan.
Output : “Negatif “ jika Bil 0
“Nol” jika Bil = 0
1.2. Notasi Algoritmik :
Program PilahBilangan
{ dibaca Bil(Integer), bilangan bulat secara sembarang dari keyboard }
{ harus dituliskan klasifikasi Bil : apakah negatif, positif atau nol }
Kamus
Bil : Integer
Algoritma / Proses
Input (Bil)
If Bil 0 Then
Output(‘ Bilangan Positif’)
Else Output(‘ Bilangan Nol’)
Endif
Endif

Contoh program :
{ Name of File : c:\pilah.pas}
{ Create by : aprilia }
{ Date : 12 april 2010 }
{ Description : }
{ dibaca Bil(Integer), bilangan bulat secara sembarang dari keyboard }
{ harus dituliskan klasifikasi Bil : apakah negatif, positif atau nol }
uses crt;
{Kamus}
Var
Bil : Integer;
Begin
{Algoritma / Proses}
{—–Input (Bil)—- }
write(‘Masukan bilangan : ‘);
readln(Bil);
If Bil 0 Then
{——Output(‘ Bilangan Positif’)—–}
write(‘Bilangan itu adalah bilangan Positif’)
Else { —- Output(‘ Bilangan Nol’)—- }
write(‘Bilangan itu adalah bilangan Nol’);
readln { untuk menahan laju proses berikutnya }
end.

Hasil program :

Masukan bilangan : -2000
Bilangan itu adalah bilangan Negatif

Masukan bilangan : 4000
Bilangan itu adalah bilangan Positif

Masukan bilangan : 0
Bilangan itu adalah bilangan Nol

Fungsi Rekursif
Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri. Fungsi ini akan terus berjalan sampai kondisi berhenti terpenuhi, oleh karena itu dalam sebuah fungsi rekursif perlu terdapat 2 blok penting, yaitu blok yang menjadi titik berhenti dari sebuah proses rekursi dan blok yang memanggil dirinya sendiri.

Contoh – contoh penerapan rekursif:
1. Fungsi cetak ke layar
Fungsi ini mencetak nilai dari paremeter yang dilempar kepadanya. Jika nilai dari parameter tersebut > 0, fungsi akan mencetak nilai dari parameter tersebut dan kemudian memanggil dirinya lagi, jika tidak, program berhenti.

Void cetak (int n) {
If (n>0) {
Printf (“\ ncetak: %i”, n);
Cetak (n-1);
}
}

Sifat rekursi kiri (left recursion) :
Sebuah grammar dikatakan bersifat rekursi kiri jika untuk sebuah simbol nonterminal A terdapat derivasi non hampa A  A. Produksi berbentuk A  A disebut produksi yang bersifat immediate left recursion.
Rekursi kiri dapat dieliminir dengan transformasi berikut :
A A transformasi menjadi : A  R, R R
Transformasi ini dapat diperluas sehingga :
A A A … A   …
bertransformasi menjadi :
A   R R… R, R  R R.. R

Contoh 1 : Diketahui : E  E + T T, T  T * F  F, F  (E) I
yang jelas mengandung immediate left recursion untuk simbol E dan T.

Transformasi menghasilkan :
E  TR , R  +TR  , T FR , R *FR  , F  (E) I

Algoritma Rekursi_Kiri
1. Rename semua nonterminal menjadi A , A , …, A
2. for i = 1 to n do begin
2.a. for j = 1 to i-1 do begin
ganti setiap produksi berbentuk A  A 
dengan produksi-produksi : A    …  
dimana : A    …  produksi-A saat iterasi ini
end
2.b. eliminasi semua immediate left recursion produksi-A
end

Contoh 2 : Diketahui : S  Aab, A AcS d
Algoritma Rekursi_Kiri akan digunakan terhadap himpunan produksi ini.
Langkah 1 : A := S, A := A sehingga produksi menjadi
A  A ab, A  A cA d

Saat i = 1 inner loop tidak dipenuhi karena (j =1) > (i-1= 0), maka program masuk ke (2.b) untuk A . Tetapi A tidak bersifat immediate left recursion. Jadi saat i = 1 program tidak melakukan apapun.
Saat i = 2,
(2.a) j = 1 : ganti A  A d dengan A  A adbd
(2.b) A  A cA adbd adalah immediate left recursion, sehingga diperoleh transformasinya :
A  bdR R , R  c R adR 
Hasilnya : A  A ab, A  bdR R , R  c R adR  , atau :
S  Aab, A bdR R , R  cR adR 

Bahasa pemrograman aplikasi

Sebuah kompiler akan mem-parsing input dari sebuah bahasa pemrograman bahasa assembly atau representasi internal dengan cara mencocokkan simbol untuk masuk Backus-Naur bentuk aturan produksi. Sebuah LL parser, juga disebut parser atas bawah atau top-down parser, berlaku setiap aturan produksi simbol-simbol yang masuk dengan bekerja dari kiri-paling simbol menghasilkan pada aturan produksi dan kemudian melanjutkan ke yang berikutnya untuk setiap aturan produksi non – simbol terminal dijumpai. Dengan cara ini, parsing dimulai pada hasil Waktu sisi (sisi kanan) dari aturan dan mengevaluasi produksi non-terminal dari Waktu pertama dan, dengan demikian, hasil menuruni pohon parsing untuk setiap baru non-terminal sebelum melanjutkan ke yang berikutnya simbol untuk aturan produksi.

Contoh:


Akan cocok dengan dan berusaha untuk mencocokkan berikutnya. Kemudian misalnya akan mencoba. Sebagai salah satu mungkin mengharapkan, beberapa bahasa yang lebih ambigu daripada yang lain. Untuk non-bahasa ambigu di mana semua produksi untuk non-terminal yang berbeda menghasilkan string: string yang dihasilkan oleh satu produksi tidak akan mulai dengan simbol yang sama dengan string yang dihasilkan oleh produksi lain. Ambigu non-bahasa mungkin dapat dipecah oleh LL (1) tata bahasa di mana (1) menandakan maju parser membaca tanda pada suatu waktu. Untuk bahasa ambigu dapat dipecah oleh LL parser, yang parser harus LookAhead lebih dari 1 simbol, misalnya LL (3).
Solusi yang umum adalah dengan menggunakan parser LR (juga dikenal sebagai bottom-up atau pergeseran-mengurangi parser).

Top down
Top-down parsing adalah strategi hubungan menganalisis data yang tidak diketahui oleh umum hipotesa struktur pohon parse dan kemudian mempertimbangkan apakah struktur-struktur fundamental yang dikenal kompatibel dengan hipotesis. Terjadi dalam analisis kedua bahasa alam dan bahasa komputer.

Top-down parsing dapat dilihat sebagai suatu usaha untuk menemukan paling kiri turunan dari input-sungai dengan mencari parse-pohon dengan menggunakan top-down ekspansi yang diberikan aturan tata bahasa resmi. Token dikonsumsi dari kiri ke kanan. Pilihan inklusif digunakan untuk mengakomodasi semua ambiguitas dengan memperluas alternatif tangan kanan-sisi aturan tata bahasa.

Menampung rekursi kiri di top-down parsing

Tata bahasa resmi yang berisi rekursi kiri tidak dapat diurai oleh keturunan yang naif parser rekursif kecuali mereka akan dikonversi ke kanan yang setara dengan lemah-bentuk rekursif. Namun, penelitian terbaru menunjukkan bahwa adalah mungkin untuk mengakomodasi rekursif kiri tata bahasa (bersama dengan semua bentuk CFGs umum) yang lebih canggih top-down parser dengan menggunakan pembatasan. Sebuah pengakuan algoritma yang ambigu mengakomodasi tata bahasa dan membatasi yang terus tumbuh rekursif kiri langsung mengurai dengan kedalaman memaksakan pembatasan berkenaan dengan masukan input yang panjang dan posisi, dijelaskan oleh Frost dan Hafiz pada tahun 2006 [5]. Algoritma yang diperpanjang untuk algoritma parsing yang lengkap untuk mengakomodasi tidak langsung (dengan membandingkan dihitung sebelumnya-konteks dengan konteks sekarang) serta rekursi kiri langsung dalam waktu polinomial, dan untuk menghasilkan ukuran yang ringkas polinomial representasi dari potensial-eksponensial jumlah parse pohon untuk tata bahasa yang sangat-ambigu oleh Frost, Hafiz dan Callaghan tahun 2007 [3]. Algoritma sejak saat itu telah diimplementasikan sebagai kumpulan combinators parser yang ditulis dalam bahasa pemrograman Haskell. Rincian pelaksanaan set baru ini combinators dapat ditemukan dalam kertas [4] oleh penulis yang disebutkan di atas, yang disajikan dalam PADL’08. X-situs SAIGA memiliki lebih banyak tentang algoritma dan implementasi detail.

Kompleksitas Algoritma Quick Sort
Kompleksitas Algoritma Quick dieksekusi dikarenakan arsitektur komputer C lebih
baik dibandingkan arsitektur komputer D. Sort Oleh karena itu kita memerlukan model abstrak Fachrie Lantera – NIM: 13506099 pengukuran waktu/ruang yang bebas dari
pertimbangan arsitektur komputer dan compiler bahasa pemrograman. Besaran yang dipakai untuk Program Studi Teknik Informatika, Sekolah Teknik menerangkan model abstrak pengukuran waktu/ruang Elektro dan Informatika ini adalah kompleksitas algoritmaAda dua macam kompleksitas algoritma, yaitu :
Kompleksitas waktu dan kompleksitas ruang. Kompleksitas waktu disimbolkan dengan T(n) dan Abstract – Makalah ini membahas kompleksitas kompleksitas ruang S(n). Kompleksitas waktu, T(n), algoritma dari Quick Sort yang merupakan algoritma
diukur dari jumlah tahapan komputasi yang dibutuhkan pengurutan. Dalam sebuah permasalahan dapat untuk menjalankkan algoritma sebagai fungsi dari mempunyai banyak algoritma penyelesaian. Algoritma ukuran masukan n. Komplesitas ruang, S(n), diukur dari penyelesaian tersebut tidak harus benar, tetapi juga memori yang digunakan oleh struktur data yang harus mangkus (efisien). Kemangkusan algoritma terdapat di dalam algoritma sebagai fungsi dari ukuran diukur dari waktu eksekusi dan kebutuhan ruang masukan n. memori yang digunakan. Algoritma yang efisien adalah algoritma yang meminimumkakan waktu eksekusi dan Dengan menggunakan besaran kompleksitas
kebutuhan ruang memori. waktu/ruang algoritma, kita dapat menentukan laju
peningkatan waktu (ruang) yang diperlukan algoritma.
Kata Kunci : efisien, kompleksitas algoritma, dengan meningkatnya ukuran masukan n.1
kompleksitas waktu asimptotik.

Di dalam sebuah algoritma terdapat bermacam jenis operasi:
- Operasi baca/tulis,
- Operasi aritmetika (+, -, *, /)
1.1 Kompleksitas Algoritma
– Operasi pengisian nilai (assignment)
– Operasi pengaksesan elemen larik
- Operasi pemanggilan fungsi/prosedur
- lebih baik dalam menyelesaikan masalah tertentu.

Untuk menjawab masalah di atas tentunya ada hal yang harus diukur supaya kita bisa menilai apakah Dalam praktek, kita hanya menghitung jumlah operasi algoritma tersebut lebih baik atau tidak.

About these ads

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Ikuti

Get every new post delivered to your Inbox.

%d bloggers like this: