Q&A Assignment #11 Chapter 9 Review Questions & Problem Set

Name : Vina Melinda

NIM  : 1801380106

Untuk kali ini saya akan menjawab Assignment #11 Problem Set dan Review Questions dari Chapter 9 dari Sebesta.

Review Questions:

6. Q: What is a Ruby array formal parameter?

A: 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. Q: What is a parameter profile? What is a subprogram protocol?
A: Parameter profile of a subprogram contains the number, order, and types of its formsl parameter. A protocol of subprogam is ite parameter profile plus, if it is a function, its return type。

8. Q: What are formal parameters? What are actual parameters?
A: Formal parameter is the parameter in the subprogram header. They are sometimes thought of as dummy variables because they are not variable in the usual case. Actusl parameter is a subprogram call statement that must inckude the nameof the subprogram and a list of parameters to be bound to the formal parameter of the subprogram.

9. Q: What are the advantages and disadvantages of keyword parameters?
A: The advantage of keyword parameters is that they can appear in any order in the actual parameter list. The disadvantage to keyword parameters is that the user of the subprogram must know the names of formal parameters.

10. Q: What are the differences between a function and a procedure?
A: A function returns a value and a procedure just executes commands. The name function comes from math. It is used to calculate a value based on input. A procedure is a set of command which can be executed in order. In most programming languages, even functions can have a set of commands. Hence the difference is only in the returning a value part. But if you like to keep a function clean, (just look at functional languages), you need to make sure a function does not have a side effect.

Problem Set:

6. Q: Present one argument against providing both static and dynamic local
variables in subprograms.
A: In subprograms local variables can be static or dynamic. If local variable treated statically, this allows for compile-time allocation or deallocation and ensures proper type checking but doesn't allow recursion. However, if local variables treated dynamically, this allows for recursion at the cost of run-time allocation or deallocation and initialization because these are stored on a stack, referencing is indirect based on stack position and possibly time consuming.

7. Q: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
b. Passed by reference
c. Passed by value-result
A: a. 1, 3
b. 2, 6
c. 2, 6

8. Q: Argue against the C design of providing only function subprograms.
A: If a language only provides functions, then programmers must live with the restriction of returning only one result from any subprogram or functions must allow side effects, which is considered bad.

9. Q: From a textbook on Fortran, learn the syntax and semantics of statement
functions. Justify their existence in Fortran.
A: The Fortran 90 standard (ISO/IEC 1539: 1991) describes the syntax and semantics of a programming language. However, the standard addresses certain aspects of the Fortran processing system, but does not address others. When specifications are not covered by the standard, the interpretation is processor dependent; that is, the processor defines the interpretation, but the interpretation for any two processors need not be the same. Programs that rely on processor-dependent interpretations typically are not portable. (Jeanne C. Adams, Walter S. Brainerd, et. al., 1992)

10. Q: 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.
A: C was downgraded because it is essentially limited to syntactic (re)naming of predefined data types and data structures, with building-block capabilities within these limitations. Unlike Ada, neither C nor C++ allows restrictions to the range of a type. The C++ extensions to C in this category are the most significant enhancement. A class in C++ is a user-defined data type that provides data hiding, guaranteed initialization of data, implicit type conversion for user-defined types, dynamic typing, user-controlled memory management, and mechanisms for overloading operators. Ada has been downgraded slightly by the SEI for lacking a mechanism like classes that permits programming by specialization and extension. (Nelson H. Weiderman, 1991)

Q&A Assignment #10 Chapter 8 Review Questions & Problem Set

Name : Vina Melinda

NIM  : 1801380106

Untuk kali ini saya akan menjawab Assignment #10 Problem Set dan Review Questions dari Chapter 8 dari Sebesta.

Review Questions:

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

A:  Python uses indentation to specify compound statements. For example,if x > y :
x = y
print “case 1″
equally indent statements are grouped as one compound statement.

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

A: If the expression returns a value, it must have an else clause

8. Q: What are the common solutions to the nesting problem for two-way
selectors?
A: The common solution to the nesting problem is to use alternating means of forming a compound statements.

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

A:
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. Q: 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?

A: 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 Set:

6. Q: 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.

