ASSIGNMENT 5 PROGRAMMING LANGUAGE CONCEPT: names,binding and scopes FOR MR. TRI DJOKO WAHJONO

R E V I E W  Q U E S T I O N S

11. What are the advantages and disadvantages of dynamic type binding?

– Advantage of dynamic type binding is more flexible and easier to write generic code, but the disadvantages is that it took a long run-time type checking and interpretation

12. Define static, stack-dynamic, explicit heap-dynamic, and implicit heap- dynamic variables. What are their advantages and disadvantages?

Static memory is allocated before execution begins and remains bound to the same memory throughout the execution.

Advantages: Run-time efficient.
Disadvantages: There is no recursion.

Stack-dynamic memory allocation of the system is a pile when declarations are analyzed/described.
Advantages: There recursion and memory-efficient.
Disadvantages: Run-time is not as efficient as static.

Explicit heap-dynamic allocation and deallocation is with explicit instructions, specified by the programmer, which is valid for execution.
Advantages: flexible storage management.
Disadvantages: Prone to error in creating a new statement / delete statements.

Implicit heap-dynamic allocation and deallocation is caused by a statement.
Advantages: Flexibility is very high.
Disadvantages: When the run-time to keep all the attrs dynamic compiler error detection is reduced.

13. Define lifetime, scope, static scope, and dynamic scope.

• Lifetime is when memory is allocated for a variable (when it exists).
• Scope is the range of statements in which the variable is visible. Variables appear in an if statement can be referenced in the statement.
• Static scope is a scope that is based on program text and link reference to a variable name.
• Dynamic scope is a scope that is based on run-time call sequence.

14. How is a reference to a non-local variable in a static-scoped program connected to its definition?

– A reference to a non-local variables in static-scoped language with nested subprograms need access two-step process:
1) Find the correct activation record.
2)Determining the correct offset in activation record.

15. What is the general problem with static scoping?

– Usually too much access. The structure was destroyed as the evolution of the program scope.

PROBLEM SETS

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

– I prefered sum_of_sales, because it’s underscore (_) make me to read into space ( ).

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

Advantages: Allows users to write programs quickly.
Disadvantages: Can not control the data and variables, the compiler can not detect any errors.

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.

Language C ++

int count;
count = count*3;

Types are likely to be calculated: the language specified at design time.
Type count: Linked at compile time.
Set of possible values ​​of the count: Tied at the time of compiler design.
Value count: Tied at execution time with this statement.
The set of possible meanings for the operator symbol “”: * Tied on a definition of the language.
* The purpose of the operator symbol “” in this statement: Linked at compile time.
Internal representation of the literal “3”: Tied at the time of compiler design.

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

– Both are associated with the task and the statement

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

– History-sensitive variables may be useful in subprograms data manipulation, in which some of the operations performed on variables, and function out, then the function is called again. In this way, the function does not have to take a variable as a parameter, but only to return it.

ASSIGNMENT 4 PROGRAMMING LANGUAGE CONCEPT: Lexical and sintax analysis FOR MR. TRI DJOKO WAHJONO

R E V I E W  Q U E S T I O N S

11. Describe the parsing problem for a bottom-up parser

– Bottom-up parser can only identify and process the low level details of the structure of the text prior to the secondary level and leave the overall structure of the highest level.

12. Explain why compilers use parsing algorithms that work on only a subset of all grammars

– Because parsing algorithms that works for any unambiguous grammar are complex and inefficient. In fact, the complexity of the algorithm is O (n3). Algorithm is O (n3) is not usually useful for practical processes, such as analysis of the syntax for the compiler, because they are too slow. In this situation, computer scientists often look for a faster algorithm, although it is less common. In the case of parsing, faster algorithm has listed who work only a subset of the set of all possible grammar

13. Why are named constants used, rather than numbers, for token codes?

– Because named constants can used to simplify the reading of lexical and syntactic analysis

14. Describe how a recursive-descent parsing subprogram is written for a rule with a single RHS?

