Assignment 6 Programming Language Concepts

Name : Alvin Theodora

NIM   : 1801428434

Here is the sixth assignment of Programming Language Concepts course. The question is taken from "Concepts of Programming Language, 10th edition" from Robert W. Sebesta in chapter 6:

Review Questions

1. What is a descriptor?

= A descriptor is the collection of the attributes of a variable. In an implementation, a descriptor is an area of memory that stores the attributes of a variable.

2. What are the advantages and disadvantages of decimal data types?

= The advantage of decimal types is being able to precisely store decimal values, at least those within a restricted range, which cannot be done with floating-point.

The disadvantage of decimal type is that the range of values is restricted because no exponents are allowed, and their representation in memory is mildly wasteful.

3. What are the design issues for character string types?

= Design issues for character string types are

1) Should strings be simply a special kind of character array or a primitive type?

2) Should strings have static or dynamic length?

4. Describe the three string length options.

= 1) Static length string : The length of string is static and set when the string is created.

2) Limited dynamic length strings : Allow strings to have varying length up to a declared and fixed maximum set by the variable’s definition. Such string variables can store any number of characters between zero and the maximum.

3) Dynamic length strings : Allow strings to have varying length with no maximum.

5. Define ordinal, enumeration, and subrange types.

= 1) Ordinal type is one in which the range of possible values can be easily associated with the set of positive integers. In Java, for example, the primitive ordinal types are integer, char, and Boolean.

2) Enumeration is one in which all of the possible values, which are named constants, are provided, or enumerated, in the definition. Enumeration types provide a way of defining and grouping collections of named constants.

3) Subrange is a contiguous subsequence of an ordinal type. For example, 12..14 is a subrange of integer type.

Problem Set

1. What are the arguments for and against representing Boolean values as single bits in memory?

= A Boolean value could be represented by a single bit. But, a single bit of memory cannot be accessed efficiently on many machines, so they are often stored in smallest efficiently addressable cell of memory, typically a byte.

2. How does a decimal value waste memory space?

= Decimal types are stored very much like character strings, using binary codes for decimal digits. These representations are called binary coded decimal (BCD). In some cases, they are stored one digit per byte, or two digits per byte. Either way, they take more storage than binary representations. It takes at least four bits to code a decimal digit. Therefore, to store a six-digit coded decimal number requires 24 bits of memory. However, it takes only 20 bits to store the same number in binary.

3. VAX minicomputers use a format for floating-point numbers that is not the same as the IEEE standard. What is this format, and why was it chosen by the designers of the VAX computers? A reference for VAX floating –point representations is Sebesta (1991).

= The existing DEC VAX formats, inherited from the PDP-11, because the PDP-11 had several uniquely innovative features, and was easier to program than its predecessors through the additional general-purpose registers.

4. Compare the tombstone and lock-and –key methods of avoiding dangling pointers, from the points of view of safety and implementation cost.

= Tombstones take more memory, while lock-and-key requires additional cpu time on each pointer assignment to copy key as well as pointer. Pointer arithmetic could overwrite key in the heap.

5. What disadvantages are there in implicit dereferencing of pointers, but only in certain contexts? For example, consider the implicit dereference of a pointer to a record in Ada when it is used to reference a record field.

= When implicit dereferencing of pointers occurs only in certain contexts, it makes the language slightly less orthogonal. The context of the reference to the pointer determines its meaning. This detracts from the readability of the language and makes it slightly more difficult to learn.

Assignment 5 Programming Language Concepts

Name : Alvin Theodora

NIM   : 1801428434

Here is the fifth assignment of Programming Language Concepts course. The question is taken from "Concepts of Programming Language, 10th edition" from Robert W. Sebesta in chapter 5:

Review Questions

1. What are the design issues for names?

= Case sensitivity and the relationship of names to special words, which are either reserved words or keywords, are the design issues for names.

2. What is the potential danger of case-sensitive names?

= To some people, it is a detriment to readability, because names that look similar in fact denote different entities.

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

= From language design aspects, reserved words are better than keywords because the ability to redefine keywords can be confusing. For example, in Fortran could have the following statements:

Integer Real

Real Integer

These statements declare the program variable Real to be Integer type and the variable Integer to be Real type.

4. What is an alias?