A: There's not really a readability problem, it's simply something you get used to, and after some experience the problems falls out of the process. Similar to how many Lisp users "don't see" the parentheses. They simply don't stand out in the general case for the experienced reader.
You have to recall the time of Algol, notably the "68" part, as in 1968.The bright side of the fi, esac, and od is that they clearly indicate what kind of block they're terminating, and they do it with a single token. Esac is no less clear than }, which is a meaningless bracket until you know otherwise. The {} have the benefit of consistency, while less wordy than Pascals begin - end generic block sequence.Finally, consider how dominant the English language is in computer language design, and while folks who don't speak english may have some initial issues with the languages, that clearly passes over time.So, it's a short hurdle that falls away quickly with use.

7. Q: 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.

A: Considering the time frame of the early to mid seventies, Knuth’s description of an advantage of the use of gotos was well understood. In fact C language which was created in the late ’60s had already dealt with the problem you’ve given as an example. With nested loops and conditions calling for exiting those loops from deep within the nesting, gotos are more efficient and even more elegant than multiple test flags and testing statements. So C incorporated the “break” statement to handle that problem. Redefining “goto” in a situation where its use is valuable to something more restricted and directed to the problem was the answer. An answer given years before.

8. Q: 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

A: Work on the formal semantics of programming languages began in the 1960’s
– a useful early reference is which reports on a conference held in Badenbei-Wien in 1964. The subsequent literature on formal semantics of sequential languages is extensive. A good state of the art example of a formal definition is that of standard ML. This definition is written in Structured
Operational Semantics. It is sobering that, after a quarter century of denotational semantics, it is still found more convenient to tackle the semantics of a language like SML in an operational way. Furthermore, it must be clear that it is extremely difficult to get a formal semantics to the stage where it correctly reflects the intuitions about a language. There are some language standards like that for Modula 2 which are actually being written using formal techniques. But overall the situation is that formal semantic definitions are written only by a very small number of highly skilled people.
The situation with recording the formal semantics

9. Q: 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++)?

A: 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. Q: 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++)?

A: 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.
Ada was designed for military grade software development.
The idea is that whenever you modify code in such a way that a new case emerges (for example adding a new value for an enumeration type), you are forced to manually revisit (and therefore re-validate) all the case statements that analyze it. Having a "default" is risky: you may forget that there is a case somewhere where the new case should not have been handled by the default.

Q&A Assignment #9 Chapter 7 Review Questions & Problem Set

Name : Vina Melinda

NIM  : 1801380106

Untuk kali ini saya akan menjawab Assignment #9 Problem Set dan Review Questions dari Chapter 7 dari Sebesta.

Review Questions:

6. Q: What associativity rules are used by APL?

A: Associativity rules are used by APL: all operators have equal precedence and all operators associate right to left.

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

A: All of the arithmetic, relational, and assignment operators, as well as array indexing, shifts, and bitwise logic operators, areimplemented as methods in Ruby

8. Q: Define functional side effect.

A: It is a side effect of a function. Occurs when the function changes either one of its parameters or a global variable.

9. Q: What is a coercion?

A: Coercion or Implicit type conversion, is an automatic type conversion by the compiler. Some languages allow, some require, compilers to provide coercion

10. Q: What is a conditional expression?

A: A conditional expression is a compound expression that contains a condition that is implicity converted to type bool in C++ (operand1), an expression to be evaluated if the condition evaluates to true (operand2), and an expression to be evaluated if the condition has the value false (operand3).

Problem Set:

6. Q: 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?

A: 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. Q: Describe a situation in which the add operator in a programming language
would not be commutative.

A: In many programming languages, the operands of an addition are actually memory locations, and the result of an addition is stored in the same location as one of the operands, so the operation is not commutative. A+B may not give quite the same result as B+A, because of the storage location of the result.

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

A: Consider the integer expression A + B + C. Suppose the values of A, B, and C are 20,000, 25,000, and -20,000, respectively. Further suppose that the machine has a maximum integer value of 32,767. If the first addition is computed first, it will result in overflow. If the second addition is done first, the whole expression can be correctly computed.

9. Q: 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 subexpressions 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
b. a * (b - 1) / c mod d
c. (a - b) / c & (d * e / a - 3)
d. -a or c = d and e
e. a > b xor c or d <= 17

f. -a + b

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

