Consider the following grammar for Boolean expressions. The recursive descent pa

Question

Consider the following grammar for Boolean expressions.

The recursive descent parser to evaluate syntactically valid Boolean expressions has a single method corresponding to the bool-expr start symbol of this grammar. A tokenizer is used to convert the input into a queue of tokens (Queue<String>) given as the argument to the parser. The tokenizer takes care of the binary-op non-terminal symbol by returning "AND" and "OR" as single tokens. You can assume that the input is syntactically valid, so that no error checking is necessary. Here is a sample value for #tokens. It represents a a boolean expression whose parse tree only has depth 3. Other incoming values can be more complicated. Note that, as terminal symbols, parenthese can be part of a boolean expression. The given sample value represents the boolean expression:

The sample value promised for #tokens is:

In this case the outgoing value of tokens should be:

Do not test for equality against "### END OF INPUT ###" or test against the length of tokens. Another sample value for the same boolean expression is:

In this latter case the outgoing value of tokens should be:

Write the code for the following method 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 a Boolean expression and returns its value.

*

* @param tokens

*            the {@code Queue<String>} that starts with a bool-expr string

* @return value of the expression

* @updates tokens

* @requires [a bool-expr string is a proper prefix of tokens]

* @ensures <pre>

* valueOfBoolExpr =

*   [value of longest bool-expr string at start of #tokens] and

* #tokens = [longest bool-expr string at start of #tokens] * tokens

* </pre>

*/

public static boolean valueOfBoolExpr(Queue<String> tokens) {...}

bool-expr T | F | NOT ( bool-expr ) | ( bool-expr binary-op bool-expr ) binary-op AND | OR

Explanation / Answer

/** * Evaluates a Boolean expression and returns its value. * * @param tokens * the {@code Queue} that starts with a bool-expr string * @return value of the expression * @updates tokens * @requires [a bool-expr string is a prefix of tokens] * @ensures

      * valueOfBoolExpr =      *   [value of longest bool-expr string at start of #tokens]  and      * #tokens = [longest bool-expr string at start of #tokens] * tokens      * 

*/ public static boolean valueOfBoolExpr(Queue tokens) { boolean result = false; String token = tokens.dequeue(); if (token.charAt(0) == '(') { result = valueOfBoolExpr(tokens); String operator = tokens.dequeue(); if (operator.equals("AND")) { result &= valueOfBoolExpr(tokens); } else if (operator.equals("OR")) { result |= valueOfBoolExpr(tokens); } } else if (token.equals("NOT")) { result = !valueOfBoolExpr(tokens); } else if (token.equals("T")) { result = true; } else if (token.equals("F")) { result = false; } return result; } }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.