CSCI 400

BNF Exercise

Add rules to the example grammar (repeated below for convenience) to create a BNF for the following constructs:

HINT: start with a non-terminal, such as <while-loop>.  What will a while loop look like in your language? That will be the right-hand side, which will include terminals (such as while) and non-terminals (such as <stmt> and others you determine are needed).

Use the BNF to create a derivation and parse tree for:

begin
 a = const;
 while (a > const)
    b = b + a;
    a = a – const
end

Create a sample derivation and parse tree for the for-loop, also.

NOTE: For this exercise, you are allowed to make some small changes to the grammar. Specifically, you may want to add tokens around the body of the while/for, such as braces { } or begin/end. For example, if you add braces, the code above would be:

begin
 a = const;
 while (a > const)
    { b = b + a;
    a = a – const }
end

Expression Grammar:
<program> -> begin <stmts> end
<stmts> -> <stmt>
    | <stmt> ; <stmts>
<stmt> -> <var> = <expr>
<var> -> a | b | c | d
<expr> -> <term> + <term>
       | <term> - <term>
       | <term>
<term> -> <var> | const

Sample code for above grammar:

begin
 a = const;
 b = c + d
end

Specific Requirements:

This exercise is worth 4 points.

Submit:

Write your answers into a text editor or Word. Submit the .txt or .doc file on Blackboard. If you work with a partner, submit just one copy and include your partner's name in the Blackboard comments.