Session III : Describing Syntax and Semantics

In this session III : Describing Syntax and Semantics, there are 5 sub topics :

• Introduction
• The General Problem of Describing Syntax
• Formal Methods of Describing Syntax
• Attribute Grammars
• Semantics

Introduction 

The task of providing a concise yet understandable description of a programming language is difficult but essential to the language’s success. ALGOL 60 and ALGOL 68 were first presented using concise formal descriptions; in both cases, however, the descriptions were not easily understandable, partly because each used a new notation. The levels of acceptance of both languages suffered as a result. On the other hand, some languages have suffered the problem of having many slightly different dialects, a result of a simple but informal and
imprecise definition. One of the problems in describing a language is the diversity of the people
who must understand the description. Among these are initial evaluators, implementors, and users. Most new programming languages are subjected to a period of scrutiny by potential users, often people within the organization that employs the language’s designer, before their designs are completed. These are
the initial evaluators. The success of this feedback cycle depends heavily on the clarity of the description.

These are the simple explanation of syntax, and semantics:

• Syntax: the form or structure of the expressions, statements, and program units
• Semantics: the meaning of the expressions, statements, and program units
• Syntax and semantics provide a language’s definition

The General Problem of Describing Syntax

A language, whether natural (such as English) or artificial (such as Java), is a set of strings of characters from some alphabet. The strings of a language are called sentences or statements. The syntax rules of a language specify which strings of characters from the language’s alphabet are in the language. English, for example, has a large and complex collection of rules for specifying the syntax of its sentences. By comparison, even the largest and most complex programming languages are syntactically very simple. Formal descriptions of the syntax of programming languages, for simplicity’s sake, often do not include descriptions of the lowest-level syntactic units. These small units are called lexemes. The description of lexemes can be given by a lexical specification, which is usually separate from the syntactic description of the language. The lexemes of a programming language include its numeric literals, operators, and special words, among others. One can think of programs as strings of lexemes rather than of characters. Lexemes are partitioned into groups—for example, the names of variables, methods, classes, and so forth in a programming language form a group called identifiers. Each lexeme group is represented by a name, or token. So, a token of a language is a category of its lexemes. For example, an identifier is a token that can have lexemes, or instances, such as sum and total. In some cases, a token has only a single possible lexeme. For example, the token for the arithmetic operator symbol + has just one possible lexeme.

In general, languages can be formally defined in two distinct ways: by recognition and by generation (although neither provides a definition that is practical by itself for people trying to learn or use a programming language). A recognition device reads input strings over the alphabet of the language and decides whether the input strings belong to the language

A language generator is a device that can be used to generate the sentences of a language. We can think of the generator as having a button that produces a sentence of the language every time it is pushed. Because the particular sentence that is produced by a generator when its button is pushed is unpredictable, a generator seems to be a device of limited usefulness as a language descriptor.

Formal Methods of Describing Syntax

• Context-Free Grammars

–Developed by Noam Chomsky in the mid-1950s

–Language generators, meant to describe the syntax of natural languages

–Define a class of languages called context-free languages

• Backus-Naur Form (1959)

–Invented by John Backus to describe the syntax of Algol 58

–BNF is equivalent to context-free grammars

• BNF Fundamentals

– In BNF, abstractions are used to represent classes of syntactic structures–they act like syntactic variables (also called nonterminal symbols, or just terminals)

–  Terminals are lexemes or tokens

–  A rule has a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and/or nonterminals

-Nonterminals are often enclosed in angle brackets

-Examples of BNF rules:

–  <ident_list> → identifier | identifier, <ident_list>

–  <if_stmt> → if <logic_expr> then <stmt>

-Grammar: a finite non-empty set of rules

-A start symbol is a special element of the nonterminals of a grammar

A grammar is a generative device for defining languages. The sentences of the language are generated through a sequence of applications of the rules, beginning with a special nonterminal of the grammar called the start symbol. This sequence of rule applications is called a derivation. In a grammar for a complete programming language, the start symbol represents a complete program and is often named.