= Aliases are two or more variables bound to the same storage address.

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

= Union type. Union is a type whose variables may store different type values at different times during program execution.

Problem Set

1. Which of the following identifier forms is most readable? Support your decision.

SumOfSales

sum_of_sales

SUMOFSALES

= sum_of_sales, because there are underscores which separate its word, and make it easier to read.

2. Some programming languages are typeless. What are the obvious advantages and disadvantages of having no types in a language?

= Advantage:

         1) It allows programmers to write sloppy programs quickly.

  Disadvantage:

         1) You are not in control of the data and variables, the compiler or interpreter is.

         2) If you mis-assign variables, there is no way for the compiler to catch any of your mistakes. It just “does what you said”,even if it is wrong.

         3) Supporting programs in a typeless language is much more difficult that in a strongly types one. It is often very difficult to determine what the original programmer wanted to do.

3. Write a simple assignment statement with one arithmetic operator in some language you know. For each component of the statement, list the various bindings that are required to determine the semantics when the statement is executed. For each binding, indicate the binding time used for the language.

= Java

count = count + 5;

Some of the bindings and their binding times for the parts of this assignment

statement are as follows:

• The type of count is bound at compile time.

• The set of possible values of count is bound at compiler design time.

• The meaning of the operator symbol + is bound at compile time, when the

types of its operands have been determined.

• The internal representation of the literal 5 is bound at compiler design

time.

• The value of count is bound at execution time with this statement.

4. Dynamic type binding is closely related to implicit heap-dynamic variables. Explain this relationship.

= Both are related to the assignment and the statement.

5. Describe a situation when a history-sensitive variable in a subprogram is useful.

= History sensitive variables may be useful in data manipulation subprograms, where some operation is performed on a variable, and the function exits, then the function is called again. This way, the function doesn’t have to take the variable as a parameter, but only to return it.

Assignment 4 Programming Language Concepts

Name : Alvin Theodora

NIM   : 1801428434

Here is the fourthassignment of Programming Language Concepts course. The question is taken from "Concepts of Programming Language, 10th edition" from Robert W. Sebesta in chapter 4:

Review Questions

1. What are three reasons why syntax analyzers are based on grammars?

= The most commonly used syntax description on syntax analyzers is context-free grammars or BNF. Using BNF, has at least three compelling advantages.

1) BNF descriptions of the syntax of programs are clear and concise, both for humans and for software systems.
2) BNF description can be used as the direct basis for the syntax analyzer.
3) Implementations based on BNF are relatively easy to maintain because of their modularity.



2. Explain the three reasons why lexical analysis is separated from syntax analysis.

= 1) Simplicity.
Techniques for lexical analysis are less complex than those required for syntax analysis, so the lexical-analysis process can be simpler if it is separate.

2) Efficiency.
Separation facilitates the optimization of lexical analyzer, because lexical analysis requires a significant portion of total compilation time.

3) Portability
Make the syntax analyzer to be platform independent from machine- dependent parts of the software system.



3. Define lexeme and token.

= ● Lexeme : Lowest level syntactic units.
   ● Tokens : Category of lexemes.



4. What are the primary tasks of a lexical analyzer?

= Lexical analyzers extract lexemes from a given input string and produce the corresponding tokens and then they detect syntactic errors in tokens.



5. Describe briefly the three approaches to building a lexical analyzer.

= These are three distinct approaches to construct a lexical analyzer:

1) Using a software tool to generate a table for a table-driven analyzer
2) Building such a table by hand
3) Writing code to implement a state diagram description of the tokens of the language being implemented.

Problem Set

1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
b. B → aB | bA | aBb
c. A → aaA | b | caB

=
a. FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test.

b. FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test.

c. FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test.

2. Perform the pairwise disjointness test for the following grammar rules.

a. S → aSB | bAA
b. A → b[aB] | a
c. B → aB | a

=
a. FIRST(aSb) = {a}, FIRST(bAA) = {b}, passes the test.

b. FIRST(b{aB}) = {b}, FIRST (a) = {a}, passes the test.

c. FIRST(aB) = {a}, FIRST(a) = {a}, Fails the test.

3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c
=
a + b * c

Call lex /* returns a */

Enter <expr>

Enter <term>

Enter <factor>

Call lex /* returns + */