10. Q: 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) ( 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

Q&A Assignment #8 Chapter 6 Review Questions & Problem Set

Name : Vina Melinda

NIM  : 1801380106

Untuk kali ini saya akan menjawab Assignment #8 Problem Set dan Review Questions dari Chapter 6 dari Sebesta.

Review Questions:

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

A: Readability is enhanced very directly and named values are easily recognized, whereas coded values are not. In reliability this enumeration types provide two other advantages 

1. No arithmetic operations are legal on enumeration types 

2. No enumeration variable can be assigned a value outside its defined range.

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

A: 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. Q: What are the design issues for arrays?

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

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

A: 1. Static: subscript ranges are statically bound and storage allocation is static (before run-time). Advantage: efficiency (no dynamic allocation).
2. Fixed stack-dynamic: subscript ranges are statically bound, but the allocation is done at declaration time. Advantage: space efficiency.
3. 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).
4. 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.
5. 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. Q: What happens when a nonexistent element of an array is referenced

in Perl?

A: A reference to a nonexistent element in Perl yields undef, but no error is reported.

Problem Set:

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

A: 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. Q: What significant justification is there for the -> operator in C and C++?

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

In C and C++, there are two ways a pointer to a record can be used to reference a field in that record. If a pointer variable p points to a record with a field named age, (*p).age can be used to refer to that field. The operator ->, when used between a pointer to a record and a field of that record, comfbines dereferencing and field reference. For example, the expression p -> age is equivalent to (*p).age. In Ada, p.age can be used, because such uses of pointers are implicitly dereferenced.

8. Q: What are all of the differences between the enumeration types of C++

and those of Java?

A: 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. Q: 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?

A: 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. Q: 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.

A: 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))

Q&A Assignment #7 Chapter 5 Review Questions & Problem Set

Name : Vina Melinda

NIM  : 1801380106

Untuk kali ini saya akan menjawab Assignment #7 Problem Set dan Review Questions dari Chapter 5 dari Sebesta.

Review Questions:

6. Q: What is the l-value of a variable? What is the r-value?
A: An l-value represents a storage region’s “locator” value, or a “left” value, implying that it can appear on the left of the equal sign (=). L-values are often identifiers. The term “r-value” is sometimes used to describe the value of an expression and to distinguish it from an l-value. All l-values are r-values but not all r-values are l-values.

7. Q: Define binding and binding time.
A: Binding is an association between an attribute and an entity, such as between a variable and its type of value, or between an operation and a symbol. Binding time is the time at which binding takes place. Binding and binding times are prominent concepts in semantics of programming language.

8. Q: After language design and implementation [what are the four times bindings can take place in a program?]
A: compile time: a variable in java bound to a particular data type, load time: a variable bound to a storage cell when a program is loaded into memory. link time: a call to a library subprogram is bound to the subprogram code. run time: certain variables declared in pascal and in c++ functions.

9. Q: Define static binding and dynamic binding.
A: Static binding: if it first occurs before run time and remains unchanged throughout program execution.

Dynamic binding: if it first occurs during execution or can change during execution of the program.

10. Q: What are the advantages and disadvantages of implicit declarations?
A: Implicit declarationscan be detrimental to reliability because they prevent the compilation process from detecting some typographical and programmer errors.


Problem Set:



6. Q: 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
ii. sub2
iii. sub3
b. Repeat part a, but assume dynamic scoping.

A: a.) i.) sub1
ii.) sub1
iii.) Main

b.) i.) sub1
ii.) sub1
iii.) sub1

7. Q: 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();

A: Static Scope then x = 5, if Dynamic Scope then x = 10

8. A: 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.

A: 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. Q: 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.

A: 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. Q: 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 four marked points in this function, list each visible variable,
along with the number of the definition statement that defines it.

A: 1) Variables : a = 1 b = 2
c = 2 d = 2

2) Variables :
a = 1 b = 2
c = 3 d = 3
e = 3

3) Variables :
a = 1 b = 2
c = 2 d = 2

4) Variables :
a = 1
b = 1
c = 1

Q&A Assignment #6 Chapter 4 Review Questions & Problem Set

Name : Vina Melinda

NIM  : 1801380106

Untuk kali ini saya akan menjawab Assignment #6 Problem Set dan Review Questions dari Chapter 4 dari Sebesta.

Review Questions:

6. Q: What is a state transition diagram?

