Assignment #5 (Concepts of Programming Languages Chapter 5 Problem Set)

Problem Set

7. Assume the following JavaScript program was interpreted using static-scoping rules. What value of x is displayed in function sub1? Under dynamic-scoping rules, what value of x is displayed in function sub1 ?
Answer :
var x;
function sub1() {
document.write(“x = ” + x + “<br />”);
}
function sub2() {
var x;
x = 10;
sub1();
}
x = 5;
sub2();

Answer:
Static scope: x=5, Dynamic scoping: x=10.

8. Consider the following JavaScript program:
Answer :
var x, y, z;
function sub1() {
var a, y, z;
function sub2() {
var a, b, z;
. . .
}
. . .
}
function sub3() {
var a, x, w;
. . .
}
List all the variables, along with the program units where they are declared, that are visible in the bodies of sub1, sub2, and sub3, assuming static scoping is used.
Answer:
Sub1: a(sub1), y(sub1), z(sub1), x(main)
Sub2: a(sub2), b(sub2), z(sub2), y(sub1), x(main)
Sub3: a(sub3), x(sub3), w(sub3), y(main), z(main)

9. Consider the following Python program:
Answer :
x = 1;
y = 3;
z = 5;
def sub1():
a = 7;
y = 9;
z = 11;
. . .
def sub2():
global x;
a = 13;
x = 15;
w = 17;
. . .
def sub3():
nonlocal a;
a = 19;
b = 21;
z = 23;
. . .
. . .
List all the variables, along with the program units where they are
declared, that are visible in the bodies of sub1, sub2, and sub3, assumingstatic scoping is used.

Answer:
point 1 :  x = 1(main), y = 9 (sub1), z = 11(sub1) ,a = 7(sub1);
point 2 :  x =15(sub2), w = 17(sub2), a = 13(sub2), y = 9(sub1);
point 3 :  x = 15(sub2), b = 21(sub3), a = 19(sub1), z = 23(sub3), w = 17(sub 2);
point 4 :  x = 15(sub2), b = 21(sub3), a = 19(sub1), z = 23(sub3), w = 17(sub 2);

10. Consider the following C program:
Answer :

void fun(void) {
int a, b, c; /* definition 1 */
. . .
while (. . .) {
int b, c, d; /*definition 2 */
. . . 1
while (. . .) {
int c, d, e; /* definition 3 */
. . . 2
}
. . . 3
}
. . . 4
}
For each of the four marked points in this function, list each visible variable,
along with the number of the definition statement that defines it.

Answer:
Point 1: a:1, b:2, c:2, d:2
Point 2: a:1, b:2, c:3, d:3, e:3
Point 3: a:1, b:2, c:2, d:2
Point 4: a:1, b:1, c:1

11. Consider the following skeletal C program:
Answer :
void fun1(void); /* prototype */
void fun2(void); /* prototype */
void fun3(void); /* prototype */
void main() {
int a, b, c;
. . .
}
void fun1(void) {
int b, c, d;
. . .
}
void fun2(void) {
int c, d, e;
. . .
}
void fun3(void) {
int d, e, f;
. . .
}
Given the following calling sequences and assuming that dynamic scoping
is used, what variables are visible during execution of the last function
called? Include with each visible variable the name of the function in
which it was defined.
a. main calls fun1; fun1 calls fun2; fun2 calls fun3.Answer:
var a = main ; var b = fun1 ; var c = fun2 ;var d,e,f = fun3

b. main calls fun1; fun1 calls fun3.Answer:
var a = main; var b,c = fun1; var d,e,f = fun3

c. main calls fun2; fun2 calls fun3; fun3 calls fun1.
Answer:
var a= main; var b,c,d = fun1 ;var e,f = fun3

d. main calls fun3; fun3 calls fun1.
Answer:
var a = main; var b,c,d = fun1; var e,f = fun3

e. main calls fun1; fun1 calls fun3; fun3 calls fun2.
Answer:
var a=main;var c,d,e=fun2; var b =fun1; var f= fun3

f. main calls fun3; fun3 calls fun2; fun2 calls fun1.
Answer:
var a=main; var b,c,d = fun1; var f= fun3;var e=fun2

12. Consider the following program, written in JavaScript-like syntax:
// main program
var x, y, z;
Answer :
function sub1() {
var a, y, z;
. . .
}
function sub2() {
var a, b, z;
. . .
}
function sub3() {
var a, x, w;
. . .
}
Given the following calling sequences and assuming that dynamic scoping
is used, what variables are visible during execution of the last subprogram
activated? Include with each visible variable the name of the unit
where it is declared.
a. main calls sub1; sub1 calls sub2; sub2 calls sub3.Answer:
a x w in sub3. b, z in sub2, y in sub1.

b. main calls sub1; sub1 calls sub3.Answer:
a x w in sub3, y z in sub1.

c. main calls sub2; sub2 calls sub3; sub3 calls sub1.Answer:
a y z in sub1, x w in sub3, b in sub2.