Every string of symbols in a derivation is a sentential form. A sentence is a sentential form that has only terminal symbols. A leftmost derivation is one in which the leftmost nonterminal in each sentential form is the one that is expanded and a derivation may be neither leftmost nor rightmost.

A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct parse trees. If we use the parse tree to indicate precedence levels of the operators, we cannot have ambiguity.

Attribute Grammars

An attribute grammar is a device used to describe more of the structure of a programming language than can be described with a context-free grammar. An attribute grammar is an extension to a context-free grammar. The extension allows certain language rules to be conveniently described, such as type compatibility. Before we formally define the form of attribute grammars, we must clarify the concept of static semantics. There are some characteristics of the structure of programming languages that are difficult to describe with BNF, and some that are impossible. As an example of a syntax rule that is difficult to specify with BNF, consider type compatibility rules. In Java, for example, a floating-point value cannot be assigned to an integer type variable, although the opposite is legal. Although this restriction can be specified in BNF, it requires additional nonterminal symbols and rules. If all of the typing rules of Java were specified in BNF, the grammar would become too large to be useful, because the size of the grammar determines the size of the syntax analyzer. As an example of a syntax rule that cannot be specified in BNF, consider the common rule that all variables must be declared before they are referenced. It has been proven that this rule cannot be specified in BNF. Attribute grammars are context-free grammars to which have been added attributes, attribute computation functions, and predicate functions. Attributes, which are associated with grammar symbols (the terminal and nonterminal symbols), are similar to variables in the sense that they can have values assigned to them. Attribute computation functions, sometimes called semantic functions, are associated with grammar rules. They are used to specify how attribute values are computed. Predicate functions, which state the static semantic rules of the language, are associated with grammar rules.

Semantics

There is no single widely acceptable notation or formalism for describing semantics

Several needs for a methodology and notation for semantics:

• Programmers need to know what statements mean
• Compiler writers must know exactly what language constructs do
• Correctness proofs would be possible
• Compiler generators would be possible
• Designers could detect ambiguities and inconsistencies

The idea behind operational semantics is to describe the meaning of a statement or program by specifying the effects of running it on a machine. The effects on the machine are viewed as the sequence of changes in its state, where the machine’s state is the collection of the values in its storage. An obvious operational semantics description, then, is given by executing a compiled version of the program on a computer. Most programmers have, on at least one occasion, written a small test program to determine the meaning of some programming language construct, often while learning the language. Essentially, what such a programmer is doing is using operational semantics to determine the meaning of the construct. There are several problems with using this approach for complete formal semantics descriptions. First, the individual steps in the execution of machine language and the resulting changes to the state of the machine are too small and too numerous. Second, the storage of a real computer is too large and complex. There are usually several levels of memory devices, as well as connections to enumerable other computers and memory devices through networks. Therefore, machine languages and real computers are not used for formal operational semantics. Rather, intermediate-level languages and interpreters for idealized computers are designed specifically for the process. There are different levels of uses of operational semantics. At the highest level, the interest is in the final result of the execution of a complete program. This is sometimes called natural operational semantics. At the lowest level, operational semantics can be used to determine the precise meaning of a program through an examination of the complete sequence of state changes that occur when the program is executed. This use is sometimes called structural operational semantics.

Denotational semantics is the most rigorous and most widely known formal method for describing the meaning of programs. It is solidly based on recursive function theory. A thorough discussion of the use of denotational semantics to describe the semantics of programming languages is necessarily long and complex.

In Axiomatic semantics, there is no model of the state of a machine or program or model of state changes that take place when the program is executed. The meaning of a program is based on relationships among program variables and constants, which are the same for every execution of the program. Axiomatic semantics has two distinct applications: program verification and program semantics specification. Axiomatic semantics based on mathematical logic.

 

Read more

Session II : Names, Binding, Scope

In this Session II : Names, Binding, and Scope, there are 4 sub topics :

• Introduction
• Names
• Variables
• The Concept of Binding
• Scope

Introduction

Imperative programming languages are, to varying degrees, abstractions of
the underlying von Neumann computer architecture. The architecture’s two
primary components are its memory, which stores both instructions and data,
and its processor, which provides operations for modifying the contents of the
memory.

