JAVA or C++ Program

Sample test program for CFG class

// Test Context-Free Grammar Class

import java.io.*;

public class TestCFG

{

public static void main(String[] args)

{

// Language: strings that contain 0+ b's, followed by 2+ a's,

// followed by 1 b, and ending with 2+ a's.

String[] C = {"S=>bS",

"S=>aaT",

"T=>aT",

"T=>bU",

"U=>Ua",

"U=>aa"};

String inString, startWkString;

boolean accept1;

CFG CFG1 = new CFG(C);

if(args.length >= 1)

{

// Input string is command line parameter

inString = args[0];

char[] startNonTerm = new char[1];

startNonTerm[0] = CFG1.getStartNT();

startWkString = new String(startNonTerm);

accept1 = CFG1.processData(inString, startWkString);

System.out.println(" Accept String? " + accept1);

}

} // end main

} // end class

This project is intended to increase your understanding of languages and grammars. In a regular grammar (RG), all production rules must have one of the following forms: n, tit,t, t,N = where t, denotes a terminal (alphabet symbol), and N, and N) denote nonterminals. Any language defined by a regular grammar is a regular language. Regular languages can also be defined by finite automata, transition graphs, and regular expressions. More complex grammars, such as context-free grammars (CF), can define additional languages beyond regular languages. In a context-free grammar, the production rules have the form: N, any string of terminals and nonterminals where N denotes a nonterminal. Any language defined by a context-free grammar is a context-free language. Regular languages are a proper subset of the set of all context-free languages. Write a CFG class that meets the following design specifications: Instance variables String[] Code char -- production rules as program code -- starting nonterminal startNT Constructor CFG (String[ C) Methods char getStartNT 0 void setStartNT (char stNT) boolean processData (String inString, String wkString) The CFG class includes an instance variable Code of type String. The Code array contains program statements that define the production rules for the grammar, The instruction format for a CFG i: LHS= >RHS where LHS is the left-hand side and RHS is the right-hand side of a production rule. For a CFG, the LHS character is a single nonterminal. The RHS string can contain both terminals and nonterminals. For example, the statement S=>aTa, with LHS-S and RHS-ala, states that S can be replaced by aTa It is assumed that the starting nonterminal is the LHS value for the first production rule. The setStartNT method can be used to change the starting nonterminal, Note that you will need a recursive algorithm for the processData method, since two production rules may have the same LHS value. Your CFG class should work for the sample test program you w ill be given. Turn in the source code for your CFG class. This project is intended to increase your understanding of languages and grammars. In a regular grammar (RG), all production rules must have one of the following forms: n, tit,t, t,N = where t, denotes a terminal (alphabet symbol), and N, and N) denote nonterminals. Any language defined by a regular grammar is a regular language. Regular languages can also be defined by finite automata, transition graphs, and regular expressions. More complex grammars, such as context-free grammars (CF), can define additional languages beyond regular languages. In a context-free grammar, the production rules have the form: N, any string of terminals and nonterminals where N denotes a nonterminal. Any language defined by a context-free grammar is a context-free language. Regular languages are a proper subset of the set of all context-free languages. Write a CFG class that meets the following design specifications: Instance variables String[] Code char -- production rules as program code -- starting nonterminal startNT Constructor CFG (String[ C) Methods char getStartNT 0 void setStartNT (char stNT) boolean processData (String inString, String wkString) The CFG class includes an instance variable Code of type String. The Code array contains program statements that define the production rules for the grammar, The instruction format for a CFG i: LHS= >RHS where LHS is the left-hand side and RHS is the right-hand side of a production rule. For a CFG, the LHS character is a single nonterminal. The RHS string can contain both terminals and nonterminals. For example, the statement S=>aTa, with LHS-S and RHS-ala, states that S can be replaced by aTa It is assumed that the starting nonterminal is the LHS value for the first production rule. The setStartNT method can be used to change the starting nonterminal, Note that you will need a recursive algorithm for the processData method, since two production rules may have the same LHS value. Your CFG class should work for the sample test program you w ill be given. Turn in the source code for your CFG class