– Recursive-descent parsing subprogram is written for a rule with a single RHS is relatively simple. For each terminal symbol in the RHS, compared with nextToken terminal symbol. If they do not match, it is a syntax error. If they match, the lexical analyzer is called to get the next input token. For each nonterminal, parsing subprogram to be called nonterminal.

15.  Explain the two grammar characteristics that prohibit them from being used as the basis for a top-down parser.

– Two characteristics of grammar that prohibits top-down parsing: Left Recursion directly or indirectly.

PROBLEM SETS

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

a. A → aB | b | cBB
b. B → aB | bA | aBb
c. C→ aaA | b | caB

a.
A -> aB | b | CBB
first(aB) = a
first(b) = b
first(CBB) = aaA = a

b.
B -> aB | ba | aBb
first(aB) = a
first(ba) = b
first(aBb) = a
They intersect and rules frustrate the test.

c.
C -> aaA | b | caB
first(aaA) = a
first(b) = b
first(caB) = c
There is not any intersect so that the rules are passed.

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.
S→ aSb | bAA
first(aSb) = a
first(bAA) = b
There is not any intersect so that the rules are passed.

b.
A → b{aB} | a
first(b{aB}) = b
first(a) = a
There is not any intersect so that the rules are passed.

c.
B → aB | a
first(aB) = a
first(a) = a
They intersect and rules frustrate the test.

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

The next token is: 10 The next lexeme is a
Enter <expr>
Enter <term>
Enter <factor>

The next token is: 21 The next lexeme is +
Exit <factor>
Exit <term>

The next token is: 10 The next lexeme is b
Enter <term>
Enter <factor>

The next token is: 10 The next lexeme is *
Exit <factor>

The next token is: 26 The next lexeme is c
Enter<factor>

The next token is: -1 The next lexeme is EOF
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).

The next token is: 10 The next lexeme is a
Enter <expr>
Enter <term>
Enter <factor>

The next token is: 21 The next lexeme is *
Exit <factor>

The next token is: 25 The next lexeme is (
Enter <factor>

The next token is: 10 The next lexeme is b
Enter <expr>
Enter <term>
Enter <factor>

The next token is: 21 The next lexeme is +
Exit <factor>

The next token is: 26 The next lexeme is c
Enter <factor>

The next token is: 26 The next lexeme is )
Exit <term>
Exit <expr>

The next token is: -1 The next lexeme is EOF
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. aaAbb

Phrases: aaAbb, aAb, b
Simple phrases: b
Handle: b

b.bBab

Phrases: bBab, ab
Simple phrases: ab
Handle: ab

c. aaAbBb (no answer)

ASSIGNMENT 3 Programming Language Concept: DESCRIBING SYNTAX AND SEMANTICS FOR MR. TRI DJOKO WAHJONO

R E V I E W  Q U E S T I O N S

11. How is the order of evaluation of attributes determined for the trees of a given attribute grammar?

– The first we must put the most general one until the most specifics one (ex: human-organ system-organ-tissue-cell-molecule-atom). The most general one is human (you make it into other thing but in programming mostly is program) and the most specific atom (in programming mostly is variable (a,b,….,z) or constants (1,2,…..,n)).

12. What is the primary use of attribute grammars?

– In real life you can see the arrangement of position in a company but in programming it used for programmer to create a new formula to a program.

13. Explain the primary uses of a methodology and notation for describing the semantics of programming languages.

– Methodology and notation use to make the reader (computer/human) with more easily to understand the program. example “for” for blocking statements, and “=” is used for formula.

14. Why can machine languages not be used to define statements in operational semantics?

– Because just can only understand about “true” or false (‘0’ or ‘1’) but semantics are more than that.

15. Describe the two levels of uses of operational semantics.

-1)structural operational semantics (small-step semantics) formally describe how the individual steps of a computation take place in computer-based system. 2)Natural semantics (big-step semantics) describe how the overall results of executions are obtained.

PROBLEM SETS

1. Consider the following grammar:

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

<A> → <A> b | b

<B> → a <B> | a

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

