GRAMMAR

      Mendefenisikan Programming Language

      Formalitas Konsep Parsing

      Mendefenikan Ekspresi Aritmatika

Komponen Context Free Grammar :

Ø  Non-terminal/syntactvic category/variable

Ø  Terminal/value

Ø  Production : aturan yang menghubungkan variable dengan variable, variable dengan terminal

Ø  Symbol production :

Contoh production:

a)      (kalimat)(subjek) (predikat) [(objek)]

b)      (subjek)(kata benda)

c)      (predikat)(kata kerja)

d)     (objek)(kata benda)

e)      (kata benda)kucing|nasi |orang

f)       (kata kerja)makan memukul ; dimana(...) :variable ;|:pillihan

Secara formal CFG ditunjukan oleh :

 

            G = (V , T , P, S )
Dimana :

V : Himpunan variabel (non terminal)

T : Himpunan terminal V  T =  (disjoint)

P : Himpunan Produksi : A a

            A : Variabel, a(v  T )

S : Star Simbol

Aplikasi produksi diatas secra terulang akan menghasilkan suatu kalimat yang utuh, misalnya:

“ Kucing Makan Kucing “

Contoh :

 Derivasi :

<kalimat>è<subjek><predikat>

è<subjek><predikat><objek>

è<subjek><predikat><kata benda>

è<subjek><predikat> kucing

è<subjek><kata kerja> kucing

è<kata benda> makan kucing

èkucing makan kucing

Derivasi menggunakan symbol :

Produksi untuk ekspresi arithmatika :

<ekspresi><ekspresi><op><ekspresi>

<ekspresi><ekspresi> + <ekspresi>

<ekspresi><ekspresi> - <ekspresi>

<ekspresi><ekspresi> * <ekspresi>

<ekspresi><ekspresi> / <ekspresi>

<ekspresi>(<ekspresi>)

<ekspresi>id

Menurunkan ekspresi aritmatika :

<ekpresi>è<ekpresi> * <ekpresi>

            è<ekpresi> * <ekpresi>

            è<ekpresi> * <ekpresi> + <ekpresi>

            è(id + <ekspresi>) * <ekpresi>

            è(id+id) * <ekpresi>

            è(id+id) * id

Contoh :

CFG untuk ekspresi aritmatika :

E→E+E

Teori  Automata : Sinar Sinurat 66

E→E*E

E→(E)

E→ id

Konversi penggunaan simbol :

1. A, B, C, D,E dan S  : variabel

2. Huruf kecil dan digit : terminal

3. X, Y, Z : terminal atau variabel

4. Huruf kecil : u,v, w, x, y dan z : variabel string

5. Huruf kecil : a, ß, γ : variabel string dan terminal

Jika A→a_1, A→a_2,... A→a_n ditulis A→a₁|a₂|...|a_k

Devirasi Language : G (V, T, P, S)

Relasi antara string dalam (V ∪ T ) : dan *

                                                            G             

G

Misalkan :

Teori  Automata : Sinar Sinurat 67

A→ß :  Produksi dalam P

a, γ elemen (V ∪T)*

Maka aAγaßγ

Misalkan :

_{1, 2}, _n string dalam (V ∪T)* ; m=1,

            ₁è₂,₂è₃,..._m-1è_m

            Maka : ₁è_m

            1 : reflexive, transitive, closure dari 2

Αß : i langkah

Definisi :

Language CFG  G: L(G)={w|w∊T* dan Sw}

Dimana : w∊T*  : terminal ;  Sw : diturunkan dari S .

L “Context Free “ jika L(G) untuk CFG  G.

Sentential  Form :

Sè, : sentential form string terminal dan non terminal

Equivalen Grammar :

G₁ dan G ₂ equivalen apabila L(G₁) = L(G₂)

Contoh : CFG : G=(V,T,P,S)

dimana V={S}

T={a,b}

P={S→aSb, S→ab}

SaSbaaSbb…èa­ⁿbⁿ

L(G) = {­ a­ⁿbⁿ | n =>>1}

Derivation Tree :

Penggambaran derivasi dalam bentuk tree : AXYZ

                        Tree                                         parse tree untuk : -(id + id)

                          A                                                       E

 

    X                   Y              Z               -                                   E

                                                                             (                    E            )

                                                                        E                        +                    E

                                                                        Id                                            id

♦ Leftmost Derivation :

Pada setiap langkah derivasi, variabel paling kiri yang

Teori  Automata : Sinar Sinurat 70

diganti.

♦ Rightmost Derivation :

Pada setiap langkah derivasi, variabel paling kanan yang

diganti.

♦ Ambiguous Grammar :

Terdapat lebih dari satu leftmost atau lebih dari satu

rightmost.

♦ Useful / Useless Symbol :

Simbol X disebut “Useful“ apabila ada suatu derivasi

Sèxßèw

W  T^*

ß(VT)*

♦ X  Useless  symbol  apabila :

1. X   tidak bisa menurunkan terminal

2. X   tidak bisa

diturunkan dari S

Lemma:

Untuk suatu L(G)≠Ø, dapat ditemukan CFG  yang ekuivalen

G'=(V',T,P',S)  dimana untuk setiap A dalam V'  terdapatsuatu string W∊T* dimana A→w

Himpunan V'   dalam Lemma di atas dapat diturunkan dengan

algoritma berikut :

Begin

1. OLDV := Ø

2. NEWV := {A|Aw untuk w∊T*

3. While OLDV ≠ NEWV  do Begin

4. OLDV := NEWV;

5. NEWV :=OLDV ∪{A|Aa untuk a∊(T∪OLDV)*}

6. V : = NEWV

End

CONTROL FLOW

C/C++                                                                                     PASCAL

 

if (E) S                                                                                    if (E) then S

if (E) S1; else S2                                                                     if (E) then S1 else S2

while (E) S                                                                              while E do S

• S ::=  ;

• | E ;                                                                                       | Break ;

• | { Slist }                                                                               | Continue ;

• | If (E) S                                                                                | Return ;

• | If (E) S Else S                                                                     | Return E ;

• | While (E) S                                                                                     | Goto L ;

• | Do S While (E) ;                                                                 | L : S

• | For (EOp ; EOp ; EOp; EOp) S                              Slist ::=  <Empty>

• | Switch (E) S                                                                                   | Slist S

• | Case Constant ; S                                                   Eop ::= <Empty>

• | Default : S                                                                                      | E

Keputusan Layout Statis

• Sintaks dalam bahasa pemrograman pascal

• <simple> ::= <name> | <enumeration> | <subrange>

• <type>    ::= <simple> | array[<simple>] of <type> |

•           record <field list> end | set of

<simple>| ^<name>

• <enumeration> ::= (<name-list>)

• <subrange> ::= <constant>..<constant>

• <field> ::= <name-list> : <type>

Menghilangkan Useless Symbol  :

Teori  Automata : Sinar Sinurat 74

Contoh : Grammar :

1.  S → AB | a

2. A → a

B dalam (1) useless sehingga produksi di atas menjadi :

1) S → a

2) A → a

A dalam 2  tidak bisa diakses dari S, grammar  di atas menjadi :

G =({S}, {a}, {S→ a}, S).