形式文法 在形式语言理论中，文法（为了避免歧义，常称作“形式文法”）是形式语言中字符串的一套。这些规则描述了如何用语言的字母表生成符合的有效的字符串。文法不描述字符串的含义，也不描述在任何上下文中可以用它们做什么——只描述它们的形式。 形式语言理论是应用数学的一个分支，是研究形式文法和语言的学科。它在理论计算机科学、理论语言学、形式语义学、数理逻辑等领域有着广泛的应用。 形式文法是从一个“开始符号”出发的一套重写字符串的规则。因此，文法通常被认为是语言生成器。然而，它有时也可以用作“识别器”（计算机学中的一种函数，用于确定给定字符串是否属于该语言，是否为语法错误）的基础。形式语言理论使用另一个理论来描述识别器，也就是自动机理论。自动机理论有一个有趣的结果，某些形式语言是无法设计出识别器的。 语法分析是通过将一段话语（自然语言中的一个字符串）分解成一组符号，并根据语言的语法分析每一个符号的过程。大多数语言的话语含义都是根据其句法结构来确定的——这种做法被称为组合语义学。因此，在语言中描述话语含义的第一步就是把它分解成若干部分，然后观察它经过分析后的形式（在计算机科学中被称为分析树，在生成文法中被称为深层结构）。 入门示例. 文法主要由一组变换字符串的规则组成。（如果它只包含这些规则，那么它就是一个。）要在该语言中生成字符串，首先需要一个只包含一个开始符号的字符串。然后按任意顺序应用产生式规则，直到生成既不包含起始符号也不包含指定非终结符号的字符串。产生式规则是通过把字符串中第一次出现产生式规则左边的地方，替换成产生式规则的右边，来作用于这个字符串的（参见理论图灵机的运算）。由文法产生的语言包含能用这种方式产生的所有不同的字符串。开始符号上的任何特定产生式规则序列都会在语言中产生一个不同的字符串。如果产生同一个字符串有多种不同的方式，那这个文法就是具有二义性的文法了。 例如，假设字母表由 "a" 和 "b" 组成，开始符号是 "S"，我们有以下产生式规则： 1. formula_1 2. formula_2 那么我们从 "S" 开始，选择一个规则。如果我们选择规则1，我们将获得字符串 "aSb"。如果我们再次选择规则1，我们用 "aSb" 替换 "S"，得到字符串 "aaSbb"。如果我们现在选择规则2，我们将 "S" 替换为 "ba" 并获得字符串 "aababb"，然后就完成了。我们可以用符号将这一系列选择写得更简短：formula_3。这种文法的语言就是无限集 formula_4，其中 formula_5 是 formula_6 重复 formula_7 次（formula_8 表示使用规则1的次数）。 形式定义. 文法的语法. 20世纪50年代，诺姆·乔姆斯基首次提出了生成语法的经典形式化理论， 其中文法 "G" 由以下部分组成： formula_10 这里的 formula_11 是克莱尼星号，formula_12 表示并集。也就是说，每个产生式规则从一个符号串映射到另一个符号串，并且产生式左侧的字符串中必须至少包括一个非终结符号。产生式右侧的字符串如果只有一个 空字符串的话，也就是说没有任何符号的话，它有一个特别的标记（通常是formula_13、"e" 或者 formula_14）。 文法的形式定义为四元组 formula_16。这种形式语法在文献中常被称为重写系统或。 关于形式文法的一些数学构造. 文法的运算可以用字符串的关系来定义: 注意文法 formula_17 实际上是 formula_32，以完全相同的方式重写字符串；唯一的区别在于我们区分了特定的非终结符号，这些符号必须在重写规则中重写，并且只对从指定的开始符号 formula_23 到没有非终结符号的字符串的重写感兴趣。 例子. "在这些例子中，形式语言使用集合建构式符号描述。" 考虑文法 formula_27，其中 formula_35，formula_36，formula_23 是开始符号，formula_38 由以下产生式规则组成： 1. formula_39 2. formula_40 3. formula_41 4. formula_42 这个文法定义了语言 formula_43，这里 formula_44 表示 "n" 个 formula_6 串连所得的字符串。因此，该语言是由1个或更多的 formula_6，后面跟着相同数量的 formula_47，接着是相同数量的 formula_48 组成的字符串集合。 formula_49 内字符串的推导例子如下： * formula_50 （标记 formula_53 读作“字符串 P 通过产生式 i 生成 Q”，替换的字符串用粗体标出。） 乔姆斯基谱系. 1956年诺姆·乔姆斯基首次将生成文法形式化时， 他将它们分为现在称为乔姆斯基谱系的四种类型。其中两种重要的文法类型分别是上下文无关文法（2型）和正则文法（3型）。可以用这两种文法描述的语言分别称为上下文无关语言和正则语言。尽管比无限制文法（0型，实际上无限制文法可以表示任何图灵机可以接受的语言）要弱得多，但这两种受限制的语法最常用，因为它们的解析器可以高效地实现。 例如，所有正规语言都可以被有限状态机识别，对于上下文无关文法的有用子集，有一些著名的算法可以生成高效的LL剖析器LR剖析器，以识别文法生成的相应语言。 上下文无关文法. 上下文无关文法要求产生式左侧只能包含一个符号，并且该符号为非终结符号。这个限制是非常重要的；不是所有的语言都可以由上下文无关的语法生成。那些可以被称为上下文无关语言。 上例定义的语言 formula_43 并不是一个上下文无关语言，并且这个可以用上下文无关语言的泵引理严格证明，但 formula_55（1个及以上 formula_6 后面跟同样数量的 formula_47）是一个上下文无关语言。因为它可以由文法 formula_58（formula_59，formula_60，formula_23 为开始符号）定义，用下列产生式规则： 1. formula_1 2. formula_63 通过可以在 formula_64 时间（参见大O符号）内识别上下文无关语言。也就是说，对于每一种上下文无关的语言，都可以构建一台以字符串为输入并及时确定字符串是否为该语言成员的机器，其中 formula_8 是字符串的长度。 是可在线性时间内识别的上下文无关语言的子集。 由多种算法针对这类语言或它的子集。 正则文法. 在正则文法中，左侧仍然只是一个非终结符号，但右侧也受到限制。右侧可以是空字符串，也可以是单个终结符号，或者是后跟非终结符号的单个终结符号，但不能是其他符号。（有时会使用更宽泛的定义：可以允许更长的终结字符串或单个非终结字符串，而不能有其他任何东西，从而使语言更易于表示，同时仍然定义同一类语言。） 上面定义的语言 formula_55 不是一个正则语言，但下面这个语言是：formula_67（一个或多个 formula_6 后面跟着一个或多个 formula_47，这两个的数量可以不一样）。它之所以是正则语言，是因为可以通过文法 formula_70 定义，其中 formula_71，formula_60，formula_23 为开始符号，还有如下产生式规则： # formula_74 # formula_75 # formula_76 # formula_77 # formula_78 由正则文法生成的所有语言都可以被有限状态机在 formula_79 时间内识别出来。虽然在实际应用中，正则文法通常使用正则表达式来表示，但是实际应用中使用的一些正则表达式并没有严格地生成正则语言，也因此没有表现出线性识别性能。 生成文法的其他形式. 语言学家和计算机科学家对乔姆斯基的形式语法的原始层次结构进行了许多扩展和变化，通常是为了增强表达能力，或者是为了使分析或解析更加容易。一些形式的文法包括: 递归文法. 递归文法是包含递归产生式规则的语法。例如，如果存在一个非终结符 "A"，可以通过产生式规则生成一个以 "A" 为最左边符号的字符串，那么上下文无关语言的文法就是左递归的。 分析型文法. 尽管有大量关于语法分析算法的文献，但这些算法大多假设要被分析的语言最初是通过生成式文法来描述的，并且目标是将生成式文法转换成一个有效的语法分析器。严格地说，生成文法不能在任何方面都与解析语言的算法对应上，而且各种算法对产生式规则的形式有不同的限制，这些产生式规则被认为是形式良好的。 另一种方法是首先根据分析型文法将语言形式化，分析型文法能更直接地对应于语言分析器的结构和语义。分析型文法体系的例子包括： 参见.