戈登·普羅特金(Gordon Plotkin)在(Plotkin04a)中引入了結構操作語義的概念作為一個定義操作語義的邏輯方式。其基本主意是使用程序組成部分的行為來定義一個程序的行為,由此來提供一個對操作語義結構性的,即按照句法和歸納性的,分析。結構操作語義對一個程序的行為的說明是通過一(組)變化關係來表示的。其形式是一系列推理規則,這些推理規則通過一組句法的轉換來定義該組的合理轉換。
比如我們考慮一個簡單計算機語言的部分語義,在Plotkin04a和Hennessy90以及其它教科書中有相應的圖像。設
為該語言的程序域,
是狀態域(即函數的存儲地址及值)。假如我們有表述(
的域)、值(
)和存儲地址(
),則一個存儲更新指令的語義為:
使用普通語言,這個公式說假如在
狀態的
的值為
則程序
會通過
更新
的狀態。
系列的語義可以用下列規則來表達:
第一個規則說假如處於狀態
的程序
可以被簡化為處於狀態
的程序
的話則處於狀態
的程序
能被簡化為處於狀態
的程序
。第二個規則說假如處於狀態
的程序
以狀態
結束的話,則處於狀態
的程序
可以簡化為處於狀態
的程序
。這裡的語義是結構化的,因為程序序列
的意義是由
的意義和
的意義定義的。
假如我們還有狀態的布爾函數表示
的話我們可以定義while指令的語義:
這樣的定義允許對程序行為進行公式化的分析和研究程序間的關係。
由於結構操作語義看上去非常易懂,結構簡單,因此它獲得了很大的歡迎,實際上成為定義操作語義的標準。結構操作語義最初的報告因此獲得了約900次引用[1],成為計算機科學中被引用最多的技術報告之一。