Kuis Teknik Kompilasi (1 April 2014)

Diketahui:

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

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

A -> a

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,)}

nomor1

Diketahui:

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]

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’) = {:}

nomor2

Diketahui:

S -> a=A

A-> aA’|bA’

A’-> +AA’|ε

Jawab:

First S ={a}

First A={a,b}

First A’={+, ε }

Follow S={$}

Follow A={$,+}

Follow A’={$,+}

nomor3

Diketahui:
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

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}

nomor4

No

Stack

Input

Output

1

be$

not(true or false) and true

and true and

false not (false) true$

be > bt be

2

bt be’$

not(true or false)

and true and true

and false not (false) true$

bt -> or bt’

3

bf bt’ be’$

not(true or false) and

true and true

and false not (false) true$

bf -> not bf

4

bf bt’ be’$

not(true or false) and

 true and true

and false not (false) true$

pop not

5

bf bt’ be’$

(true or false) and true

and true and

false not (false) true$

bf -> (be)

6

bt’ be’$

true or false) and

true and true

and false not (false) true$

pop (

7

be) bt’ be’$

true or false) and

true and true and

false not (false) true$

be -> bt be’

8

bt be’ ) bt’ be’$

true or false) and

true and true

and false not (false) true$

bt -> bf bt’

9

bf bt be’ ) bt’ be’$

true or false) and true

and true and

false not (false) true$

bf -> true

10

bt’ be’ ) bt’ be’$

or false) and true

and true and

false not (false) true$

pop true

11

bt’ be’ ) bt’ be’$

or false) and true and

true

and false not (false) true$

bt’ -> ε

12

be’ ) bt’ be’$

or false) and true

and true

and false not (false) true$

be -> or  bt be’

13

bt be’ ) bt’ be’$

false) and

true and

true and

false not (false) true$

pop or

14

bt be’ ) bt’ be’$

false) and true

and true and

false not (false) true$

bt -> bf bt’

15

bf bt’ be’ ) bt’ be’$

false) and true and

true and false not (false) true$

bf -> false

16

false bt’ be’ ) bt’ be’$

) and true

and true

and false not (false) true $

pop false

17

bt’ be’ ) bt’ be’$

) and true

and true and false not (false) true $

be’->ε

18

be’ ) bt’ be’$

) and true

and true

and false not (false) true $

be’->ε

19

 ) bt’ be’$

 and true

and true

and false not (false) true $

pop )

20

bt’ be’$

 and true and

true and

false not (false) true $

bt’->and bf br’

21

and bf  bt’ be’$

true and true

and false not (false) true $

pop and

22

bf  bt’ be’$

true and true and false

not (false) true $

bf->true

23

true  bt’ be’$

and true and false

not (false) true $

pop true

24

bt’ be’$

and true and false

not (false) true $

bt’ -> and bf bt’

25

and bf  bt’ be’$

true and false

not (false) true $

pop and

26

bf  bt’ be’$

true and false

not (false) true $

bf -> true

27

true  bf  bt’ be’$

and false

not (false) true $

pop true

28

bt’ be’$

and false

not (false) true $

bt’ -> and bf bt’

29

and  bf  bt’ be’$

false not (false)

true $

pop and

30

bf  bt’ be’$

false not (false)

true $

bf -> false

31

false  bf  bt’ be’$

 not (false)

true $

pop false

32

bt’ be’$

 not (false)

true $

rejected

www.binus.ac.id

Analisis Entity Relationship Diagram Twitter

ERD_twitterKeterangan dari gambar ERD diatas :

Tabel MsUser menampung data-data user seperti userId, fullName, email, password, username, totalFollowing, dan totalFollower.

Tabel Interaction merupakan table yang dapat berhubungan dengan table MsUser, Following, Tweet, DirectMessage. Tabel Interaction menggambarkan interaksi-interaksi yang dapat dilakukan oleh user seperti MsUser, Following, Tweet, DirectMessage.

Tabel Following berisi interactionId, followingId, followingStatus. Tabel ini menggambarkan bahwa user dapat melakukan following dengan user lain serta mengetahui status apakah sudah following dengan user lain atau belum.

