BNF grammar for the set of rules

Question

I have a problem

(a) Give a grammar using BNF rules to construct a program in the language "witless". A witless program must follow the rules: The program must start and end with the word 'endstart' . There are three types of statements in the language: print , read , and compute. These statements can occur in any order except that the print can only occur immediately after the compute statement. Here is any nonempty string of uppercase letters. Your BNF must define also. An example of a legal witless program is: endstart read SAM read TED compute compute print FRED compute read TIM endstart (b) Is your grammar ambiguous? Explain your answer.

I came up with the following solution. But I need to make sure that it is right.

<witless_program>::=endstart <statement> endstart
<statement>::=<read>|<compute>
<read>::='read' <var>|<statement>
<print>::='print' <var>
<compute>::='compute' | 'compute' <print>|<statement>
<var>::=<letter> | <var><letter>
<letter>::=A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

The grammar seems to be unambiguous. Am I right?

Answer 1

It looks like your grammar is a little bit off. For assumption lets say someone chooses a derivation like the following:

program --> endstart <statement> endstart
--> endstart <read> endstart
--> endstart read <var>

Using the current grammar you will not be able to use recursion to continue the sentence in the language as after the non terminal var has been fully derived there are no references back to the non terminal statement.

I would consider the following grammar to suit your needs:

<statement> --> <read> | <compute>
<read>      --> read <var> <statement> | read <var>
<compute>   --> compute <print> <statement> | compute <print> | compute <statement> | compute
<print>     --> print <var>
<var>       --> <letter> | <letter><var>
<letter>    --> A|B|C|...

Now lets derive the sentence "endstart read SAM read TED compute compute print FRED compute read TIM endstart" using LHS substitution:

program --> endstart <statement> endstart
--> endstart <read> endstart endstart
--> endstart read <var> <statement> endstart
--> endstart read <letter><var> <statement> endstart
--> endstart read S<var> <statement> endstart
--> endstart read S<letter><var> <statement> endstart
--> endstart read SA<var> <statement> endstart
--> endstart read SA<letter> <statement> endstart
--> endstart read SAM <statement> endstart
--> endstart read SAM <read> endstart
--> endstart read SAM read <var> <statement> endstart
--> endstart read SAM read <letter><var> <statement> endstart
--> endstart read SAM read T<var> <statement> endstart
--> endstart read SAM read T<letter><var> <statement> endstart
--> endstart read SAM read TE<var> <statement> endstart
--> endstart read SAM read TE<letter> <statement> endstart
--> endstart read SAM read TED <statement> endstart
--> endstart read SAM read TED <compute> endstart
--> endstart read SAM read TED compute <statement> endstart
--> endstart read SAM read TED compute <compute> endstart
--> endstart read SAM read TED compute compute <print> <statement> endstart
--> endstart read SAM read TED compute compute print <var> <statement> endstart
... play the same game to spell out FRED ...
--> endstart read SAM read TED compute compute print FRED <statement> endstart
--> endstart read SAM read TED compute compute print FRED compute <statement> endstart
--> endstart read SAM read TED compute compute print FRED compute <read> endstart
--> endstart read SAM read TED compute compute print FRED compute read <var> endstart
... play the same game to spell out TIM ...
--> endstart read SAM read TED compute compute print FRED compute read TIM endstart

Now that we have a derivation the issue of ambiguity can be addressed. The question you should be asking is whether or not the grammar has an additional parse tree. The trick to this is looking at the grammar and trying to identify any non terminals that have productions which contain an instance of itself which could lead to one path or another. Think

<statement> --> <statement><statement> | some_terminal

For this sort of production the parser has to decide which path to go down (in this case, which statement to replace first). If your grammar doesn't have productions with this sort of property, it usually is unambiguous.

And to answer your question -- No, the corrected grammar is not ambiguous.