TEKNIK KOMPILASI · huruf Digit Huruf, Digit Blank Digit Contoh : suatu tata bahasa memiliki himpunan simbol terminal/token berikut (ID, PLUS, MINUS, dan INT) token ID untuk karakter

TEKNIK KOMPILASI

Sekolah Manajemen Informatika dan Komputer (STMIK) Palangkaraya

2012

Konsep & Notasi Bahasa

KonsepKonsep dandan NotasiNotasi bahasabahasa Teknik Kompilasi merupakan kelanjutan dari konsep-

konsep yang telah kita pelajari dalam teori bahasa danotomata

Thn 56-59 Noam Chomsky melakukan penggolongantingkatan dalam bahasa, yaitu menjadi 4 class

Penggolongan tingkatan itu disebut dengan hirarkiChomsky

1959 Backus memperkenalkan notasi formal baru untuksintaks bahasa yang lebih spesifik

Peter Nour (1960) merevisi metode dari sintaks. Sekarangdikenal dengan BNF (Backus Nour Form)

KonsepKonsep dandan NotasiNotasi bahasabahasa Tata bahasa (grammar) adalah sekumpulan dari

himpunan variabel-variabel, simbol-simbol terminal, simbol

non-terminal, simbol awal yang dibatasi oleh aturan-aturan

produksi

Aturan produksi adalah pusat dari tata bahasa yang

menspesifikasikan bagaimana suatu tata bahasa melakukan

transformasi suatu string ke bentuk lainnya

KonsepKonsep dandan NotasiNotasi bahasabahasa

Sintaks : suatu aturan yang memberitahu apakah sesuatu

kalimat (string) adalah valid dalam program atau tidak

Semantic : suatu aturan-aturan yang memberikan arti kepada

program

Sebuah simbol : suatu entitas abstrak yang tidak kita definisikan secara formal. Contoh: huruf dan digit.

String (kata/untai): suatu deretan berhingga dari simbol-simbol. Contoh: ‘abcd’ adalah sebuah string, yang terdiri dari simbol ‘a’, ‘b’, ‘c’ dan ‘d’. Panjang string merupakan jumlah simbol yang membentuk string.

String kosong dinyatakan dengan simbol ɛ. Panjang string = 0.

Penggolongan ChomskyBahasa Mesin Automata Aturan Produksi

Konsep dan Notasi bahasa

Tipe 3 Atau Regular

Finite state automata (FSA) meliputi; deterministic Finite Automata (DFA) & Non Deterministic Finite Automata (NFA)

adalah sebuah simbol variabel maksimal memiliki sebuah simbol variabel yang bila ada terletak diposisi paling kanan

Tipe 2 Atau Contex Free

Push Down Automata adalah sebuah simbol variabel

Tipe 1 Atau Contex Sensitive

Linier Bounded Automata || <= ||

Tipe 0 Atau Unrestricted/ Phase Structure/ natural language

Mesin Turing Tidak ada Batasan

Keterangan menyatakan simbol – simbol yang berada di ruas kiri aturan

produksi menyatakan simbol – simbol yang berada di ruas kanan aturan

produksi Simbol-simbol terdiri dari simbol terminal dan non

terminal/variabel (masih bisa diturunkan lagi) Simbol terminal biasanya dinyatakan dengan huruf kecil, contoh :

‘a’, ’b’, ‘c’ Sementara non terminal dengan huruf besar, contoh : ‘A’, ‘B’, ‘C’

Aturan Produksi Aturan produksi dinyatakan dalam bentuk :

“ ” dibaca : menghasilkan , atau menurunkan

Dengan menerapkan aturan produksi, suatu tata bahasa bisamenghasilkan sejumlah string.

Himpunan string tersebut adalah bahasa yang didefinisikanoleh tata bahasa tersebut.

Aturan Produksi Contoh aturan produksi :

T a dibaca : “T menghasilkan a”

E T | T + Edibaca : “E menghasilkanT atau E menghasilkanT + E”Merupakan pemendekan dari :E TE T+E

