Concepts of Programming Languages – Chapter 5 – Names, Bindings, and Scopes

REVIEW QUESTIONS:
1. What are the design issues for names?

The design issues for names are about if names are case sensitive and if the special words of the language are reserved or keywords.

3. In what way are reserve words better than keywords?

Reserved words are better than keywords in a language design choice, since its ability to redefine keywords can be confusing.

4. What is an alias?

An alias is a variable name that can be used to access the same memory location.

5. Which category of C++ reference variables is always aliases?

Category of C++ reference variables is always aliases when a C++ pointer is set to point at a named variable, the pointer, when dereferenced.

6. What is the l-value of a variable? What is the r-value?

l-value of a variable is the address of a variables since the address is what is required when the name of variable appears in the left side of an assignment.

r-value of a variable is the variable’s value since it is what is what is required when the name of the variable appears in the right side of an assignment statement.

7. Define binding and binding time.

Binding is an association between an attribute and an entity, such as between a variable and its type or value, or between a variable and its type or value, or between an operation and a symbol.

Binding time is the time at which a binding takes place.

PROBLEM SET:

1. Decide which of the following indentifier names is valid in C language. Support your decision.

_student //  valid.

int // not valid, because int is a keyword for integer used in variable declaration.

Student // valid.

123Student // not valid, because variable doesn’t start with number.

Student123 // valid.

2. What is the l-value? Write a statement in C language which gives the compile time error “l-value required”.

#include <stdio.h>

int main(){
int a;
2 = a;
}

4. Why is the type declaration of a variable necessary? What is the value range of the int type variable in Java?

The type declaration of a variable is necessary because the type of a variable determines the range of values the variable can store and the set of operations that are defined for values for the type.

Concepts of Programming Languages – Chapter 3 – Describing Syntax and Semantics

Review Questions:

1. Define syntax and semantics.

Syntax of a programming language is the form of its expressions, statements, and program units.

Semantics is the meaning of those expressions, statements, and program units.

3. Describe the operation of general language generator.

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. The particular sentence produced by a generator when its button is pushed is unpredictable.

5. What is the difference between a sentence and a sentential form?

Sentence is a sentential form that has only terminal symbols. A sentential form is each of the string in the derivation, including <program>.

6. Define a left-recursive grammar rule.

A left-recursive grammar rule is when a grammar rule has its left-hand side(LHS) also appearing at the beginning of its right-hand side(RHS). This left recursion specifies left associativity. It  disallows the use of important syntax analysis algorithms. When such algorithms are to be used, the grammar must be modified to remove the left recursion. This, in turn, disallows the grammar from precisely specifying that certain operators are left associative. Left associativity can be enforced by the compiler, even though the grammar does not dictate it.

7. What three extension are common to most EBNF’s?

Three extension common to most EBNF’s are:

– The first of these denotes an optional part of an RHS, which is delimited by brackets.

– The second extension is the use of braces in a n RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. This extension allows lists to be built with a single rule, instead of using recursion and two rules.

– The third extension deals with multiple-choice options. When a single element must be chosen from a group, the options are placed in parentheses and separated by the OR operator, |.

10. What is the difference between synthesized and an inherited attribute?

Synthesized attribute is used to pass semantic information up a parse tree while inherited attribute is used to pass semantic information down and across a tree.

12. What is the primary use of attribute grammars?

The primary use of attribute grammar is describing more of the structure of a programming language than can be described with a context-free grammar.

16. In denotational semantics,  what are the syntactic and semantic domains?

The mapping functions in denotational semantics programming languages, like all functions in mathematics, have a domain and range. -Syntactic domain is the domain in denotational semantic which is collection of values are legitimate parameters to the function.
-Semantic domain is the range in denotational semantic which is the collection of objects to which parameters are mapped.

21. When is a grammar rule said to be left recursive?

A grammar is said to be left recursive when a grammar rule has its left-hand side(LHS) also appearing at the beginning of its right-hand side(RHS).

23. On what branch of mathematics is axiomatic semantics based?

Axiomatic semantic is based on mathematical logic.

Problem Set:

1. Syntax error and semantic error are two types of compilation error. Explain the difference between the two in a program with examples.

Syntax error is the wrong form of the expressions, statements, and program units in programming language.

Semantics error is the wrong meaning of the expressions, statements, and program units in programming language.

-Instance of syntax error:
#include<stdio.h>

int main()
{
int i = 0;

for(i<10) //*syntax error*
{
printf(“%d\n”, i);
i++;
}
}

*Note: it is error because the wrong form of for statement in C. The for statement in C has a form:

for(expression 1; expression 2; expression 3;)

{
statement;
}

Expression 1 is the initial value. Expression 2 is the control value. Expression 3 is the increment/decrement control variable.

-Instance of semantic error:
#include <stdio.h>

void main()
{
int a;
int b;

a = 1;
b = 2;

if((a==1)&(b==2)) //*semantic error*
{
printf(“1+2 = 3”);
}
getchar();
}

*Note: The operator & should’ve been && because it is a logical operator.

3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *.

<assign> -> <id> = <expr>
<id> -> A|B|C
<expr> -> <expr> – <term>
| <term>
<term> -> <term> / <factor>
| <factor>
<factor> -> ( <expr> )
| <id>

6. Using the grammar in Example 3.2, show a parse tree for each of the following statements:

a. A = A * ( B * ( C + A) )

<assign> => <id> = <expr>

=> A = <expr>

=> A = <id> * <expr>

=> A = A * <expr>

=> A = A * ( <expr> )

=> A = A * ( <id> * <expr> )

=> A = A * ( B * <expr> )

=> A = A * ( B * ( <expr> ) )

=> A = A * ( B * ( <id> + <expr> ) )

=> A = A * ( B * ( C + <expr> ) )

=> A = A * ( B * ( C + <id> ) )

=> A = A * ( B * ( C + A ) )

b. B = C * ( A + C * B)

<assign> => <id> = <expr>

=> B = <expr>

=> B = <id> * <expr>

=> B = C * <expr>

=> B = C * ( <expr> )

=> B = C * ( <id> + <expr> )

=> B = C * ( A + <expr> )

=> B = C * ( A + <id> * <expr> )

=> B = C * ( A + C * <expr> )

=> B = C * ( A + C * <id> )

=> B = C * ( A + C * B )

c. A = A + ( B * (C) )

<assign> = <id> = <expr>

=> A = <expr>

=> A = <id> + <expr>

=> A =  A + <expr>

=> A =  A + ( <expr> )

=> A =  A + ( <id> * <expr> )

=> A =  A + ( B * <expr> )

=> A =  A + ( B * (<expr>) )

=> A =  A + ( B * (<id>) )

=> A =  A + ( B * (C) )

9. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *.

<assign> -> <id> = <expr>

<id> -> A|B|C

<expr> -> <expr> + <term>

| <term>

<term> -> <term> * <factor>

| <factor>

<factor> -> ( <expr> )

| <id>

| – <id>

12. Consider the following grammar:

<S> →a <S> c <B> |<A> |b

<A> →c <A> |c

<B> →d |<A>

Which of the following sentences are in the language generated by this grammar?

a. abbccd

b. acccbdda

c. accbcbccc   

d. acddaccd

e. acccdc

13. Write a grammar for the language consisting of strings that have n copies of the letter a followed by double the number of copies of the letter b, where n > 0. For example, the strings abb, aabbbb, and aaaabbbbbbbb are in the language but a, aabb, ba, and aaabb are not.

S -> aSb | ab

15. Convert the BNF of Example 3.1 to  EBNF.

BNF:

<program> -> begin <stmt_list> end

<stmt_list>-><stmt>

| <stmt> ; <stmt_list>

<stmt> -> <var> = <expression>

<var> -> A | B | C

<expression> -> <var> + <var>

| <var> – <var>

| <var>

EBNF:

<program> -> begin <stmt_list> end

<stmt_list> -> <stmt> [<stmt_list>]

<stmt> -> <var> = <expression>

<var> -> A | B | C

<expression> -> <var> ( + | – ) <var>

| <var>

16. Convert the BNF of Example 3.3 to EBNF.

BNF:

<assign> -> <id> = <expr>

<id> -> A|B|C

<expr> -> <id> + <expr>

| <id> * <expr>

| ( <expr> )

| <id>

EBNF:

<assign> -> <id> = <expr>

<id> -> A|B|C

<expr> -> <id> (+ | *) <expr>

| ( <expr> )

| <id>

17. Convert the following EBNF to BNF:

S -> A{bA}

A -> a[b]A

Answer:

The BNF of S -> A{bA}

S -> A

     |bA

The BNF of A -> a[b]A

A -> aA

      |abA

18. What is a fully attributed parse tree?

A fully attributed parse tree is a parse tree based on its underlying BNF grammar, with a possibly empty set of attribute values attached to each node and if all the attribute values in a parse tree have been computed.

Concepts of Programming Languages – Chapter 2 – Evolution of The Major Programming Languages

Review Questions:

1. In what year was Plankalkul designed? In what years was that design published?

Plankalkul was designed in 1943 by Konrad Zuse as his proposal for his Ph. D. dissertation. In a lengthy manuscript dated 1945. The design was published in 1972.

2. Mention an interesting feature of Zuse’s programs.

An interesting feature of Zuse’s programs was the inclusion of mathematical expressions showing the current relationships between program variables. These expression stated that would be true during execution at the points in the code where they appeared. These are very similar to the assertions of Java and in those in axiomatic semantics.

3. What does Plankalkul mean?

Plankalkul means program calculus. It was defined and the algorithms were written in language to solve a wide variety of problems by Zuse.

4. Speedcoding was invented to overcome two significant shortcomings of the computer hardware of the early 1950s. What were they?

They were the novel facility of automatically incrementing address registers which didn’t appear in hardware until the UNIVAC 1107 computers of 1962.  The speedcoding interpreter effectively converted the problem of 701 ti a virtual three-address floating-point calculator.

5. What is the number of bits in a single word of the UNIVAC I’s memory? How are the bits grouped?

The number of bits in a single word of the UNIVAC I’s memory is 72 bits and the bits are grouped as 12 six-bit bytes.

6. What hardware capability that first appeared in the IBM 704 computer strongly affected the evolution of programming language? Explain why.

Indexing and floating-point instructions in hardware, because one of the primary reasons why the slowness of interpretive system was tolerated from the late 1940s to the mid-1950s was the lack of floating-point hardware in the available computers. All floating-point operations had to be simulated in software, a very time-consuming process. Because so much processors time was spent in software floating-point processing, the overhead of interpretation and the simulation of indexing were relatively insignificant. As long as floating-point had to be done by software, interpretation was an acceptable expense.

7. Who developed the Speedcoding system for the IBM 701?

The speedcoding system was developed by John Backus for the IBM 701 which is an example of such a system (Backus, 1954).

8. Who developed Short Code? Why is Short Code called automatic programming?

Short Code was developed by John Mauchly. It is called automatic programming because it is not translated to machine code, rathter it was implemented with a pure interpreter. It clearly simplifies the programming process, but at the expense of execution time.

9. Under what environmental consideration as Fortran developed? Which is the first version of Fortran?

Environmental consideration as Fortran developed was under:

– Computers had small memories and were slow and relatively unreliable

– The primary use of computer was for scientific computations

– There were no existing efficient and effective ways to proram computers

– Because of the high cost of computers compare to the cost of programmers, speed of the generated object code was the primary goal of the first Fortran compilers.

The first version of Fortran is Fortran 0.

10. What was the most significant feature added to Fortran I to get Fortran II?

The most significant feature added to Fortran I to get Fortran II was the independent compilation of subroutines. Without it, any change in a program required that the entire program be recompiled.

11. What control flow statements were added to Fortran IV to get Fortran 77?

Control flow statements added to Fortran IV to get Fortran 77 were logical loop control statements and an If with an optional Else clause.

12. Which versions of Fortran was the first to have any sort of dynamic variables?

Fortran 90(ANSI, 1992) was the first version of Fortran to have any sort of dynamic variables.

13. Which version of Fortran was the first to have character string handling?

Version of Fortran that was the first to have character string handling was Fortran 77. Moreover it became standard in 1978 and it retained most of features of Fortran IV.

14. Why are linguist interested in artificial intelligence in the late 1950s?

Linguist were interested in artificial intelligence in the late 1950s because the were concerned with natural language processing.

15. What are the different data types and structures in Common LISP?

The different data types and structures in common LISP are the Common LISP has a large number of data types and structures, including records, arrays, complex number, and character strings. It also has a form of a packages for modularizing collections of functions and data providing access control.

23. In what year did the COBOL design process begin?

COBOL design process was begun  in 1959 when it was held the meeting of the subject of a common language for business applications, which was sponsored by the Department of Defense at the Pentagon.

27. Why was BASIC was an important language in the early 1980s?

In early 1980s BASIC was an important language because it was easy for beginners to learn, especially those were not science oriented, and its smaller dialects can be implemented on computers with very small memories.

Problem Set:

1. What features of Fortran IV do you think would have had the greatest influence of Java if the Java designers had been familiar with Fortran?

It think they would be the capability of passing subprograms as parameter to others subprogram, explicit type declarations for variables, and a logical if construct.

3. Write a short history of the Fortran 0, Fortran I, Fortran II, Fortran IV systems.

