形式文法

在形式語言理論中，文法（formal grammar)是形式語言中字串的一套產生式規則（production rule）。這些規則描述了如何用語言的字母表生成符合句法(syntax)的有效的字串。文法不描述字串的含義，也不描述在任何上下文中可以用它們做什麼——只描述它們的形式。

形式語言理論是應用數學的一個分支，是研究形式文法和語言的學科。它在理論電腦科學、理論語言學、形式語意學、數理邏輯等領域有着廣泛的應用。

形式文法是從一個「開始符號」出發的一套重寫字串的規則。因此，文法通常被認為是語言生成器。然而，它有時也可以用作「辨識器」（電腦學中的一種函數，用於確定給定字串是否屬於該語言，是否為語法錯誤）的基礎。形式語言理論使用另一個理論來描述辨識器，也就是自動機理論。自動機理論有一個有趣的結果，某些形式語言是無法設計出辨識器的。^[1] 語法分析是通過將一段話語（自然語言中的一個字串）分解成一組符號，並根據語言的語法分析每一個符號的過程。大多數語言的話語含義都是根據其句法結構來確定的——這種做法被稱為組合語意學。因此，在語言中描述話語含義的第一步就是把它分解成若干部分，然後觀察它經過分析後的形式（在電腦科學中被稱為分析樹，在生成文法中被稱為深層結構）。

入門範例

文法主要由一組變換字串的規則組成。（如果它只包含這些規則，那麼它就是一個半圖厄系統（英語：semi-Thue system）。）要在該語言中生成字串，首先需要一個只包含一個開始符號的字串。然後按任意順序應用產生式規則，直到生成既不包含起始符號也不包含指定非終結符號的字串。產生式規則是通過把字串中第一次出現產生式規則左邊的地方，替換成產生式規則的右邊，來作用於這個字串的（參見理論圖靈機的運算）。由文法產生的語言套件含能用這種方式產生的所有不同的字串。開始符號上的任何特定產生式規則序列都會在語言中產生一個不同的字串。如果產生同一個字串有多種不同的方式，那這個文法就是具有二義性的文法了。

例如，假設字母表由 a 和 b 組成，開始符號是 S，我們有以下產生式規則：

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ba}$

