Definisi

Syntax adalah bentuk atau struktur dari ekspresi, pernyataan, dan unit program.

Semantics adalah terjemahan dari ekspresi, pernyataan, dan unit program.

Permasalahan dalam Mendeskripsikan Syntax:

Terminologi:

• Sebuah kalimat terdiri dari karakter string yang merupakan huruf.
• Sebuah bahasa terdiri dari berbagai kalimat.
• Sebuah lexemes adalah level terendah dari syntactic unit dari sebuah bahasa (sum, begin, *).
• Sebuah token adalah kategori dari lexemes (identifier).

Definisi formal

1. Recognizers

Sebuah alat recognition membaca input string dari sebuah bahasa dan memutuskan apakah input sting merupakan sebuah bahasa.

1. Generators

Sebuah alat yang dapat menghasilkan kalimat dari sebuah bahasa. Alat ini dapat menentukan apakah kalimat tersebut benar menurut syntax dengan membandingkannya ke sebuah struktur generator.

BNF Fundamentals

Dalam BNF, abstraksi digunakan untuk merepresentasi kelas dari syntactic structure (nonterminal symbols atau terminals).

Terminal adalah lexemes atau tokens.

Peraturannya adalah memiliki lengan kiri (LHS) yang merupakan nonterminal dan lengan kanan (RHS) yang merupakan string terminals dan/atau nonterminals.

Nonterminals biasanya diapit oleh angle brackets (<>) seperti <ident_list> -> identifier | identifier.

BNF Rule

Sebuah abstraksi ( atau nonterminal symbol) boleh memiliki lebih dari satu RHS.

<stmt> -> <single_stmt>

| begin <stmt_list> end

Derivasi

Sebuah derivasi adalah aplikasi yang diulang oleh aturan tertentu, dimulai dari simbol start dan diakhiri dengan sebuah kalimat (all terminal symbols).

Setiap string dari simbol dalam derivasi merupakan sentential form.

Sebuah kalimat adalah sentential form yang hanya memiliki simbol terminal.

Sebuah derivasi yang paling kiri dimana yang paling kiri merupakan nonterminal dalam setiap sentential form adalah yang diperluas.

Sebuah derivasi mungkin tidak paling kiri atau paling kanan.

Ambiguitas dalam Grammar

Sebuah grammar adalah ambigu jika dan hanya jika sebuah grammar menghasilkan sentential form yang memiliki dua atau lebih distinct parse trees.

Static Semanctics

Context-free grammars (CFG) tidak dapat mendeskripsikan semua syntax dari programming language.

Kategori konstruksi yang menjadi masalah:

• Context-free tetapi tidak praktis
• Non-context-free

Attribute Grammars (AG)

AG adalah context-free grammar dengan beberapa tambahan sebagai berikut:

• Setiap grammar symbol x memiliki sebuah set A(x) dari attribute values
• Setiap peraturan memiliki fungsi yang dapat mendefinisikan attribute tertentu dari sebuah nonterminal dalam peraturan.
• Setiap peraturan memiliki sebuah set predikat untuk mengecek konsistensi attribute.

AG memiliki tambahan CFG untuk membawa semantic info ke parse tree nodes.

Nilai utama dari AG:

• Static semantics specification
• Compiler design (static semantics checking)

Contoh AG:

• Syntax

<assign> -> <var> = <expr>

<expr> -> <var> + <var> | <var>

• actual_type: synthesized for <var> and <expr>
• expected_type: inherited for <expr>

Operational Semantics

Mendeskripsikan arti sebuah program dengan mengeksekusi pernyataan dalam mesin, baik simulasi maupun nyata. Perubahan lokasi dalam mesin menandakan arti dari pernyataan. Untuk mengoperasikan semantik, dibutuhkan high-level language dan sebuah virtual machine.

Operational semantics digunakan untuk: bahasa manual dan textbook serta untuk mengajarkan bahasa pemrograman.

Denotational Semantics

Sebuah proses membangun denotational specification untuk sebuah bahasa:

• Menerjemahkan mathematical object untuk setiap kesatuan bahasa.
• Menerjemahkan fungsi yang menghubungkan kesatuan bahasa dengan kesatuan corresponding mathematical object.

Axiomatic Semantics

• Pre post form: (P) statement (Q)

Contoh:

• a = b + 1 (a > 1)
• One possible precondition (b > 10)
• Weakest precondition ( b > 0)

Denotation Semantics vs Operational Semantics

• Dalam operational semantics, perpindahan lokasi diartikan sebagai coded algorithms
• Dalam denotational semantics, perpindahan lokasi diartikan sebagai rigorous mathematical functions.