Soal

Tentukan apakah dari sebuah titik sembarang ada didalam, bersinggungan atau diluar lingkaran yang dihasilkan dari sebuah titik sembarang dengan jari-jari R.

Jawab
Misalkan:
Titik pertama berkoordinat x1, y1
Titik kedua berkoordinat x2, y2
Jari-jari untuk titik pertama adalah R

PseudoCode:
//inisialisasi variabel
float selisihx
float selisihy
float totalselisih
input x1,y1,x2,y2,R

//perhitungan jarak antar 2 titik
selisihx=(x1-x2)^2
selisihy=(y1-y2)^2
totalselisih=selisihx + selisihy

//syarat titik dalam bersinggungan atau di luar lingkaran
if(R>totalselisih)then
print”Titik didalam lingkaran”
else if (R<totalselisih) then
print”Titik diluar lingkaran”
else
print”Titik bersinggungan dengan lingkaran”

Code Generator untuk soal diatas:
1.    Mov x1, r0
2.    Mov x2, r1
3.    Sub r1, r0
4.    Mul r0, r0
5.    Mov r0, selisihx
6.    Mov y1, r2
7.    Mov y2, r3
8.    Sub r3, r2
9.    Mul r2, r2
10.    Mov r2, selisihy
11.    Add selisihy, selisihx
12.    Mov selisihx, totalselisih
13.    Mov R, r4
14.    Mul r4, r4
15.    Gt totalselisih, r4
16.    Jmpf totalselisih, 19
17.    Prt “Titik di dalam lingkaran”
18.    Jmp , 24
19.    Lt totalselisih, r4
20.    Jmpf , 23
21.    Prt “Titik di luar lingkaran”
22.    Jmp 24
23.    Prt “Titik bersinggungan dengan lingkaran”
24.    ……

www.binus.ac.id

Kuis Teknik Kompilasi

1. Perhatikan CFG (Context Free Grammar) berikut ini :

S -> S+A | S-A | A+S | A-S | B*A

B -> aB | B(a+B) | B*a | a(a+B) | b

A -> a

Tentukan First, Follow & Table dari Production data.

Jawab :

S    -> ASˈˈ | B*ASˈ

Sˈ  -> +ASˈ | -ASˈ | ԑ

Sˈˈ -> +SSˈ | -SSˈ

B   -> aBˈˈ | bBˈ

Bˈ  -> (a+B)Bˈ | aBˈ | ԑ

Bˈˈ -> BBˈ | (a+B)Bˈ

A   -> a

First :

–          First (S)         = { a,b }

–          First (Sˈ)       = { +,-,ԑ }

–          First (Sˈˈ)      = { +,- }

–          First (B)        = { a,b }

–          First (Bˈ)       = { (,a,ԑ }

–          First (Bˈˈ)      = { a,b,c }

–          First (A)        = { a }

Follow :

–          Follow (S)    = { $ }

–          Follow (Sˈ)   = { $ }

–          Follow (Sˈˈ) = { $ }

–          Follow (B)    = { *,),(,a }

–          Follow (Bˈ)  = { *,),(,a }

–          Follow (Bˈˈ) = { *,),(,a }

–          Follow (A)   = { +,-,$ }

Tabel Produksi dari hasil diatas:

2.

S  -> if E then S | if E then S else S | V := E

V -> id | id [E]

E -> E + T | E – T | T

T -> T * F | T / F | F

F -> V | (E) | const

Tentukan first, follow, dan tabel dari produksi tersebut.

Jawab

S -> if E then S’ | v := E

S’ ->ε | else S

V -> idV’

V’ -> ε | [E]

E ->TE’

E’ -> +TE’ | -TE’ | ε

T -> FT’

T’ -> *FT’ | /FT’ | ε

F -> V | (E) | const

• Menentukan first

first (S) = { id, if }

first (S’) = { ε, else }

first (V) = { id }

first (V’) = { ε, [ }

first (E) = { id, (, const }

first (E’) = { +, -,  ε }

first (T) = { id, (, const }

first (T’) = { *, / ,  ε }

first (F) = { id, (, const }

• Menentukan follow

follow (S) = { $, else }

follow (S’) = { $, else }

follow (V) = { : }

follow (V’) = { : }

follow (E) = { ], ) }

follow (E’) = { ], ) }

fololw (T) = { +, -, ], ) }

follow (T’) = { +, -, ], ) }

follow (F) = { *, /, +, -, ] , ) }

• Tabel

3. S -> a= A

A -> aA’|bA’

A’ -> + AA’ |  ԑ

Carilah First dan Follow serta buatlah tabel produksinya!

First (S) = {a}

First (A) = {a,b}

First (A’) = {+, ԑ}

Follow (S) = {$} menggunakan syarat algoritma follow 1

Follow (A) = {$, +} menggunakan syarat algoritma follow 2 dan 3a