A: State diagram, is a directed graph. The nodes of a state diagram are labeled with state names. The arcs are labeled with the input characters that cause the transitions among the states. An arc may also include actions the lexical analyzer must perform when the transition is taken.

State diagrams of the form used for lexical analyzers are representations

of a class of mathematical machines called finite automata. Finite automata

can be designed to recognize members of a class of languages called regular

languages. Regular grammars are generative devices for regular languages.

The tokens of a programming language are a regular language, and a lexical

analyzer is a finite automaton.

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

A: 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. Q: What are the two distinct goals of syntax analysis?

A: 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. Q: Describe the differences between top-down and bottom-up parsers.

A: Parsers are categorized according to the direction in which they build parse trees. Top-down parsers is in which the tree is built from the root downward to the leaves. While bottom-up parsers, in which the parse tree is built from the leaves upward to the root.

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

A: 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 xbB , xcBb , or xa . This is the parsing decision problem for top-down

parsers.

Problem Set

6. Q: 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. aAcccbbc

b. AbcaBccb

c. baBcBbbc

A: (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

5. – aaAbb



Phrases: aaAbb, aAb, b

Simple phrases: b

Handle: b

-bBab



Phrases: bBab, ab

Simple phrases: ab

Handle: ab

c. aaAbBb: -

7. Q: 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: 

Grammar:

1. E → E + T

2. E → T
3. T → T * F
4. T → F
5. F → (E)
6. F → id

Parse Table (pg. 196)

Complete parse:

Stack Content	Input String	Action
0	id * (id + id) $	Shift 5
0id5	* (id + id) $	Reduce 6, Goto(0, F)
0F3	* (id + id) $	Reduce 4, Goto(0, T)
0T2	* (id + id) $	Reduce 2, 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, Goto(4, F)
0T2*7(4T2	+ id) $	Reduce 4, Goto(4, T)
0T2*7(4E8	+ id) $	Reduce 2, Goto(4, E)
0T2*7(4E8+6	id) $	Shift 6
0T2*7(4E8+6id5	) $	Shift 5
0T2*7(4E8+6F3	) $	Reduce 6, Goto(6, F)
0T2*7(4E8+6T9	) $	Reduce 4, Goto(6, T)
0T2*7(4E8	) $	Reduce 1, Goto(4, E)
0T2*7(4E8)11	$	Shift 11
0T2*7F10	$	Reduce 5, Goto(7, F)
0 T 2	$	Reduce 5, Goto(0, T)
0 E 1	$	Reduce 2, Goto(0, E)
- ACCEPT -

8. Q: 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: Grammar:

1.      E -> E + T

2.      E -> T

3.      T -> T * F

4.      T -> F

5.      F -> ( E )

6.      F -> id

Parse table: please note that S4 in row state 0 should be under ( , instead of under *.

No	Stack	Input	Action
1	0	( id + id ) * id $	Shift 4
2	0 ( 4	id + id ) * id $	Shift 5
3	0 ( 4 id 5	+ id ) * id $	Reduce 6, Goto(4, F)
4	0 ( 4 F 3	+ id ) * id $	Reduce 4, Goto(4, T)
5	0 ( 4 T 2	+ id ) * id $	Reduce 2, Goto(4, E)
6	0 ( 4 E 8	+ id ) * id $	Shift 6
7	0 ( 4 E 8 + 6	id ) * id $	Shift 5
8	0 ( 4 E 8 + 6 id 5	) * id $	Reduce 6, Goto(6, F)
9	0 ( 4 E 8 + 6 F 3	) * id $	Reduce 4, Goto(6, T)
10	0 ( 4 E 8 + 6 T 9	) * id $	Reduce 1, Goto(4, E)
11	0 ( 4 E 8	) * id $	Shift 11
12	0 ( 4 E 8 ) 11	* id $	Reduce 5, Goto(0, F)
13	0 F 3	* id $	Reduce 4, Goto(0, T)
14	0 T 2	* id $	Shift 7
15	0 T 2 * 7	id $	Shift 5
16	0 T 2 * 7 id 5	$	Reduce 6, Goto(7, F)
17	0 T 2 * 7 F 10	$	Reduce 3, Goto(0, T)
18	0 T 2	$	Reduce 2, Goto(0, E)
19	0 E 1	$	Accept

9. Q: 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. Q: 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> ‘}’