Chapter 6 - programming Language

Review Question : 
------------------------------------------------------------------------------------------------------------
6. What are the advantages of user-defined enumeration types?

• The advantages are readability and reliability.

7.In what ways are the user-defined enumeration types of C# more reliable than those of C++?

• C# enumeration types are like those of C++, except that they are never coerced to integer. So, operations on enumeration types are restricted to those that make sense. Also, the range of values is restricted to that of the particular enumeration type.

8. What are the design issues for arrays?
The primary design issues specific to arrays are the following:

• What types are legal for subscripts?
• Are subscripting expressions in element references range checked?
• When are subscript ranges bound?
• When does array allocation take place?
• Are ragged or rectangular multidimensioned arrays allowed, or both?
• Can arrays be initialized when they have their storage allocated?
• What kinds of slices are allowed, if any?

9 Define static, fixed stack-dynamic, stack-dynamic, fixed heap-dynamic, and heap-dynamic arrays. What are the advantages of each?

• Static: subscript ranges are statically bound and storage allocation is static (before run-time). Advantage: efficiency (no dynamic allocation). 
• Fixed stack-dynamic: subscript ranges are statically bound, but the allocation is done at declaration time. Advantage: space efficiency. 
• Stack-dynamic: subscript ranges are dynamically bound and the storage allocation is dynamic (done at run-time). Advantage: flexibility (the size of an array need not be known until the array is to be used). 
• Fixed heap-dynamic: similar to fixed stack-dynamic: storage binding is dynamic but fixed after allocation. Advantage: space efficiency, storage is allocated from heap, and binding is done when requested. 
• Heap-dynamic: binding of subscript ranges and storage allocation is dynamic and can change any number of times. Advantage: flexibility (arrays can grow or shrink during program execution).

10. What happens when a nonexistent element of an array is referenced

in Perl?

• No error will be reported

Programming Language :

------------------------------------------------------------------------------------------------------------

6. Explain all of the differences between Ada’s subtypes and derived types.

• A subtype is compatible with its base type, so you can mix operands of the base type with operands of the base type. For example:
• subtype Week_Days is Integer range 1..7; Since this is a subtype, you can (for example) add 1 to a weekday to get the next weekday.
• A derived type is a completely separate type that has the same characteristics as its base type. You cannot mix operands of a derived type with operands of the base type. If, for example, you used:
• type Week_Day is new Integer range 1..7;  Then you would not be able to add an integer to a weekday to get another weekday. To do manipulations on a derived type, you'd normally define those manipulations yourself (e.g., create a package). At the same time, a derived type does "inherit" all the operations of its base type (even some that may not make sense) so you do still get addition.

7.What significant justification is there for the -> operator in C and C++?

• The only justification for the -> operator in C and C++ is writability. It is slightly easier to write p -> q than (*p).q.

8.What are all of the differences between the enumeration types of C++ and those of Java?

• In C++, an enumeration is just a set of named, integral constants. In Java, an enumeration is more like a named instance of a class. You have the ability to customize the members available on the enumeration.Also, C++ will implicitly convert enum values to their integral equivalent, whereas the conversion must be explicit in Java.

9.The unions in C and C++ are separate from the records of those languages, rather than combined as they are in Ada. What are the advantages and disadvantages to these two choices?

• Ada :
• Advantage:
• Unconstrained variant records in Ada allow the values of their variants to change types during execution.

• disadvantage:
• However, the type of the variant can be changed only by assigning the entire record, including the discriminant. This disallows inconsistent records because if the newly assigned record is a constant data aggregate, the value of the tag and the type of the variant can be statically checked for consistency.

10. Multidimensional arrays can be stored in row major order, as in C++, or in column major order, as in Fortran. Develop the access functions for both of these arrangements for three-dimensional arrays.

• Let the subscript ranges of the three dimensions be named min(1), min(2), min(3), max(1), max(2), and max(3). Let the sizes of the subscript ranges be size(1), size(2), and size(3). Assume the element size is 1.
• Row Major Order:
• location(a[i,j,k]) = (address of a[min(1),min(2),min(3)])+((i-min(1))*size(3) + (j-min(2)))*size(2) + (k-min(3))
• Column Major Order:
• location(a[i,j,k]) = (address of a[min(1),min(2),min(3)])+((k-min(3))*size(1) + (j-min(2)))*size(2) + (i-min(1))

dedi sutomo

1801376582

Assignment #5 - Programming Language (Chapter 5)

.: Chapter 5 :.

--------------------------------------------------------------------------------------------------------------------------Review Questions:--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

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

• The l-value of variable is the address of a variable because the address is required when the name of a variable appears in the left side of an assignment. While r-value of variable is a variable’s value because it is required when the name of the variable appears in the right side of an assignment statement.