Exit <factor>

Exit <term>

Call lex /* returns b */

Enter <term>

Enter <factor>

Call lex /* returns * */

Exit <factor>

Call lex /* returns c */

Enter <factor>

Call lex /* returns end-of-input */

Exit <factor>

Exit <term>

Exit <expr>

4. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a * (b + c)
a * (b + c)

=

Call lex /* returns a */

Enter <expr>

Enter <term>

Enter <factor>

Call lex /* returns * */

Exit <factor>

Call lex /* return (*/

Enter <factor>

Call lex /* returns b */

Enter <expr>

Enter <term>

Enter <factor>

Call lex /* returns + */

Exit <factor>

Exit <term>

Call lex /* returns c */

Enter <factor>

Exit <term>

Call lex / *return )*/

Exit <factor>

Exit <term>

Exit <expr>

Call lex /* returns end-of-input */

Exit <factor>

Exit <term>

Exit <expr>

5. Given the following grammar and the right sentential form, draw a parse tree and show the phrases and simple phrases, as well as the handle. S – > aAb | bBA A-> ab|aAB B->aB|b
a. aaAbb
b. bBab
c. aaAbBb

=
a.

parse tree =

S

/ | \

a A b

/|\

a A B

|

b

Handles = b, aAB

Phrases = aaAbb, aaABb, aAb

Simple Phrase = b

b.

parse tree =

S

/ | \

b B A

/ \

a b

Handles = ab

Phrases = bBab, bBA

Simple phrase = ab

c.aaAbBb = aSBb = aSBB = x

Assignment 3 Programming Language Concepts

Name : Alvin Theodora
NIM   : 1801428434

Here is the third assignment of Programming Language Concepts course. The question is taken from "Concepts of Programming Language, 10th edition" from Robert W. Sebesta in chapter 3:

Review Questions

1.       Define syntax and semantics.

= Syntax and semantics are related to each other, and both terms are used in relation to aspects of language. Syntax is the form of its language expressions, statements, and program units. Semantics is the meaning of those expressions and statements.

2.       Who are language descriptions for?

= Language description is like an instruction to use the language itself. Hence, the language description is made for the implementers, user, and also software developer to determine the semantics of a programming language.

3.       Describe the operation of a general language generator.

= A general language generator is a device that can be used to generate the sentences of a language. However, it generates sentence that is unpredictable, therefore a language generator is a limited usefulness as a language descriptor

4.       Describe the operation of a general language recognizer.

= A language recognizer is used to indicate whether the input of a given string is in a specific language or not. A language recognizer is capable of reading characters or string in the language. Such devices are like filters to determine whether the syntax is from a specific language.

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

= A sentence of a language is generated through sequence of the grammar’s rules. And, sentential form is each of the strings in the derivation of a grammar in programming language

Problem Set

1.       The two mathematical models of language description are generation and recognition. Describe how each can define the syntax of a programming language.

= A language recognizer is capable of reading characters or string in the language and determines whether the programs are in the specific language and syntactically correct. And a language generator is used to define the syntax of a language is true or not.

2.       Write EBNF descriptions for the following:

a.       A java class definition header statement

b.      A Java method call statement

c.       A C switch statement

d.      A C union definition

e.      C float literals

 a. a java class definition header statement

= <class_head> ® {<modifier>} class <id> [extends class_name] [implements<interface_name> {, <interface_name>}] <modifier> ® public | abstract | final<class_head> ® {<modifier>} class <id> [extendsclass_name] [implements<interface_name> {, <interface_name>}] <modifier> ® public | abstract | final

b. a Java method call statement

= <for> -> for ‘(‘ [[<type>] <id> = <expr> {, [<type>] <id> = <expr>}] ; [<expr>] ; [<expr>{, <expr>}] ‘)’ ‘{‘ <stmt_list> ‘}’

 c. a C switch statement

= <stmt>    ->   switch ( <int expr> ) {

case <int const> :  { <stmt> ; }

{ case <int const> :  { <stmt> ; }}

[ default :  { <stmt>  ;  } ]

}

d. a C union definition

= <union_defn> -> union <var_list> <union_identifier>;

<var_list> -> <list_of_data-type specifier> <var>

<list_of_data-type specifier> -> int | float | long |char | double