Tabel Tweet berisi interactionId, tweetId, tweetTime. Tabel ini menggambarkan bahwa user dapat melakukan jenis interaksi berupa tweet dan mengetahui waktu saat user melakukan suatu tweet. Di samping itu, tabel Tweet juga terhubung dengan tabel tweetText, tweetPhoto, tweetMap. Hal tersebut menunjukkan bahwa user dapat melakukan tweet seperti text, photo dan lokasi dari user.

Tabel Direct_Message terdiri dari interactionId, messageId, messageContent, dan messageTime. Tabel ini menunjukkan bahwa interaksi lain yang dapat dilakukan oleh user yaitu mengirim dan menerima pesan kepada user lain dalam bentuk direct message.

Tabel TweetText terdiri dari tweetTextId, tweetTextContent, tweetId, dan interactionId. Tabel ini berfungsi untuk menampung tweet-tweet yang dilakukan oleh user dalam hal ini text.

Tabel TweetPhoto terdiri dari tweetPhotoId, tweetPhotoContent, tweetId, dan interactionId. Tabel ini berfungsi untuk menampung tweet-tweet yang dilakukan oleh user dalam hal ini photo.

Tabel TweetMap terdiri dari tweeMapId, tweetMapLink, tweetId, dan interactionId. Tabel ini berfungsi untuk menampung tweet-tweet yang dilakukan oleh user berupa lokasi user.

www.binus.ac.id

Create Table dengan Keyword “GROUP BY”

“GROUP BY” merupakan klausa (clause) yang terdapat pada SQL dan digunakan untuk agregasi data berdasarkan group (pengelompokan) suatu kolom dengan pernyataan SELECT. Di samping itu, keyword tersebut dapat digunakan sebagai nama suatu tabel. Namun, perlu diketahui bahwa keyword “GROUP BY” sudah ada pada SQL (reserved keyword).

Langkah-langkah untuk membuat tabel dengan nama “GROUP BY” antara lain:

1. Membuat table terlebih dahulu

satu

Pada gambar di atas, Create Table gagal atau tidak bisa dilakukan karena nama table yang digunakan adalah “GROUP BY”. GROUP BY merupakan reserved keyword. Sehingga pada gambar di atas, kata ” GROUP BY “ dikenali sebagai syntax yang terdapat di dalam SQL. Untuk mengatasi hal tersebut, maka harus memperbaiki nama tabel dengan menambahkan tanda “[ ]” sehingga menjadi “[ nama tabel ]”.

2. Memperbaiki nama table

dua

Pada gambar di atas, perlu ditambahkan tanda “[ ]” pada syntax Create Table sehingga CREATE TABLE GROUP BY diubah menjadi CREATE TABLE [GROUP BY]. Dengan menambahakn tanda “[ ]” pada proses CREATE TABLE maka tidak terjadi error lagi dan tabel dengan nama ” GROUP BY “ berhasil dibuat.

3.Menampilkan isi tabel yang bernama ” GROUP BY

tiga

Gambar di atas menampilkan data-data yang ada pada tabel ” GROUP BY “. Namun data tersebut masih kosong, sehingga perlu dilakukan proses INSERT data ke dalam tabel tersebut.

4. Melakukan INSERT data ke dalam tabel ” GROUP BY “

empat

Kemudian melakukan proses INSERT data ke dalam tabel ” GROUP BY “ maka terdapat tulisan “1 row(s) affected”. Artinya, kita sudah berhasil melakukan proses INSERT data ke dalam tabel tersebut.

5. Menampilkan kembali data pada tabel ” GROUP BY “

lima

Menampilkan kembali semua data yang telah di-insert pada tabel “GROUP BY” dengan query “SELECT * FROM [GROUP BY]”.

Referensi :

http://technet.microsoft.com/en-us/library/ms189822.aspx

http://fairuzelsaid.wordpress.com/2012/06/10/sql-klausa-group-by/

www.binus.ac.id

Data Model

1. Data and Type Data

Data Model merupakan suatu fakta yang menarik bagi organisasi yang disimpan dalam database.

Value merupakan data aktual atau yang sebenarnya yang disimpan dan biasanya berupa angka biner.

Literal merupakan sebuah representasi yang dapat dibaca oleh manusia mengenai suatu nilai.

Variable merupakan wadah atau tempat (container) yang diberi nama untuk menyimpan nilai.