7. Define binding and binding time.

• A binding is an association between an attribute and an entity, such as between a variable and its type or value, or between an operation and a symbol. While the time at which a binding takes place is called binding time.

8. After language design and implementation [what are the four times bindings can take place in a program?]

• First the compile time binding, second the load time binding, third the link time binding and lastly the run time binding.

9. Define static binding and dynamic binding.

• A static binding is when the binding occurs before run time begins and remains unchanged throughout program execution. If the binding first occurs during run time or can change in the course of program execution, it is called dynamic binding.

10. What are the advantages and disadvantages of implicit declarations?

• The advantage of implicit declarations is that Simple in naming conventions. In this case, the compiler or interpreter binds a variable to a type based on the syntactic form of the variable’s name. While the disadvantage of implicit declarations is it can be detrimental to reliability because they prevent the compilation process from detecting some typographical and programmer errors.

Problem Sets:

6. Consider the following JavaScript skeletal program:

// The main program

var x;

function sub1() {

var x;

function sub2() {

…

}

}

function sub3() {

…

}

Assume that the execution of this program is in the following unit order:

main calls sub1

sub1 calls sub2

sub2 calls sub3

a. Assuming static scoping, in the following, which declaration of x is the correct one for a reference to x?

i. sub1

sub1: sub1

ii. sub2

sub2: sub1

iii. sub3

sub3: main

b. Repeat part a, but assume dynamic scoping.

i. sub1

sub1: sub1

ii. sub2

sub2: sub1

iii. sub3

sub3: sub1

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?

var x;
function sub1() {
document.write(“x = ” + x + “<br />”);
}
function sub2() {
var x;
x = 10;
sub1();
}
x = 5;
sub2();

static scoping rule = 5

dynamic scoping rule = 10

8. Consider the following JavaScript program:

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.

Variable                       Where Declared

In Sub1:

a                                             Sub1

y                                             Sub1

z                                             Sub1

x                                             Main

In Sub2:

a                                             Sub2

b                                             Sub2

z                                             Sub2

y                                             Sub1

x                                             Main

In Sub3:

a                                             Sub3

x                                             Sub3

w                                            Sub3

y                                             Main

z                                             Main

9. Consider the following Python program:

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, assuming static scoping is used.

Variable                       Where Declared

In Sub1:

a                                              Sub1

y                                              Sub1

z                                              Sub1

x                                              Main

In Sub2:

a                                              Sub2

x                                              Sub2

w                                             Sub2

y                                              Main

z                                              Main

In Sub3:

a                                              Sub3

b                                              Sub3

z                                              Sub3

w                                             Sub2

x                                              Sub2

y                                              Main

10. Consider the following C program

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 4 marked points, list all visible variables, along with the number of the definition statement that defines it.

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

dedi sutomo

1801376582

Assignment #4 - Programming Language (Chapter 4)

Review Question :
--------------------------------------------------------------------------------------------------------------------------
6. What is a state transition diagram?

• A state transition diagram is a directed graph. Where the nodes of a state diagram are labeled with state names.

7. Why are character classes used, rather than individual characters, for the letter and digit transitions of a state diagram for a lexical analyzer?

• Suppose we need a lexical analyzer that recognizes only arithmetic expressions,
  including variable names and integer literals as operands. Assume that
  the variable names consist of strings of uppercase letters, lowercase letters, and digits but must begin with a letter. Names have no length limitation. The first
  thing to observe is that there are 52 different characters (any uppercase or lowercase letter) that can begin a name, which would require 52 transitions from the transition diagram’s initial state. However, a lexical analyzer is interested only in determining that it is a name and is not concerned with which specific
  name it happens to be. Therefore, we define a character class named LETTER
  for all 52 letters and use a single transition on the first letter of any name.

8. What are the two distinct goals of syntax analysis?

• First, the syntax analyzer must check the input program to determine whether it is syntactically correct.
  When an error is found, the analyzer must produce a diagnostic message and
  recover. In this case, recovery means it must get back to a normal state and
  continue its analysis of the input program. This step is required so that the
  compiler finds as many errors as possible during a single analysis of the input
  program. If it is not done well, error recovery may create more errors, or at
  least more error messages. The second goal of syntax analysis is to produce a
  complete parse tree, or at least trace the structure of the complete parse tree,
  for syntactically correct input. The parse tree (or its trace) is used as the basis
  for translation.

9. Describe the differences between top-down and bottom-up parsers.

• Top-down, meaning they construct left most derivations and a parse tree in top-down order, which mean the tree is built from the root downward to leaves. In bottom-up order the parse tree is built from leaves upward to the root.