<union_identifier> -> <var>

e.      C float literals

= <float-literal> –>   <real> <suffix>

| <real> <exponent> <suffix>

| <integer> <exponent> <suffix>

3.       Rewrite the BNF of Example 3.4 to give + precedence over * and force + to be right associative.

= <assign>→<id>=<expr>
<id>→A|B|C
<expr>→< term >*< expr >| <term>
<term>→<term>+<factor>| <factor>
<factor>→(<expr>) | <id>



4.      Rewrite the BNF of Example 3.4 to add the ++ and – unary operators of Java.

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

<id> -> A | B | C

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

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

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

5.       Write a BNF description of the Boolean expressions of Java, including the three operators &&, ||,         and ! and the relational expressions.

= <Boolean_expr> -> <Boolean_expression> || <Boolean_term> | <Boolean_term>

<Boolean_term> -> <Boolean_term> && <Boolean_factor> | <Boolean_factor>

<Boolean_factor> -> id | ! <Boolean_factor> | ( <Boolean_expr> ) | <relation_expr>

<relation_expr> -> id = = id | id != id | id < id | id <= id | id >= id | id > id

Assignment 2 Programming Language Concepts

Name   : Alvin Theodora
NIM     : 1801428434

Here is the second assignment of Programming Language Concept course, taken from the tenth edition of "Concepts of Programming Language" book by Robert W. Sebesta chapter 2 :

Review Questions

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

= Plankalkul was designed in 1945, but Plankalkul was not published at that time, because of many factors, such as conditions in wartime and post-war Germany, and his efforts to commercialize the Z3 computer and its successors. And, Plankalkul was comprehensively published in 1972.

2.  What two common data structures were included in Plankalkul?

= Two common data structures in Plankalkul were arrays and records, which called structs in C-based language.

3.  How were the pseudocodes of the early 1950s implemented?

= The pseudocodes in early 1950s did not literally mean as its contemporary meaning. It was named the way it was, and to use for. At that time, there were no high programming languages, or even assembly language, so programming was done with machine code, which is error prone. These deficiencies led to the development of somewhat higher programming language, and it was named pseudocodes, but it had not been an assembly language though.

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

= The shortcoming of the computer hardware of the early 1950s were pseudoinstructions for the four arithmetic operations on floating point data and the novel facility of automatically incrementing address register. Because of such features, the writability to program was drastically improved, rather than using machine code.

5.  Why was the slowness of interpretation of programs acceptable in the early 1950s?

= At that time, there was still lack of floating point hardware in the available computers. All floating point operations had to be simulated to software, a very time-expense. Hence, the slowness of interpretation was still acceptable at that time.

Problem Set Question

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

= If Fortran 0 had been familiar with Plankalkul, Fortran 0 would have included arrays and records as its data structure, test the connectivity of a given graph, and perform syntax analysis on logic formulas that had parentheses and precedence.

2.  Determine the capabilities of Backus’s 701 Speedcoding system, and compare them with those of a contemporary programmable hand calculator.

= The Speedcoding interpreter effectively converted 701 to a virtual three-address floating-point calculator. The system included pseudoinstructions for the four arithmetic operations on floating-point data, but it has small limitations on the memory, for instance, the remaining usable memory after loading the interpreter was just 700 words and the add instruction took 4.2 milliseconds to execute. Contemporary programmable hand calculator was interpreted with the machine code, which has faster time-execution, however it could not handle complex syntax of arithmetic operations as speedcoding did.

3.  Write a short history of the A-0, A-1, and A-2 systems designed by Grace Hopper and her associates.

= Between 1951 and 1953, Grace Hopper and her associates developed a series of compiling system, named A-0, A-1, and A-2 that expanded pseusocode into machine code subprograms. The pseudocode source for this compiler was still quite primitive, however it had been a better improvement over the machine code because it made source programs much shorter.

4.   As a research project, compare the facilities of Fortran 0 with those of the Laning and Zierler system.

= -) Fortran 0 provided the efficiency of hand-coded programs and the ease of programming of the interpretive pseudocode systems.

   -) Laning and Zierler system translated arithmetic expressions, used separately coded subprograms to compute transcendental functions, and included arrays.

5.  Which of the three original goals of the ALGOL design committee, in your opinion, was most difficult to achieve at that time?

