Tugas Teknik Kompilasi Code Generator – Menentukan Jarak Dari Titik Ke Lingkaran
Soal Kuis 20 Mei 2014 :
Tentukan apakah dari sebuah titik sembarangan ada didalam, bersinggungan atau diluar lingkaran yang dihasilkan dari sebuah titik sembarang dengan jari-jari R
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 :
- Mov x1, r0
- Mov x2, r1
- Sub r1, r0
- Mul r0, r0
- Mov r0, selisihx
- Mov y1, r2
- Mov y2, r3
- Sub r3, r2
- Mul r2, r2
- Mov r2, selisihy
- Add selisihy, selisihx
- Mov selisihx, totalselisih
- Mov R, r4
- Mul r4, r4
- Gt totalselisih, r4
- Jmpf totalselisih, 19
- Prt “Titik di dalam lingkaran”
- Jmp , 24
- Lt totalselisih, r4
- Jmpf , 23
- Prt “Titik di luar lingkaran”
- Jmp 24
- Prt “Titik bersinggungan dengan lingkaran”
- ……
Teknik Kompilasi – Quiz 1 April
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 :
a |
b |
+ |
– |
( |
) |
* |
$ |
|
S |
S -> ASˈˈ |
S -> B*AS |
||||||
Sˈ |
Sˈ -> +ASˈ |
Sˈ -> ASˈ |
Sˈ -> ԑ |
|||||
Sˈˈ |
Sˈˈ -> +SSˈ |
Sˈˈ -> -SSˈ |
||||||
B |
B -> aBˈˈ |
B -> bBˈ |
||||||
Bˈ |
Bˈ -> aBˈ , Bˈ -> ԑ |
Bˈ -> (a+B)Bˈ , Bˈ -> ԑ |
Bˈ -> ԑ |
Bˈ -> ԑ |
||||
Bˈˈ |
Bˈˈ -> BBˈ |
Bˈˈ -> BBˈ |
Bˈˈ -> (a+B)Bˈ |
|||||
A |
A -> a |
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 Produksi dari hasil diatas :
|
id |
if |
else |
[ |
( |
const |
+ |
– |
* |
/ |
: |
) |
] |
$ |
S |
S->V:=E |
S->if E then S S’ |
|
|
|
|
|
|
|
|
|
|
|
|
S’ |
|
|
S’->else S
|
|
|
|
|
|
|
|
|
|
|
S’-> ε |
V |
V->idV’ |
|
|
|
|
|
|
|
|
|
|
|
|
|
V’ |
|
|
|
V’->[E]
|
|
|
|
|
|
|
V’-> ε |
|
|
|
E |
E->TE’ |
|
|
|
E->TE’ |
E’->TE’ |
|
|
|
|
|
|
|
|
E’ |
|
|
|
|
|
|
E’->+TE’
|
E’->-TE’
|
|
|
E’-> ε |
E’-> ε |
|
|
T |
T->FT’ |
|
|
|
T->FT’ |
T->FT’ |
|
|
|
|
|
|
|
|
T’ |
|
|
|
|
|
|
T’-> ε |
T’-> ε |
T’-> *FT’ |
T’-> /FT’ |
|
T’-> ε |
T’-> ε |
|
F |
F->V |
|
|
|
F->(E) |
F->const |
|
|
|
|
|
|
|
|
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
|
a |
b |
+ |
$ |
S |
S -> a=A |
|
|
|
A |
A -> aA’ |
A ->bA’ |
|
|
A’ |
|
|
A’ -> +AA’ , A’-> ԑ |
A’ -> ԑ |
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
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 -> bf bt’ |
3 |
bf bt’ be’$ |
not (true or false) and true and true and false not (false) true$ |
bf -> not bf |
4 |
not 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 |
(be) 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 |
true bt’ be’ ) bt’ be’$ |
true 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 |
or bt be’ ) bt’ be’$ |
or 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’$ |
false) 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$ |
bt’ -> ԑ |
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 bt’ |
21 |
and bf bt’ be’$ |
and 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’$ |
true 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’$ |
and true and false not (false) true$ |
Pop and |
26 |
bf bt’ be’$ |
true and false not (false) true$ |
bf -> true |
27 |
true bt’ be’$ |
true and false not (false) true$ |
Pop true |
28 |
bt’ be’$ |
and false not (false) true$ |
bt’ -> and bf bt’ |
29 |
and bf bt’ be’$ |
and false not (false) true$ |
Pop and |
30 |
bf bt’ be’$ |
false not (false) true$ |
bf -> false |
31 |
false bt’ be’$ |
false not (false) true$ |
Pop false |
32 |
bt’ be’$ |
not (false) true$ |
Rejected |
Tugas Analisis Design Database Sosial Media
Create Table dengan menggunakan Keyword SQL
Berikut ini merupakan contoh query dalam SQL dengan menggunakan keyword (VIEW) sebagai nama sebuah entity atau table.
Dari percobaan di atas dapat dilihat bahwa query tersebut tidak bisa dijalankan dan menghasilkan error. Hal ini dikarenakan VIEW merupakan salah satu keyword SQL, dan tidak dapat digunakan sebagai nama sebuah entity atau table.
Apabila kita tetap ingin menggunakan keyword tersebut sebagai nama sebuah entity atau table. Maka, solusinya yaitu kita harus menuliskan keyword tersebut ke dalam square brackets ( [] ), atau bisa juga dengan menambahkan underscore ( _ ).
Contoh :
Dari hasil contoh tersebut dapat kita lihat bahwa cara tersebut berhasil dan query dapat dijalankan dengan sempurna.
Teknik Kompilasi TM 2
Soal :
Mengapa Top Down Parsing harus menghilangkan left-recursion & left-factoring?
Jawab :
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 dan akan bersifat ambigu.
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.
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
Web Database – Tugas GSLC 1
Edwin Anderson Loho
1501148942
06PFT
Session 1 – Web Database Environment
Data and Information
Data adalah kumpulan kejadian yang diangkat dari suatu kenyataan (fakta), dimana dapat berupa angka-angka, huruf, simbol-simbol khusus, atau gabungan dari ketiganya.
Informasi adalah sekumpulan data/fakta yang diorganisasi atau diolah dengan cara tertentu sehingga mempunyai arti bagi penerima.
Functional Requirement merupakan penjelasan tentang layanan yang perlu disediakan oleh sistem, bagaimana sistem menerima dan mengolah masukan, dan bagaimana sistem mengatasi situasi-situasi tertentu. Selain itu kadang-kadang juga secara jelas menentukan apa yang tidak dikerjakan oleh sistem.
Non-functional Requirement secara umum berisi batasan-batasan pada pelayanan atau fungsi yang disediakan oleh sistem. Termasuk di dalamnya adalah batasan waktu, batasan proses pembangunan, standar-standar tertentu.
Business rules merupakan batasan/ketentuan yang dapat menjaga integritas/keabsahan data perusahaan untuk menjamin sistem dapat berjalan seperti yang diharapkan.
Database atau basis data adalah kumpulan data yang disimpan secara sistematis di dalam komputer dan dapat diolah atau dimanipulasi menggunakan perangkat lunak (program aplikasi) untuk menghasilkan informasi.
Database schema adalah deskripsi database yang diberikan selama proses pendesainan database.
Database instance adalah struktur proses dan memory yang menjalankan sistem database (DBMS -> Database Management System).
Metadata adalah data yang mendiskripsikan struktur dan penggunaan informasi dan juga menggambarkan suatu sistem untuk mengelola informasi tersebut.
Web Database Technology
Web server adalah perangkat lunak yang dipasang dalam sebuah server berguna untuk menyediakan layanan permintaan data dengan protokol http atau https yang diakses melalui aplikasi tertentu seperti web browser. Web server merespon permintaan dengan mengirimkan kembali konten berupa gambar, tulisan atau lainya dan kemudian menampilkanya melalui browser.
Database Management System (DBMS) merupakan suatu sistem software yang memungkinkan seorang user dapat mendefinisikan, membuat, dan memelihara serta menyediakan akses terkontrol terhadap data.
Database client merupakan suatu perangkat lunak yang digunakan oleh end user untuk berinteraksi dengan DBMS.
Static and Dynamic Web Content
Pengertian Web Statis dan Web Dinamis
1. Web Statis
Web statis adalah website yang mana pengguna tidak bisa mengubah konten dari web tersebut secara langsung menggunakan browser. Interaksi yang terjadi antara pengguna dan server hanyalah seputar pemrosesan link saja. Halaman-halaman web tersebut tidak memliki database, data dan informasi yang ada pada web statis tidak berubah-ubah kecuali diubah sintaksnya. Dokumen web yang dikirim kepada client akan sama isinya dengan apa yang ada di web server.
Contoh dari web statis adalah web yang berisi profil perusahaan. Di sana hanya ada beberapa halaman saja dan kontennya hampir tidak pernah berubah karena konten langsung diletakan dalam file HTML saja.
2. Web Dinamis
Dalam web dinamis, interaksi yang terjadi antara pengguna dan server sangat kompleks. Seseorang bisa mengubah konten dari halaman tertentu dengan menggunakan browser. Request (permintaan) dari pengguna dapat diproses oleh server yang kemudian ditampilkan dalam isi yang berbeda-beda menurut alur programnya. Halaman-halaman web tersebut memiliki database. Web dinamis, memiliki data dan informasi yang berbeda-beda tergantung input apa yang disampaikan client. Dokumen yang sampai di client akan berbeda dengan dokumen yang ada di web server.
Contoh dari web dinamis adalah portal berita dan jejaring sosial. Lihat saja web tersebut, isinya sering diperbaharui (di-update) oleh pemilik atau penggunanya. Bahkan untuk jejaring sosial sangat sering di-update setiap harinya.
Perbedaan Web Statis dan Web Dinamis
– Interaksi antara pengunjung dan pemilik web
Dalam web statis tidak dimungkinkan terjadinya interaksi antara pengunjung dengan pemilik web. Sementara dalam web dinamis terdapat interaksi antara pengunjung dengan pemilik web seperti memberikan komentar, transaksi online, forum, dll.
– Bahasa Script yang digunakan
Web statis hanya menggunakan HTML saja, atau paling tidak bisa ditambah dengan CSS. Sedangkan web dinamis menggunakan bahasa pemrograman web yang lebih kompleks seperti PHP, ASP dan JavaScript.
– Penggunaan Database
Web statis tidak menggunakan database karena tidak ada data yang perlu disimpan dan diproses. Sedangkan web dinamis menggunakan database seperti MySQL, Oracle, dll untuk menyimpan dan memproses data.
– Konten
Konten dalam web statis hanya diberikan oleh pemilik web dan jarang di-update, sementara konten dalam web dinamis bisa berasal dari pengunjung dan lebih sering di-update. Konten dalam web dinamis bisa diambil dari database sehingga isinya pun bisa berbeda-beda walaupun kita membuka web yang sama.
Distributed Database
Centralized Database system adalah database yang dikontrol secara terpusat.
Distributed database system yaitu database yang ada tersebar pada masing-masing terminal yang saling berhubungan lewat jalur komunikasi.
Distributed database system terdiri atas 2 macam, yaitu :
Homogenous Distributed merupakan suatu database terdistribusi, dimana data di distribusikan pada beberapa komputer dengan menggunakan DBMS(database management system) yang sama.
Heterogenous Distributed adalah kebalikan dari Homogenous, dimana data di sebarkan dengan menggunakan DBMS yang berbeda.
Session 2 – Network, Database and Web Technology
DML and DDL
Data manipulation languages (DML) adalah bahasa untuk melakukan manipulasi terhadap data di dalam database seperti insert, update, dan delete record.
DML dibagi menjadi dua, yaitu Procedural DML dan Non Procedural DML.
Procedural DML digunakan untuk memberi tahu sistem, data apa yang dibutuhkan dan bagaimana cara mengambil data tersebut. Procedural DML di embed ke dalam bahasa pemrograman tingkat tinggi.
Contoh Procedural DML Menggunakan Java :
try{
Statement st = connection.createStatement();
ResultSet rs = st.executeQuery(“SELECT * FROM mahasiswa”);
while(rs.next){
String s = rs.getString(1);
//dst…
}
} catch(SQLException e){}
Baris Resultset menyatakan data apa yang dibutuhkan, dimana di dalam baris tersebut terdapat query SQL : SELECT * FROM mahasiswa. Sedangkan baris while ke bawah menyatakan cara untuk mengambil data tersebut.
Non Procedural DML
Non Procedural DML digunakan untuk menyatakan data apa yang dibutuhkan, bukan bagaimana data tersebut diambil. Non procedural disebut juga dengan declarative programming.
Contoh Non Procedural DML di dalam statement SQL :
Data Definition Language (DDL) adalah bahasa dalam DBMS yang digunakan untuk membuat atau mendefinisikan obyek-obyek di dalam database. Secara umum digunakan untuk membuat obyek table dan view.
Secara khusus, di dalam DBMS tertentu digunakan untuk :
- Membuat trigger
- Membuat stored procedure
- Membuat database, index, rule, schema dll (tergantung DBMS)
Contoh sintaks DDL :
DDL untuk tabel
* Untuk membuat tabel
CREATE TABLE <namatabel> (
<column_definition> | <table_constraint>
)
* Untuk menghapus tabel
DROP TABLE <namatabel>
* Untuk memodifikasi tabel
– Menambahkan kolom baru
ALTER TABLE <namatabel>
ADD <namakolom> <tipedata> <aturan>
– Menghapus kolom
ALTER TABLE <namatabel>
DROP <namakolom>
DDL untuk view
* Untuk membuat view
CREATE VIEW <namaview> AS <SQLQuery>
* Untuk menghapus view
DROP VIEW <namaview>
DDL untuk trigger
* Untuk membuat trigger
CREATE TRIGGER <namatrigger> ON TABLE <namatabel> ON [DELETE] [,] [INSERT] [,] [UPDATE] AS <perintahSQL>
Teknik Kompilasi TM 1
Soal :
Buatlah Soal RE dan konversikan ke DFA dengan ketentuan sebagai berikut :
- Jumlah State DFA min 5 dan max 8.
- Jumlah Final State DFA min 2 dan max 3.
Tentukan : RE, ε-NFA, DFA, dan Min DFA
———————————————————————————————————–
Jawaban :
Melalui cara follow post ternyata langsung didapat DFA minimizednya :
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 🙂