d. main calls sub3; sub3 calls sub1.Answer:
a y z in sub1; x w in sub3;

e. main calls sub1; sub1 calls sub3; sub3 calls sub2.Answer:
a b z in sub2, x w in sub3; y in sub1.

f. main calls sub3; sub3 calls sub2; sub2 calls sub1.Answer:

a y z in sub1; b in sub2; x w in sub3.

Assignment #4 (Concepts of Programming Languages Chapter 4 Problem Set)

Problem Set 

A=Answer

6. 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.
A=
S → AbB bAc A → Ab aBB B → Ac cBb c a.

a. aAcccbbc
S -> AbB -> aBBbB -> aAcBbB -> aAccBbbB -> aAcccbbc

b. AbcaBccb
S -> AbB -> AbcBb -> AbcAcb -> AbcaBBcb -> AbcaBccb

c. baBcBbbc
S -> bAc -> baBBc -> baBcBbc -> baBcBbbc

7. Show a complete parse, including the parse stack contents, input string, and action for the string id * (id + id), using the grammar and parse table in Section 4.5.3.
A=

8. Show a complete parse, including the parse stack contents, input string, and action for the string (id + id) * id, using the grammar and parse table in Section 4.5.3.
A=

9. Write an EBNF rule that describes the while statement of Java or C++. Write the recursive-descent subprogram in Java or C++ for this rule.
A=

<while_stmt> -> WHILE ‘(‘ (<arith_expr> | <logic_expr>) ‘)’ <block> <block> -> <stmt> | ‘{‘ <stmt> {<stmt>} ‘}’

10. Write an EBNF rule that describes the for statement of Java or C++. Write the recursive-descent subprogram in Java or C++ for this rule.
A=

Assume the following non-terminals are given: <type>, <id>, <literal>, <assign>, <expr>, and <stmt_list>.

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

Assignment #5 (Concepts of Programming Languages Chapter 5 Review Questions)

Review Question

A=Answer

16. What is the referencing environment of a statement?
A=The referencing environment of a statement is the collection of all variables that are visible in the statement. The referencing environment of a statement in a static-scoped language is the variables declared in its local scope plus the collection of all variables of its ancestor scopes that are visible.

17. What is a static ancestor of a subprogram? What is a dynamic ancestor of a subprogram?
A=The static ancestors of a subprogram sub() are all the procedures in the program within which the procedure sub() is defined, i.e., the definition of the procedure sub() is nested. The definition of a procedure may be directly nested within only one procedure, called its static parent procedure. However, this static parent procedure may itself be nested within another procedure, and so on up to the main() program. All these procedures are considered to be static ancestors of the procedure sub(). Simply put, the static ancestors are those that strictly contain the subprogram in question.
The dynamic ancestors of a subprogram sub() are all the procedures called before sub() during the execution of a program, that have not yet finished executing. These are the procedures that are waiting for procedure sub() to finish executing before they can terminate. Simply put, dynamic ancestors are those that are called to reach the subprogram in question.

18. What is a block?
A=Such vari-ables are typically stack dynamic, so their storage is allocated when the section is entered and deallocated when the section is exited

19. What is the purpose of the let constructs in functional languages?
A=“let” introduces a new variable scope, and allows you to bind variables to values for that scope. It is often read as “let x be [value] in …”

20. What is the difference between the names defined in an ML let construct from the variables declared in a C block?

Assignment #4 (Concepts of Programming Languages Chapter 4 Review Questions)

REVIEW QUESTION :

A=Answer

16.  What is the FIRST set for a given grammar and sentential form ?

A=

FIRST( ) = {a => * a } (If => *  ,   is in FIRST( ))   

in which =>* means 0 or more derivation steps.

17.Describe the pairwise disjointness test.

A=It is a test of non-left recursive grammar that indicates whether left recursion can be done. It requires the ability to compute a set based on the RHSs of a given nonterminal symbol in a grammar.

18.What is left factoring ?

A=Left factoring is the action taken when a grammar leads backtracking while marking parsing/syntax tree.

19.What is a phrase of a sentential form ?

A=A phrase is a subsequence of a sentential form that is eventually reduced to a single non-terminal

20.What is a simple phrases of a sentential form?

A=simple phrases is just a phrase that takes a single derivation step from its root nonterminal node.

Assignment #3 (Concepts of Programming Languages Chapter 3 Problem Set)

Problem Set :

a=Answer

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

a. 

15. Convert the BNF of Example 3.1 to EBNF. 

a.

EBNF:

<program> → begin <stmt_list> end

<stmt_list> → <stmt> { ;  <stmt_list>}

<stmt> → <var> = <expression>

<var> → A | B | C

<expression> → <var> { (+|-) <var>}

16. Convert the BNF of Example 3.3 to EBNF. 

a.
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> {(+ | *) <expr>}
| <id>

17. Convert the following EBNF to BNF: S → A{bA} A → a[b]A 

a. 

S -> A | AX
X -> bA | bAX
A -> aA | abA

18. What is the difference between an intrinsic attribute and a nonintrinsic synthesized attribute?