Follow (A’) = {$, +} menggunakan syarat algoritma follow 2

Sehingga tabel produksinya adalah

4. be -> bt be’

be’ -> or bt be’

be’ -> ԑ

bt   -> bf bt’

bt’ -> and bf bt’

bt’ -> ԑ

bf -> not bf

bf -> (be)

    bf -> true

    bf -> false

Cek string sbb: not (true or false) and true and true and false not (false) true

www.binus.ac.id

Berikut adalah hasil percobaan CREATE dan SELECT tabel dengan nama tabel menggunakan keyword SQL   :

Query tersebut menghasilkan error :

Hal ini disebabkan karena SELECT yang  digunakan sebagai nama tabel dan atribut pada query tersebut dikenal sebagai keyword SQL. Jika ingin menggunakan keyword SQL sebagai nama tabel atau atribut bisa ditambahkan square brackets ( [ ] ) atau misalnya dengan menambahkan underscore ( _ ).

www.binus.ac.id

Web Technology dan Database

Web merupakan kumpulan dokumen-dokumen multimedia yang saling terhubung satu sama lain. Informasi yang ditampilkan dapat terdiri dari text, grafik, gambar, suara, dan video.

Web terdiri dari jaringan komputer yang bisa berinteraksi melalui dua aturan :

• Sebagai server yang menyediakan informasi,
• Sebagai client yang mencari dan meminta informasi.

Aturan yang menjamin pertukaran informasi antara server dan client adalah Hypertext Transfer Protocol (HTTP).

Komponen dasar dari web :

Arsitektur Client/Server

Client/server secara sederhana dapat diartikan sebagai kemampuan sebuah komputer untuk meminta data atau layanan ke komputer lain.

Jenis – jenis client/server :

• Arsitektur 2-tier client/server, yaitu hanya berupa client dan server. Client menyediakan user interface, formulasi query, dan data manipulation. Sedangkan server menyediakan standar DBMS service serperti query optimization, atau transaction management.

• Arsitektur 3-tier client/server, adanya penambahan tier antara database server dan client. Tier ketiga (middle) dapat digunakan untuk menjalankan business rules dan melakukan pemrosesan.

Tiga tier terdiri dari :

–        User interface yang berjalan pada komputer end-user (client).

–        Business logic dan proses data berjalan pada application server.

–        DBMS, menyimpan data yang dibutuhkan oleh middle tier.

Arsitektur 3-tier client/server dapat mengurangi beban pada DBMS server sehingga transaksi pada DBMS server dapat berjalan dengan efisien karena business logic dipindahkan ke lapisan middle yang memungkinkan thin client.

Database Management System (DBMS)

DBMS adalah kumpulan program yang digunakan untuk mendefinisikan, mengatur dan memproses database.

Untuk berinteraksi dengan DBMS menggunakan bahasa database yang telah ditentukan oleh perusahaan DBMS. Bahasa database biasanya terdiri atas perintah-perintah yang diformulasikan sehingga perintah tersebut akan diproses olah DBMS. Perintah-perintah biasanya ditentukan oleh user. Ada 2 bahasa database :

1. Data Definition Language (DDL)

DDL digunakan untuk menggambarkan desain basis data secara keseluruhan, biasanya untuk membuat tabel baru, membuat indeks, ataupun mengubah tabel.

2. Data Manipulation Language (DML)

DML digunakan untuk melakukan manipulasi dan pengambilan data pada suatu database seperti penambahan data baru ke dalam database, menghapus data dan pengubahan data.

Sumber :

http://www2.ukdw.ac.id/kuliah/info/IM2043/materi/2006/Pengantar%20Web%20Database.pdf

http://wildanfaizzani.wordpress.com/2010/04/03/pengertian-dbms-database-management-system/

http://blog.simcrest.com/images/3tier.jpg

http://blog.simcrest.com/images/2tier1.jpg

Bahan kuliah T0206 – Sistem Basis Data dan T0213 – Web Database

www.binus.ac.id

Left Recursive dan Left Factoring

Pada top down parsing tidak diperbolehkan adanya left recursive serta grammar yang akan di parsing harus di left-factored (menggunakan metode left-factoring) karena :

1. Grammar yang memiliki left recursive tidak bisa diperiksa, sehingga harus diubah dulu agar tidak left recursive lagi. Karena left recursive akan mengakibatkan loop yang terus-menerus .

Contoh grammar yang memiliki left recursive :

Dari contoh di atas, dapat kita lihat bahwa grammar tersebut mengalami loop yang terus menerus. Oleh karena itu, untuk menghindari penurunan kiri yang looping, perlu dihilangkan sifat rekursif, dengan langkah-langkah sebagai berikut :

• Pisahkan Aturan produksi yang rekursif kiri dan yang tidak.

