/** * This class parses terms of propositional logic, and constructs an instance of * {@link BoolTerm BoolTerm}. * *
* This class provides a method, {@link #parse(String) parse()}, for parsing * terms of propositional logic. This method takes a string and determines * whether or not it represents a well-formed term of propositional logic (see * the page * on propositional logic for more details). *
* ** It is assumed that the strings to be parsed will be small: the class stores * the string to be parsed as an array of bytes (rather than using a stream of * characters, which would be a better approach for parsing long strings). *
* * @author Grant Malcolm * @version 0.0 */ public class Parser { // ***************************************************************** // the tokens of the language: /** Opening bracket */ private final static String LPAREN = "("; /** Closing bracket */ private final static String RPAREN = ")"; /** Operator for conjunction */ private final static String AND = "and"; /** Operator for disjunction */ private final static String OR = "or"; /** Operator for implication */ private final static String IMPLIES = "implies"; /** Operator for negation */ private final static String NOT = "not"; /** Constant: true */ private final static String TRUE = "true"; /** Constant: false */ private final static String FALSE = "false"; // ***************************************************************** // fields /** * Stores the string to be parsed as an array of characters. */ private byte[] input; /** * Index of the current character in the string. * * The string to be parsed is read character-by-character; this field stores * the location of the character currently being read. As each character is * read, this field should be incremented. */ private int index; /** * Index of the last accepted character. * * Sometimes a character is read that needs to be "put back"; for example, * reading an opening bracket causes a recursive call of the * {@link #parseToPrec(int) parseToPrec()} method, that will read an entire * term up until the closing bracket; once the closing bracket is read in * the recursive call, that call "puts the bracket back" by setting * {@link #index index} to the value ofbackIndex
and returns
* the term it has read; in the calling method, the closing bracket is read
* (to check that brackets match).
*/
private int backIndex;
// *****************************************************************
/**
* Parse a string representing a term in propositional logic.
*
* @param s
* the String
string to be parsed
* @return the BoolTerm
representing that term
* @exception ParseException
* if the given string is not a well-formed sentence in
* propositional logic.
*/
public BoolTerm parse(String s) throws ParseException {
// store the string as an array of bytes, removing any leading
// or trailing spaces
input = s.trim().getBytes();
// move to start of input
backIndex = 0;
index = 0;
if (input.length == 0)
parseError("Empty input");
BoolTerm t = parseToPrec(Operators.MAX_PREC);
// check that input is fully read
if (index != input.length)
parseError("Expected input to end at character number " + index);
// otherwise
return t;
}
// *****************************************************************
/**
* parse a term
*
* This method parses a term according to the precedence of its operators;
* for example, a term "a or b and c" will be parsed as a or (b and c) since
* "and" has a lower precedence than "or".
*
* The argument gives a precedence value, and the routine will return the
* BoolTerm corresponding to the largest initial substring of the input that
* does not contain an operator with a higher precedence than the argument
* (unless such an operator with higher precedence is nested in
* parentheses). Thus, calling the routine with MAXPREC causes the entire
* string to be parsed, because no operator can have a higher precedence
* than MAXPREC.
*
* Thus a call parseToPrec(p) will construct a term from the largest
* possible initial segment of the input string, that contains no operators
* with precedence higher than p, unless they are nested in brackets.
*
* @param prec
* the precedence of an operator; the method recursively reads a
* term until an operator of greater precedence is read
* @return the BoolTerm
representing the term read
* @exception ParseException
* if the term read is not a well-formed sentence in
* propositional logic.
*/
private BoolTerm parseToPrec(int prec) throws ParseException {
BoolTerm t1, t2;
Operator op;
// read the first term
t1 = readOneTerm();
backIndex = index;
// read an operator
int pr; // the precedence of the operator
String s;
while (!endOfInput()) {
s = nextToken();
// if s is a closing bracket, then t1 is the largest subterm
// that can be read
if (s.equals(RPAREN)) {
index = backIndex;
return t1;
}
// otherwise, the next token should be an operator
op = getOperator(s);
pr = op.getPrecedence();
// only read further if the precedence of the new operator
// is no greater than prec
if (pr > prec) {
index = backIndex;
return t1;
} else // op has lower precedence
{
t2 = parseToPrec(pr);
t1 = new BoolTerm(op, new BoolTerm[] { t1, t2 });
}
}
return t1;
}
/**
* Parse the smallest initial segment that can be read as a valid term.
*
* @return A {@link BoolTerm BoolTerm} representing the initial term
* @exception ParseException
* if the term read is not a well-formed sentence in
* propositional logic.
*/
private BoolTerm readOneTerm() throws ParseException {
BoolTerm t;
String s = nextToken();
if (s.equals(LPAREN)) {
t = parseToPrec(Operators.MAX_PREC);
read(RPAREN);
return t;
}
if (s.equals(NOT)) {
t = parseToPrec(Operators.NOT_PREC);
return new BoolTerm(Operators.NOT, new BoolTerm[] { t });
}
if (s.equals(TRUE)) {
return new BoolTerm(Operators.TRUEC);
}
if (s.equals(FALSE)) {
return new BoolTerm(Operators.FALSEC);
}
t = new BoolTerm(Operators.makeVar(s));
return t;
}
/**
* Test whether the end of the input string has been reached
*
* @return true
when {@link #index index} points to the end of
* {@link #input input}; false
otherwise
*/
private boolean endOfInput() {
return (index == input.length);
}
// *****************************************************************
/**
* Parse a string as the name of an {@link Operator Operator}. The string
* should be the name of one of the operators declared in {@link Operators
* Operators.java}.
*
* @param s
* a string representing the name of an {@link Operator Operator}
* @return the {@link Operator Operator} representing the initial term
* @exception ParseException
* if the string is not the name of an operator declared in
* {@link Operators Operators.java}.
*/
private Operator getOperator(String s) throws ParseException {
if (s.equals(AND)) {
return Operators.AND;
}
if (s.equals(OR)) {
return Operators.OR;
}
if (s.equals(IMPLIES)) {
return Operators.IMPLIES;
}
// else
throw new ParseException(
"Expected one of \"and\", \"or\", or \"implies\"");
}
/**
* Parse the smallest initial segment that can be read as a token
*
* @return the smallest initial string that can be read as a token
*/
private String nextToken() {
if (input[index] == '(') {
index++;
readWhiteSpace();
return LPAREN;
}
if (input[index] == ')') {
index++;
readWhiteSpace();
return RPAREN;
}
return readLiteral();
}
/**
* Check that the next part of the input is a given string.
*
* @param s
* the string that is expected to be next in the input
* @exception ParseException
* if that string is not next in the input
*/
private void read(String s) throws ParseException {
String t = readNext(s.length());
if (!t.equals(s))
parseError("Expected " + s + " at character number "
+ (index - s.length()));
}
/**
* Remove any leading white space in the input. {@link #index index} is
* incremented while the current input is white space
*/
private void readWhiteSpace() {
while ((!endOfInput()) && isWhiteSpace())
index++;
}
/**
* Test whether the current input is white space.
*
* @return true
if the current input character is white space
*/
private boolean isWhiteSpace() {
byte b = input[index];
return (b == 9 || b == 10 || b == 32);
}
/**
* Test whether the current input character is alphanumeric
*
* @return true
if the current input character is a letter or a
* digit; false otherwise
*/
private boolean isAlphanum() {
byte b = input[index];
return isAlpha(b) || isNum(b);
}
/**
* Test whether the current input character is a letter
*
* @return true
if the current input character is a letter;
* false otherwise
*/
private boolean isAlpha(byte b) {
return (65 <= b && b < 91) || (97 <= b && b < 123);
}
/**
* Test whether the current input character is a digit
*
* @return true
if the current input character is a digit;
* false otherwise
*/
private boolean isNum(byte b) {
return 48 <= b && b < 58;
}
/**
* Read a number of characters in the input.
*
* @param n
* the number of characters to be read
* @return the string consisting of the next n
characters from
* input
* @exception ParseException
* if there are fewer than n
characters
* remaining in the input
*/
private String readNext(int n) throws ParseException {
if (index + n > input.length)
parseError("Unexpected end of input");
String s = new String(input, index, n);
index += n;
readWhiteSpace();
return s;
}
/**
* Read an alphanumeric string from input.
*
* @return the longest alphanumeric string currently to be read in the input
*/
private String readLiteral() {
int start = index;
while ((!endOfInput()) && isAlphanum()) {
index++;
}
String s = new String(input, start, index - start);
readWhiteSpace();
return s;
}
// *****************************************************************
/**
* Throw a {@link ParseException ParseException} with a given error-message.
*
* @param s
* the error-message.
*/
private void parseError(String s) throws ParseException {
throw new ParseException(s);
}
}// Parser