形式文法

在形式语言理论中，文法（为了避免歧义，常称作“形式文法”）是形式语言中字符串的一套产生式规则（英语：Production (computer science)）。这些规则描述了如何用语言的字母表生成符合语法（英语：syntax (programming languages)）的有效的字符串。文法不描述字符串的含义，也不描述在任何上下文中可以用它们做什么——只描述它们的形式。

形式语言理论是应用数学的一个分支，是研究形式文法和语言的学科。它在理論計算機科學、理论语言学、形式语义学、数理逻辑等领域有着广泛的应用。

形式文法是从一个“开始符号”出发的一套重写字符串的规则。因此，文法通常被认为是语言生成器。然而，它有时也可以用作“识别器”（计算机学中的一种函数，用于确定给定字符串是否属于该语言，是否为语法错误）的基础。形式语言理论使用另一个理论来描述识别器，也就是自動機理論。自动机理论有一个有趣的结果，某些形式语言是无法设计出识别器的。^[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. (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 （页面存档备份，存于互联网档案馆）