IF-UTAMA 1. Penurunan (Derivation) [2] Penurunan (Derivation) Contoh Penurunan [1] Parse Tree [1]

Penurunan (Derivation) [2] • Berfungsi untuk menggambarkan atau mengetahui bagaimana memperoleh suatu string dari dari suatu tata bahasa dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal. • Proses penurunan dilakukan dengan cara : – Leftmost derivation : simbol variabel paling kiri yang diturunkan terlebih dahulu – Rightmost derivation : simbol variabel paling kanan yang diturunkan terlebih dahulu

• Jenis Penurunan – Derivation string / Penurunan String : dimulai dengan simbol awal dan menggunakan tanda “⇒” yang menunjukan hasil penurunannya. – Derivation tree / Pohon Penurunan, disebut juga derivation (parse) tree : root dari pohon penurunan adalah simbol awal, sedangkan node (daun) dari pohon penurunan adalah simbol-simbol non terminal atau terminal dari tata bahasa tersebut atau kemungkinan simbol ε

Penurunan (Derivation) Pertemuan : 5 Dosen Pembina : Danang Junaedi IF-UTAMA

1

IF-UTAMA

Parse Tree [1]

Contoh Penurunan [1] Misalkan diketahui sebuah context free grammar G3 dengan aturan produksi sebagai berikut: E→E+E E→E-E E → (E) E→V V→x V→z V→y Bagaimana cara menurunkan string x+(y-z)?

Formally, let G = (V, T, P, S) be a CFG, a parse tree for G must be such that: • Every vertex has a label from V∪T ∪{ε}. • The root is labeled S. • The label of any internal vertex is in V. • If a vertex is labeled ε, it must be a leaf and has no sibling. • If a vertex is labeled A and its children are labeled X1, X2, ..., Xk from left to right, then A → X1 X2 … X3 is a production in P.

IF-UTAMA

IF-UTAMA

2

3

IF-UTAMA

4

1

Contoh Penurunan (contd) Kita bisa membuat pohon penurunan sebagai berikut :

CFG G3: E → E + E | E - E | (E) | V V→x|y|z

E

V ( E ) x E - E V

y

z

Leftmost Derivation E⇒E+E ⇒V+E ⇒x+E ⇒ x + (E) ⇒ x + (E - E) ⇒ x + (V - E) ⇒ x + (y - E) ⇒ x + (y - V) ⇒ x + (y - z)

Derivation String: E⇒E+E ⇒V+E ⇒x+E ⇒ x + (E) ⇒ x + (E - E) ⇒ x + (V - E) ⇒ x + (y - E) ⇒ x + (y - V) ⇒ x + (y - z)

E + E

V

Contoh Penurunan (contd)

String x+(y-z) diperoleh dengan cara membaca node daun) dari cabang paling bawah kiri ke kanan.

IF-UTAMA

V

y

z

y

z

IF-UTAMA

6

Ambiguity [1]

• Each parse tree has one unique leftmost derivation and one unique rightmost derivation. • A grammar is ambiguous if some strings in it have more than one parse trees, i.e., it has more than one leftmost derivations (or more than one rightmost derivations). • Consider the following grammar G: S → AS | a | b A → SS | ab A string generated by this grammar can have more than one parse trees. Consider the string abb:

S A

IF-UTAMA

V

5

Ambiguity [1]

S a

E Rightmost derivation E⇒E+E E + E ⇒ E + (E) E + E ⇒ E + (E - E) ⇒ E + (E - V) ( E ) V V ( E ) ⇒ E + (E - z) ⇒ E + (V - z) E - E x x E - E ⇒ E + (y - z) ⇒ V + (y - z) V V ⇒ x + (y - z) E

As another example, consider the following grammar: E → E + E | E * E | (E) | x | y | z There are 2 leftmost derivations for x + y + z: E E

S b

A a IF-UTAMA

b

E

+ z E⇒E+E ⇒x+E ⇒x+E+E ⇒x+y+E ⇒x+y+z

S

b

+ E

x y

S S

E

b 7

x

+ E z

+ y E⇒E+E ⇒E+E+E ⇒x+E+E ⇒x+y+E ⇒x+y+z IF-UTAMA

8

2

Ambiguity [1]

Studi Kasus [1]

• Note that a CFL L can be generated by several different grammars, e.g., the language L={anbm | n > m > 0) can be generated by both G1 and G2: G1: S → aS’b S’→ aS’b|A A → aA|a G2: S → AB A → aA|a B → aBb|ab • A CFL L is said to be inherently ambiguous if all its grammars are ambiguous. If any one of them is unambiguous, L is unambiguous.

1. Consider the grammar of an if-statement: <stat>

→ → → →

if then <stat> if then <stat> else <stat> P|Q | R | S

Consider the following if-statement: if P then if Q then R else S This grammar is ambiguous since the above statement can have two parse trees. What are they?

