Program 2 - Build a Parser and and Language

Build a program to take a BNF grammar and generate sentences in the language specified by the grammar. The program will read the grammar and then it will allow interactively building a sentence in the language specified by the grammar. Assume the BNF is correct. No BNF rule will have more than 15 items on the right hand side. All items in a rule are separated by white space. (You can require exactly one space between items). Each rule is exactly one line. You can limit the number of rules to 50.

The BNF rules (referred to as a grammar) are stored in a file. Your program is to read and echo the grammar file, and then walk the user through the process of building a sentence.

Once the grammar is read, the program will prompt the user to build a sentence in the specified grammar. For example assume the grammar is:

  <s> ->  let <var> = <val>
  <val> -> <var> | <num>
  <var> -> a | b
  <num> -> 1 | 2 | 3

The program and the user could have the following interaction (user answers after the ?):

deriving <s> 
deriving <var>
specify number of choice: 1 a, 2 b
?2
deriving <val>
specify number of choice: 1 <var>, 2 <num>
?2
deriving <num>
specify number of choice: 1 1, 2 2, 3 3
?1
The derived sentence is:
let b = 1

Assume the left hand side (LHS) of the first rule specifies the start symbol. Demonstrate the program with at least two grammars and for each grammar at least two examples. You need to use recursion to run through a rule after you start. Otherwise, you have to keep a stack of states of where you are.

You are graded on the report you turn in. It needs to show that the features work. If you do not have test data for a feature, it is assumed it is not in the code and you will be graded accordingly. It does not matter if it is in the code or not. That is, you are also graded on the test data. You need to develop test data that shows the major required features are in your program.

HINTS FOR PROBLEM 2

If we wrote a program to list out a single rule (with no nonterminals on the RHS), it could look something like this:

struct rule 
  {
    char *token[MAX_TOKEN_COUNT];
    int  tokencount;
  }

RULE:           <s> -> a + b
SUBSCRIPTS:      0  1  2 3 4
rule.tokencount:             5
PSEUDO-CODE:

list_rule(rule)
            for( i=2; i<rule.tokencount; i++)
	      list_terminal(rule.token[i]);

If you could have nonterminals we would have to add in some code to handle the nonterminals. This example assumes no choices.

RULES:		<s> -> <var> + 5
		<var> -> a

list_rule(rule)
	for( i =2; i<rule.tokencount; i++)
	  if( non_terminal(rule.token[i]) ) list_nonterminal( rule.token[i])
	  else list_terminal(rule.token[i]);