1. baab
2. bbbab
3. bbaaaaa
4. bbaab

– a,b, and d

2. 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?

1. abcd
2. acccbd
3. acccbcc
4. acd
5. accc

– a and e

3. Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b, where n > 0. For example, the strings ab, aaaabbbb, and aaaaaaaabbbbbbbb are in the language but a, abb, ba, and aaabb are not.

<S> →  <A> <B>

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

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

or

<S> →  a <S> b  | ab

4. Draw parse trees for the sentences aabb and aaaabbbb, as derived from the grammar of Problem 13.

5. Convert the BNF of Example 3.1 to EBNF.

Program -> begin <stmt_list> end
<stmt_list -> <stmt> {; <stmt>)
stmt -> var = expression
var -> A | B | C
<exppression> -> <var> {(+|-) <var>}

Assignment 2 Programming Language Concept: EVOLUTION OF THE MAJOR PROGRAMMING LANGUAGE for Mr. Tri Djoko Wahjono

R E V I E W  Q U E S T I O N S

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

– Logical Boolean expressions and if-else statements.

2. Which version of Fortran was the first to have any sort of dynamic variables?

– Fortran 90 was the first version Fortran which had any sort of dynamic variables.

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

– Fortran 77 was the first to have character string handling.

4. Why were linguists interested in artificial intelligence in the late 1950s?

– Because they were concern with natural language processing. In that years, there are only computers with computation based on numeric data in arrays.

5. Where was LISP developed? By whom?

– LISP was developed at Massachusetts Institute of Technology (MIT) by John McCarthy

PROBLEM SETS

1. Was IBM’s assumption, on which it based its decision to develop PL/I, correct, given the history of computers and language developments since 1964?

– The assumption is correct because it has impressed widely for business and scientific applications.

2. Describe, in your own words, the concept of orthogonality in programming language design.

– It just like math in using ‘+’, ‘-’, ‘*’, ‘/’, ‘><’, ‘()’ and more to put which one is more important or which other logical concept for design.

3. What is the primary reason why PL/I became more widely used than ALGOL 68?

– Because PL/I is design to be all things to all programmer.

4. What are the arguments both for and against the idea of a typeless language?

– Argument “for” is more easy to use for blocking statements and argument “against” is more complicated for a programmer to express the statement to program.

5. Are there any logic programming languages other than Prolog?

– Yes, there are Flora-2, Absys, Logtalk, Oz, etc.

Assignment 1 Programming Language Concept: Preliminaries for Mr. Tri Djoko Wahjono

R E V I E W  Q U E S T I O N S

1. What primitive control statement is used to build more complicated control statements in languages that lack them?

– if and else, go to, do while such as for.

2. What construct of a programming language provides process abstraction?

– Subs programs

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

– Easy to understand by user (human) and computer, efficient (use less of memory and don’t waste the time), and the most important is it can be performed under every condition.

4. Why is type checking the parameters of a subprogram important?

– Because it make us know where’s still error.

5. What is aliasing?

– 2 or more distinct names that can be used to access the same memory cell.

PROBLEM SETS

1. Describe some design trade-offs between efficiency and safety in some language you know.

– I just know C, there’s some check of error list, warning. Because of “CASE SENSITIVE”, it make user become more know about where they did some error.

2. In your opinion, what major features would a perfect programming language include?

– Logical (need some keyword such as if, else, for, do, don’t, read, listen, play, etc), and can read calculation (such as +,-,*,/,sin, cos, tan, <, >, =, etc).

3. Was the first high-level programming language you learned implemented with a pure interpreter, a hybrid implementation system, or a compiler? (You may have to research this.)

– My first high programming language I learned is C++ which implemented with visual C++ and it’s compiler

4. Describe the advantages and disadvantages of some programming environment you have used.

– C++ is quiet simple because of human’s language keyword, and disadvantages is it still can’t use pseudocode for coding.

5. How do type declaration statements for simple variables affect the readability of a language, considering that some languages do not require them?

– I don’t really understand, but I think that you can put “” or make a statement with =.