Problem (3), homework 1

Below is a Pascal(-like) grammar. I have numbered the productions for ease of reference. The key points to note are the following (look at the grammar while reading these points):

I. There are no <blocks> in Pascal; so a <stmt> cannot be a block. But still it is possible to get nested structures because procedure and function declarations are nested. (Note: I will use "declaration" to mean what C/C++ calls "definition".) A proc/fn. declaration consists of the header [i.e., name, return type if any, list of parameters (including their types)], and body. The body consists of a <decl seq> followed by <stmt seq>. The <decl seq> consists of zero or more variable declarations followed by zero or more proc/fn. declarations.

II. An example:

     int X, Y; bool Z;                        // (a)
     procedure P1(int X, bool Y)              // (b)
        { float U;                            // (c)
          procedure P11()                     // (d)
             { ... omitted ...}               // (d1)
          function f11(bool X):int            // (e)
             { ... omitted ...}               // (e1)
          ...body of P1...  }     // end of P1   (f)
     procedure P2(bool X, int Y)              // (g)
        { float W;                            // (h)
          function f21(int Y):int             // (i)
             { ... omitted ...}               // (i1)
          function f22(float X):bool          // (j)
             { ... omitted ...}               // (j1)
          ...body of P2...  }     // end of P2   (k)

     begin                                    // (l)
       ...main program statements...          // (m)
     end                                      // (n)
Here, we have declared [line (a)] three variables X, Y, Z in the main program; then a procedure P1 [lines (b) through (f)], another procedure P2 [lines (g) through (k)], then the body of the main program.

Procedure P1 expects two parameters of type int, bool respectively. Inside P1, we declare a variable U (of type float) a procedure P11 [no paramters] and a function f11 which expects one parameter of type bool and returns an int value.

Procedure P2 [lines (g) through (k)] expects two parameters of types bool and int. Inside P2, we declare a variable W, a function f21, and another function f22. f21 expects an int parameters and returns an int. f22 expects a float parameter and returns a bool.

The bodies of all the procedures and functions are omitted.

The static scope rule of Pascal says that in the main program [line (m)], we can use variables X, Y, Z [declared in (a)] and call P1 and P2. Note that we cannot call P11, f11, f21, f22 because those are nested inside P1 and P2. Similarly we cannot use the U declared in (c) or the W in (h) because again those are nested.

In the body of P1 [line (f)], we can use Z [line (a)], U [line (c)]; we cannot use X, Y of line (a) because the names of P1's parameters conflict with those names. So if we say "Y" in line (f), it will mean P1's second parameter. Also, in (f), we can call P11, f11, and P1 [recursively]. But we cannot call P2 because although both P1 and P2 are declared in the main program, we have not yet seen P2's declaration when looking at line (f). This is the difference with Algol-like languages and the main issue you have to address in problem (3) of the homework.

In the body of P11, we can call P1, use X, Y, U of P1 and Z of the main program; but we cannot call f11 [since we have not yet seen its definition when we are in line (d1)]. In the body of f11, we can call P1, P11, and use Z of the main program, Y, U of P1 [but not X because that name conflicts f11's parameter name].

III. In summary, the difference with the Algol-like languages is that here, we can access the names that are accessible according to standard static scope rule *provided* the declaration of that name *precedes* the point where we are trying to access it. That is the essential difference.

If you notice any mistakes in any of the above or in the grammar below, please email me or post on Piazza and/or the newsgroup.


[This is not the actual Pascal grammar but it is similar.]

          <prog> ::= program <decl seq> begin <stmt seq> end          ...(1)

      <decl seq> ::= <var declns> <proc&fn declns>                    ...(2)

<proc&fn declns> ::= \epsilon | <proc or fn decl> <proc&fn declns>    ...(3)
                     (note: "\epsilon" is the empty string)

<proc or fn decl>::= <proc decl> | <fn decl>                          ...(4)

     <proc decl> ::= procedure <id> (<par list>) <body>               ...(5)

       <fn decl> ::= function <id> (<par list>): <return type> <body> ...(6)

      <par list> ::= \epsilon | <par>, <par list>                     ...(7)
           <par> ::= int <id> | bool <id> | float <id>                ...(8)
   <return type> ::= int | bool | float                               ...(9)

          <body> ::= { <decl seq> begin <stmt seq> end }              ...(10)

    <var declns> ::= \epsilon | <var decl> <var declns>               ...(11)

      <var decl> ::= int <id list>; | bool <id list>; | float <id list>...(12)

       <id list> ::= <id> | <id>, <idlist>                             ...(13)

      <stmt seq> ::= <stmt> | <stmt> <stmt seq>                        ...(14)

          <stmt> ::= skip; | <assign> | <if> | <loop> | <input/output> | 
                             <proc call> | <return>                    ...(15)

<assign>, <if>, <loop> are as usual; we won't worry about <input/output>

     <proc call> ::= call <id>(<arg list>);                            ...(16)

      <arg list> ::= \epsilon | <arg> <arg list>                       ...(17)

           <arg> ::= <exp>                                             ...(18)

        <return> ::= return; | return <exp>;                           ...(19)
<exp> is as usual but it can also include calls to functions because functions return a value. Remember, in Pascal, things that don't return values are called procedures. That is why there are two kinds of <return> statements, one that returns from a procedure and does not include an <exp>, and the other used for returning from a function and does include <exp>. A procedure can also return by just reaching the end of its body; but that is not an option for functions (why not?).
  <exp> ::= <id> | <exp> + <exp> | ... | <exp> && <exp> | ~<exp> | ...  ...(20)
             | f(<arg list>)
<exp> + <exp> correspond to arithmetic expressions; ~<exp> etc. correspond to boolean expressions; the main new one is the function call, f(<arg list>) which can return any of int, bool, or float types.