Fotran 0 was the first version of Fortran. It stated that it would provide the efficiency of hand-coded programs and the ease of programming of the interpretive pseudocode systems. Environmental consideration as Fortran developed was under: computers had small memories and were slow and relatively unreliable, the primary use of computer was for scientific computations, there were no existing efficient and effective ways to proram computers, because of the high cost of computers compare to the cost of programmers, speed of the generated object code was the primary goal of the first Fortran compilers.

Fortran I included input/output formatting, variable names of up to six characters, user-defined subroutines, the if selection statement and the Do loop statement. There were no data typing, variable whose names began with I, J, K, L, M, N were implicity integer type, and all others were implicitly floating-point.

Fortran II fixed many of the bugs in the Fortran I compilation system and added some significant features to the language, most important being the independent compilation of subroutines. Without independent compilation, any change in a program required that the entire program be recompiled. The capability of including precompiled machine language versions of subprograms shortened the compilation process considerably and made it practical to develop much larger programs.

Fortran IV became one of the most widely used programming languages of its time. It was an improvement over Fortran II in many ways. It added explicit type declaration for variable, a logical If construct, and the capability of passing subprograms as parameters to other subprograms.

9. Why in your opinion, did Fortran allow names that began with I, J, K, L, M, and N as implicitly integer type?

In my opinion Fortran allowed it due to the programmers habits of using those character as name of variable. And it eased the programmers to declare the variable with int data type whenever they needed it.

10. Outline the major developments in ALGOL 60.Major development of ALGOL 60:

– The concept of block structure was introduced. This allowed the programmer to localize parts of programs by introducing new data environments, or scopes.

– Two different means of passing parameters to subprograms were allowed: pass by value and pass by name.

– Procedures were allowed to be recursive. The ALGOL 58 description was unclear on this issue. Note that although this recursion was new for the imperative languages, LISP had already provided recursive functions in 1959.

– Stack-dynamic arrays were allowed. A stack-dynamic array is one for which the subscript range or ranges are specified by variables, so that the size of the arrays is set at the time storage is allocated to they array, which happens when the declaration is reached during execution.

15. Are there any non procedural languages other than Prolog?

Yes there are, SQL is non procedural languages.

16. What is your opinion of the argument that languages that are too complex are too dangerous to use, and we should therefore keep all languages small and simple?

My opinion about it is that those language are literally not dangerous. It is dangerous if an amateur tries to create a complex program with less understanding of concept of that languages which are too complex. If it is reachable to create a language which are small and simple, why not? As long as it can provide all that we need to create a program. Regarding simplicity is one of the characteristic that a programming language should have.

24. Why, in your opinion, do new scripting languages appear more frequently than new compiled languages?

In opinion I think it is because a scripted language is easier for the beginner to learn and implement than a compiled language. And also due to scripting languages efficiency of its ease built in interfaces and give the fastest turnaround from script to execution.

25. Give a brief general description of the Java servlet.

Java servlet is Java platform technology of choice for extending and enhancing Web servers. Servlets provide a component-based, platform-independent method for building Web-based applications, without the performance limitations of CGI programs. And unlike proprietary server extension mechanisms (such as the Netscape Server API or Apache modules), servlets are server- and platform-independent.

Concepts of Programming Languages – Chapter 1 – Preliminaries

Review Questions:

6. In what language is most of UNIX written?

UNIX operating system is written almost entirely in C (ISO, 1999), which has made it relatively easy to port, or move, to different machines.

9. What is one example of a lack of orthogonality in the design of C?

Example of lack of orthogonality in C is although C has two kinds of structured data types, arrays, and records (structs), records can be returned from functions but arrays cannot. A member of a structure ca be any data type except void or a structure of the same type. An array element can be any data type except void or a function. Parameters are passed by value, unless they re arrays, in which case they are, in effect, passed by reference ( because the appearance of an array name without a subscript in a C program is interpreted to be the address of the array’s first element). As an example of context dependence, consider the C expression

A + B

This expression often means that the values of a and b are fetched and added together. However, if a happens to be a pointer, it affects the value of b. For example, if a points to a float value that occupies four bytes, then the value of b must be scaled, in this case multiplied by 4, before it is added to a. Therefore, the type of a affects the treatment of the value of b. The context of b affects its meaning.

13. What does it mean for a program to be reliable?

A program is said to be reliable if it performs to its specifications under all conditions. It is including the:

-Type checking. Simply testing for type errors in a given program, either by the compiler or during program execution.

-Exception handling. Ability of a program to intercept run-time errors(as well as other unusual conditions detectable by the program), take corrective measures, and then continue is an obvious aid to readability,

