De Morgan與yacc的法則

Question

A有一個用yacc編寫的簡單語法，它從邏輯表達式構建樹，包括子表達式和AND（或OR（||）和NOT（！）運算符）。我不會在這裏提供語法本身，因爲它沒有什麼特別之處，它與無數YACC教程示例類似。

但是，我需要解析這些邏輯表達式，以便根據De Morgan定律擴展NOT運算符的所有括號。例如，我需要把表達

!((A && B) || C)) 

爲

(!A || !B) && !C 

是否有可能通過修改現有yacc語法來實現這一點？

Answer 1

在構建AST時，可以在YACC對而不是（！）操作符的縮減操作中執行此操作。你可以在語義動作中編寫任何你想要的代碼。你可以編寫代碼來檢查孩子是否具有所需的形狀，而不是「盲目地」爲它的孩子組裝樹節點而不是（通常的代碼，你可以在這種縮減動作中找到）因此，構建每個的de Morgan等價樹。這樣做的代碼有點麻煩，因爲它必須爬上樹下，匹配節點和重新劃分子樹，但它只是愚蠢的，並不壞。請注意，德摩根法律可以適用於形如「（A & & B）」的兒童。 C）和（A || B & & C）），所以你要處理兩個主要的子類。

我同意Len;您通常不會在解析器中執行此操作。它的目的是讓你設置更復雜的活動，除非DeMorganizing是唯一的目的，否則在解析完成後需要其他代碼來處理各種AST，所以爲什麼不把所有的處理都留在那裏？

遵循這個想法，我的recent SO answer on eliminating configured-dead code簡化了符號布爾邏輯;它展示了一種使用模式匹配源到源轉換來轉換布爾邏輯AST的方法。這種方法可以避免糟糕的樹檢查/黑客代碼。這應該是顯而易見的如何編寫可讀的轉換實現de摩根法則的技術（事實上，我們已經做過兒子）。

Answer 2

這不是你應該在yacc語法本身做的事情;您應該對AST的語法結構進行後處理，以執行此類減少操作。

你的語法應該來生產的AST某種-你想走路的結構和尋找的東西，其中!((A && B)|| C)形狀相匹配，並將其轉換就地對(!A || !B) && C。

如果您需要更多指導，請添加更多信息或提出更多問題。

編輯：如果你想與這個任何援助，在所有你應該提供你的語法。這聽起來像一個家庭作業練習，所以我希望這不是你不提供代碼的唯一原因。幫助我們幫助你。我們不知道你在語法動作上所做的是什麼，所以我們如何猜測我們能爲你做些什麼？