形式語言:現代工程師可以用程式語言、不需要用紙帶打洞來寫程式都要感謝它

電腦如何判讀高階語言?形式語言

如果你想要學編譯器的相關原理,必修形式語言的邏輯。

1950 年代的電腦程式都還是機器語言,也就是所有的指令只能用 0 與 1 的排列組合來表示,這使得寫程式、除錯、修改程式都相當浪費時間。

美國電腦科學家約翰·巴克斯(John Backus)當時在 IBM 工作,後來向老闆提出:應該開發比較接近人類語言的高階語言,更方便編程。

要怎麼讓電腦辨識人類的語言特性呢?

這就要用到形式語言啦!在數學、邏輯和電腦科學領域中,形式語言(Formal language)是用精確的數學或機器、可處理的公式定義的語言。

形式語言的研究始於 20 世紀初,而把形式語言用於模擬自然語言是 1950 年代左右。

當時,許多數理語言學家致力於用數學方法研究自然語言的結構,尤其是 1946 年第一台電腦 ENIAC 出現以後,人們很快想到能用電腦來作自然語言的機械翻譯。

可是這項工作在取得一些初步的成功以後便停滯不前,翻譯的質量很難提高,主要是因為當時對自然語言結構的理解太表面化。

1956 年,喬姆斯基發表了用形式語言方法研究自然語言的第一篇文章,稱為「轉換生成文法」。

轉換生成文法繼續發展喬姆斯基先前提出的普遍文法理論 (Universal Grammar)。喬姆斯基認為,若普遍文法是正確的話,人類的大腦應該能夠系統性地生產文法正確的字句。

因此他嘗試利用轉換生成文法,來描述生產正確文法字句的過程。

1957 年,IBM 的約翰.巴克斯等人發明了高階語言 Fortran 語言與編譯器。人們發現巴克斯使用的語法幾乎就是喬姆斯基發表的文法理論。

從而成了形式語言被廣泛應用於程式語言的濫觴,使程式語言設計成為現代電腦科學的一個重要分支。

在數學或電腦科學當中,形式語言就是「一個符號字串的集合、加上其所對應規則的集合。」

(In mathematics and computer science, a formal language is a set of strings of symbols together with a set of rules that are specific to it.)

所以我們在分析語言時,需要將語言以數學模型的抽象形式表達。比如機器翻譯、語音識別等,然後利用計算機去針對該數學模型求解。

來看看語言要如何用數學式來表達吧!

 

什麼是語言?字串所成的集合

a, b, 3, *, %, w, 0… 這些符號都叫做一個「符號」或「字元」。把字元集合起來可以變成「字串」,比如變成:abcde,這就叫「含有五個字元的字串」。

喬姆斯基對語言的定義方法是:給定一組符號(有限多個),稱為字母表,以 ∑ 表示之。

又以 ∑* 表示由 ∑ 中字母組成的所有字串的集合。則 ∑* 的每個子集都是 ∑ 上的一個語言。

例如,若令 ∑ 為 26 個字母加上空格和標點符號,則每個英語句子都是 ∑* 中的一個元素,所有合法的英語句子的集合是 ∑* 的一個子集,最後構成一個語言。

喬姆斯基的語言定義方法為人們所公認,一直沿用下來。

 

將上述理論以數學表達:

假設 ∑ 為一個有限的非空符號所成的集合,稱為符號集 (alphabet)。

∑ 的次方定義成:

  1. 1 = ∑
  2. n+1  = { xy | x ∈ ∑, y ∈ ∑n }

( $latex \sum^{n}$ 表示佈於 $latex \sum$ 的 n 個符號或字母的串連 (concatenation) )

—舉例—

$latex \sum = \left\{ 0, 1 \right\}$,則 $latex \sum^{2} = \left\{ 00, 01, 10, 11 \right\}$

$latex \sum = \left\{ a, b, c, d \right\}$,則 $latex \sum^{3}$ 包含的字串個數為 $latex 4^{3} = 64$,例如 aaaa, abad, bcda 等皆為 $latex \sum^{3}$ 的字串。

 

我們也可找到由一個符號集,來構成一個語言:

假設 $latex \sum$ 為一個符號集,若 $latex A \subseteq \sum^{*}$ 則稱 A 為佈於 $latex \sum$ 的一個語言。( A is a language over $latex \sum$ )

—舉例—

$latex \sum = \left\{ a, b, c \right\}$

  • $latex L{1} = \left\{ a, ab, ac, bc, abc, acb, cab \right\}$
  • $latex L{2} = \left\{ abcba, bcbca \right\}$
  • $latex L{3} = \left\{  \right\}$
  • $latex L{4} = \left\{a^{i}cb^{i}  \mid i\geqslant 1 \right\}$

則 $latex L{1}, L{2}, L{3}, L{4}$ 均為佈於 $latex \sum$ 的語言。

轉換生成文法:生成文法正確的語言

喬姆斯基提出了「轉換生成文法」(Transformational-Generative Grammar) 作為描述形式語言的方法。比如:

  • 語言 ɑ*, 意指包括了 a, aa, aaa, aaaa… 等至少包含一個 a 的字串。
  • 其文法為 {S → ɑ, S → ɑS}

