Code Generator untuk Menentukan Titik pada Lingkaran

Kuis 1 April 2014 Teknik Kompilasi

1. 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, dan Table Parsing!

Jawab:

S -> A+SS’ | A – SS’ | B * AS’

S’ -> +AS’ | -AS’ | ε

S = >  AF | B * AS’

S’ -> +AS’ | -AS’ | ε

S’’ -> +SS’ | -SS’

B -> aBB’ | a(a+B)B’ | bB’

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

B -> aG | bB’

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

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

A -> a

First S -> {a,b}

First S’ -> {+,-, ε}

First S’’ -> {+,-}

First B -> {a,b}

First B’ -> {(,*}

First B’’ -> {a,b,(}

Follow S -> {$,+,-}

Follow S’ -> {$}

Follow B -> {$,a,b,)}

Follow B’ -> {$}

Follow S’’ -> {$,+,-}

Follow B’’ -> {$,a,b,)}

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

S’->ε | else S

E-> TE’

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

T->FT’

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

F-> V|(E)|const

V-> id V’

V’-> ε|[E]

Tentukan First, Follow, dan Table Parsing!

first(S) = {if, id}

first(S’) = {ε, else}

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

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

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

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

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

first(V) = {id}

first(V’) = {a b c}

follow(S) = {$}

follow(S’) = {$}

follow(E) = { then, $,),]}

follow(E’) = { then, $,),]}

follow(T) = {+, -}

follow(T’) = {+, -}

follow(F) = {*,/ }

follow(V) = {:}

follow(V’) = {:}

3. S -> a = A

A -> aA’ | bA’

A’ -> +AA’ | ε

Tentukan First, Follow, dan Table Parsing!

Jawab:

First S = {a}

First A = {a,b}

First A’ = {+, ε }

Follow S = {$}

Follow A = {$,+}

Follow A’ = {$,+}

4. Diketahui grammar sbb:

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

Tentukan input ini diterima atau ditolak!

not(true or false) and true and true and false not (false) true

Jawab:

First (be) -> not,(,true,false

First (be’) -> or, ε

First (bt) -> not,(,true,false

First (bt’) -> and, ε

First (bf) -> not,(,true,flase

Follow (be) -> {$,)}

Follow (be’) -> {$,)}

Follow (bt) -> {or,$,)}

Follow (bt’) -> {or,$,)}

Follow (bf) -> {or,$,), and}

www.binus.ac.id

Analisis ERD dari Twitter

Dalam analisis kami ini, kami mendapatkan 7 tabel diantaranya Member, Tweet, DirectMessage, TweetTransaction, DirectMessageTransaction, Following, dan Follower.

Dalam analisis kami ini, kami sengaja memisahkan antara tabel DirectMessage dengan Tweet karena keduanya memiliki perbedaan yang signifikan dimana Tweet itu dapat dilihat oleh banyak orang walaupun orang itu tidak memfollow atau tidak kita follow sedangkan DirectMessage hanya dapat dilihat antara orang yang berkirim pesan saja dan tentunya harus memfollow dan kita follow terlebih dahulu baru transaksi direct message bisa terjadi sehingga dapat kita simpulkan keduanya terpisah karena cara transaksi mereka yang sedikit berbeda. DirectMessage terhubung dengan DirectMessageTransaction dimana DirectTransaction sebagai detail dari transaksi yang terjadi seperti siapa yang melakukan, kapan waktunya, pesannya apa, dll. Begitu juga dengan Tweet yang dihubungkan ke Member oleh tabel TweetTransaction dimana tugas dari TweetTransaction ini sama dengan DirectMessageTransaction. Tabel Following dan Follower sengaja kami pisah karena ada sedikit perbedaan dan keduanya terhubung ke tabel Member.

www.binus.ac.id

Penggunaaan keyword SQL sebagai nama tabel

Pada SQL Server, terdapat batasan dalam memberi nama tabel baru yang ingin kita buat. Karena pada SQL Server terdapat banyak keyword yang menjadi grammar dari SQL yang digunakan untuk mendefinisikan, memanipulasi, dan mengakses database. Keyword-keyword tersebut tidak dapat kita gunakan sebagai nama identifier suatu tabel.

Contoh:

CREATE TABLE dengan nama “ALTER”

Dari gambar di atas, proses CREATE TABLE tidak dapat dilakukan karena dianggap sebagai error.

Untuk dapat menggunakan keyword SQL sebagai identifier, kita perlu menambahkan tanda ‘[]’ pada nama identifier.

CREATE TABLE dengan menambahkan ‘[]’

Solusi di atas diizinkan oleh SQL Server, maka terdapat message bahwa perintah CREATE TABLE sukses.

Kemudian jika kita ingin menampilkan tabel tersebut, kita juga harus menambahkan tanda ‘[]’ pada nama tabel.

SELECT tabel ALTER tanpa menggunakan ‘[]’

SELECT tabel ALTER dengan menambahkan ‘[]’

www.binus.ac.id

Web Database – Data Models

Beberapa istilah yang digunakan dalam model data:

1. Data : informasi atau fakta yang dimiliki oleh organisasi yang disimpan ke dalam database
2. Value : data aktual yang biasanya berupa bilangan biner
3. Literal : representasi dari value yang dapat dibaca dan dipahami manusia
4. Operator : menggabungkan nilai-nilai yang diwakili oleh literal dan variabel. Dibutuhkan satu atau lebih nilai sebagai input yang kemudian diubah dalam beberapa cara menjadi single value.
5. Expression : sebuah kombinasi yang valid dari literal, variabel dan operator
6. Data type : seperangkat nama jenis nilai-nilai data
7. User-defined : jenis sistem yang diciptakan oleh database designer atau database administrator (DBA) untuk memenuhi kebutuhan aplikasi tertentu, dan mungkin tidak dapat diakses oleh semua aplikasi database.
8. System defined : jenis sistem yang dibangun ke dalam DBMS sehingga tersedia untuk setiap aplikasi.

