COCS3308 Program-2 Due: 9/27/2006 Well-formed parenthesis (WFP) expression Generation THE FOLLOWING CFG MAY DEFINE THE SET OF WELL-FORMED PARENTHESIS (WFP) EXPRESSIONS: S -> S R S -> R R -> ( S ) R -> ( ) Objectives: 1. Appreciate the practical utility of unambiguous grammars. 2. Understand the process of leftmost derivations in obtaining all possible derivations. Task: Your task is to write a well-structured program (in any language of your choice) that generates and prints all different expressions for length of 8, 10, 12, and 14 respectively. For example, for the length of 4, we have two such expressions: (()) ()() and for the length of 6, we have five such expressions: ((())) (()()) (())() ()(()) ()()() SUGGESTED Functions 1. void S(int N, int POS, CHARSTRING A) { // N is the number of nonterminals yet to be derived and // it is initially half the length being sought. CHARSTRING Save; if (N==0) PRINT(A,POS) // TO PRINT AN EXPRESSION found // AFTER CONVERTING EVERY NONTERMINAL TO "()" else { strcpy(Save,A); RULE1 (N,POS,A); // TO APPLY RULE#1 AND THEN // RECURSIVELY CALL S() to continue strcpy(A,Save); RULE2 (N,POS,A); // TO APPLY RULE#2 AND THEN // call R() to continue } } // End of S() 2. void R(SAME PARAMETERS) { Charstring Save; if (N==0) PRINT(A,POS); else { strcpy(Save,A); RULE3 (N,POS,A); // TO APPLY RULE#3 AND THEN CALL S() to // continue strcpy(A,Save); RULE4 (N,POS,A); // TO APPLY RULE#4, LOCATE NEXT // NONTERMINAL R AND CALL R() to continue } } // END of R() 3. void RULE1 (int MORENONT, int POS, CHARSTRING A) { // Applying the rule-1: S -> S R int M; for ( M=MAXSIZE-1; M>=POS+1; M--) A[M+1]=A[M]; A[POS+1] := 'R'; S(MORENONT-1,POS,A); // as the result of applying rule-1, the number of remaining // nonterminals is reduced by one. } // end of RULE1() 4. OTHER functions: RULE2 RULE3 RULE4 PRINT(A, Pos) // This function will print the string // contents of 'A' after converting each remaining // nonterminal to be found beyond the given position // into "()"