操作語義學

操作語義學的基本思想來源於程序設計語言的實施。英國1964年1月P.J.蘭丁使用“棧-環境-控制-外儲” 抽象機器（簡稱SECD機器），第一次系統地、嚴格地陳述了表達式的操作語義。

IBM公司的維也納實驗室 60年代在研究程序設計語言RL/1的形式定義時，提出描述操作語義的一種元語言──維也納定義語言（簡稱 VDL）。1974年歐洲計算機制造商聯合會和美國國家標準局正式建議使用 VDL定義的PL/1語義作為PL/1的標準。

1980年前後，英國愛丁堡大學的計算機科學家提出結構式操作語義學。它在一般的數學結構（不必是抽象機器）上用數學的歸約關係建立語義的解釋系統。這種方法具有指稱語義學的結構式特徵，並更多地略去了機器操作的細節。

表達式求值程序設計語言中的算術表達式用於加工計算機系統中現存的數據，以形成新的數據。如表達式〔(x1*x2)+1〕表示將計算機系統中對應變量x1,x2的存儲單元中數據相乘，再將乘積加1,形成一個新的數據。計算機系統中保存數據的存儲區可以用數據向量來表示。k個存儲單元保存的數據都是1時，可用k維向量(1,1,…,1)表示。計算機系統中還要有保存程序的區域，和保存加工過程中必要信息的工作區。就此可提出一種解釋執行算術表達式求值的抽象機器的模型。這個機器的存儲區分成三部分：棧區(用作工作區)，環境區(保存數據向量等)，控制區(保存程序)，整個存儲區記作(st,s,c),稱為抽象機器的一個大狀態。這個抽象機器具有識別符號，完成算術和邏輯運算，轉儲信息，實現大狀態之間的轉移等基本功能。

這個機器的大狀態轉移規則分為四類。 　第一類規則表示，當控制區中待執行的程序要求完成表達式(e1ope2)的求值時,抽象機就轉移自己的大狀態，準備先求子表達式e1和e2的值,然後再按照相應的運算op（+，-，*或其他算子），求出整個表達式的值，符號“/”用於分割存放的信息。第二類規則表示,當求值的表達式是一個常量時，則其值就是抽象機中表示這個常量的相應的量（粗體用來區別語言中的符號和在抽象機中的相應表示）。表達式的值暫存於棧區。第三類規則表示，當表達式是一個變量時，則其值就是環境區中相應單元的當前值。即第 i個變量xi的值就是數據向量s的第i個分量si的值。第四類規則表示,當運算op的兩個操作數都已經求得，則可按照抽象機中的相應運算求出op作用於操作數的結果。

在這個抽象機中，表達式(x1*x2)+1(在x1,x2值為2和3時)的求值是由下述大狀態的轉移序列完成的,轉移符號⇒的上方標有實現這一轉移依據的轉移規則號，設s=(2,3)。 　這個抽象機正確劃出算術表達式求值的全過程，故可作為算術表達式的操作語義。

賦值語句為定義賦值語句(xi:=e)的操作語義,可在上述抽象機中添加如下轉移規則 　第五條規則表示,當抽象機執行(xi:=e)時，先求出表達式e的值，然後再給xi賦值。

第六條規則表示，對xi賦以值n,相當於將數據向量s的第i個分量(即保存xi當前值的存儲單元)改為n，表示為。

在定義程序設計語言的過程語句的操作語義時，由於不同的過程使用不同的環境、不同的棧區、不同的控制區，故引入外儲區，外儲區中保存有當前未調用的所有過程的全部環境區、棧區和控制區，這種機器就是蘭丁的SECD抽象機。

人們希望語言的語義是獨立於實施的，故操作語義學中使用了抽象機器，但仍不可避免地涉及語言的實施，這是它的弱點。但現代研究狀況表明，操作語義學對語言的設計和實施仍有其指導作用，如在定義併發式程序設計語言的語義時，其他語義學方法都遇到了困難，而結構式操作語義學則提出了帶有標號的歸約規則，顯示了它獨有的長處。 ^[1]