正規語言 (Formal Language)

在資訊系的相關課程當中,與高階語言相關的課程,包含程式語言 (Programming Language)、正規語言 (Formal Language)、以及編譯器 (Compiler) 等等。這些課程的核心是語法理論,我們可以利用生成規則 (例如:BNF, EBNF 等) 描述程式的語法。一但能正確的描述某個程式語言,就能撰寫剖析該語言的剖析程式,將這些語法轉換成語法樹 (或稱剖析樹)。

高階語言所使用的語法,大致上分為兩個層次,在單詞的語法上會使用正規語法 (Regular Grammar),而句法結構上則使用與上下文無關的文法 (Context-Free Grammar,簡稱 CFG),這兩個語法都可以使用近代語言學之父的喬姆斯基 (Chomsky) 的生成語法 (Generative Grammar) 描述。在程式語言的領域,我們通常用 BNF 與 EBNF 語法描述這些程式的語法。

Chomsky 是個語言學家,提出的生成語法主要也是為了描述人類所說的語言,這在資訊科學的領域被稱為自然語言,以便與程式設計時所用的程式語言區分開來。然而,生成語法雖然主要為了描述自然語言而提出,但卻同樣適用於程式語言的語法上,甚至在程式語言的設計上造成了相當大的影響,這或許是當初 Chomsky 所沒有想到的。

語法的概念或許並非 Chomsky 所第一個提出的,但以正規的遞迴結構,有系統的描述英文的文法,則應歸功於 Chomsky,當初 Chomsky 看出了英文文法當中具有強烈的結構性,可以利用生成語法規則描述。透過有限的 (甚至是只有很少的幾條) 語法規則,就可以描述變化無窮的英文語句,這導至語言學研究的重要革命。同樣的,在程式語言上,也能利用規則,產生變化無窮的程式組合,這可以說是一個意外的收穫。

有關喬姆斯基語法階層的理論,是正規語言課程的主題,甚至牽涉到進階的計算理論主題,在此我們僅簡單的列出各型語法於表格 7.1當中,詳細內容請參考正規語言與計算理論課程的教科書。

表格 7.1 喬姆斯基語法階層

文法 語言 自動機 產生式規則
0-型 遞迴可枚舉語言 (Recursively Enumerable) 圖靈機 (Turing Machine) α-> β
1-型 上下文相關語言 (Context Sensitive Grammar) 線性有界非確定圖靈機 (Linear Bounded Automata) αAβ -> αγβ
2-型 上下文無關語言 (Context Free Grammar) 非確定下推自動機(Push Down Automata) A -> γ
3-型 正規語言 (Regular Grammar) 有限狀態自動機 (Finite State Automata) A -> aB A -> a
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License