C語言分析器的數學表達式與一個變量，並將其保存到一個函數

Question

我知道有像boost.spirit或從http://jamesgregson.blogspot.de/2012/06/mathematical-expression-parser-in-c.html和許多其他表達式分析器的庫。

但是，我的表達式要在循環內進行很多次評估，而且每次運行解析器都效率不高。

假設我的表達式字符串是"exp(-0.5*(t-t_0)^2/(b^2))"（簡單高斯）， 其中t_0b和是常數，只有t（=時間）的環內變化。我想能夠將表達式以某種方式保存到接受一個參數（對於變量t）的函數中，然後該函數將評估該表達式。

你有什麼想法知道如何做到這一點，或者它是否可以完成？

Answer 1

你想實現的是完全可行的。例如，可以從表達式構建AST（https://en.wikipedia.org/wiki/Abstract_syntax_tree），其中樹的某些節點表示變量。

然後，對變量的某些值的表達式的評估對應於該樹的評估。實際上，大多數解析器都會在內部生成這樣的樹，並且您可能能夠找到一些庫來爲您的需要生成AST，或者您可能想自己編寫AST（另請參閱https://en.wikipedia.org/wiki/Shunting-yard_algorithm）。 Here是一個生成AST的表達式解析器的簡單例子（儘管在Java中）。

Answer 2

將（字符串）表達式轉換爲抽象語法樹，並在每次迭代中解釋它，而不是每次都解析它。如果這還不夠，那麼找到合適的字節代碼表示形式，並將您的抽象語法樹編譯爲字節代碼列表並將其提供給（字節代碼）解釋器。如果仍然沒有足夠的性能，那麼將您的抽象語法樹或字節代碼編譯爲機器代碼，使用（平臺相關）方式讓操作系統知道它是可執行代碼並調用它。

正如您可能已經猜到的那樣，每一步的難度和複雜性都會大大增加。但這是一個很好的學習項目。對於產品代碼，您可以考慮將llvm用於字節代碼以執行機器代碼編譯任務。

Answer 3

我完全同意上面提到的有關創建AST並在每次迭代中對其進行評估的所有答案。這是迄今爲止做你想做的最好的（也是最正確的）方式。

但我寫了編譯器爲生，我不禁建議另一個有趣的解決方案。當你說你想創建一個接受1個參數並返回結果的「函數」時，我提出了一個額頭。

讓我們試着做到這一點。

我們將開始爲我們的「功能」分配一些內存。

現在讓我們假設4k字節就足夠了。 所以我們開始做

void* my_func = malloc(4k); 

現在，這是我們需要使該地區執行真正的功能。這將取決於您的操作系統，您將不得不調用正確的系統調用。 您只需將執行權限授予此頁面即可。

現在我們解析表示表達式的字符串。 我在這裏假設WIN 64 fastcall調用約定。你可以使用你自己的。 所以參數t將在％rcx中，thr的結果將以％rax的形式返回。

現在，讓我們的示例表達 - T * 2 + 5

因此，我們將有總成 -

imulq $2, %rcx, %rcx 
addq $5, %rcx 
movq %rcx, %rax 
retq 

現在我們組裝成等效字節這在my_func，並將

所以你會有一些等效的 -

strcpy((char*)my_func, "\x48\x6B\xC9\x02\x48\x83\xC1\x05\x48\x89\C8\C3\0"); 

而不是一個字符串喲你將擁有建立在解析的緩衝區。 但你明白了。

如果需要更多內存，您可以分配兩倍的大小並複製內容。

最後，所有你所要做的就是打電話給你的內循環「功能」 -

typedef int (*func_type)(int); 
for(t=0; t<N; t++) 
    s=(func_type)(my_func)(t); 

雖然這是最不切實際，難以實現方法，我向你保證這會給你最好的性能（假設你生成有效的組裝）。

這是一個有趣的練習不被重視。很高興看到一個庫爲簡單的表達式做這件事。

另外不要忘記釋放你的記憶並移除執行標誌。

編輯：一個半最佳，但容易產生策略將是使用堆棧的所有操作。基本上，一旦解析完成後構建AST，就會從堆棧中彈出每個節點的參數，然後使用寄存器計算結果並將其推回堆棧。最終值可以彈出到％rax中。這個策略對AST的任何運行時間評估都是有效的。 爲您節省了所有的寄存器分配和指令調度的負擔。