A variable can be characterized by a collection of properties, or attributes,
the most important of which is type, a fundamental concept in programming
languages. Designing the data types of a language requires that a variety of
issues be considered. Among the most important of these issues are the scope and lifetime of variables.

Names

A name is a string of characters used to identify some entity in a program. For every programming language, they have maximum length for the names. Fortran 95, in their programming language, can only contain names with maximum length of 31. C99: no limit but only the first 63 are significant. And for C#, Java, C++ have no limit for their name’s length.

And for some other programs, they need special character for the names. For example : PHP, all variable names must begin with dollar signs($) ; Perl,all variable names begin with special characters, which specify the variable’s type; and Ruby, for variable names that begin with @ are instance variables and for those that begin with @@ are class variables. And also there are some programs that are case sensitive such as C, C#, and Java

For notes : if the names are too short, they cannot be connotative by others. So it’s recommended to have longer length for the names ( or as clear as possible for the names so it can be read by others )

Variables

Variable is an abstraction of a computer memory cell or collection of cells.

The move from machine languages to assembly languages was largely one
of replacing absolute numeric memory addresses for data with names, making
programs far more readable and therefore easier to write and maintain. That
step also provided an escape from the problem of manual absolute addressing,
because the translator that converted the names to actual addresses also chose
those addresses.
A variable can be characterized as a sextuple of attributes: name, address,
value, type, lifetime, and scope.

The Concept of Binding

A binding is an association between an attribute and an entity, such as
between a variable and its type or value, or between an operation and a symbol.
The time at which a binding takes place is called binding time.

Binding can be divided into two : Static and Dynamic. A binding is static if it first occurs before run time begins and remains unchanged throughout program execution. If the binding first occurs during run time or can change in the course of program execution, it is called dynamic. However, this processes are maintained by computer hardware, and the changes are invisible to the program and the user. Static and Dynamic type of binding have their own advantage and disadvantage. For the static type of binding, it’s efficient but lacks of flexibility. And for the dynamic type of binding, it’s really flexible but hard to be checked if there’s something wrong or missing and has high cost.

Back to the variable sub-topic, variables’ attributes : storage bindings and lifetime. Storage bindings of the variables can be divided into two : allocation and deallocation. Allocation is a process that the memory cell to which a variable is bound somehow must be taken from a pool of available memory. And deallocation is the process of placing a memory cell that has been unbound from a variable back into the pool of available memory. The lifetime of a variable is the time during which the variable is bound to a specific memory location. So, the lifetime of a variable begins when it is bound to a specific cell and ends when it is unbound from that cell.

The lifetime of variables itself has 4 categories :

• Static  : bound to memory cells before execution begins and remains bound to the same memory cell throughout execution
• Stack-dynamic  : Storage bindings are created for variables when their declaration statements are elaborated.
• Explicit heap-dynamic  : Allocated and deallocated by explicit directives, specified by the programmer, which take effect during execution
• Implicit heap-dynamic  : Allocation and deallocation caused by assignment statements

Scope

Scope is also one of the variables’ attributes. The scope of a variable is the range of statements in which the variable is visible. The scope of a variable can also be divided into 3 categories : Local variables, those that are declared in that unit;  The nonlocal variables, those that are visible in the unit but not declared there; and global variables, that are a special category of nonlocal variables. Scope itself can be divided into Static and Dynamic Scope. Static scope refers to scope of a variable is defined at compile time itself that is when the code is compiled a variable to bounded to some block scope if it is local, can be bounded to entire Main block if it is global. Dynamic scope refers to scope of a variable is defined at run time rather than at compile time.

 

End of the Session II : Names, Binding, and Scope

Read more

Sesi I : Introduction

Pada Sesi I : “Pengenalan pada Konsep Bahasa Pemrograman” ini, terbagi menjadi 6 sub topik yaitu :

