Chapter 10

Review Questions
========================================================================

6. What is the difference between an activation record and an activation record instance?

*An activation record is the format, or layout, of the moncode part of a subprogram. An activation record instance is a concrete example of an activation record, a collection of data in the form of an activation record.


7. Why are the return address, dynamic link, and parameters placed in the bottom of the activation record?

*It's because the entry must appear first.


8. What kind of machines often use registers to pass parameters?

*RISC Machines often use registers to pass parameters.


9. What are the two steps in locating a nonlocal variable in a static-scoped language with stack-dynamic local variables and nested subprograms?

*First step, find correct activation record (the harder part) and then the second step is determine the offset within that activation record (easy part).


10. Define static chain, static_depth, nesting_depth, and chain_offset.

*Static chain is chain of static links connecting an activation record to all of it's static ancestors (it's enclosing subprograms).
Static depth is depth of the nesting for each enclosing static scope.
Nesting depth is the difference between the static depth of the reference and that of the scope where it was declared.
Chain offset is same as nesting depth.



========================================================================
Problem Set
========================================================================

6. Although local variables in Java methods are dynamically allocated at the beginning of each activation, under what circumstances could the value of a local variable in a particular activation retain the value of the previous activation?

*Each activation allocates variables in exactly the same order. Variables are not initialized to any value unless the program contains an initialization statement for the variable – they simply have whatever value is stored in the location they are allocated. If a procedure finishes executing, returns, and is immediately reinvoked, a variable would be assigned the same stack location it had on the previous invocation, and would have the last value from that previous invocation.


7. It is stated in this chapter that when nonlocal variables are accessed in a dynamic-scoped language using the dynamic chain, variable names must be stored in the activation records with the values. If this were actually done, every nonlocal access would require a sequence of costly string comparisons on names. Design an alternative to these string comparisons that would be faster.

*Using approach that uses an auxiliary data structure called a display. Or, to write variable names as integers. These integers act like an array. So when the activation happens, the comparisons will be faster.


8. Pascal allows gotos with nonlocal targets. How could such statements be handled if static chains were used for nonlocal variable access? Hint: Consider the way the correct activation record instance of the static parent of a newly enacted procedure is found (see Section 10.4.2).

*Based on the hint statement, the target of every goto in a program could be represented as an address and a nesting depth, where the nesting depth is the difference between the nesting level of the procedure that contains the goto and that of the procedure containing the target. Then, when a goto is executed, the static chain is followed by the number of links indicated in the nesting depth of the goto target. The stack top pointer is reset to the top of the activation record at the end of the chain.


9. The static-chain method could be expanded slightly by using two static links in each activation record instance where the second points to the static grandparent activation record instance. How would this approach affect the time required for subprogram linkage and nonlocal references?

*Including two static links would reduce the access time to nonlocals that are defined in scopes two steps away to be equal to that for nonlocals that are one step away. Overall, because most nonlocal references are relatively close, this could significantly increase the execution efficiency of many programs.


10. Design a skeletal program and a calling sequence that results in an activation record instance in which the static and dynamic links point to different activation-recorded instances in the run-time stack.

*\\
\emph{Answer}:\\
procedure Main\_2 is\\
\verb+ + X : Integer;\\
\verb+ +procedure Bigsub is\\
\verb+ +\verb+ + A, B, C : Integer;\\
\verb+ +\verb+ + procedure Sub1 is\\
\verb+ +\verb+ +\verb+ + A, D : Integer;\\
\verb+ +\verb+ +\verb+ + begin -- of Sub1\\
\verb+ +\verb+ +\verb+ + A := B + C; $\longleftarrow$ 1\\
\verb+ +\verb+ +\verb+ + ...\\
\verb+ + end; -- of Sub1\\
\verb+ + procedure Sub2(X : Integer) is\\
\verb+ +\verb+ + B, E : Integer;\\
\verb+ +\verb+ + procedure Sub3 is\\
\verb+ +\verb+ +\verb+ + C, E : Integer;\\
\verb+ +\verb+ +\verb+ + begin -- of Sub3\\
\verb+ +\verb+ +\verb+ + ...\\
\verb+ +\verb+ +\verb+ + Sub1;\\
\verb+ +\verb+ +\verb+ + ...\\
\verb+ +\verb+ +\verb+ + E := B + A; $\longleftarrow$ 2\\
\verb+ +\verb+ + end; -- of Sub3\\
\verb+ +\verb+ + begin -- of Sub2\\
\verb+ +\verb+ + ...\\
\verb+ +\verb+ + Sub3;\\
\verb+ +\verb+ + ...\\
\verb+ +\verb+ + A := D + E; $\longleftarrow$ 3\\
\verb+ + end; -- of Sub2\\
\verb+ + begin -- of Bigsub\\
\verb+ +\verb+ + ...\\
\verb+ +\verb+ + Sub2(7);\\
\verb+ +\verb+ + ...\\
\verb+ + end; -- of Bigsub\\
begin -- of Main\_2\\
\verb+ + ...\\
\verb+ + Bigsub;\\
\verb+ + ...\\
end; -- of Main\_2\\
\\
The sequence of procedure calls is:\\
Main\_2 calls Bigsub\\
Bigsub calls Sub2\\
Sub2 calls Sub3\\
Sub3 calls Sub1\\
\\
The activation records with static and dynamic links is as follows:\\
\begin{figure}
\centering
\includegraphics[scale=0.5]{ari}
\end{figure}