= Among of the three original goals of the ALGOL design committee, I think that the first goal point which is “The syntax of the language should be as close as possible to standard mathematical notation, and programs should be readable with little further explanation” was the most difficult to achieve at that time, because it competed with the another existing language ( Fortran ) for scientific applications to be the universal language of its application area at that time.

Assignment 1 Programming Language Concepts

Name: Alvin Theodora                                                                                                                NIM   : 1801428434

I make this blog as a requirement from my lecture Mr. Tri Djoko Wahjono,Ir.,M.sc. as a part of assignment in Programming Language Concepts course. And here is the first assignment, taken from tenth edition of book "Concepts of Programming Languages" by Robert W. Sebesta chapter 1 :

1. Why is it useful for a programmer to have some background in language design even though he or she may never actually design a programming language?

Answer:

We find it useful to have some background in language design because we can gain benefits from learning it, for instance, we will know the evolution of language design, from imperative language to functional language that discussed about the efficiency of both language. The development on programming design methodologies brought us too to emerge such a transition from procedure – oriented methodology to data – oriented which provided data abstraction, and it continued to begin new era to object – oriented which is more powerful and enhance its efficiencies.

All the points stated above lead us to widen our thoughts that new language constructs and designs is needed due to complexity of problems which computers had to solve along with technology development.

2. How can knowledge of programming language characteristics benefit the whole computing community?

Answer:

The understanding of programming language characteristics will benefit us because we can examine and evaluate the capabilities of one programming language to another on its writability, readability, and its reliability. And the most important, by knowing wider of language capabilities, we would be better able to choose language with the features that are more appropriate to the problems or tasks.

3. What programming language has dominated scientific computing over the past 50 years?

Answer:

Fortran is the most commonly used language in scientific applications, which is the first language for scientific applications and appeared in late 50s.

4. What programming language has dominated business applications over the past 50 years?

Answer:

COBOL is the most commonly used language in business applications, which appeared in 1960.

5. What programming language has dominated artificial intelligence over the past 50 years?

Answer:

LISP is the most commonly used language in artificial intelligence applications, which appeared in 1959.

6. Do you believe our capacity for abstract thought is influenced by our language skills? Support your opinion.

Answer:

Yes, it does. The more we know on languages, the more we can choose the best languages specific problems or tasks we encountered. The awareness of needing to learn various programming languages can reduce limitation of abstraction thoughts too and increase capacity to express ideas. With that knowledge, we can become a better programmer by understanding the choices among the programming language construct and features and its advantages and disadvantages. 

7. What are some features of specific programming languages you know whose rationales are a mystery to you?

Answer:

I am pretty curious about the logic programming language, such as Prolog. We know that logic programming language works in no particular order. It choose what procedure that has to come first to produce the desired results. I see this the same way as object-oriented language, so why does it have to create a logic programming language instead of making the object – oriented directly.

8. What arguments can you make for the idea of a single language for all programming domains?

Answer:

My arguments of a single language for all programming domains are: 

The advantages and disadvantages of a programming language are judged by its capability and criteria, such as writability, readability, reliability, simplicity, and etc. However, in my opinion, simplicity and reliability are the most important thing to design a language, because people these days need such a fast and practical in their lives. And reliability involves the effectiveness and a well-organized language construct, which shows the quality and integrity of a language. Moreover, one single language for all programming domains create a general language, so anyone just have to learn that language and will not make such confusion and learning other languages. So, for the points I stated above, I would say that we need a single language for all programming domains.

9. What arguments can you make against the idea of a single language for all programming domains?

Answer:

Here are my arguments against the single language for all programming domains. 

In order to make a very reliability language, it will be followed by a large number of basic construct of the language, which makes it difficult to read and has more complexity and impacts on execution time to be longer. But, to make a simple program, for example calculation program, it does not need a very complex construct in it, and the execution – time will be shorter. So, we cannot make a single language for all domains, every single language is divided by its capability and its own purpose as it was designed for. 

10. Name and explain another crtierion by which languages can be judged (in addition to those discussed in this chapter).

Answer: 

Another criterion for a programming language to be evaluated is by its user friendly. User friendly means the ease of use and to access the features in the programming language with an interface or construct which human can interpret it as well as human language itself.