Fall 1999-2000

Date: 16^th September 1999 Assignment # 1: Syntax and Semantics Due date: 25^th September 1999

Download this assignment from the course page and take it on a floppy. If you open it in a browser, you will have the advantage of easy navigation to some web documents through hot links. Deliverables and Submission guidelines are provided on-line.

On-line Exploration and Reading Part

Exercise 1 [Online Reference Section]:

Programming Languages Reference Section, Java Reference Section, and other Online Books. Examine the various programming language books in it. In particular review your C-programming basics as you will be doing a programming assignment in C shortly. Skim through the following books (just) for the discussion of C:

(i) “Visual C++ Unleashed”

(ii) “C++ Builder Unleashed”

(iii) “Visual C++ in 12 Easy Lessons”

(iv) “Teach Yourself C++ in 21 Days”

If you have any good book on C detailed examination of the above can be skipped. In addition, slowly, start familiarizing yourself with the books and tutorials on Java from the Java Reference Section.

Exercise 2 [Reading from Textbook]:

Chapter 3 (excluding Section 3.6.3) of the textbook.

Written Part

1. Written Exercises [Problems from Chapter 3 of the Textbook]:

Solve the following problems from pages 147-149 of the textbook.

Problems	Topic
2 (c—d)	EBNF
4	Sentence Derivation
5	Ambiguity
12 (c—d)	Operational Semantics
14	Weakest pre-Conditions
(see below)	Program Correctness

2. Written Exercises [Problems from Chapter 3 of the Textbook]:

Prove the following program is correct.

{ x = V_x and y = V_y }

if (x > y) then

temp = x;

x = y;

y = temp;

endif

{ x = min(V_x, V_y) and y = max(V_x, V_y)}

3. Optional Written Exercises for Extra Credit:

Solve problem 20 from page 154 of the textbook.

King Fahd University of Petroleum and Minerals

Department of Information and Computer Science

ICS 313: Fundamentals of Programming Languages

Fall 1999-2000

Date: 16^th September 1999 Assignment # 1: Syntax and Semantics Due date: 25^th September 1999

1. Written Exercises [Problems from Chapter 3 of the Textbook]:

Q. 2. (pp. 147) (10 points)

c) A C switch statement

<switch_stmt> ® switch (<expr>) case <literal> : <stmt_list>

{case <literal> : <stmt_list>} [default : <stmt_list>]}

d) A C union definition

<union> ::= union [<identifier>] { { <structure-declaration> } }
<structure-declaration> ::= <type-specifier> {<identifier>}

Q. 4. (pp. 147) (40 points)

In the following parts we will use the following appreviations: <a> for <assign>, <e> for <expr>, <t> for <term>, <f> for <factor> and <id> for <identifier>.

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

Parse Tree Left-most Derivation

=> A := <e>

=> A := <f> * <t>

A <t> => A := ( <e> ) * <t>

=> A := ( <e> + <t> ) * <t>

=> A := ( <f> + <t> ) * <t>

( <e> ) <f> => A := ( <id> + <t> ) * <t>

=> A := ( A + <t> ) * <t>

=> A := ( A + <id> ) * <t>

=> A := ( A + B ) * <f>

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

<id> B

b) A := B + C + A

Parse Tree Left-most Derivation

=> A := <e>

=> A := <e> + <t> + <t>

A <e> + <t> => A := <e>

=> A := <t> + <t> + <t>

=> A := <id> + <t> + <t>

=> A := B + <f> + <t>

=> A := B + C + <t>

=> A := B + C + <id>

B => A := B + C + A

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

Parse Tree Left-most Derivation

=> A := <e>

=> A := <f> * <f>

A <t> * <f> => A := <id> * <f>

=> A := A * <f>

<f> ( <e> ) => A := A * (<e>)

=> A := A * (<e> + <t>)

<id> <e> + <t> => A := A * (<e> + <t>)

=> A := A * (<t> + <t>)

A <t> <f> => A := A * (<f> + <t>)

=> A := A * (<id> + <t>)

<f> <id> => A := A * (B + <t>)

=> A := A * (B + <f>)

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

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

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

Parse Tree Left-most Derivation

=> A := <e>

=> A := <f> * <f>

A <t> * <f> => A := <id> * <f>

=> A := B * <f>

<f> ( <e> ) => A := B * (<e>)

=> A := B * (<t> * <f>)

<id> <t> * <f> => A := B * (<f> * <t>)

=> A := B * (<id> * <t>)

B <f> ( <e> ) => A := B * (C * <t>)

=> A := B * (C * <f>)

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

=> A := B * (C * (<e> + <e>))

C <t> <t> => A := B * (C * (<t> + <e>))

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

<f> <f> => A := B * (C * (A + <e>))

=> A := B * (C * (A + <t>))

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

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

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

Q. 5. (pp. 147) (10 points)

We prove that this grammar is ambiguous by showing at least owing two distinct parse tree for the same string. For the expression a+b+c we can generate the following parse trees:

<S> <S>