At position 1 in procedure Sub1, the reference is to the local variable,
A, not to the nonlocal variable A from Bigsub. This reference to A has the
chain\_offset/local\_offset pair (0, 3). The reference to B is to the nonlocal B
from Bigsub. It can be represented by the pair (1, 4). The local\_offset is 4,
because a 3 offset would be the first local variable (Bigsub has no parameters). Notice that if the dynamic link were used to do a simple search for
an activation record instance with a declaration for the variable B, it would
find the variable B declared in Sub2, which would be incorrect. If the (1, 4)
pair were used with the dynamic chain, the variable E from Sub3 would be
used. The static link, however, points to the activation record for Bigsub,
which has the correct version of B . The variable B in Sub2 is not in the
referencing environment at this point and is (correctly) not accessible. The
reference to C at point 1 is to the C defined in Bigsub, which is represented
by the pair (1, 5).\\
\\

\noindent

Chapter 9

Review Question:
========================================================================
6. What is a Ruby array formal parameter?

Ruby supports a complicated but highly flexible actual parameter configuration. The initial parameters are expressions, whose value objects are passed to the corresponding formal parameters. The initial parameters can be following by a list of key => value pairs, which are placed in an anonymous hash and a reference to that hash is passed to the next formal parameter. These are used as a substitute for keyword parameters, which Ruby does not support. The hash item can be followed by a single parameter preceded by an asterisk. This parameter is called the array formal parameter.


7. What is a parameter profile? What is a subprogram protocol?

Parameter profile is the number, order, and types of its formal parameters. Subprogram protocol is its parameter profile plus, if it is a function, its return type. In languages in which subprograms have types, those types are defined by the subprogram’s protocol.


8. What are formal parameters? What are actual parameters?

- Formal parameters are the parameters in the subprogram header.

- Actual parameters are a list of parameters to be bound to the formal parameters of the subprogram which must be included with the name of the subprogram by the subprogram call statements.


9. What are the advantages and disadvantages of keyword parameters?

- The advantage : they can appear in any order in the actual parameter list.

- The disadvantage : the user of the subprogram must know the names of formal parameters.

10. What are the differences between a function and a procedure?

A function returns value but procedures do not. Function are structurally resemble procedures but are semantically modeled on mathematical parameter.


========================================================================
Problem Sets:
========================================================================

6. Present one argument against providing both static and dynamic local variables in subprograms.

In subprograms local variables can be static or dynamic;
If local variable treated statically:
This allows for compile-time allocation/ deallocation and ensures proper type checking but does not allow for recursion.
If local variables treated dynamically:
This allows for recursion at the cost of run-time allocation/ deallocation and initialization because these are stored on a stack, referencing is indirect based on stack position and possibly time-consuming.


7. Consider the following program written in C syntax:
void fun (int first, int second) {
first += first; second += second;
}
void main() {
int list[2] = {1, 3};
fun(list[0], list[1]);
}

For each of the following parameter-passing methods, what are the values
of the list array after execution?
a. Passed by value : 1,3
b. Passed by reference : 2,6
c. Passed by value-result : 2,6


8. Argue against the C design of providing only function subprograms.