Simbol ‘|’ menyatakan ‘atau’

Aturan ProduksiAturan Produksi Tipe O / Unrestricted: Tidak ada batasan pada aturan produksi

Abc De

Tipe 1 / Context sensitive: Panjang string ruas kiri harus lebih kecil atau sama dengan ruas kanan(|α| ≤ |β|)

Ab DeFCD eFS ɛ

Tipe 2 / Context free grammar: Ruas kiri haruslah tepat satu simbol variableB CDeFgD BcDe

Tipe 3 / Regular: Ruas kiri hanya 1 simbol variabel, Ruas kanan hanya memiliki maksimal 1 simbolnon terminal / variabel dan diletakkan paling kanan sendiri

A eA efgA efgHC D

Aturan produksi yang tidak legal !!!

Simbol ɛ tidak boleh berada pada ruas kirimisal ɛAbdɛ merupakan string kosong

Aturan produksi yang ruas kirinya hanya memuat simbolterminal sajamisal : a bd atau ab bd

Bahasa manusia/bahasa alami termasuk ke dalam tata bahasa Tipe 0/unrestricted, tidak ada batasa pada aturan produksinya.

Batasan context sensitive biasanya turut digunakan dalam prosesanalisis semantik pada tahapan kompilasi

Bahasa context free menjadi dasar dalam pembentukan suatuparser / proses analisis sintaksis, dideskripsikan dengan notasiBNF (Backus Normal Form)

Hirarki Chomsky

RegularRegular

Context free

Context Sensitive

Unrestricted

NotasiNotasi BNF (Backus Normal Form)BNF (Backus Normal Form) Aturan Produksi bisa dinyatakan dengan notasi BNF

BNF menggunakan abstraksi untuk struktur syntax

::= sama identik dengan simbol

| sama dengan atau

< > pengapit simbol non terminal

{ } Pengulangan dari 0 sampai n kali

Misalkan aturan produksi sbb:

E T | T+E | T-E

T a

Notasi BNF-nya adalah

<E> ::= <T> | <T> + <E> | <T> - <E>

<T>::= a

Contoh Tata Bahasa SederhanaContoh Tata Bahasa Sederhana <program> ::= BEGIN <statement-list> END

<statement-list> ::= <statement> | <statement>; <statement-list> <statement> ::= <var> := <expression> <expression> ::= <term> | <term><op1> <expression> <term> ::= <factor> | <factor> <op2> <term> <factor> ::= <var> | <constant>

<var> ::= A|B| ….| Z <op1> ::= + | - | = <op2> ::= ^ | * | / <constant> ::= <real_number> | <integer_part>

<real_number> ::= <integer_part> . <fraction> <integer_part> ::= <digit> | <integer_part> < digit> <fraction> ::= <digit> | <digit> <fraction> <digit> ::= 0|1|….|9

ContohContoh

BEGIN

A := 1;

B := A + 2

END

Latihan ! TBO, Firrar Utdirartatmo hal 13-15…

Diagram StateDiagram State

Digunakan untuk mendapatkan token, mempermudah

melakukan analisis lexical

Token adalah simbol terminal dari teori bahasa dan

automata

S

ID

INT

PLUS

MINUS

+

-

huruf

Digit

Huruf, Digit

DigitBlank

Contoh : suatu tata bahasa memiliki himpunan simbolterminal/token berikut (ID, PLUS, MINUS, dan INT)token ID untuk karakter huruf a-z, 0-9, token INT untuk digit, token PLUS untuk Penjumlahan dan token MINUS untuk Pengurangan

Diagram SyntaxDiagram Syntax Alat bantu (tools) dalam pembuatan parser/ analisis sintaksis

Menggunakan simbol persegi panjang untuk non terminal

Lingkaran untuk simbol terminal

Misalnya

E T | T+E | T-ET

+

-

E

BNF: <Block> ::= BEGIN <statement> { SEMICOL <statement>} END

BEGIN Statement END

;

Latihan!