a. An intrinsic attribute is an inherent characteristic of a terminal symbol in the grammar. So the value of the attribute is determined solely from the terminal symbol. A nonintrinsic synthesized attribute is an attribute of a non-terminal symbol in the grammar.

Assignment #3 (Concepts of Programming Languages Chapter 3 Review Questions)

Review Questions :

a=Answer

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

a. The mapping functions of a denotational semantics programming language specification, like all functions in math, have a domain and a range, the domain is called the syntactic domain, and the range is called the semantic domain.

17. What is stored in the state of a program for denotational semantics? 

a. The state of a program for denotational semantics is the value of all its current variable.

18. Which semantics approach is most widely known?

a. The Denotational semantics is the most widely known semantics approach.

19. What two things must be defined for each language entity in order to construct a denotational description of the language? 

a. objects and functions 

20. Which part of an inference rule is the antecedent? 

a. The antecedent is the top part of an inference rule.

21. What is a predicate transformer function? 

a. wp(statement, postcondition) = precondition A wp function is often called a predicate transformer, because it takes a predicate, or assertion, as a parameter and returns another predicate.

22. What does partial correctness mean for a loop construct? 

a. If loop termination can be shown, the axiomatic description of the loop is called total correctness. If the other conditions can be met but termination is not guaranteed, it is called partial correctness. computing the precondition for a while loop depends on finding a loop invariant, proving the correctness of programs with while loops using axiomatic semantics can be difficult.

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

a. Axiomatic semantics, thus named because it is based on mathematical logic.

24. On what branch of mathematics is denotational semantics based?

a. mathematical objects (called denotations). 

Assignment #2 (Concepts of Programming Languages Chapter 2 Problem Set)

Problem Set :

a=Answer

14. What are the arguments both for and against the idea of a typeless language? 
Arguments for the idea:

a. Flexibility, Brevity of syntax. It places stricter controls on what objects can receive and send, so making it easier to enforce design strategies throughout the application. When there are errors in types, there can be picked up during precompilation or in the IDE.

Arguments against the idea:

a. Without type checking, there is no means to verify the integrity of the data without executing the application. The syntax of typed languages can be viewed as overly long or verbose. Typed languages aren’t as flexible as untyped languages, as data structures need to be cast to the correct type before another object can receive them. It is also said that by using typed languages, the compiler spends less time dynamically typing objects and so executes faster. However, this point is a grey area and that the main area of argument is how these language differences play out when designing applications where more then a few people are working on the code.

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

a. Yes, there are Fortran, C++, COBOL, Algol.

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? 

a. Languages are too complex are too dangerous to use because of its meaning itself. Ambiguous languages can cause trouble and misunderstanding among people.    So, we must keep it small and simple to avoid ambiguation and misunderstanding.

17. Do you think language design by committee is a good idea? Support your opinion. 

a. Language design by committee definitely has its advantages, with varying points of view from different domains, different programming backgrounds, and even different language backgrounds all contributing for the better of the language like ALGOL 58. Knowledge of Plankalkul enhanced ALGOL 58 because members from Europe were familiar with the language. Improvements like variable length identifiers and array dimensions were improved upon previous languages. Even though many arguments and conflicts arise, like whether to use a comma (European) or a period (American) for a decimal point took place, it is beneficial to have options. I think history would show that the best use of committees would be after a language has been invented and accepted. At this point a better evaluation is possible and committee members would be better conditioned to make improvements than initial discoveries.

18. Languages continually evolve. What sort of restrictions do you think are appropriate for changes in programming languages? Compare your answers with the evolution of Fortran.

a. A good deal of restraint must be used in revising programming languages. The greatest danger is that the revision process will continually add new features, so that the language grows more and more complex. Compounding the problem is the reluctance, because of existing software, to remove obsolete features.

Assignment #2 (Concepts of Programming Languages Chapter 2 Review Questions)

Review Questions :

a=Answer

16. In what way are Scheme and Common LISP opposites of each other? 

a. In its sizes, complexity, adn scoping(scheme: static scoping, Common LISP: both dynamic and static scoping).

17. What dialect of LISP is used for introductory programming courses at some universities?

a. Scheme

18. What two professional organizations together designed ALGOL 60?

a. The two professional organizations are Association for Computing Machinery (ACM) and GAMM

19. In what version of ALGOL did block structure appear?

a. ALGOL 60

20. What missing language element of ALGOL 60 damaged its chances for widespread use?

a. The lack of input and output statements with formatting

21. What language was designed to describe the syntax of ALGOL 60?

a. The language was  Backus Naur Form (BNF), which was Backus’s new notation for describing syntax of programming languages.

22. On what language was COBOL based?

a. FLOW-MATIC

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

a. The beginning of COBOL similar to ALGOL 60 that was designed by a committee of people meeting for relatively short periods of time and in 1959, the design process of COBOL began and sponsored by the Department of Defense.

24. What data structure that appeared in COBOL originated with Plankalkül? 

a. Hierarchical data structure