10. Describe the parsing problem for a top-down parser.

• The general form of a left sentential form is xAy, whereby our notational conventions x is a string of terminal symbols, A is a non terminal, and y is a mixed string. Because x contains only terminals, A is the leftmost non terminal in the sentential form, so it is the one that must be expanded to get the next sentential form in a left- most derivation. Determining the next sentential form is a matter of choosing the correct grammar rule that has A as its LHS. For example, if the current sentential form is xAy and the A-rules are A → bB, A → cBb, and A → a, a top-down parser must choose among these three rules to get the next sentential form, which could be xbBy, xcBby, or xay. This is the parsing decision problem for top-down parsers.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

Problem Set :

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

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.

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.

Stack Input Action
0 id * (id + id) $ Shift 5
0id5 * (id + id) $ Reduce 6 (Use GOTO[0, F])
0F3 * (id + id) $ Reduce 4 (Use GOTO[0, T])
0T2 * (id + id) $ Reduce 2 (Use GOTO[0, E])
0T2*7 (id + id) $ Shift 7
0T2*7(4 id + id ) $ Shift 4
0T2*7(4id5 + id ) $ Shift 5
0T2*7(4F3 + id ) $ Reduce 6 (Use GOTO[4, F])
0T2*7(4T2 + id ) $ Reduce 4 (Use GOTO[4, T])
0T2*7(4E8 + id ) $ Reduce 2 (Use GOTO[4, E])
0T2*7(4E8+6 id ) $ Shift 6
0T2*7(4E8+6id5 ) $ Shift 5
0T2*7(4E8+6F3 ) $ Reduce 6 (Use GOTO[6, F])
0T2*7(4E8+6T9 ) $ Reduce 4 (Use GOTO[6, T])
0T2*7(4E8 ) $ Reduce 1 (Use GOTO[4, E])
0T2*7(4E8)11 $ Shift 11
0T2*7F10 $ Reduce 5 (Use GOTO[7, F])
0T2 $ Reduce 5 (Use GOTO[0, T])
0E1 $ Reduce 2 (Use GOTO[0, E])
–ACCEPT–

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.

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.

• <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.

• 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 #3 - Programming Language (Chapter 3)

Review Question :
--------------------------------------------------------------------------------------------------------------------------
6. Define a left-recursive grammar rule.

• A left-recursive grammar means that the parser can get into a loop in the parsing rules without making any progress consuming the input. A grammar is left-recursive if we can find some non-terminal A which will eventually derive a sentential form with itself as the left-symbol.

7. What three extensions are common to most EBNFs?

• Denotes an optional part of a RHS, which is delimited by brackets, the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether, deals with multiple choice options.

8. Distinguish between static and dynamic semantics.

• Static semantics is only indirectly related to the meaning of programs during execution. Dynamic semantics is not universally accepted in notation.

9.What purpose do predicates serve in an attribute grammar?

• The use of predicates functions is to state the static semantic rules of the language.

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

• An inherited attribute proceeds in a top-down order, from roots to leaves. A synthesized attribute proceeds in a completely bottom-up order, from leaves to root.

---------------------------------------------------------------------------------------------------------------------------------

Problem Set :

---------------------------------------------------------------------------------------------------------------------------------

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

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

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

<id> -> A | B | C

<expr> – > <id> + <expr>

| <id> * <expr>

| ( <expr> )

| <id>

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

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

<id> -> A | B | C

<expr> – >  <id> * <expr>

| <id> + <id> *<id>

| ( <expr> )

| <id>

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

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

<id> -> A | B | C

<expr> – > <id> + <expr>

| <id> * <expr>

| ( <expr> )

| (<id>)

| <id>

7. Using the grammar in Example 3.4, show a parse tree and a leftmost derivation for each of the following statements:

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

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

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

b.)A = B + C + A

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

• A=<expr>
• A=<expr>+<term>
• A=<expr>+<term>+<term>
• A=<term>+<term>+<term>
• A=<factor>+<term>+<term>
• A=<id>+<term>+<term>
• A=A+<term>+<term>
• A=A+<factor>+<term>
• A=A+<id>+<term>
• A=A+C+<term>
• A=A+C+<factor>
• A=A+C+<id>
• A=A+C+A
• 
  

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

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

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

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

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

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

8. Prove that the following grammar is ambiguous!

<S> -> <A>

<S> -> <A> * <A> | <id>

<id> -> x | y | z

It has two distinct parse tree. Unambiguous grammar don't have 2 distinct parse tree.

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>

10. Describe, in English, the language defined by the following grammar:

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

LHS non-terminal S defined to non-terminal A, B, C, where A can be one or more a. B also can be one or more b and C can be one or more c.