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.