If a language provides only functions, then either programmers must live with the restriction of returning only a single result from any subprogram, or functions must allow side effects, which is generally considered bad. Since having subprograms that can only modify a single value is too restrictive, C’s choice is not good.


9. From a textbook on Fortran, learn the syntax and semantics of statement functions. Justify their existence in Fortran.

The Fortran 1966 standard provided a reference syntax and semantics, but vendors continued to provide incompatible extensions. These standards have improved portability.


10. Study the methods of user-defined operator overloading in C++ and Ada, and write a report comparing the two using our criteria for evaluating languages.

One of the nice features of C++ is that you can give special meanings to operators, when they are used with user-defined classes. This is called operator overloading. You can implement C++ operator overloads by providing special member-functions on your classes that follow a particular naming convention. For example, to overload the + operator for your class, you would provide a member-function named operator+ on your class. Meanwhile for Ada, since much of the power of the language comes from its extensibility, and since proper use of that extensibility requires that we make as little distinction as possible between predefined and user-defined types, it is natural that Ada also permits new operations to be defined, by declaring new overloading of the operator symbols.

Chapter 8

Review Question:

========================================================================

6. What is unusual about Python’s design of compound statements?

Python uses indentation to specify compound statements.
For example,
if x < y :
x = y
print "value of x is modified".
All statements equally indented are included in the compound statement.


7. Under what circumstances must an F# selector have an else clause?

An F# selector have an “else” clause if the “if” expression does return a value.


8.What are the common solutions to the nesting problem for two-way selectors?

A programmer should avoid syntactic entity because in some cases, syntactic entity leads to ambiguous meaning when it is compiled. Another way to avoid the issue of nested selection statements is to use an alternative means of forming compound statements.


9. What are the design issues for multiple-selection statements?

1. What is the form and type of the expression that controls the selection?• How are the selectable segments specified?
2. Is execution flow through the structure restricted to include just a single selectable segment?
3. How are the case values specified?
4. How should unrepresented selector expression values be handled, if at all?


10. Between what two language characteristics is a trade-off made when deciding whether more than one selectable segment is executed in one execution of a multiple selection statement?

The C# switch statement differs from that of its C-based predecessors in two ways. First, C# has a static semantics rule that disallows the implicit execution of more than one segment. The rule is that every selectable segment must end with an explicit unconditional branch statement: either a break,
which transfers control out of the switch statement, or a goto, which can transfer control to one of the selectable segments (or virtually anywhere else).

As with C, if there is no break at the end of the selected segment, execution continues into the next segment.


========================================================================
Problem Sets:

========================================================================

6. Analyze the potential readability problems with using closure reserved words for control statements that are the reverse of the corresponding initial reserved words, such as the case-esac reserved words of ALGOL 68. For example, consider common typing errors such as transposing characters.

The potential readability problem is the typing errors. It’s very possible to occur if we don’t type the code carefully.


7. Use the Science Citation Index to find an article that refers to Knuth (1974). Read the article and Knuth’s paper and write a paper that summarizes both sides of the goto issue.

An alternative viewpoint is presented in Donald Knuth's Structured Programming with go to Statements, which analyzes many common programming tasks and finds that in some of them GOTO is the optimal language construct to use.[7] In their quasi-standard book on the C programming language, Dennis Ritchie and Brian Kernighan warn that goto is "infinitely abusable", but also suggest that it could be used for end-of-function error handlers and for multi-level breaks from loops.


8. In his paper on the goto issue, Knuth (1974) suggests a loop control statement that allows multiple exits. Read the paper and write an operational semantics description of the statement.

Operational semantics are a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execution and procedures, rather than by attaching mathematical meanings to its terms (denotational semantics).


9. What are the arguments both for and against the exclusive use of Boolean expressions in the control statements in Java (as opposed to also allowing arithmetic expressions, as in C++)?

The primary argument for using Boolean expressions exclusively as control expressions is the reliability that results from disallowing a wide range of types for this use. In C, for example, an expression of any type can appear as a control expression, so typing errors that result in references to variables of incorrect types are not detected by the compiler as errors. No , it would not be a good idea. Although this custom precedence sounds like increasing flexibility, requiring parentheses to show a custom precedence would impact in readability and writability of a program.


10. In Ada, the choice lists of the case statement must be exhaustive, so that there can be no unrepresented values in the control expression. In C++, unrepresented values can be caught at run time with the default selector. If there is no default, an unrepresented value causes the whole statement to be skipped. What are the pros and cons of these two designs (Ada and C++)?