• Alasan mempelajari Konsep Bahasa Pemrograman secara umum
• Domain dari Programming
• Kriteria dari bahasa pemrograman
• Pengaruhnya pada desain pemrograman
• Kategori bahasa pemrograman
• Metode Implementasi

Alasan Mempelajari Konsep Bahasa Pemrograman

Ada banyak sekali benefit dari mempelajari konsep programming,

berikut adalah beberapa alasan utama dari pentingnya mempelajari Konsep  Bahasa Pemrograman :

Mengasah kemampuan mengekspresikan ide

Dengan mempelajari semakin banyak bahasa pemrograman, seorang programmer akan terasah cara berfikir agar dapat mengekspersikan idenya ke dalam bahasa pemrograman

Dapat memilih bahasa pemrograman yang efektif

Agar mendapatkan hasil dari pemrograman yang tepat dan efisien, haruslah memilih bahasa pemrograman yang efektif. Contohnya : untuk membuat mobile app untuk iOS, dapat menggunakan aplikasi Swift. Untuk membuat website, dapat menggunakan aplikasi Pascal

Lebih mudah untuk mempelajari bahasa pemrograman baru

Dengan mempelajari konsep dari programming, seseorang akan dengan mudah dapat mempelajari bahasa pemrograman baru. Hal itu dikarenakan semua bahasa pemrograman memiliki konsep yang sama ( hanya bahasanya saja yang berbeda )

Kemampuan Implementasi 

Kemampuan untuk membuat aplikasi dengan efektif

Advancement

Kemampuan untuk meneliti dan membuat suatu program yang lebih efektif dan efisien dari sebelumnya

 

Domain dari Programming

Terbagi menjadi :

• Scientific App

Bahasa Pemrograman Scientific App yang pertama kali dibuat adalah Fortran pada tahun 1940-an lalu pada tahun 1960-an dibentuk ALGOL 60. Scientific App pada saat itu hanya berbatas pada data yang relatif sederhana. Struktur yang paling umum digunakan pada saat itu adalah matriks dan deret.

• Business App

Bahasa Pemrograman Business App yang pertama kali sukses dan terkenal adalah COBOL. Business App digunakan umumnya untuk membuat laporan, menyimpan angka dan karakter dengan tepat hingga operasi deret aritmetika

• Artificial intelligence

Bahasa Pemrograman Artificial Intelligence umumnya digunakan untuk memprediksi kemungkinan-kemungkinan sehingga membuat komputer melakukan hal-hal yang dapat dilakukan oleh manusia

• Software Programming

Bahasa Pemrograman Software Programming haruslah efisien karna software programming tersebut akan digunakan hampir secara terus menerus. Kebanyakan software zaman sekarang menggunakan bahasa pemrograman C

• Web Programming

Bahasa Pemrograman Web Programming digunakan dalam pembuatan website

 

Kriteria Dari Bahasa Pemrograman

• Readability : Bahasa Pemrograman dapat dibaca dan mudah dimengerti termasuk oleh orang lain
• Writability : Bahasa Pemrograman yang digunakan mudah untuk membuat program
• Reliablity : Dapat bekerja dengan optimal
• Cost : Mengetahui total cost / expense dari program yang dibuat

 

Pengaruh Pada Desain Pemrograman

• Comp Architecture

Arsitektur dasar komputer memberikan efek pada bahasa desain pemrograman. Sebagian besar bahasa populer tersebut telah dirancang ke dalam arsitektur komputer yang lazim, yang disebut arsitektur von Neumann

• Programming Design Methodologies

Metode pengembangan software baru yang menyebabkan paradigma pemrograman baru dan perluasan, bahasa pemrograman baru

Kategori Bahasa Pemrograman

• Logic
• OOP (object oriented program)
• Imperative
• Scripting Language

Metode Implementasi

• Compilation

Mentranslate dari high-level program menjadi machine code

• Pure Interpretation

Tidak ada proses translation, umumnya membutuhkan lebih banyak space, slower execution , sudah jarang digunakan untuk traditional high-level languages

• Hybrid Implementation Systems

Gabungan antara compilation + hybrid system. Lebih cepat dibandingkan dengan pure interpretation

 

Read more