這個文法由兩條規則所產生。

每一步轉換(推導),都用一條轉換規則的右邊、替換它的左邊。

S 是出發點,代表語言 ɑ 中任何一個可能的句子。

例如,句子 ɑɑɑɑɑ 可以這樣推導出來:S → ɑS → ɑɑS → ɑɑɑS → ɑɑɑɑS → ɑɑɑɑɑ。

推導共分五步。前四步用了第二條規則,第五步用了第一條規則。

按這個辦法,可以生成 ɑ* 中的所有句子,即整個 ɑ* 語言。

——A language could be generated by the grammar.

 

note: 文法四要素組成:起始, 非終端, 終端, 產生規則

嚴格來說,喬姆斯基將「轉換生成文法」定義為四個要素:

G 為一個文法,$latex G = \left ( S, N, T, P \right ) $

(1) T 為終端符號(有限集合),表示不能再以其他符號代替

(2) N 為非終端符號,表示可以再以其他符號來替代。而 N 與 T 須具以下的關係:N∩T=φ

(3) S 為起始符號,表示文法推演之步驟由 S 開始,S ∈ N

(4) P 為文法產生規則的集合

(a) P 中的每個規則,具有 α → β 的形式。

(b) 其中 α ∈ (N U T)* – T*, β ∈ (N U T)*

(c) α ∈ (N U T)*-T*  代表 α 由非終端符號與終端符號所組成的任意長度之字串,但至少包含一個非終端符號。

(d)  β ∈ (N U T)* 代表由 β 非終端符號與終端符號所組成的任意長度之字串。

note: 文法 G 能用來生成語言 l(g)

$latex G = \left ( S, N, T, P \right ) $ 為一個文法。

可由 S 推導出的所有字串、所成的集合,稱為 G 生成的語言 (Language generated by G),記作 L(G)。

數學式記為:$latex L(G) = \left\{  \alpha \in T^{*} \mid S \overset{*}{\rightarrow} \alpha \right\}$

 

文法的分類—喬姆斯基體系中的四型文法

根據 P 中的產生規則 a → β 的特點,可以將形式文法及其產生的形式語言分類,構成形式語言譜系,也被稱為「喬姆斯基譜系」。

在形式語言的理論中,主要研究四類型的文法、和其所生成的語言(也是現在電腦科學程式語言設計的重點研究項目):

 

假設 $latex G = \left ( S, N, T, P \right ) $ 為一個文法:

(1) 0 型文法 (Type-0 Grammar)

每個推論規則 $latex \alpha \rightarrow \beta$ 無任何限制。

(2) 1 型文法 (Type-1 Grammar)

與上下文有關文法 (Context-Sensitive Grammar),其文法產生規則必須滿足:

 α → β ∈ P,其中 |α| ≤ |β\

規定文法產生規則,左方的符號長度不得大於右方的符號長度

(3) 2 型文法 (Type-2 Grammar)

與上下文無關文法 (Context-Free Grammar),又稱為 BNF 文法。(Backus Normal Form,由開發 Fortan 語言的 John Backus 和 Peter Naur 首先引入、用來描述電腦語言語法的符號集)

文法產生規則必須滿足:

 α → β ∈ P,其中 α ∈ N,  β ∈ (N U T)* – {λ} (λ表示空字串)

規定文法產生規則,左方僅允許長度為 1 之非終端符號

因為 α 符號可以被 β 字串自由替換,而無需考慮 α 符號出現的上下文,故稱為與上下文無關。由於此語法良好的表達能力,幾乎所有程式語言的語法都是用此語法定義。

(4) 3 型文法 (Type-3 Grammar)

正規文法 (Regular Grammar)。

規定文法產生規則,左方僅允許長度為 1 之非終端符號右方僅允許長度為 1 之終端符號

也被應用為「正規表達式」,通常用來定義檢索模式。

 

從 Type-0 到 Type-3 的四種文法、依次擁有越來越嚴格的產生式規則,同時文法所能表達的語言也越來越少。

Type-0 文法必包含 Type-1、Type-2、Type-3;Type-1 文法必包含 Type-2 和 Type-3… 以此類推。

編譯器在編譯時,會對程式碼中的每一條敘述,按照先後順序均做一次之轉換處理、產生對應之目的碼。

這種轉換處理的工作,必須完全遵守該程式語言所規定的文法規則 (grammar rules)。

不同程式語言的文法規則是不相同的。若撰寫程式時違背了程式語言的文法規則,編譯時會發生文法錯誤之訊息。

 

如何讓電腦判斷一段字串是否屬於合法的句子?

給定一個字串,電腦需要判定這個字串,是否屬於我們給定的一個語法 G 、所產生的語言L(G) 。

也就是說,電腦需要判定一個字串是不是屬於這個集合。

在轉換生成語法理論中,一個句子要麼是「正確的」,要麼是「不正確的」。