---- C++ :
1. Control expression can be only an integer type
2. Selectable segments can be statement sequences, blocks, or compound statements
3. Construct is encapsulated
4. Any number of segments can be executed in one execution of the construct (there is no implicit branch at the end of selectable segments) (a trade-off between reliability and flexibility–convenience) - To avoid it, the programmer must supply a break statement for each segment.
5. default clause is for unrepresented values (if there is no default, the whole statement does nothing)

----- Ada:
1. Constant lists can include: - Subranges e.g., 10..15
- Boolean OR operators
e.g., 1..5 | 7 | 15..20
2. Lists of constants must be exhaustive - Often accomplished with others clause
- This makes it more reliable

Chapter 7

Review Question :
========================================================================
6. What associativity rules are used by APL?

    :: APL used right to left associativity rules for all operators.

7. What is the difference between the way operators are implemented in C++ and Ruby?

    :: What sets Ruby apart from the C-based languages in the area of expressions is that all of the                 arithmetic, relational, and assignment operators, as well as array indexing, shifts, and bitwise               logic operators, are implemented as methods. For example, the expression a + b is a call to the +         method of the object referenced by a, passing the object referenced by b as a parameter.

8. Define functional side effect.

    :: A side effect of a function, naturally called a functional side effect, occurs when the function              changes either one of its parameters or a global variable. (A global variable is declared outside            the function but is accessible in the function.)

9. What is a coercion?

    :: Coercion was defined as an implicit type conversion that is initiated by the compiler.
       Type conversions explicitly requested by the programmer are referred to as explicit conversions,        or casts, not coercions.

10. What is a conditional expression?
      

      :: A conditional expression is an expression that returns value A or value B depending on whether          a Boolean value is true or false. A conditional expression lets you write a single assignment                statement that has the same effect as the following:
         if condition:

         x = true_value
         else:
         x = false_value

========================================================================

Problem Set

========================================================================

6. Should C’s single-operand assignment forms (for example, ++count) be included in other languages (that do not already have them)? Why or why not?

• Yes C should, because it will ease the increment or even decrement while we use in looping rather than manually by the assigning, and also by using that we can easily know that it is not operation, instead it is an increment or decrement which is usually used in repetition.

7. Describe a situation in which the add operator in a programming language would not be
commutative.

• It wouldn’t be commutative when it deals with the negative integers. Recall that we can consider subtraction as addition in which one of two operator is a negative integer.

8. Describe a situation in which the add operator in a programming language would not be associative.

• It is not associative when it includes the other operator with higher precedence like the multiplication and division.

9. Assume the following rules of associativity and precedence for expressions:

Precedence
     Highest                         *, /, not
                                          +, –, &, mod
                                          – (unary)
                                          =, /=, <, <=, >=, >
                                          And
     Lowest                         or, xor
     Associativity                Left to right

Show the order of evaluation of the following expressions by parenthesizing all sub expressions and placing a superscript on the right parenthesis to indicate order. For example, for the expression
a + b * c + d
the order of evaluation would be represented as
((a + (b * c)1)2 + d)3

a. a * b - 1 + c ((( a * b )1 - 1)2 + c )3
b. a*(b-1)/c mod d ((( a * ( b - 1 )1 )2 / c )3 mod d )4
c. (a-b)/c&(d*e/a-3) (((a - b)1 / c)2 & ((d * e)3 / a)4 - 3)5)6
d. -a or c = d and e (( -a )1 or ( ( c = d )2 and e )3 )4
e. a>b xor c or d<=17 (((a > b)1 xor c)3 or (d <= 17)2 )4
f. –a + b (–( a + b )1 )2

10. Show the order of evaluation of the expressions of Problem 9, assuming that there are no precedence rules and all operators associate right to left.

(a) ( a * ( b – ( 1 + c )1 )2 )3
(b) ( a * ( ( b – 1 )2 / ( c mod d )1 )3 )4
(c) ( ( a – b )5 / ( c & ( d * ( e / ( a – 3 )1 )2 )3 )4 )6
(d) ( – ( a or ( c = ( d and e )1 )2 )3 )4
(e) ( a > ( xor ( c or ( d <= 17 )1 )2 )3 )4
(f) ( – ( a + b )1 )2

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> ‘}’