那麼我們從 S 開始，選擇一個規則。如果我們選擇規則1，我們將獲得字串 aSb。如果我們再次選擇規則1，我們用 aSb 替換 S，得到字串 aaSbb。如果我們現在選擇規則2，我們將 S 替換為 ba 並獲得字串 aababb，然後就完成了。我們可以用符號將這一系列選擇寫得更簡短：${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$。這種文法的語言就是無限集 ${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$，其中 ${\displaystyle a^{k}}$ 是 ${\displaystyle a}$ 重複 ${\displaystyle k}$ 次（${\displaystyle n}$ 表示使用規則1的次數）。

形式定義

主條目：無限制文法

文法的語法

20世紀50年代，諾姆·喬姆斯基首次提出了生成語法的經典形式化理論，^[2][3] 其中文法 G 由以下部分組成：

• 有限的非終結符號集 N，與 G 生成的字串無交。
• 有限的終結符號集 ${\displaystyle \Sigma }$，與 N 無交。
• 有限的產生式規則集 P，每個規則都為如下形式

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

這裏的 ${\displaystyle {*}}$ 是克萊尼星號，${\displaystyle \cup }$ 表示併集。也就是說，每個產生式規則從一個符號串對映到另一個符號串，並且產生式左側的字串中必須至少包括一個非終結符號。產生式右側的字串如果只有一個 空字串的話，也就是說沒有任何符號的話，它有一個特別的標記（通常是${\displaystyle \Lambda }$、e 或者 ${\displaystyle \epsilon }$）。

• 開始符號 ${\displaystyle S\in N}$，也叫句子符號。

文法的形式定義為四元組 ${\displaystyle (N,\Sigma ,P,S)}$。這種形式語法在文獻中常被稱為重寫系統或短語結構文法（英語：phrase structure grammar）。^[4][5]

關於形式文法的一些數學構造

文法的運算可以用字串的關係來定義:

• 設有文法 ${\displaystyle G=(N,\Sigma ,P,S)}$，${\displaystyle (\Sigma \cup N)^{*}}$ 內的字串的二元關係 ${\displaystyle {\underset {G}{\Rightarrow }}}$（讀作「G經過直接推導為」）定義為：

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• 關係 ${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$（讀作「G經0或更多步推導」）定義為 ${\displaystyle {\underset {G}{\Rightarrow }}}$ 的自反傳遞閉包
• 句型是指可以由開始符號 ${\displaystyle S}$ 經過有限步推導得到的 ${\displaystyle (\Sigma \cup N)^{*}}$ 的一個成員；也就是，句型是 ${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$ 的一個成員。不包含非終結符號（即 ${\displaystyle \Sigma ^{*}}$ 的成員）的句型稱為句子。^[6]
• ${\displaystyle G}$ 的語言，記為 ${\displaystyle {\boldsymbol {L}}(G)}$，定義為從開始符號 ${\displaystyle S}$ 開始經過有限步驟可以推導出的所有句子；也就是集合 ${\displaystyle \left\{w\in \Sigma ^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$。

注意文法 ${\displaystyle G=(N,\Sigma ,P,S)}$ 實際上是半圖厄系統（英語：semi-Thue system） ${\displaystyle (N\cup \Sigma ,P)}$，以完全相同的方式重寫字串；唯一的區別在於我們區分了特定的非終結符號，這些符號必須在重寫規則中重寫，並且只對從指定的開始符號 ${\displaystyle S}$ 到沒有非終結符號的字串的重寫感興趣。

例子

在這些例子中，形式語言使用集合建構式符號描述。

考慮文法 ${\displaystyle G}$，其中 ${\displaystyle N=\left\{S,B\right\}}$，${\displaystyle \Sigma =\left\{a,b,c\right\}}$，${\displaystyle S}$ 是開始符號，${\displaystyle P}$ 由以下產生式規則組成：

1. ${\displaystyle S\rightarrow aBSc}$

2. ${\displaystyle S\rightarrow abc}$

3. ${\displaystyle Ba\rightarrow aB}$

4. ${\displaystyle Bb\rightarrow bb}$

這個文法定義了語言 ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$，這裏 ${\displaystyle a^{n}}$ 表示 n 個 ${\displaystyle a}$ 串連所得的字串。因此，該語言是由1個或更多的 ${\displaystyle a}$，後面跟着相同數量的 ${\displaystyle b}$，接着是相同數量的 ${\displaystyle c}$ 組成的字串集合。

${\displaystyle L(G)}$ 內字串的推導例子如下：

• ${\displaystyle {\boldsymbol {S}}{\underset {2}{\Rightarrow }}{\boldsymbol {abc}}}$
• ${\displaystyle {\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}\\&{\underset {2}{\Rightarrow }}aB{\boldsymbol {abc}}c\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}bcc\\&{\underset {4}{\Rightarrow }}aa{\boldsymbol {bb}}cc\end{aligned}}}$
• ${\displaystyle {\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}{\underset {1}{\Rightarrow }}aB{\boldsymbol {aBSc}}c\\&{\underset {2}{\Rightarrow }}aBaB{\boldsymbol {abc}}cc\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}Babccc{\underset {3}{\Rightarrow }}aaB{\boldsymbol {aB}}bccc{\underset {3}{\Rightarrow }}aa{\boldsymbol {aB}}Bbccc\\&{\underset {4}{\Rightarrow }}aaaB{\boldsymbol {bb}}ccc{\underset {4}{\Rightarrow }}aaa{\boldsymbol {bb}}bccc\end{aligned}}}$

（標記 ${\displaystyle P{\underset {i}{\Rightarrow }}Q}$ 讀作「字串 P 通過產生式 i 生成 Q」，替換的字串用粗體標出。）

喬姆斯基譜系

主條目：喬姆斯基譜系

1956年諾姆·喬姆斯基首次將生成文法形式化時，^[2] 他將它們分為現在稱為喬姆斯基譜系的四種類型。其中兩種重要的文法類型分別是上下文無關文法（2型）和正則文法（3型）。可以用這兩種文法描述的語言分別稱為上下文無關語言和正則語言。儘管比無限制文法（0型，實際上無限制文法可以表示任何圖靈機可以接受的語言）要弱得多，但這兩種受限制的語法最常用，因為它們的解析器可以高效地實現。^[7] 例如，所有正規語言都可以被有限狀態機辨識，對於上下文無關文法的有用子集，有一些著名的演算法可以生成高效的LL剖析器LR剖析器，以辨識文法生成的相應語言。

上下文無關文法

上下文無關文法要求產生式左側只能包含一個符號，並且該符號為非終結符號。這個限制是非常重要的；不是所有的語言都可以由上下文無關的語法生成。那些可以被稱為上下文無關語言。

上例定義的語言 ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$ 並不是一個上下文無關語言，並且這個可以用上下文無關語言的泵引理嚴格證明，但 ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$（1個及以上 ${\displaystyle a}$ 後面跟同樣數量的 ${\displaystyle b}$）是一個上下文無關語言。因為它可以由文法 ${\displaystyle G_{2}}$（${\displaystyle N=\left\{S\right\}}$，${\displaystyle \Sigma =\left\{a,b\right\}}$，${\displaystyle S}$ 為開始符號）定義，用下列產生式規則：

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ab}$

通過Earley演算法（英語：Earley's algorithm）可以在 ${\displaystyle O(n^{3})}$ 時間（參見大O符號）內辨識上下文無關語言。也就是說，對於每一種上下文無關的語言，都可以構建一台以字串為輸入並及時確定字串是否為該語言成員的機器，其中 ${\displaystyle n}$ 是字串的長度。^[8] 確定性上下文無關語言（英語：Deterministic context-free language）是可線上性時間內辨識的上下文無關語言的子集。^[9] 由多種演算法針對這類語言或它的子集。

正則文法

在正則文法中，左側仍然只是一個非終結符號，但右側也受到限制。右側可以是空字串，也可以是單個終結符號，或者是後跟非終結符號的單個終結符號，但不能是其他符號。（有時會使用更寬泛的定義：可以允許更長的終結字串或單個非終結字串，而不能有其他任何東西，從而使語言更易於表示，同時仍然定義同一類語言。）

上面定義的語言 ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$ 不是一個正則語言，但下面這個語言是：${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$（一個或多個 ${\displaystyle a}$ 後面跟着一個或多個 ${\displaystyle b}$，這兩個的數量可以不一樣）。它之所以是正則語言，是因為可以通過文法 ${\displaystyle G_{3}}$ 定義，其中 ${\displaystyle N=\left\{S,A,B\right\}}$，${\displaystyle \Sigma =\left\{a,b\right\}}$，${\displaystyle S}$ 為開始符號，還有如下產生式規則：

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

由正則文法生成的所有語言都可以被有限狀態機在 ${\displaystyle O(n)}$ 時間內辨識出來。雖然在實際應用中，正則文法通常使用正則表達式來表示，但是實際應用中使用的一些正則表達式並沒有嚴格地生成正則語言，也因此沒有表現出線性辨識效能。

生成文法的其他形式

語言學家和電腦科學家對喬姆斯基的形式語法的原始階層進行了許多擴充和變化，通常是為了增強表達能力，或者是為了使分析或解析更加容易。一些形式的文法包括:

• 樹-鄰接文法允許重寫規則在分析樹上操作，而不僅僅是字串，從而提高了傳統生成文法的表達能力。^[10]
• 詞綴文法（英語：Affix grammar）^[11]和屬性文法（英語：attribute grammar）^[12][13]允許通過語意屬性和操作擴充重寫規則，這對於提高語法表達能力和構建實用的語言翻譯工具都很有用。

遞歸文法

提示：此條目頁的主題不是遞歸語言。

遞歸文法是包含遞歸產生式規則的語法。例如，如果存在一個非終結符 A，可以通過產生式規則生成一個以 A 為最左邊符號的字串，那麼上下文無關語言的文法就是左遞歸的。^[14]

分析型文法

儘管有大量關於語法分析演算法的文獻，但這些演算法大多假設要被分析的語言最初是通過生成式文法來描述的，並且目標是將生成式文法轉換成一個有效的語法剖析器。嚴格地說，生成文法不能在任何方面都與解析語言的演算法對應上，而且各種演算法對產生式規則的形式有不同的限制，這些產生式規則被認為是形式良好的。

另一種方法是首先根據分析型文法將語言形式化，分析型文法能更直接地對應於語言剖析器的結構和語意。分析型文法體系的例子包括：

• 語言機器 （頁面存檔備份，存於互聯網檔案館）直接實現了無限制的分析型文法。替換規則用於轉換輸入以產生輸出和行為。該系統還可以生成lm圖 （頁面存檔備份，存於互聯網檔案館），顯示在應用無限制分析型文法規則時的情況。
• 自頂向下的語法分析語言（英語：Top-down parsing language）（TDPL）：一種高度簡約的分析型文法形式，在20世紀70年代早期發展起來，用來研究自頂向下的語法剖析器（英語：Top-down parsing）的行為。^[15]
• 連接文法（英語：Link grammar）：為語言學設計的一種分析型文法形式，它通過檢查詞對之間的位置關係來推導句法結構。^[16][17]
• 解析表達文法（PEG）：圍繞程式語言和編譯器編寫者的實際表達性（英語：Expressivity (computer science)）需求而設計的TDPL的最新概括。^[18]

參見

• 抽象語法樹
• 適應型文法（英語：Adaptive grammar）
• 歧義文法（英語：Ambiguous grammar）
• 巴科斯範式 (BNF)
• 範疇文法（英語：Categorial grammar）
• 分析樹
• 擴充巴科斯範式 (EBNF)
• 語法
• L系統
• 邏輯語
• 後規範系統（英語：Post canonical system）
• 形狀文法（英語：Shape grammar）
• 合式公式

參考文獻

1. Meduna, Alexander, Formal Languages and Computation: Models and Their Applications, CRC Press: 233, 2014 [2019-11-12], ISBN 9781466513457, （原始內容存檔於2020-04-15）. 有關此主題的更多資訊，請參見不可判定問題。
2. Chomsky, Noam. Three models for the description of language. IRE Transactions on Information Theory. Sep 1956, 2 (3): 113–124. doi:10.1109/TIT.1956.1056813.
3. Chomsky, Noam. Syntactic Structures. The Hague: Mouton. 1957.
4. Ginsburg, Seymour. Algebraic and automata theoretic properties of formal languages. North-Holland. 1975: 8–9. ISBN 978-0-7204-2506-2.
5. Harrison, Michael A. Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. 1978: 13. ISBN 978-0-201-02955-0.
6. Sentential Forms （頁面存檔備份，存於互聯網檔案館）, Context-Free Grammars, David Matuszek
7. Grune, Dick & Jacobs, Ceriel H., Parsing Techniques – A Practical Guide, Ellis Horwood, England, 1990.
8. Earley, Jay, "An Efficient Context-Free Parsing Algorithm （頁面存檔備份，存於互聯網檔案館）," Communications of the ACM, Vol. 13 No. 2, pp. 94-102, February 1970.
9. Knuth, D. E. On the translation of languages from left to right (PDF). Information and Control. July 1965, 8 (6): 607–639 [29 May 2011]. doi:10.1016/S0019-9958(65)90426-2. （原始內容 (PDF)存檔於2012-03-15）.
10. Joshi, Aravind K., et al., "Tree Adjunct Grammars （頁面存檔備份，存於互聯網檔案館）," Journal of Computer Systems Science, Vol. 10 No. 1, pp. 136-163, 1975.
11. Koster , Cornelis H. A., "Affix Grammars," in ALGOL 68 Implementation, North Holland Publishing Company, Amsterdam, p. 95-109, 1971.
12. Knuth, Donald E., "Semantics of Context-Free Languages （頁面存檔備份，存於互聯網檔案館）," Mathematical Systems Theory, Vol. 2 No. 2, pp. 127-145, 1968.
13. Knuth, Donald E., "Semantics of Context-Free Languages (correction)," Mathematical Systems Theory, Vol. 5 No. 1, pp 95-96, 1971.
14. Notes on Formal Language Theory and Parsing （頁面存檔備份，存於互聯網檔案館）, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
15. Birman, Alexander, The TMG Recognition Schema （頁面存檔備份，存於互聯網檔案館）, Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.
16. Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.
17. Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Third International Workshop on Parsing Technologies, 1993. (Revised version of above report.)
18. Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking （頁面存檔備份，存於互聯網檔案館）, Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.

外部連結

• Yearly Formal Grammar conference （頁面存檔備份，存於互聯網檔案館）