1. Understanding simple grammars and parsing 

 2. Implementing a Recursive-Descent Parser. 

Consider the following grammar that defines all possible arithmetic expressions provided that: 

 a. we have only three operators: +, -, and * 

 b. we have only three operands: A, B, and C 

 c. we have any number of parentheses in the normal way. 

 d. we want the usual operator precedence incorporated into any expression we get. 

 EXP -> EXP + Term 

 EXP -> EXP - Term 

 EXP -> Term 

 Term -> Term * Fact 

 Term -> Fact 

 Fact -> A 

 Fact -> B 

 Fact -> C 

 Fact -> ( EXP ) 

 Task: 

 Write a program that does: 

 1. Read one expression (as a character string, of course) 

 after another and check to see if it is an expression  

 of the expected kind, and 

 2. Print the input expression followed by a message that  

 indicates whether or not it is a legitimate expression. 

 Suggestion for Program Design 

1. Set up a function (java method) for each nonterminal (our textbook calls variable) of  

the grammar. 

2. main method() 

 2a. establish an input file stream // To read input exps from a file. 

 2b. while (input-not-over) 

 read next input expression. 

 echo-print the input expression. 

 append an end=marker ($) to the input expression. 

 initial current to zero. 

 if(E()&&exp[current]=='$')  

 println (" INPUT EXPRESSION LEGITIMATE. ") 

 else println (" INPUT EXPRESSION NOT LEGITIMATE. ") 

 3. parsing function setup 

 int E() // return 1 if successful else 0 

 // EXP -> Term {+ Term || - Term}* 

 { if (!Term()) 

 return 0; //the very first term is not found, hence a failure 

 else 

 { while (exp[current] == '+' || exp[current] == '-') 

 { current++; 

 if (!Term()) return 0; 

 } // All terms are found in success, so return in success 

 return 1; 

 } 

 } 

 //////////////////////////////// 

 int Term() // This function can be set up more or less like E() above. 

 //////////////////////////////// 

 int Fact() // A factor is either 'A', 'B', 'C', or "(EXP)" 

 { char Cur = exp[current]; 

 if (Cur=='A' || Cur=='B' || Cur=='C') 

 { current++; 

 return 1; 

 } 

 else if (Cur=='(') // a case of (E) 

 { current++; 

 if(!E()) return 0; 

 else if (exp[current]==')') 

 { current++; 

 return 1; 

 } 

 else return 0; // matching right-paren missing 

 } 

 else // A missing factor. 

 return 0; 

 } 

 Inputs: 

 For the sake of simplicity, we can assume that an input 

 expression does not contain any embedded blanks. 

 And, that each input expression is no longer than 50 characters long.  

 Use the following six input expressions for testing your program: 

 ((A+A*B)-B)*C // Legitimate 

 (((A+B-C)))+A*B // Legitimate 

 ((A+B*C)+(A+B*C) // Illegitimate 

 ((A*B*C))-(A*B+C)*A)) // Illegitimate 

 A+B/C+((A+B*C)*C) // Illegitimate 

 A*B+()*B+A // Illegitimate