Chapter 8 Answers

Nama : Christian Gunawan
NIM : 1801384174

Kali ini saya akan menjawab assigntment #8 dari chapter 8 Programming Language Concepts R Sebesta E-book :


Review Questions #6-10 :
6. What is unusual about Python’s design of compound statements?

Ada, Python, and Ruby, the then and else clauses are statement sequences, rather than compound statements. The complete selection statement is terminated in these languages with a reserved word.1
Python uses indentation to specify compound statements. For example,

If x > y :
x = y
print "case 1"

All statements equally indented are included in the compound statement.2 Notice that rather than then, a colon is used to introduce the then clause in Python.


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

An F# if need not return a value, for example if its clause or clauses create side effects, perhaps with output statements. However, if the if expression does return a value, as in the example above, it must have an else clause.


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

The else clause would be paired with the second then clause. The disadvantage of using a rule rather than some syntactic entity is that although the programmer may have meant the else clause to be the
alternative to the first then clause and the compiler found the structure syntactically correct, its semantics is the opposite.

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?

• What is the form and type of the expression that controls the selection?
• How are the selectable segments specified?
• Is execution flow through the structure restricted to include just a single selectable segment?
• How are the case values specified?
• 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 Set #6-10 :
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.


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.


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.


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++)?

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

Chapter 7 Answers

Nama : Christian Gunawan
NIM : 1801384174

Kali ini saya akan menjawab assigntment #7 dari chapter 7 Programming Language Concepts R Sebesta E-book :


Review Questions #6-10 :

6. What associativity rules are used by APL?

In APL, all operators have the same level of precedence. Thus, the order of evaluation of operators in APL expressions is determined entirely by the associativity rule, which is right to left for all operators.

For example, in the expression : A × B + C

the addition operator is evaluated first, followed by the multiplication operator (* is the APL multiplication operator). If A were 3, B were 4, and C were 5, then the value of this APL expression would be 27.

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?

If-then-else statements can be used to perform a conditional expression assignment. For example, consider :

if (count == 0)

       average = 0;

else

       average = sum / count;

In the C-based languages, this code can be specified more conveniently in an assignment statement using a conditional expression, which has the form

expression_1 ? expression_2 : expression_3.

Problem Set #6-10 :

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)

=, /=, < , <=, >=, >

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 Answers

Nama : Christian Gunawan
NIM : 1801384174

Kali ini saya akan menjawab assigntment #6 dari chapter 6 Programming Language Concepts R Sebesta E-book :


Review Questions #6-10 :
6. What are the advantages of user-defined enumeration types?

Enumeration types provide a way of defining and grouping collections of named constants,
which are called enumeration constants.

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

enum days {Mon, Tue, Wed, Thu, Fri, Sat, Sun};

8. What are the design issues for arrays?

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

A static array is one in which the subscript ranges are statically bound and storage allocation is static (done before run time). The advantage of static arrays is efficiency: No dynamic allocation or deallocation is required. The disadvantage is that the storage for the array is fixed for the entire execution time of the program.

A fixed stack-dynamic array is one in which the subscript ranges are staticallybound, but the allocation is done at declaration elaboration time during execution. The advantage of fixed stack-dynamic arrays over static arrays is space efficiency.

A stack-dynamic array is one in which both the subscript ranges and the storage allocation are dynamically bound at elaboration time. Once the subscript ranges are bound and the storage is allocated, however, they remain fixed during the lifetime of the variable. The advantage of stack-dynamic arrays over static and fixed stack-dynamic arrays is flexibility. The size of an array need not
be known until the array is about to be used.

A fixed heap-dynamic array is similar to a fixed stack-dynamic array, in that the subscript ranges and the storage binding are both fixed after storage is allocated. The differences are that both the subscript ranges and storage bindings are done when the user program requests them during execution, and the storage is allocated from the heap, rather than the stack. The advantage of fixed heap-dynamic arrays is flexibility—the array’s size always fits the problem.

