如何構建真值表生成器？

我正在尋找一個真相表生成器作爲個人項目。如何構建真值表生成器？

有幾個基於web的在線here和here。

alt text
(Example screenshot of an existing Truth Table Generator）

我有以下問題：

我應該如何去分析類似的表達式：（（P => Q）&（Q => R ））=>（P => R）
我應該使用像ANTLr或YACC這樣的解析器生成器，還是使用直線正則表達式？
一旦我解析了表達式，我該如何去生成真值表？表達式的每個部分都需要分成最小的組成部分，並從表的左側重新構建到右側。我將如何評估這樣的事情？

任何人都可以提供有關解析這些任意表達式並最終評估解析的表達式的提示嗎？

來源

2009-07-05 KingNestor

正則表達式由於任意數量的括號而不起作用。你需要使用某種解析器生成器。 – 2009-07-05 21:42:29

我認爲，這些源代碼（http://mrieppel.net/prog/truthtable.html）很有用。 – yv4 2015-04-25 14:43:23

這聽起來像一個偉大的個人項目。你將學到很多關於編譯器基本部分如何工作的知識。我會跳過嘗試使用解析器生成器;如果這是爲了你自己的教化，你會從頭開始學習更多。

這種系統的工作方式是我們如何理解自然語言的形式化。如果我給你一句話：「狗，羅孚，吃了他的食物」，你做的第一件事就是把它分解成文字和標點符號。「The」，「SPACE」，「dog」，「COMMA」，「SPACE」，「Rover」......這是「標記化」或「lexing」。

您接下來要做的是分析令牌流以查看句子是否是語法。英語的語法非常複雜，但這句話很簡單。主題同位語謂賓。這是「解析」。

一旦你知道這個句子是語法的，你就可以分析這個句子，以便真正從中得到意義。例如，你可以看到這句話有三個部分 - 主語，同位語和賓語中的「他」 - 都指同一個實體，即狗。你可以發現狗是吃東西的東西，食物就是被吃的東西。這是語義分析階段。

編譯器然後有人類沒有的第四個階段，這是他們生成的代碼，代表在語言中描述的操作。

所以，做到這一點。首先定義你的語言的標記，定義一個基類Token和一組派生類。（IdentifierToken，OrToken，AndToken，ImpliesToken，RightParenToken ...）。然後編寫一個接受一個字符串並返回一個IEnumerable'的方法。這是你的詞法分析器。

其次，找出你的語言的語法是什麼，並編寫一個遞歸下降解析器，將IEnumerable分解成一個抽象語法樹，它表示語言中的語法實體。

然後寫一個分析工具，着眼於樹和數字的東西出來，像「有多少不同的自由變量做我有嗎？」

然後編寫一個代碼生成器，用於生成評估真值表所需的代碼。隨地吐痰IL似乎過度殺傷，但如果你想成爲真正的愛好者，你可以。讓表達式樹庫爲你做這件事可能會更容易;您可以將您的分析樹轉換爲表達式樹，然後將表達式樹轉換爲委託並評估委託。

祝你好運！

來源

2009-07-05 22:34:17

我認爲解析器生成器是一個矯枉過正的問題。您可以使用將表達式轉換爲後綴和evaluating postfix expressions（或直接從中綴表達式構建表達式樹並使用該表達式生成真值表）的想法來解決此問題。

來源

2009-07-05 21:44:49

但是，這是建立一個解析器，無論是手卷一個。如果你知道如何使用Lex（或者它是喜歡的），你也知道如何使用Lex。 – 2009-07-05 22:24:51

由於邁赫達德提到你應該能夠手卷的同時解析，因爲它會花時間去學習詞法分析器/解析器的語法。你需要的最終結果是你給出的表達式的一些抽象語法樹（AST）。

然後，您需要構建一些輸入生成器，用於爲表達式中定義的符號創建輸入組合。

然後在輸入集迭代，產生每個輸入組合的結果，給定的規則（AST）在第一個步驟中解析。

我會怎麼做：

我能想象使用lambda功能，解析樹來表達AST /規則，並建立一個符號表你分析，你則可以構建輸入集，將符號表解析爲lambda表達式樹，以計算結果。

來源

2009-07-05 22:39:39

如果你的目標是處理布爾表達式，解析器發電機和所有以去機械是浪費時間，除非你想了解他們是如何工作的（那麼任何人就可以了）。

但很容易建立手工遞歸下降解析器布爾表達式，計算並返回「評估」表達的結果。這樣的解析器可以用於第一遍以確定唯一變量的數量，其中「評估」是指「每個新變量名稱的數據1」。編寫一個生成器爲N個變量生成所有可能的真值是微不足道的;對於每組值，只需再次調用解析器並用它來評估表達式，其中評估意味着「根據運算符組合子表達式的值」。

你需要一個語法：

formula = disjunction ; 
disjunction = conjunction 
       | disjunction "or" conjunction ; 
conjunction = term 
       | conjunction "and" term ; 
term = variable 
     | "not" term 
     | "(" formula ")" ;

此致可能更復雜，但對於布爾表達式不能是複雜得多。

對於每個語法規則，寫1個子程序使用一個全球性的「掃描」字符串索引被解析：

int disjunction() 
// returns "-1"==> "not a disjunction" 
// in mode 1: 
// returns "0" if disjunction is false 
// return "1" if disjunction is true 
{ skipblanks(); // advance scan past blanks (duh) 
    temp1=conjunction(); 
    if (temp1==-1) return -1; // syntax error 
    while (true) 
    { skipblanks(); 
     if (matchinput("or")==false) return temp1; 
     temp2= conjunction(); 
     if (temp2==-1) return temp1; 
     temp1=temp1 or temp2; 
    } 
    end 

    int term() 
    { skipblanks(); 
    if (inputmatchesvariablename()) 
     { variablename = getvariablenamefrominput(); 
     if unique(variablename) then += numberofvariables; 
     return lookupvariablename(variablename); // get truthtable value for name 
     } 
    ... 
    }

您的每一個解析例程將這個複雜的。認真。

來源

2009-08-22 11:57:55

你可以在http://code.google.com/p/pyttgen/source/browse/#hg/src得到pyttgen程序的源代碼，它產生的真值表的邏輯表達式。基於ply庫的代碼，所以它非常簡單:)

來源

2010-05-14 20:19:25 RANUX

如何構建真值表生成器？

回答

相關問題