Model Data Relasional

Pada model database relasional, seluruh data diwakili dalam bentuk tuple, digabungkan dalam relasi-relasi. Database yang diorganisasikan dalam hal model relasi merupakan database relasi.

Beberapa istilah yang dipakai dalam model data relasional :

1. Candidate key : satu atribut atau kombinasi satu atribut atau lebih yang secara unik menjadi identifier pada suatu relasi.
2. Candidate key constraint : sebuah ekspresi Boolean yang menyatakan bahwa kombinasi dari nilai-nilai kolom candidate key pada setiap baris adalah unik.
3. Primary key : candidate key yang dipilih sebagai pengidentifikasi utama untuk tabel.
4. Simple key : key yang terdiri dari satu kolom.
5. Composite key : key yang terdiri dari dua atau lebih kolom.
6. Foreign key : kolom atau field pada suatu tabel yang berfungsi sebagai kunci tamu dari tabel lain. Foreign Key sangat berguna bila kita bekerja dengan banyak tabel yang saling berelasi satu sama lain.
7. Referencing table : tabel yang mengandung foreign key.
8. Referenced table : tabel yang mengandung matching candidate key.
9. Matching candidate key : candidate key pada referenced table yang nilainya cocok dengan nilai foreign key dari referencing table.
10. Foreign key constraint : menyatakan bahwa untuk setiap baris dari referencing table, harus ada baris dari referenced table sehingga nilai kolom foreign key sama dengan nilai kolom matching candidate key.
11. Null : merepresentasikan bahwa suatu kolom bernilai kosong atau “unknown”.

Perbedaan Base Table dan Derived Table

Base table menyimpan instance nya ke dalam media penyimpanan persisten (cth:  hard disk) sedangkan Derived table hanya menyimpan instance nya ke dalam memory.

Perbedaan View dan Ordinary Derived Table

View adalah tabel yang skema tabelnya disimpan dalam kamus data (data dictionary).

Referensi :

• Slide Binusmaya T0213 – November 2011 – S03
• http://id.wikipedia.org/wiki/Model_relasional

www.binus.ac.id

TM2 Teknik Kompilasi

Mengapa top down parsing harus menghilangkan left recursion dan left factoring?

Alasan:

Top-Down Parsing merupakan salah satu metode yang digunakan untuk mencari leftmost derivation pada input suatu string. Selain itu, Top-Down Parsing juga dapat digunakan untuk membuat pars tree dari suatu input string yang dimulai dari root sampai dengan leaves dengan urutan preorder.

Ada 2 hal yang perlu diperhatikan pada Top-Down Parsing. Pertama, left recursive harus dihilangkan karena terdapat Metode Brute-Force. Ciri pada metode tersebut antara lain seperti memilih aturan produksi mulai dari kiri, meng-expand simbol non terminal hingga terminal. Sehingga apabila terjadi kesalahan, dalam hal ini string yang tidak sesuai maka dilakukan backtrack. Salah satu kelemahan yang ditemukan pada Metode Brute-Force adalah mencoba semua aturan produksi yang ada sehingga menjadi lambat. Hal tersebut menyebabkan grammar yang memiliki left recursive (rekursif kiri) mengalami loop secara terus-menerus. Kedua, berkaitan dengan left factoring. Left factoring dapat menghasilkan suatu grammar yang ambigu (ambiguity). Suatu kalimat disebut ambigu apabila terdapat lebih dari 1 pohon sintaks yang dapat dibentuk oleh kalimat tersebut.

www.binus.ac.id

TM1 Teknik Kompilasi

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

Cara 1 :

Followpos 1        :               1 , 2, 3, 5, 6
Followpos 2        :               2, 3, 5, 6
Followpos 3        :               4
Followpos 4        :               2, 3, 5, 6
Followpos 5        :               7
Followpos 6        :               7
Followpos 7        :               –

S0 = 1, 2, 3, 5, 6

Maka hasil DFAnya ialah :

DFA tersebut tidak dapat diminimisasi lagi.

Cara 2 : 

S0 ɛ closure = (0, 1, 3, 4, 5, 6, 11, 12, 14)

S0,a = (2, 13)           ɛ closure = (1, 2, 3, 4, 5, 7, 11, 12 ,14, 16) –> S1*
S0,b = (6, 15)          ɛ closure = (4, 5, 7, 10 ,11, 12 14, 16) –> S2*
S0,c = (8)                  ɛ closure = (ɸ) –> S3
S0,d = ɸ

S1,a = (2, 13) –> S1
S1,b = (6,15) –> S2*
S1,c = (8) –> S3
S1,d = ɸ

S2,a = (13)               ɛ closure (16) –> S4*
S2,b = (6, 15) –> S2*
S2,c = (8) –> S3
S2,d = ɸ

S3,a = ɸ
S3,b = ɸ
S3,c = ɸ
S3,d = (9)                  ɛ closure (10, 11, 12, 14) –> S5

S4,a = ɸ
S4,b = ɸ
S4,c = ɸ
S4,c = ɸ

S5,a = (13) –> S4
S5,b = (15) –> S2
S5,c = (8) –> S3
S5,c = ɸ

Maka hasil DFAnya:

Link Binus Website

Hello world!

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 🙂