CFG & CFLSTIKOM Artha Buana

Teknik Informatika

2014

Ir. Ahmad Haidaroh, M.Kom.2

Sentensial

• Turunan (derivation) yang masih memiliki

variabel (non-terminal) disebut dengan

bentuk sentensial.

• Contoh:

S AbA adalah Non Terminal

Contoh Sentensial• Dari aturan produksi (P):

S A1 | 0B

A 0B 1

• S A1 merupakan bentuk sentensial dari P.• S 0B merupakan bentuk sentensial dari P.• Karena A dan B bukanlah Non Terminal

Sentens

• Turunan (derivation) yang hanya memiliki

terminal disebut dengan sentens.

• Contoh:

S b

S 0

S 1

Contoh Sentens• Dari aturan produksi (P):

S A1 | 0B

A 0B 1

• S A1 01 merupakan sentens dari P.• S 0B 01 merupakan sentens dari P.

Pohon Penurunan (Parse Tree)• Turunan dapat juga dinyatakan

dalam bentuk tree/pohon.

• Sebagai root adalah simbol awal

(S).root

nodenode

Pohon Penurunan (Parse Tree)• Turunan dapat juga dinyatakan

dalam bentuk tree/pohon.

• Sebagai root adalah simbol awal

(S).

• Node dapat berupa terminal

atau variabel.

S

nodenode

Pohon Penurunan (Parse Tree)• Turunan dapat juga dinyatakan

dalam bentuk tree/pohon.

• Sebagai root adalah simbol awal

(S).

• Node dapat berupa terminal

atau variabel.

• Variabel harus diturunkan

sampai membentuk terminal.

S

aA

Pohon Penurunan (Parse Tree)• Turunan dapat juga dinyatakan

dalam bentuk tree/pohon.

• Sebagai root adalah simbol awal

(S).

• Node dapat berupa terminal

atau variabel.

• Variabel harus diturunkan

sampai membentuk terminal.

S

aA

a

Contoh:G = ({S, A}, {a,b}, P, S)P adalah:

S aASS aA SbAA SSA ba

Salah satu turunannya adalah aabbaa, buktikan dengan parse tree!

Contoh: PenyelesaianString aabbaa diperoleh melalui:

Aturan Produksi:S aASS aA SbAA SSA ba

S

a A S

S b A a

a b a

Contoh: PenyelesaianString aabbaa diperoleh melalui:

S

a A S

S b A a

a b a

Aturan Produksi:S aASS aA SbAA SSA ba

Latihan No.1Diketahui suatu CFG,

G = ({S}, {a,b}, P, S)

dengan P:

S aSb

S aSbb

S a. Buatlah bentuk sentens dari aabbb!

b. Gambarkan parse tree untuk aabb!

Latihan No.2Diketahui aturan produksi suatu CFG,

S 0A | 1B

A 0AA | 1S | 1

B 1BB | 0S | 0

a. Tuliskan quadruple dari CFG ini!

b. Buatlah derivation dari 001101 (LM dan RM)

c. Gambarkan parse tree untuk masing-masing derivation tersebut (LM dan RM)!

Latihan No.3Diketahui aturan produksi suatu CFG,

S AB | CD

A 0A1 | 01

B 2B | 2

C 0C | 0

D 1D2 | 12

a. Tuliskan quadruple dari CFG ini!

b. Buatlah derivation dari 012 (LM dan RM)

c. Gambarkan parse tree untuk masing-masing derivation tersebut (LM dan RM)!

Diketahui grammar G = {I H | IH | IA, H a|b|c|...|z, A 0|1|2|...|9}dengan I adalah simbol awal.

Latihan No.4

Berikut ini kedua cara analisa sintaks untuk kalimat x23b.

I IH IAHIAAH HAAHxAAH x2AHx23H x23b

cara 1 (Derivasi) cara 2 (Parsing)

Latihan No.5Diketahui grammar G = {S SOS|A , O *|+, A 0|1|2|...|9}Kalimat : 2*3+7 mempunyai dua pohon sintaks berikut :

Sebuah kalimat yang mempunyai lebih dari satu pohon sintaks disebut kalimat ambigu

S SOS AO *

+A 0

1 2 3 …..

Diketahui Grammar {S → S + S | S * S | angka, angka → 0 |1 |2 |3 |… |9}

Latihan No.6

kalimat ambigu

S S + S S * S angka

Angka 0 1 2 3 …..

Latihan No.6• Karena hasil keduanya tidak sama maka tidak dapat diimplementasikan pada pelajaran matematika.

• Untuk menyempurnakannya maka diberi tanda kurung = UNAMBIGOUS

S → (S + S) | (S * S) | angka

angka → 0 |1 |2 |3 …….| 9

Contoh• CFG

S → a S | S a | a

bentuk tree dari kata aaa

Ambiguous

Contoh

Perbaikan CFG diatas

S → a S | a UNAMBIGOUS

Contoh ImplementasiDiketahui CFG :

• S → * | + | Angka

• + → + + | + * | + Angka | * + | * * | * Angka | Angka + | Angka * | Angka Angka

• * → * * | + * | + Angka | * + | * * | * Angka | Angka + | Angka * | Angka Angka

• Angka → 0 | 1 | 3 | …… | 9

PREORDER * + * + 1 2 + 3 4 5 6 * + * + 1 2 7 5 6 * + * 3 7 5 6 * + 21 5 6 * 26 6 156

Contoh Implementasi

Contoh Implementasi

Diberikan Rule Grammar sebagai berikut1. S → x2. S → y3. S → z4. S → S + S5. S → S - S6. S → S * S7. S → S / S8. S → (S)

Diberikan string ( x + y ) * x – z * y / ( x + x )

Contoh Implementasi ( x + y ) * x – z * y / ( x + x )

1. S → x2. S → y3. S → z4. S → S + S5. S → S - S6. S → S * S7. S → S / S8. S → (S)

Rules

Parsing Tree