CSCI 384 FALL 2021

HOMEWORK 1: Grammars

We’ve spent class time describing program language syntax using grammars. The idea behind grammars is that we use production rules to give the layout of common constructs in the language. For example, we might use the rules

     stmt ::= loop | cndl
     loop ::= while ( expn ) { blck }
     cndl ::= if ( expn ) { blck } else { blck }

to describe two kinds of program statments possible in C++. These would be among the many rules describing the full language. The rules describe how their code should be structured. For example, there is a while loop in C++, and it expects to have a parenthesized expression following its keyword, then followed by a block of program statements. The syntax of expn and blck would be specified in other parts of the grammar. They might say, for example, that one such expression could be a comparison of two things, with the syntax

    expn ::= expn < expn

or else the negation of some other expression

    expn ::= ! expn

and so forth.

We also defined grammars more formally, in particular defining a derives relation for “computing” strings generated by a grammar. Our definition said that if

    A ::= w

was a production, and we’ve derived l A r then we can say that

    l A r => l w r

And so for example the derivation

    B
      => [ B ]
      => [ B B ]
      => [ [ B ] B ]
      => [ [ [ B ] ] B ]
      => [ [ [ ] ] B ]
      => [ [ [ ] ] [ B ] ]
      => [ [ [ ] ] [ ] ]

is possible using the rules of the grammar for balanced brackets shown below:

    B ::= B B
    B ::= [ B ]
    B ::= •

This means that [ [ [ ] ] [ ] ] is in its language.

The derivation just given is a leftmost derivation, because we are always choosing to replace the leftmost B in each derivation step. We noted that that grammar was ambiguous because there were two leftmost derivations for some string of tokens generated by the grammar.

[HW1 EX1] brackets

• Part A: Using the balanced bracket grammar, give a different leftmost derivation of the token string [ [ [ ] ] [ ] ].

Now consider the following grammar:

    B ::= [ B ] B
    B ::= •

• Part B: Give a leftmost derivation of [ [ [ ] ] [ ] ] using this grammar.

The grammar is not ambiguous, it turns out.

• Part C: Argue that it generates the same language as the ambiguous one.

[HW1 EX2] if then else

Here is a grammar that models the syntax of programming languages that have “if-then” and “if-then-else” statements.

    X ::= if c then X
    X ::= if c then X else X
    X ::= s

This grammar is also ambiguous.

• Part A: Why? Give a token string that has two leftmost derivations using this grammar.

• Part B: Devise a grammar that generates the same set of token strings but is not ambiguous.

[HW1 EX3] facts

In class I worked out a grammar for a subset of the Python programming language. It specified that a program consisted of a series of function definitions (using the def statement) followed by a block of statements that called them.

For this exercise, I’d like you to examine a similar grammar that defines a subset of the language OCaml. The subset I define is analogous to what we did with Python. I call it OCaml-lite.

An OCaml-lite program consists of a series of procedure and function definitions, each ending with ;; and introduced by a let. These definitions are then followed by a single let _ = statement. A statement, however, can be “compounded” by writing a begin, then a series of statements separated by semi-colons, ending with an end. Here, for example, is an OCaml-lite program that prints a sequence of factorials:

let rec fact(n) = if n = 0 then 1 else n * fact(n - 1) ;;

let facts(n,m) =
begin
    let i = ref n in
    while !i <= m do
    begin
        let si = string_of_int(!i) in
        let sf = string_of_int(fact(!i)) in
        print_string("factorial(" ^ si ^ ") is " ^ sf ^ ".\n");
        i := !i + 1;
    end done;
end;;

let _ =
begin
    print_string("Enter a starting integer:\n");
    let first = int_of_string(read_line()) in
    print_string("Enter an ending integer:\n");
    let last = int_of_string(read_line()) in
    facts(first,last);
end

It defines a function fact and then a procedure facts, and then has a main script that asks for two integers and executes facts with those two entered integers.

There are a few quirks. In particular there are two kinds of variables that can be managed within the statements of procedures. There are “immutable” variables that are given a value, but cannot be reassigned within the code. These are procedue parameters or else introduced with a let statement with this syntax:

    let name = expn in stmt

The other variables are “mutable” (or “reference”) variables and introduced with a let statement with this syntax:

    let name = ref expn in stmt

These variables can be reassigned with the statement

     name := expn

To access their values, you must prefix them with an exclamation mark, just as in the statement

i := !i + 1;

in the example above. You cannot use mutable variables within function definitions, only mutable ones.

The full summary of the syntax is given by this grammar

• TO DO: Modify the code so that it does not define a function fact. Instead, within facts, it computes the product of the numbers from 1 up to n, outputs that factorial, then continues to multiply that product by a variable i that counts up to m, giving a report on each successive factorial.

It should behave exactly the same as the program I wrote above, just use this different strategy for computing successive factorials, only using a modified facts procedure.

Here is its behavior with one run of the program:

Enter a starting integer:
3
Enter an ending integer:
6
factorial(3) is 6.
factorial(4) is 24.
factorial(5) is 120.
factorial(6) is 720.

[HW1 EX4 BONUS] guess six

Here is a link to some source code for a guessing game, written in OCaml-lite.

• TO DO: Modify the guessing game code, changing it so that a player can make no more than 6 guesses. If they fail to guess after 6 tries it should let them know that they failed, and then reveal to them the number they failed to guess.

NOTE: The guessing game code relies on random number generation, and this is not strictly part of our grammar’s syntax. Hopefully its use makes sense, anyway, and you write code that uses it.

Testing OCaml-lite code on your computer

The two prior exercises have you write code in a novel language, one that is a sub-dialect of the OCaml language. This language runs on many computer platforms, and you might want to try to get it working on your own machine. If so, you can follow the instructions on the OCaml language’s web pages for installing the system, particularly these install pages.

Once you feel like you have installed everything correctly, you’ll want to start working through their tutorial to see if it’s installed correctly. Just try a few simple interactions with the system, entering expressions as they suggest.

On my Mac I just typed the following in Terminal

ocaml

and the language system came up and gave me a prompt, just like in their tutorial.

You don’t need to read their Chapter 1 exhaustively. Just try a few things out and report back to me on Friday how that went. If it is installed correctly, then you can use it to test your work for Exercises 3 and 4.

Testing OCaml-lite code on-line

There is also a web page that provides an editor and interpreter for OCaml. It can be found at

    https://try.ocamlpro.com/

One of its quirks is that the call to read_line does not work. This mean that you won’t be able to easily test the guessing game. You can test a variant of the facts program by changing the bottom of the script to something like

let _ = facts(3,6)

instead of all that interactive code between begin and end in the last seven lines.

The most you can do in this demo, for code that uses read_line is make sure the code you write is syntacticly correct, and type checks ok.

Testing OCaml-lite code on patty.reed.edu

There is a Linux machine that I am setting up for this course so that you can all have an account. It will contain many of the tools I plan for us to use in this course. I will notify you with an email or Slack of your user’s name (same as your Reed login) along with a temporary password.

Once I have, you can log in and try out ocaml there.