Operator digunakan untuk menggabungkan nilai-nilai yang diwakili oleh literal dan variable. Dibutuhkan satu atau lebih nilai sebagai masukan (input), kemudian mengubahnya dengan beberapa cara dan output nilai tunggal. Nilai tunggal tersebut belum tentu dari tipe data yang sama sebagai masukan.

Sebuah operator perbandingan mengambil nilai-nilai dari tipe data tunggal, membandingkannya dalam beberapa cara dan mengembalikan nilai boolean untuk menunjukkan apakah masukan memenuhi atau tidak memenuhi saat uji perbandingan.

Expression adalah kombinasi yang valid dari literal, variable dan operator.

Type Data merupakan sekumpulan nilai-nilai pada data yang diberi nama.

System-Defined Types dibangun kedalam DBMS sehingga tersedia untuk setiap aplikasi. User-Defined Types diciptakan oleh database designer atau database administrator (DBA) untuk memenuhi aplikasi tertentu dan mungkin tidak dapat diakses oleh semua aplikasi database.

2. Relational Data Model

Model Data Relasional (Relational Data Model) adalah suatu model basis data yang menggunakan tabel dua dimensi yang terdiri dari baris dan kolom untuk menggambarkan berkas data.

Model Data Relasional digunakan untuk menunjukkan cara mengelola atau mengorganisasikan data secara fisik dalam memori sekunder yang akan berdampak dalam mengelompokkan data dan keseluruhan data yang terkait dengan sistem yang akan dibuat.

Beberapa keuntungan dari model data relasional antara lain:

  • Bentuknya sederhana.
  • Mudah untuk melakukan berbagai operasi data (query, insert, update, delete).

Contoh DBMS yang mengelola basis data relasional seperti Ms.Access, DB2, Oracle.

Relational Model Terminology

Relational Model Terminology

Relational Model Terminology:

  • Relation (relasi) direpresentasikan sebagai table yang terdiri dari baris dan kolom. Diaplikasikan pada struktur logical bukan physical.
  • Attributes (atribut) adalah nama kolom pada table.
  • Tuple merupakan baris pada table (record).
  • Domain merupakan himpunan nilai dari satu atau lebih atribut.
  • Degree adalah banyaknya atribut atau kolom pada table.
  • Cardinality adalah banyaknya tuple atau baris pada tabel.
  • Relational database merupakan kumpulan relasi ternormalisasi dengan nama relasi yang jelas dan dapat dibedakan.

Sifat-sifat relasi terdiri dari:

  • Nama relasi berbeda satu sama lain dalam skema relasional.
  • Setiap sel (baris, kolom) dari relasi berisi satu nilai atomik.
  • Setiap atribut memiliki nama yang berbeda.
  • Nilai suatu atribut berasal dari domain yang sama.
  • Setiap tuple berbeda, dan tidak ada duplikasi tuple.

Kunci-Kunci (Keys) Relasional (Relational Keys) antara lain:

  • Superkey merupakan sebuah atribut atau himpunan atribut yang mengidentifikasi secara unik tuple-tuple yang ada dalam relasi.
  • Candidate key merupakan atribut dalam relasi yang mempunyai nilai unik.
  • Primary key adalah candidate key yang dipilih untuk mengidentifikasi tuple secara unik dalam suatu relasi.
  • Alternate keys adalah candidate key yang tidak terpilih sebagai primary key.
  • Foreign key merupakan himpunan atribut dalam relasi yang disesuaikan (matching) dengan candidate key pada beberapa relasi.

Relational Integrity

  • Null merepresentasikan nilai untuk atribut yang tidak diketahui atau tidak digunakan atau tidak tersedia untuk suatu tuple. Null berkaitan dengan ketidaklengkapan atau pengecualian data.
  • Entity integrity. Pada relasi dasar, tidak ada atribut ataupun primary key yang bernilai NULL.
  • Referential integrity. Jika terdapat foreign key dalam suatu relasi, maka nilai foreign key tersebut harus sesuai (match) dengan nilai candidate key dari beberapa tuple pada database atau nilai foreign key harus NULL seluruhnya.
  • Enterprise constraint merupakan aturan tambahan yang dispesifikasikan oleh user atau DBA.

Referensi

http://putthat.files.wordpress.com/2011/11/picture38.png

http://prastiyotunggal.wordpress.com/basis-data-2/

 

www.binus.ac.id

TM 2 Teknik Kompilasi

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 ParsingPertama, 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