邏輯表達式化簡：基於遞歸下降解析器的實現

問題背景：從中綴到展開式

給定一個包含邏輯與(*)、邏輯或(+)及括號([])的表達式，如 a*[b*[c+d]*e+f]+g，目標是將其化簡為不含括號的標準和項式：a*b*c*e+a*b*d*e+a*f+g。這本質上是布爾代數的分配律展開過程，也是編譯器前端表達式處理的核心環節。

編譯原理視角：LL(1) 文法與遞歸下降

參考編譯原理經典產生式，定義針對本問題的文法（已消除左遞歸）：

exp    → term { OR term }
OR     → '+'
term   → factor { AND factor }
AND    → '*'
factor → letter | '[' exp ']'
letter → [A-Z] | [a-z]

其中 exp 處理或運算，term 處理與運算，factor 處理括號遞歸與字母終結符。優先級隱含在文法結構中：factor > term > exp。

核心算法：遞歸下降解析器實現

每個非終結符對應一個解析函數。以 exp 為例：

CString Exp() {
    CString temp = Term();
    while (!IsEnd() && PeekChar() == '+') {
        Match('+');                 // 消費 '+'
        temp += "+" + Term();       // 遞歸處理下一項
    }
    return temp;
}

Term()、Factor() 同理。關鍵在於 Factor() 遇到 [ 時遞歸調用 Exp()，實現括號嵌套處理。化簡邏輯在構建返回字符串時自然完成：term 內部用 * 連接，exp 層用 + 連接，自動實現分配律展開。

運行效果與工程應用

程序支持多字母變量、任意層級括號嵌套，輸出標準化展開式。可作為規則引擎、邏輯電路優化、查詢解析器的基礎模塊。

總結與感悟

這是作者在 VCKBASE 發表的首篇文章。實踐證明：扎實的編譯原理功底能將看似複雜的字符串處理問題，轉化為結構清晰、易於維護的解析器代碼。理論與工程的結合，才是編程真正的樂趣所在。