A heap-dynamic array is one in which the binding of subscript ranges and storage allocation is dynamic and can change any number of times during the array’s lifetime. The advantage of heap-dynamic arrays over the others is flexibility: Arrays can grow and shrink during program execution as the need for space changes.


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

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



Problem Set#6-10 :
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/C++, enums are more or less integers (that's the way they are handled under the hood). You can't give your enum methods or anything like that, basically you only capable of making variables of the type and giving them the values you list.

In Java, your enums can have methods attached.


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:

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

Chapter 5 Answers

Nama : Christian Gunawan
NIM : 1801384174

Kali ini saya akan menjawab assigntment #5 dari chapter 5 Programming Language Concepts R Sebesta E-book :

Review Questions#6-10 :

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

L-value is the address of a variable , because the address is what is required when the name of a variable appears in the left side of an assignment.

R-value is a name for a variable's value because it is what 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.

Whilst 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?]

Language design time — bind operator symbols to operations
Language implementation time– bind floating point type to a representation
Compile time — bind a variable to a type in C or Java
Load time — bind a C or C++ static variable to a memory cell)
Runtime — bind a non-static local variable to a memory cell

9. Define static binding and dynamic binding.

A static binding is if it first occurs before run time and remains unchanged throughout program execution. A dynamic binding is if it first occurs during execution or can change during execution of the program.

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

Disadvantage : A static binding is if it first occurs before run time and remains unchanged throughout program execution. A dynamic binding is if it first occurs during execution or can change during execution of the program.

Advantage : There are several different bases for implicit variable type bindings. The simplest of these is 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.

Problem Set #6-10 : 

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

a. In sub1: sub1
    In sub2: sub1
    In sub3: main

b.In sub1: sub1
   In sub2: sub1
   In 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: x=5;
Dynamic scoping: x=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.

Sub1: a(sub1), y(sub1), z(sub1), x(main).
Sub2: a(sub2), b(sub2), z(sub2), y(sub1), x(main)
Sub3: a(sub3), x(sub3), w(sub3), y(main), z(main)

  

9. Consider the following Python program:

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 four marked points in this function, list each visible variable,

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

Chapter 4 Answers

Nama : Christian Gunawan
NIM : 1801384174

Kali ini saya akan menjawab assigntment #4 dari chapter 4 Programming Language Concepts R Sebesta E-book :

Review Questions#6-10 :

6. What is a state transition diagram?

A state transition diagram, or just state diagram, is a directed graph. 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?

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?

There are 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.

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.

The two broad classes of parsers are top-down, in which the tree is built from the root downward to the leaves, and bottom-up, in which the parse tree is built from the leaves upward to the root.

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

if the current sentential form is

xA α

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

Problem Set#6-10 :

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

Phrases:

      aAcccbbc, aAcccb, Ac, ccb, c_1, c_2

Simple phrases:

      Ac, c_1, c_2

Handle:

      Ac

b. AbcaBccb

Phrases:

            AbcaBccb, caBccb, aBcc, aBc, c_1

Simple Phrases:

            c_1

Handle:

            c_1

c. baBcBbbc

Phrases:

      baBcBbbc, aBcBbb, aBcBb, cBb

Simple Phrases:

      cBb

Handle:

      cBb

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])

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.

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])

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.

<for_stmt> -> FOR '(' (<arith_expr>; <logic_expr>; <arith_expr>) ')'  <block>
  <block> -> <stmt> | '{' <stmt> {<stmt>} '}'

Chapter 3 Answers

Nama : Christian Gunawan
NIM : 1801384174

Kali ini saya akan menjawab assigntment #3 dari chapter 3 Programming Language Concepts R Sebesta E-book :

Review Questions #6-10 :
6. Define a left-recursive grammar rule.

When a grammar rule has its LHS also appearing at the beginning of its RHS, the rule is said to be left recursive. This left recursion specifies left associativity.

7. What three extensions are common to most EBNFs?

Three extensions are commonly included in the various versions of EBNF.
The first of these denotes an optional part of an RHS, which is delimited by brackets.

The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. This extension allows lists to be built with a single rule, instead of using recursion and two rules.