換句話說,轉換生成語法的規則是一個算法,會對一個句子的合法度(符合語法 Syntax 的程度)進行判斷,但只會得出「是」或「否」的結果。

當我們在寫程式時遇到 Syntax Error 訊息,代表電腦判斷不過你這個句子屬於它看得懂得語言。

要做到這一步,是一個非常難解的問題。實際上涉及到語法分析的問題——給你一個句子,如果這個句子是屬於這個語言的句子的話,那麼你要給出它被構造而出的過程。

這個構造的過程,與我們在形式系統當中進行證明這是一樣的——假設這個命題是正確的,那你要用我一系列的公式、給出一個證明,說明命題是正確的。

同樣的,如果想判定這個句子是屬於這個語言的(命題是正確的),你也必須要給出一個構造的過程——如何用這個產生式一步一步地推出來(證明過程)。

這就叫識別和判定的過程。

一般來講,要讓機器要能判定喬姆斯基的各種類型語法,是一個難解的問題。

好消息是,科學家的確研究出了幾種不同的機器(事實上是數學模型),能拿來判定語言。但因為機器的能力依其強弱不同,所以能判斷的文法範圍也不同:

(1) Type-0 文法產生的語言,能被圖靈機 (Turing Machine) 所辨識

(2) Type 1 文法所產生的語言可被線性限制自動機 (Linear Bounded Automata) 辨識

(3) Type 2 文法所產生的語言可利用推壓自動機 (Push Down Automata) 辨識

(4) Type 3 文法所產生的語言可利用有限狀態自動機 (Finite State Automata) 辨識

規則越嚴越好判定,需要的機器能力越弱。所以「圖靈機」是裡面最強的機器。

由於 Type-3 語言(文法)、也就是正規表達語言,是一個最嚴謹的語言,因此它可以透過一個比較簡單的識別機器來進行判定,也就是上面提到的「有限狀態自動機」。

下一集開始,就讓我們來為大家介紹,什麼是有限狀態自動機吧:)

 

 


  • 後記補充

我們能使用文法來推導出語言,

並判斷一個字串是否屬於該語言:

G 為一個文法,$latex G = \left ( S, N, T, P \right )$

(1) S 為起始符號,$latex S \in N$

(2) $latex N = \left\{ S, A \right\}$

(3) $latex T = \left\{ a, b\right\}$

(4) $latex P = \left\{ S \rightarrow bS, S \rightarrow aS, A \rightarrow bA, A \rightarrow b \right\}$

找出此文法的語言 L(G) :

G 中 由 S 開始的推導過程為——

其中 $latex n\geqslant 0, m\geqslant 1$,所以由 G 所導出的語言為 $latex L(G) = \left \{ b^{n}ab^{m-1} \mid n\geqslant 0, m\geqslant 1 \right \}$

判斷:字串 bbabb 是否屬於這個語言?

推導過程:

S 可導出字串 bbabb,故屬於這個語言。

 

我們也可以設計一個文法,來生成所指定的語言。

設計一文法,能生成語言 $latex L= \left \{ a^{i}b^{i}  \mid i, j \geq 1, i \neq j \right \}$

設計過程:

假設 $latex L{1} = \left \{ a^{i}b^{i} \mid i, j\geq 1, i > j \right \} , L{2} = \left \{ a^{i}b^{i} \mid i, j\geq 1, i <  j \right \} $

令 $latex G{1} = \left ( S, N{1}, T, P{1} \right )$ 為生成 $latex L{1} $ 的文法

$latex T = \left\{ a, b\right\}, N = \left\{A, B \right\} $

  • A 為起始符號,表示 a 出現的個數比 b 出現的個數至少多一個。
  • B 表示 a 出現的個數與 b 出現的個數相同。

因為 a 出現的個數比 b 出現的個數至少多一個可分成兩種情形,一種為剛好多一個、一種為至少多兩個。

  • 剛好多一個: A → aB
  • 至少多二個:A → aA

所以 $latex P{1} $ 包含以下推論規則:

A → aA, A → aB, B → aBb, B → ab

令 $latex G{2} = \left ( S, N{2}, T, P{2} \right ) $ 為生成 $latex L{2} $ 的文法

$latex T = \left\{ a, b \right\}, N = \left\{C, B \right\} $

  • C 為起始符號,表示 a 出現的個數比 b 出現的個數至少少一個。
  • B 表示 a 出現的個數與 b 出現的個數相同。

a 出現的個數比 b 出現的個數至少少一個可分成:剛好少一個、至少少兩個,因此 $latex P{2} $ 包含以下推論規則:

C → Bb, C → Cb, B → aBb, B → ab

欲求的生成語言 $latex L = L{1} \cup L{2}$ ,其文法 $latex G = \left ( S, N, T, P \right )$ 。令:

  • $latex N = N{1} \cup N{2}$
  • $latex P = P{1} \cup P{2} \cup \left\{ S \rightarrow A, S \rightarrow C \right\} $
    • P 包含下列推論規則:
    • S → A, A → aA, A → aB, B → aBb, B → ab, S → C, C → Cb, C → Bb

此即為生成語言 L 的文法 G。