-Aliasing. Having two or more distinct names that can be used to access the same memory cell. Others languages greatly restrict aliasing to increase their reliability.

15. What is aliasing?

Aliasing is having two or more distinct names that can be used to access the same memory cell. Others languages greatly restrict aliasing to increase their reliability.

16. What is exception handling?

Exception handling is ability of a program to intercept run-time errors(as well as other unusual conditions detectable by the program), take corrective measures, and then continue is an obvious aid to readability,

17. Why is readability important to writability?

Because most of the language characteristic that affect readability also affects writability. This follows directly from the fact that the process of writing a program requires the programmer frequently to reread the part of the program that is already written.

29. What is a hybrid implementation system?

Hybrid Implementation System is a compromise between compilers and pure interpreters; they translate high-level language programs to an intermediate language designed to allow easy interpretation.

30. What are the advantages of using Borland JBuilder?

The advantages of Borland JBuilder is the programming environment provided that provides ant integrated compiler, editor, debugger, and file system for Java development, where all four are accessed through a grapahical interface. JBuilder is also a complex and powerful system for creating Java software.

Problem Set

1. Do you believe that solving a problem in a particular algorithmic step requires programming languages skills? Support your opinion.

I believe that solving a problem in a particular algorithmic step requires programming language skills because by using programming language skill we can solve the problem itself easier and more efficient by the features included in the programming language.

2. Who is said to be the first programmer in human history? Use the Internet for help.

Augusta Ada King, Countess of Lovelace (10 December 1815 – 27 November 1852), born Augusta Ada Byron and now commonly known as Ada Lovelace, was an English mathematician and writer chiefly known for her work on Charles Babbage‘s early mechanical general-purpose computer, the Analytical Engine. Her notes on the engine include what is recognized as the first algorithm intended to be processed by a machine. Because of this, she is often considered the world’s first computer programmer.

4. In what way do the languages for scientific applications differ from the languages for business applications? Support your view.

Scientific applications uses relative simple data structure, but required large numbers of floating point arithmetic computations. The most common data structures were arrays and matrices; the most common control structures were counting loops and selections. Rather than business applications, it is characterized by facilities for producing elaborate reports, precise ways of describing and storing decimal numbers and character data, and the ability to specify decimal arithmetic operations. Also scientific is usually used for a specific measurement that scientist does rather than a business application that is purposed for business needs.

5. In what way do the languages for artificial intelligence differ from the languages for web software? Support your view.

Artificial Intelligence is a broad area of computer application characterized by the use of symbolic rather than numeric computations. Symbolic computations means that symbols, consisting of names rather than numbers, are manipulated. Also, symbolic computation is more conveniently done with linked list of data rather than arrays. This kind of programing sometimes requires more flexibility than other programming domains. It is different with web software that is supported by an electric collection of languages, ranging from markup languages, such as HTML, which is not a programming language, to general-purpose programing language. It is clear enough that from the point view of needs, we have already been able to determine that the needs of its each need is different.

6. Which characteristic of programming languages do you think are the most important and why?

I think the most important characteristics of programming languages are writability and readability. Because two of them are the key we can understand to learn programming languages. Moreover both of them scope others characteristic too including the orthogonality and simplicity. Eventually other characteristics are important too.

9. Explain how orthogonality in programming language is closely related to simplicity.

Orthogonality is closely related to simplicity because the more orthogonal the design of a language, the fewer exceptions the languages rules require. Fewer exceptions mean a higher degree of regularity in the design, which makes the language easy to learn, read, and understand.

12.Can we call any programming language complete, in your opinion? Why or why not?

We can’t call any programming language complete because every programming language is created for different needs changing and developing through times. Therefore, a programming language is never said complete so they will have to renew / update or even programmers may have to create a new programming languages.

17. Some programming languages-for example, SQL-use “=” to check the equality of two expressions, while C uses it to assign values to variable. Which of those, in your opinion, is most natural and least likely to result in syntax errors? Support your answer.

I think C is more natural and least likely to result in syntax error. Because the use of “=” as the equality of expression is usually used in the if-statement, instead we often do assigning value rather than comparing equality, hence we use “=” to assign value.

Stevanus Sugianto – 02PBT – 1601210764

Hello there! Finally I made this blog which currently functions as a page to do my Concepts of Programming Languages homework.

Lecturer: Mr. Tri Djoko Wahyono

Text Book: Concepts of Programming Languages, Tenth Edition. Robert W. Sebesta.

Name: Stevanus. Sugianto

NIM: 1601210764

Class: 02-PBT