2. Consider the grammar: S → aB | bA A → a | aS | bAA B → b | bS | aBB – Generate 4 strings from this grammar. – Do you know what language does this CFG represent?

IF-UTAMA

IF-UTAMA

Penyederhanaan [5]

Penyederhanaan [5] (contd)

• Tujuan : Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti. • Contoh : S
AB | a A
a Kelemahan CFG di atas, aturan produksi S
AB tidak berarti karena B tidak memiliki penurunan. • Untuk CFG berikut : S
A A
B B
C C
D D
a|A Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S
a, produksi D
A juga menyebabkan kerumitan.

• Suatu CFG dapat disederhanakan dengan melakukan : 1. Penghilangan produksi ε 2. Penghilangan produksi unit 3. Penghilangan produksi useless (tidak berguna)

IF-UTAMA

IF-UTAMA

9

11

IF-UTAMA

10

12

3

Penghilangan Produksi ε [5]

Penghilangan Produksi ε [5] (contd)

• Produksi ε adalah produksi dalam bentuk α
ε • Atau bisa dianggap sebagai produksi kosong (empty). • Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε, atau biasa disebut nullable. • Contoh S
bcAd A
ε A nullable serta A
ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan Hasil penyederhanaan tata bahasa bebas konteks menjadi: S
bcd

•

IF-UTAMA

13

IF-UTAMA

Penghilangan Produksi Unit [5]

Penghilangan Produksi Unit [5] (contd)

• Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan: A
B, C
D. • Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu. • Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit. • Contoh: S
Sb S
C C
D C
ef D
dd Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘⇒’ dibaca ‘menjadi’): C
D => C
dd S
C => S
dd | ef Sehingga aturan produksi setelah penyederhanaan: S
Sb S
dd | ef

• Contoh: S
A S
Aa A
B B
C B
b C
D C
ab D
b Penggantian yang dilakukan : – C
D => C
b – B
C => B
b | ab, karena B
b sudah ada, maka cukup dituliskan B
ab – A
B => A
ab | b – S
A => S
ab | b – Sehingga aturan produksi setelah penyederhanaan: S
ab | b S
Aa A
ab | b

IF-UTAMA

IF-UTAMA

•

Contoh S
bcAd A
bd | ε – A nullable, tapi A
ε bukan satu-satunya produksi dari A – hasil penyederhanaan: S
bcAd | bcd A
bd Contoh S
Ab | Cd A
d C
ε – Variabel yang nullable adalah variabel C. – Karena penurunan C
ε merupakan penurunan satusatunya dari C, maka kita ganti S
Cd menjadi S
d – Kemudian produksi C
ε kita hapus. – Setelah penyederhanaan menjadi: S
Ab | d A
d

15

IF-UTAMA

14

16

4

Penghilangan Produksi Useles [5]

Penghilangan Produksi Useles [5] (contd)

• Produksi useless didefinisikan sebagai : – Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya. – Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih) • Contoh : S
aSa | Abd | Bde A
Ada B
BBB | a Maka : – Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan – Konsekuensi : aturan produksi S
Abd tidak memiliki penurunan – Penyederhanaan menjadi: S
aSa | Bde B
BBB | a

•

IF-UTAMA

A
ab | D E
aEa

B
b | E

– Aturan produksi A
D, simbol variabel D tidak memiliki penurunan. – Aturan produksi C
bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah mencapai C – Simbol variabel E tidak memiliki aturan produksi yang menuju terminal – Konsekuensi no (3) Aturan produksi B
E, simbol variabel E tidak memiliki penurunan.

Maka produksi yang useless: A
D C
bb Penyederhanaannya menjadi: S
Aa | B A
ab 17

Referensi

Buat penyederhanaan untuk aturan-aturan produksi berikut ini : 1.Aturan Produksi 1 : S
aAb | cEB A
dBE | eeC B
ff C
ae D
h 2.Aturan Produksi 2 : S
Cba | D A
bbC B
Sc | ddd C
eAn | f | C D
E | SABC E
gh 3.Aturan Produksi 3 : S
AaCD A
CD | AB B
b|ε C
d|ε D
ε Berdasarkan ke tiga aturan di atas buat string hasil penurunannya

1. 2. 3. 4. 5.

19

E
aEa

B
E

B
b

IF-UTAMA

Studi Kasus

IF-UTAMA

IF-UTAMA

Contoh : S
Aa | B C
bb Maka :

18

http://www.cse.cuhk.edu.hk/~csc3130/ Swinglly Purba, “Otomata dan Bahasa Formal”, Graha Ilmu,Yogyakarta, 2008 Firrar Utdirartatmo, “Teori Bahasa dan Otomata”, Graha Ilmu, Yogyakarta, 2005 Roni Djuliawan, M.T., “Diktat & Handout Kuliah Teori Bahasa & Otomata”, Teknik Informatika – Universitas Widyatama, 2003 http://idhaclassroom.com/download/TeknikOtomasi-Bahasa-Kompilasi/BahasaKompilasi.pdf

IF-UTAMA

20

5