Consider the following grammar for arithmetic expressions. It is similar to the
ID: 3858866 • Letter: C
Question
Consider the following grammar for arithmetic expressions. It is similar to the one discussed in class.
The recursive descent parser to evaluate syntactically valid arithmetic expressions has five methods corresponding to each of the five non-terminal symbols of this grammar. A tokenizer is not used for this parser. Instead, each method gets input characters from a StringBuilder parameter called source. You can assume that the source argument does not contain any white space or any other characters not part of the expression except for at least one "sentinel" character after the end of the expression to mark the end. In other words, any proper prefix of the argument can contain only characters from the set {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '(', ')', '+', '-', '*', '/'}. You can further assume that the input is syntactically valid, so that no error checking is necessary.
Here are few more hints:
A string s1 being a proper prefix of a string s2 means both that the length of s1 is strictly less than (less than but not equal to) the length of s2 and that s1 is a prefix of s2.
The instance methods charAt(int) and deleteCharAt(int) defined in StringBuilder will be useful to manipulate the input.
The static methods isDigit(char) and digit(char, int) in class Character can be used to check if a character is a digit and to convert a digit character into the corresponding integer value, respectively.
Write the code for the following 5 methods making sure you use the grammar above as a guide (as discussed in class and in Recursive-Descent Parsing). [http://cse.osu.edu/software/2231/web-sw2/extras/slides/27.Recursive-Descent-Parsing.pdf] [JAVA]
/**
* Evaluates an expression and returns its value.
*
* @param source
* the {@code StringBuilder} that starts with an expr string
* @return value of the expression
* @updates source
* @requires <pre>
* [an expr string is a proper prefix of source, and the longest
* such, s, concatenated with the character following s, is not a prefix
* of any expr string]
* </pre>
* @ensures <pre>
* valueOfExpr =
* [value of longest expr string at start of #source] and
* #source = [longest expr string at start of #source] * source
* </pre>
*/
public static int valueOfExpr(StringBuilder source) {...}
/**
* Evaluates a term and returns its value.
*
* @param source
* the {@code StringBuilder} that starts with a term string
* @return value of the term
* @updates source
* @requires <pre>
* [a term string is a proper prefix of source, and the longest
* such, s, concatenated with the character following s, is not a prefix
* of any term string]
* </pre>
* @ensures <pre>
* valueOfTerm =
* [value of longest term string at start of #source] and
* #source = [longest term string at start of #source] * source
* </pre>
*/
private static int valueOfTerm(StringBuilder source) {...}
/**
* Evaluates a factor and returns its value.
*
* @param source
* the {@code StringBuilder} that starts with a factor string
* @return value of the factor
* @updates source
* @requires <pre>
* [a factor string is a proper prefix of source, and the longest
* such, s, concatenated with the character following s, is not a prefix
* of any factor string]
* </pre>
* @ensures <pre>
* valueOfFactor =
* [value of longest factor string at start of #source] and
* #source = [longest factor string at start of #source] * source
* </pre>
*/
private static int valueOfFactor(StringBuilder source) {...}
/**
* Evaluates a digit sequence and returns its value.
*
* @param source
* the {@code StringBuilder} that starts with a digit-seq string
* @return value of the digit sequence
* @updates source
* @requires <pre>
* [a digit-seq string is a proper prefix of source, which
* contains a character that is not a digit]
* </pre>
* @ensures <pre>
* valueOfDigitSeq =
* [value of longest digit-seq string at start of #source] and
* #source = [longest digit-seq string at start of #source] * source
* </pre>
*/
private static int valueOfDigitSeq(StringBuilder source) {...}
/**
* Evaluates a digit and returns its value.
*
* @param source
* the {@code StringBuilder} that starts with a digit
* @return value of the digit
* @updates source
* @requires 1 < |source| and [the first character of source is a digit]
* @ensures <pre>
* valueOfDigit = [value of the digit at the start of #source] and
* #source = [digit string at start of #source] * source
* </pre>
*/
private static int valueOfDigit(StringBuilder source) {...}
expr term { + term | - term } term factor { * factor | / factor } factor ( expr ) | digit-seq digit-seq digit { digit } digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Explanation / Answer
public final class ExpressionEvaluator { /** * Base used in number representation. */ private static final int RADIX = 10; /** * Private constructor so this utility class cannot be instantiated. */ private ExpressionEvaluator() { } /** * Evaluates a digit and returns its value. * * @param source * the {@code StringBuilder} that starts with a digit * @return value of the digit * @updates source * @requires 1 < |source| and [the first character of source is a digit] * @ensures* valueOfDigit = [value of the digit at the start of #source] and * #source = [digit string at start of #source] * source **/ private static int valueOfDigit(StringBuilder source) { assert source != null : "Violation of: source is not null"; int value = 0; while (source.length() > 0) { char op = source.charAt(0); if (Character.isDigit(op)) { value = Character.digit(op, RADIX); StringBuilder rest = source.deleteCharAt(0); value += valueOfDigit(rest); } else { StringBuilder rest = source.deleteCharAt(0); value += valueOfDigit(rest); } } return value; } /** * Evaluates a digit sequence and returns its value. * * @param source * the {@code StringBuilder} that starts with a digit-seq string * @return value of the digit sequence * @updates source * @requires
* [a digit-seq string is a proper prefix of source, which * contains a character that is not a digit] ** @ensures
* valueOfDigitSeq = * [value of longest digit-seq string at start of #source] and * #source = [longest digit-seq string at start of #source] * source **/ private static int valueOfDigitSeq(StringBuilder source) { assert source != null : "Violation of: source is not null"; int value = valueOfDigit(source); return value; } /** * Evaluates a factor and returns its value. * * @param source * the {@code StringBuilder} that starts with a factor string * @return value of the factor * @updates source * @requires
* [a factor string is a proper prefix of source, and the longest * such, s, concatenated with the character following s, is not a prefix * of any factor string] ** @ensures
* valueOfFactor = * [value of longest factor string at start of #source] and * #source = [longest factor string at start of #source] * source **/ private static int valueOfFactor(StringBuilder source) { assert source != null : "Violation of: source is not null"; int value; if (source.charAt(0) == '(') { source.deleteCharAt(0); value = valueOfExpr(source); source.deleteCharAt(0); } else { String number = source.substring(0, 0); source.deleteCharAt(0); value = Integer.parseInt(number); } return value; } /** * Evaluates a term and returns its value. * * @param source * the {@code StringBuilder} that starts with a term string * @return value of the term * @updates source * @requires
* [a term string is a proper prefix of source, and the longest * such, s, concatenated with the character following s, is not a prefix * of any term string] ** @ensures
* valueOfTerm = * [value of longest term string at start of #source] and * #source = [longest term string at start of #source] * source **/ private static int valueOfTerm(StringBuilder source) { assert source != null : "Violation of: source is not null"; int value = valueOfDigitSeq(source); while (source.charAt(0) == '+' || source.charAt(0) == '-' || source.charAt(0) == '*' || source.charAt(0) == '/') { char op = source.charAt(0); StringBuilder rest = source.deleteCharAt(0); if (op == '+') { value += valueOfFactor(rest); } else if (op == '-') { value -= valueOfFactor(rest); } else if (op == '*') { value *= valueOfFactor(rest); } else if (op == '/') { value /= valueOfFactor(rest); } } return value; } /** * Evaluates an expression and returns its value. * * @param source * the {@code StringBuilder} that starts with an expr string * @return value of the expression * @updates source * @requires
* [an expr string is a proper prefix of source, and the longest * such, s, concatenated with the character following s, is not a prefix * of any expr string] ** @ensures
* valueOfExpr = * [value of longest expr string at start of #source] and * #source = [longest expr string at start of #source] * source **/ public static int valueOfExpr(StringBuilder source) { assert source != null : "Violation of: source is not null"; int value = valueOfTerm(source); while (source.charAt(0) == '+' || source.charAt(0) == '-') { char op = source.charAt(0); StringBuilder rest = source.deleteCharAt(0); if (op == '+') { value += valueOfTerm(rest); } else { value -= valueOfTerm(rest); } } return value; } /** * Main method. * * @param args * the command line arguments */ public static void main(String[] args) { SimpleReader in = new SimpleReader1L(); SimpleWriter out = new SimpleWriter1L(); out.print("Enter an expression followed by !: "); String source = in.nextLine(); while (source.length() > 0) { /* * Parse and evaluate the expression after removing all white space * (spaces and tabs) from the user input. */ int value = valueOfExpr(new StringBuilder(source.replaceAll( "[ ]", ""))); out.println(source.substring(0, source.length() - 1) + " = " + value); out.print("Enter an expression followed by !: "); source = in.nextLine(); } in.close(); out.close(); } }
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.