ICS 313: Fundamentals of Programming Languages (991)                                                       Section: 03

 

Date:   25th September 1999                          Quiz #1 (Solution)                                        Time: 20 Minutes

 

Question 1:

a)   List three reasons for studying programming languages?                                                           (1.5 points)

* Increased capacity to express ideas in the PL.              * Improved background for choosing appropriate languages

* Increased ability to learn  new PLs.                                 * Better understanding of the siginficant of the implementation.

* Increased ability to design  new PLs.                              * Overall advancment of computing.

b)   During the process of designing a programming language the designer may face some conflicting criteria that he needs to make a trade-off between them. Briefly explain two of these.                                                   (2 points)

*      Reliability and cost of execution: Getting more reliability increas the cost of execution while improving the cost of execution will result in less reliability.

 

 

Question 2:

a)   Fill in the binding times for the following bindings?                                                                    (1.5 points)

 

Description

Binding Time

Fixing a meaning for the symbol % as modulus.

Language design time.

Fixing a length on the identifier length

Language implementation time.

Fixing an address of a subroutine coming from a standard library, e.g., log()

Programs linking time

 

b)   Briefly describe the difference between the concepts of static and dynamic scopes of variables  (3 points)

In programming languages that support static scoping then the variable is visible to the statements in the same block definition (e.g. procedure) or the textual blocks included in that block. While if they support dynamic scoping then the variable is visible to the statements in the same block execution (e.g. procedure) or the calling procedures.

 

Question 3:

Consider the following grammar. For your convenience rules are given labels. In your answer you can refer to those rule numbers and also use the abbreviations: <s> for <statements>, <e> for <expression>, <t> for <term>, <f> for <factor>

 

R1:  <statements>   à <expression> ;

R2:                 à <statements> <statements>

R3:  <expression>   à <term>

R4:                 à <expression> + <expression>

R5:  <term>         à <factor>

R6:                 à <factor> * <term>

R7:  <factor>       à number

R8:                 à ( <expression> )

 

a)      Show the derivation of the expression  (1 + 2 ) * 3; 4;   for the above Grammar.      (3.5 points)

 

1

<s> à <s><s>              R2

10

    à (1+<f>)*<t>;<s>     R5

2

    à <e>;<s>             R1

11

    à (1+2)*<t>;<s>       R7

3

    à <t>;<s>             R3

12

    à (1+2)*<f>;<s>       R5

4

    à <f>*<t>;<s>         R6

13

    à (1+2)*3;<s>         R7

5

    à (<e>)*<t>;<s>       R8

14

    à (1+2)*3;<e>;        R1

6

    à (<e>+<e>)*<t>;<s>   R4

15

    à (1+2)*3;<t>;        R3

7

    à (<t>+<e>)*<t>;<s>   R3

16

    à (1+2)*3;<f>;        R5

8

    à (<f>+<e>)*<t>;<s>   R5

17

    à (1+2)*3;4;          R7

9

    à (1+<t>)*<t>;<s>     R7

 

 

 

b)         Construct the parse tree for the expression   1 + 2 * 3 ;                                               (3.5 points)

 

                                     <s>

 


               <e>      ;

 


            <e>        +          <e>

 


            <t>                  <t>

 


            <f>         <f>        *          <t>

 


            1           2                    <f>

 


                                       3