The third common extension deals with multiple-choice options. When a single element must be chosen from a group, the options are placed in parentheses and separated by the OR operator, |.

8. Distinguish between static and dynamic semantics.

The static semantics of a language is only indirectly
related to the meaning of programs during execution; rather, it has to do
with the legal forms of programs (syntax rather than semantics).

Dynamic semantics is a perspective on natural language semantics that emphasises the growth of information in time. It is an approach to meaning representation where pieces of text or discourse are viewed as instructions to update an existing context with new information, with an updated context as result.

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

Predicates in attribute grammar states the static semantic rules a language needs to follow. A false value in predicates indicates that there is an invalid syntax or static semantics and determines whether an action is allowed or not.

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

actual_type—A synthesized attribute associated with the nonterminals <var> and <expr>. It is used to store the actual type, int or real, of a variable or expression.

expected_type—An inherited attribute associated with the nonterminal <expr>. It is used to store the type, either int or real, that is expected for the expression, as determined by the type of the variable on the left side of the assignment statement.



Problem Set#6-10 :
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>

= > A = <expr>

            = > A = <id> * <expr>

= > A = A * <expr>

            = > A = A * ( <expr> )

= > A = A * ( <id> + <expr> )

            = > A = A * ( B + <expr> )

            = > A = A * ( B + ( <expr> ) )

            = > A = A * ( B + (<id><expr>) )

            = > A = A * ( B + (C * <expr> ))

            = > A = A * ( B + ( C * <id> ) )

            = > A = A * ( B + ( C * A ) )

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

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

  = > B = <expr>

              = > B = <id> + <expr>

  = > B = C + <expr>

              = > B = C + ( <expr> )

  = > B = C + ( <id> + <expr> )

              = > B = C + ( A * <expr> )

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

              = > B = C + ( A * C + <expr> )

              = > B = C + ( A * C + <id> )

              = > B = C + ( A * C + B )

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

    

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

  = > A = <expr>

              = > A = <id> + <expr>

  = > A = A * <expr>

              = > A = A * (<expr> )

  = > A = A * ( <id> + <expr> )

              = > A = A * ( B + <expr> )

              = > A = A * ( B + ( <expr> ) )

              = > A = A * ( B + ( <id> ) )

              = > A = A * ( B + ( C ) )

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=<term>*<factor>

=> A=<factor>*<factor>

=>  A=(<expr>)*<factor>

=>  A=(<expr>+<term>)*<factor>

=>  A=(<term>+<term>)*<factor>

=>  A=(<factor>+<term>)*<factor>

=>  A=(<id>+<term>)*<factor>

=>  A=(A+<term>)*<factor>

=>  A=(A+<factor>)*<factor>

=>  A=(A+<id>)*<factor>

=>  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>
<A> → <A> + <A> | <id>
<id> → a | b | c

A grammar is ambiguous if there are two different trees for derivation of same expression. Expressed in more formal way, a grammar is ambiguous if fr(T)=fr(T’) implies T <> T’. fr(T) means a frontier of a tree, which specifies the leaves of a tree. Therefore, if two trees have same frontiers and the grammar is ambiguous, the trees will be structurally different.

Moreover, two trees for a derivation of an expression are structurally different if the grammar allows both left and right growing of the tree.

For the grammar of this problem and the expression a=a+b+c there are two different leftmost derivations:

<S>-><A>

-> <A>+<A>

-> <A>+<A>+<A>

-> <id>+<A>+<A>

-> a+<A>+<A>

-> a+<id>+<A>

-> a+b+<A>

-> a+b+<id>

-> a+b+c

Or 

<S>-><A>

-><A>+<A>

-><id>+<A>

->a+<A>

->a+<A>+<A>

->a+<id>+<A>

->a+b+<A>

->a+b+<id>

->a+b+c

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> | - <factor>

<term> => <term>*<factor> | <factor>

<factor> => (<expr>) | <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

All sentences consisting of one or more a’s followed by one or more b’s followed by one or more c’s