Java自定义布尔逻辑表达式解析器开发求助

问题背景 #

我正在开发一个布尔逻辑表达式解析器，用来判断表达式中的词汇是否匹配文档内容。之前完全不懂解析器相关理论，查了很多资料还是搞不定——既没法写出无左递归的有效语法，也实现不了能正确运行的解析器，课堂又没讲过相关内容，实在头疼。

表达式规则与示例 #

需要解析的表达式示例：({w1 w2 w3} & !w4) | (w5 & "mark likes food")

• {}：内部词汇必须全部出现在文档中
• ""：必须完全匹配的字符串字面量

已定义的Token #

[AND, OR, NOT, LPAREN, RPAREN, LSET, RSET, LSEQ, RSEQ, WRD]
比如表达式(w1 & {w2 w2})会被分词为[LPAREN WRD AND LSET WRD WRD RSET RPAREN]

尝试过的无效语法 #

S -> E
E -> T AND T | T OR T | T
T -> LSET W RSET | LSEQ W RSEQ | LPAREN E RPAREN | NOT E | WRD
W -> WRD*  // 表示接受直到RSET或RSEQ前的所有WRD Token数组（不确定正式写法）

这个语法存在诸多问题：表达式无法完全求值（首次返回就停止）、括号处理错误等。

当前代码（分词器已验证正常） #

public class BoolExprParser {

    private final String expression;
    private final BoolExprTokenizer tokenizer;
    private BoolExprTokenizer.Token currentToken;

    private void advance() {
        currentToken = tokenizer.getNext();
    }

    private boolean currentEquals(BoolExprTokenizer.Token t) {
        return currentToken == t;
    }

    private boolean parse(Document doc) {
        advance();
        boolean val = expr(doc);
        if (!currentEquals(BoolExprTokenizer.Token.END)) {
            // error
        }

        return val;
    }

    private boolean expr(Document doc) {
        boolean leftExpr = subExpr(doc);
        switch (currentToken) {
            case AND:
                advance();
                boolean rightExpr = subExpr(doc);
                return leftExpr && rightExpr;
            case OR:
                advance();
                rightExpr = subExpr(doc);
                return leftExpr || rightExpr;
            case END:
                return leftExpr;
            default:
                //error
        }

        return false;
    }

    private boolean subExpr(Document doc) {
        switch (currentToken) {
            case NOT:
                advance();
                boolean result = expr(doc);
                return !result;
            case WRD:
                advance();
                return doc.isWord(tokenizer.getWord());
            case LSet:
                advance();
                boolean wordsInsideSet = wordsSet(doc);
                if (!currentEquals(BoolExprTokenizer.Token.RSet)) {
                    // error
                } else {
                    advance();
                }
                return wordsInsideSet;
            case LP:
                advance();
                boolean exprInside = expr(doc);
                if (!currentEquals(BoolExprTokenizer.Token.RP)) {
                    // error
                } else {
                    advance();
                }
                return exprInside;
            default:
                // error
        }

        return false;
    }

    private boolean wordsSet(Document doc) {
        boolean validToken = currentEquals(BoolExprTokenizer.Token.WRD);
        boolean isInDoc = true;

        while (validToken) {
            if (isInDoc) isInDoc = doc.isWord(tokenizer.getWord());
            advance();
            validToken = currentEquals(BoolExprTokenizer.Token.WRD);
        }

        if (!currentEquals(BoolExprTokenizer.Token.RSet)) {
            // error
        }

        return isInDoc;
    }
}

问题分析与修复方案 #

1. 语法设计：无左递归且支持运算符优先级 #

你原来的语法无法处理连续的AND/OR运算（比如A & B | C），正确的无左递归语法需要按运算符优先级（NOT > AND > OR）拆分：

S → E
E → E OR T | T          // 处理OR连续运算，优先级最低
T → T AND F | F          // 处理AND连续运算，优先级高于OR
F → NOT F | LPAREN E RPAREN | LSET WRD* RSET | LSEQ WRD* RSEQ | WRD

这种右递归结构既能避免左递归，又能支持任意长度的连续布尔运算。

2. 代码核心问题修复 #

你的代码存在三个关键问题：expr()只处理单次AND/OR、缺少字符串字面量（LSEQ/RSEQ）处理、错误处理不明确。以下是修复后的代码：

public class BoolExprParser {

    private final BoolExprTokenizer tokenizer;
    private BoolExprTokenizer.Token currentToken;

    public BoolExprParser(BoolExprTokenizer tokenizer) {
        this.tokenizer = tokenizer;
        this.currentToken = tokenizer.getNext(); // 初始化当前Token
    }

    private void advance() {
        currentToken = tokenizer.getNext();
    }

    private boolean match(BoolExprTokenizer.Token expected) {
        if (currentToken == expected) {
            advance();
            return true;
        }
        return false;
    }

    public boolean parse(Document doc) {
        boolean result = expr(doc);
        if (currentToken != BoolExprTokenizer.Token.END) {
            throw new IllegalArgumentException("表达式末尾存在无效Token: " + currentToken);
        }
        return result;
    }

    // 处理OR运算（优先级最低）
    private boolean expr(Document doc) {
        boolean result = term(doc);
        while (currentToken == BoolExprTokenizer.Token.OR) {
            advance();
            result = result || term(doc);
        }
        return result;
    }

    // 处理AND运算（优先级高于OR）
    private boolean term(Document doc) {
        boolean result = factor(doc);
        while (currentToken == BoolExprTokenizer.Token.AND) {
            advance();
            result = result && factor(doc);
        }
        return result;
    }

    // 处理原子表达式：NOT、括号、集合、字符串、单个词
    private boolean factor(Document doc) {
        switch (currentToken) {
            case NOT:
                advance();
                return !factor(doc); // NOT作用于原子表达式，符合优先级
            case LPAREN:
                advance();
                boolean result = expr(doc);
                if (!match(BoolExprTokenizer.Token.RPAREN)) {
                    throw new IllegalArgumentException("缺少闭合括号");
                }
                return result;
            case LSET:
                advance();
                boolean allInSet = true;
                while (currentToken == BoolExprTokenizer.Token.WRD) {
                    allInSet = allInSet && doc.isWord(tokenizer.getWord());
                    advance();
                }
                if (!match(BoolExprTokenizer.Token.RSET)) {
                    throw new IllegalArgumentException("缺少集合闭合符}");
                }
                return allInSet;
            case LSEQ:
                advance();
                StringBuilder literal = new StringBuilder();
                while (currentToken == BoolExprTokenizer.Token.WRD) {
                    if (literal.length() > 0) {
                        literal.append(" ");
                    }
                    literal.append(tokenizer.getWord());
                    advance();
                }
                if (!match(BoolExprTokenizer.Token.RSEQ)) {
                    throw new IllegalArgumentException("缺少字符串闭合引号");
                }
                return doc.containsLiteral(literal.toString()); // 假设Document有此方法
            case WRD:
                String word = tokenizer.getWord();
                advance();
                return doc.isWord(word);
            default:
                throw new IllegalArgumentException("遇到无效Token: " + currentToken);
        }
    }
}

3. 关键改进说明 #

• 拆分expr()/term()/factor()对应语法层级，确保运算符优先级正确
• 用循环处理连续AND/OR，解决表达式无法完全求值的问题
• 新增字符串字面量处理逻辑，拼接后匹配文档
• 替换注释为明确的异常抛出，便于调试
• 调整NOT的作用对象为原子表达式，符合布尔运算优先级规则

内容的提问来源于stack exchange，提问作者Jafeth