Aturan produksi yang rekursif kiri :

A -> A α1 | A α2 | … | A αn

Aturan produksi yang tidak rekursif kiri

A -> β1 | β2 | … | βn

• Lakukan pergantian aturan produksi yang rekursif kiri, sebagai berikut :

1. A -> β1 Z | β2 Z | … | βn Z

2. Z -> α1 | α2 | … | αn

3. Z -> α1 Z | α2 Z | … | αn Z

• Pergantian dilakukan untuk setiap aturan produksi dengan simbol ruas kiri yang sama, bisa diganti dengan variabel Z1, Z2 dst, sesuai dengan variabel yang menghasilkan rekurisif kiri.

Contoh :

S -> Sab | aSc | dd | ff | Sbd

• Pisahkan aturan produksi yang rekursif kiri

S -> Sab | Sbd

Ruas Kiri untuk S: α1=ab , α2=bd

• Aturan Produksi yang tidak rekursif kiri

S -> aSc | dd | ff

Dari situ didapat untuk Ruas Kiri untuk S: β1 = aSc, β2 = dd, β3= ff

• Langkah berikutnya adalah penggantian yang rekursif kiri

S -> Sab | Sbd, dapat digantikan dengan

1. S -> aScZ1 | ddZ1 | ffZ1

2. Z1 -> ab | bd

3. Z1 -> abZ1 | bdZ1

• Hasil akhir yang didapat setelah menghilangkan rekursif kiri adalah sebagai berikut :

S -> aSc | dd | ff

S -> aScZ1 | ddZ1 | ffZ1

Z1 -> ab | bd

Z1 -> abZ1 | bdZ1

2. Grammar yang belum di left-factored menggunakan left-factoring maka akan mengakibatkan konflik First-first yaitu konflik dimana susah untuk menentukan First dari suatu variable dalam grammar karena memiliki 2 produksi yang dimulai dengan terminal yang sama (mengakibatkan suatu grammar ambigu) sehingga dapat digunakan left-factoring untuk menghilangkan keambiguan dalam grammar tersebut.

Contoh grammar yang memiliki konflik first-first:

E → T + E | T

T → int | int * T | ( E )

Penjelasan:

First(E) adalah T dimana ada 2 produksi E yang dimulai dengan T yang sama sehingga susah untuk diprediksi T yang mana merupakan First dari E. (T + E | T)

First(T) adalah int dan ( tetapi untuk int ada 2 sehingga juga susah diprediksi int yang mana merupakan first dari T. (int | int * T)

Penyelesaian dengan Left Factoring:

Mengeluarkan prefix yang sama dalam produksi yang bisa mengakibatkan munculnya

ε-productions:

E → T + E | T menjadi E → T (+ E | ε ) => (dalam hal ini mengeluarkan T) sehingga membentuk:

E → T X

X → + E | ε

T → int | int * T | ( E ) menjadi T → int (* T | ε ) | ( E ) => (dalam hal ini mengeluarkan int) sehingga membentuk:

T → int Y | ( E )

Y → * T | ε

Setelah di left factoring maka untuk menentukan First dari suatu grammar akan tidak keliru dan lebih mudah diprediksi dan diparsing.

www.binus.ac.id

Sumber :

http://asanisembiring.files.wordpress.com/2012/02/pertemuan-7.doc

http://cecs.wright.edu/~tkprasad/courses/cs780/L101TDP.pdf

https://webdosen.budiluhur.ac.id/dosen/930011/buku_tekom2010.pdf

http://pages.cs.wisc.edu/~cs536-1/readings/5b.TOP-DOWN-PARSING.html

http://en.wikipedia.org/wiki/LL_parser#Left_Factoring

Tugas :

Membuat DFA dari RE dengan metode Tree dan ε-NFA, dengan syarat :

• Jumlah state DFA minimal 5 state dan maximal 8 state.
• Jumlah final state DFA minimal 2 state dan maximal 3 state.

1.      RE : ( a | b )* ( aa | bb )

 2.      Membuat DFA dengan Metode Tree

RE         : ( a | b )* ( a a | b b ) . #

Index   :     1   2         3 4  5 6     7

S₀ = 1, 2, 3, 5

Followpos 1 = 1, 2, 3, 5

Followpos 2 = 1, 2, 3, 5

Followpos 3 = 4

Followpos 4 = 7

Followpos 5 = 6

Followpos 6 = 7

Followpos 7 = –

Minimalisasi DFA

DFA sudah dalam bentuk minimal karena tidak ada state yang mempunyai index yang sama pada inputan a dan b dengan state yang lainnya.

3.      Membuat DFA dengan Metode ε-NFA

Kelompok 5 :

Bernardus Robby – 1501144332

Rifan Wijaya  – 1501145700

Glory Tannia – 1501187470

Haris Winoto – 1501188611

www.binus.ac.id

Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