正规文法

在形式语言理论中，文法（为了避免歧义，常称作“形式文法”）是形式语言中字符串的一套产生式规则（英语：Production (computer science)）。这些规则描述了如何用语言的字母表生成符合语法（英语：syntax (programming languages)）的有效的字符串。文法不描述字符串的含义，也不描述在任何上下文中可以用它们做什么——只描述它们的形式。形式语言理论是应用数学的一个分支，是研究形式文法和语言的学科。它在理论计算机科学、理论语言学、形式语义学、数理逻辑等领域有着广泛的应用。形式文法是从一个“开始符号”出发的一套重写字符串的规则。因此，文法通常被认为是语言生成器。然而，它有时也可以用作“识别器”（计算机学中的一种函数，用于确定给定字符串是否属于该语言，是否为语法错误）的基础。形式语言理论使用另一个理论来描述识别器，也就是自动机理论。自动机理论有一个有趣的结果，某些形式语言是无法设计出识别器的。 语法分析是通过将一段话语（自然语言中的一个字符串）分解成一组符号，并根据语言的语法分析每一个符号的过程。大多数语言的话语含义都是根据其句法结构来确定的——这种做法被称为组合语义学。因此，在语言中描述话语含义的第一步就是把它分解成若干部分，然后观察它经过分析后的形式（在计算机科学中被称为分析树，在生成文法中被称为深层结构）。文法主要由一组变换字符串的规则组成。（如果它只包含这些规则，那么它就是一个半图厄系统（英语：semi-Thue system）。）要在该语言中生成字符串，首先需要一个只包含一个开始符号的字符串。然后按任意顺序应用产生式规则，直到生成既不包含起始符号也不包含指定非终结符号的字符串。产生式规则是通过把字符串中第一次出现产生式规则左边的地方，替换成产生式规则的右边，来作用于这个字符串的（参见理论图灵机的运算）。由文法产生的语言包含能用这种方式产生的所有不同的字符串。开始符号上的任何特定产生式规则序列都会在语言中产生一个不同的字符串。如果产生同一个字符串有多种不同的方式，那这个文法就是具有二义性的文法了。例如，假设字母表由 a 和 b 组成，开始符号是 S，我们有以下产生式规则：那么我们从 S 开始，选择一个规则。如果我们选择规则1，我们将获得字符串 aSb。如果我们再次选择规则1，我们用 aSb 替换 S，得到字符串 aaSbb。如果我们现在选择规则2，我们将 S 替换为 ba 并获得字符串 aababb，然后就完成了。我们可以用符号将这一系列选择写得更简短： S ⇒ a S b ⇒ a a S b b ⇒ a a b a b b {displaystyle SRightarrow aSbRightarrow aaSbbRightarrow aababb} 。这种文法的语言就是无限集 { a n b a b n ∣ n ≥ 0 } = { b a , a b a b , a a b a b b , a a a b a b b b , … } {displaystyle {a^{n}bab^{n}mid ngeq 0}={ba,abab,aababb,aaababbb,dotsc }} ，其中 a k {displaystyle a^{k}} 是 a {displaystyle a} 重复 k {displaystyle k} 次（ n {displaystyle n} 表示使用规则1的次数）。20世纪50年代，诺姆·乔姆斯基首次提出了生成语法的经典形式化理论， 其中文法 G 由以下部分组成：文法的形式定义为四元组 ( N , Σ , P , S ) {displaystyle (N,Sigma ,P,S)} 。这种形式语法在文献中常被称为重写系统或短语结构文法（英语：phrase structure grammar）。文法的运算可以用字符串的关系来定义:注意文法 G = ( N , Σ , P , S ) {displaystyle G=(N,Sigma ,P,S)} 实际上是半图厄系统（英语：semi-Thue system） ( N ∪ Σ , P ) {displaystyle (Ncup Sigma ,P)} ，以完全相同的方式重写字符串；唯一的区别在于我们区分了特定的非终结符号，这些符号必须在重写规则中重写，并且只对从指定的开始符号 S {displaystyle S} 到没有非终结符号的字符串的重写感兴趣。在这些例子中，形式语言使用集合建构式符号描述。考虑文法 G {displaystyle G} ，其中 N = { S , B } {displaystyle N=left{S,Bright}} ， Σ = { a , b , c } {displaystyle Sigma =left{a,b,cright}} ， S {displaystyle S} 是开始符号， P {displaystyle P} 由以下产生式规则组成：这个文法定义了语言 L ( G ) = { a n b n c n ∣ n ≥ 1 } {displaystyle L(G)=left{a^{n}b^{n}c^{n}mid ngeq 1right}} ，这里 a n {displaystyle a^{n}} 表示 n 个 a {displaystyle a} 串连所得的字符串。因此，该语言是由1个或更多的 a {displaystyle a} ，后面跟着相同数量的 b {displaystyle b} ，接着是相同数量的 c {displaystyle c} 组成的字符串集合。L ( G ) {displaystyle L(G)} 内字符串的推导例子如下：1956年诺姆·乔姆斯基首次将生成文法形式化时， 他将它们分为现在称为乔姆斯基谱系的四种类型。其中两种重要的文法类型分别是上下文无关文法（2型）和正则文法（3型）。可以用这两种文法描述的语言分别称为上下文无关语言和正则语言。尽管比无限制文法（0型，实际上无限制文法可以表示任何图灵机可以接受的语言）要弱得多，但这两种受限制的语法最常用，因为它们的解析器可以高效地实现。 例如，所有正则语言都可以被有限状态机识别，对于上下文无关文法的有用子集，有一些著名的算法可以生成高效的LL分析器LR分析器，以识别文法生成的相应语言。上下文无关文法要求产生式左侧只能包含一个符号，并且该符号为非终结符号。这个限制是非常重要的；不是所有的语言都可以由上下文无关的语法生成。那些可以被称为上下文无关语言。上例定义的语言 L ( G ) = { a n b n c n ∣ n ≥ 1 } {displaystyle L(G)=left{a^{n}b^{n}c^{n}mid ngeq 1right}} 并不是一个上下文无关语言，并且这个可以用上下文无关语言的泵引理严格证明，但 { a n b n ∣ n ≥ 1 } {displaystyle left{a^{n}b^{n}mid ngeq 1right}} （1个及以上 a {displaystyle a} 后面跟同样数量的 b {displaystyle b} ）是一个上下文无关语言。因为它可以由文法 G 2 {displaystyle G_{2}} （ N = { S } {displaystyle N=left{Sright}} ， Σ = { a , b } {displaystyle Sigma =left{a,bright}} ， S {displaystyle S} 为开始符号）定义，用下列产生式规则：通过Earley算法（英语：Earley's algorithm）可以在 O ( n 3 ) {displaystyle O(n^{3})} 时间（参见大O符号）内识别上下文无关语言。也就是说，对于每一种上下文无关的语言，都可以构建一台以字符串为输入并及时确定字符串是否为该语言成员的机器，其中 n {displaystyle n} 是字符串的长度。 确定性上下文无关语言（英语：Deterministic context-free language）是可在线性时间内识别的上下文无关语言的子集。 由多种算法针对这类语言或它的子集。在正则文法中，左侧仍然只是一个非终结符号，但右侧也受到限制。右侧可以是空字符串，也可以是单个终结符号，或者是后跟非终结符号的单个终结符号，但不能是其他符号。（有时会使用更宽泛的定义：可以允许更长的终结字符串或单个非终结字符串，而不能有其他任何东西，从而使语言更易于表示，同时仍然定义同一类语言。）上面定义的语言 { a n b n ∣ n ≥ 1 } {displaystyle left{a^{n}b^{n}mid ngeq 1right}} 不是一个正则语言，但下面这个语言是： { a n b m ∣ m , n ≥ 1 } {displaystyle left{a^{n}b^{m}mid m,ngeq 1right}} （一个或多个 a {displaystyle a} 后面跟着一个或多个 b {displaystyle b} ，这两个的数量可以不一样）。它之所以是正则语言，是因为可以通过文法 G 3 {displaystyle G_{3}} 定义，其中 N = { S , A , B } {displaystyle N=left{S,A,Bright}} ， Σ = { a , b } {displaystyle Sigma =left{a,bright}} ， S {displaystyle S} 为开始符号，还有如下产生式规则：由正则文法生成的所有语言都可以被有限状态机在 O ( n ) {displaystyle O(n)} 时间内识别出来。虽然在实际应用中，正则文法通常使用正则表达式来表示，但是实际应用中使用的一些正则表达式并没有严格地生成正则语言，也因此没有表现出线性识别性能。语言学家和计算机科学家对乔姆斯基的形式语法的原始层次结构进行了许多扩展和变化，通常是为了增强表达能力，或者是为了使分析或解析更加容易。一些形式的文法包括:递归文法是包含递归产生式规则的语法。例如，如果存在一个非终结符 A，可以通过产生式规则生成一个以 A 为最左边符号的字符串，那么上下文无关语言的文法就是左递归的。尽管有大量关于语法分析算法的文献，但这些算法大多假设要被分析的语言最初是通过生成式文法来描述的，并且目标是将生成式文法转换成一个有效的语法分析器。严格地说，生成文法不以任何方式对应用于解析语言的算法，而且各种算法对被认为是格式良好的产生式规则的形式有不同的限制。严格地说，生成文法不能在任何方面都与解析语言的算法对应上，而且各种算法对产生式规则的形式有不同的限制，这些产生式规则被认为是形式良好的。另一种方法是首先根据分析型文法将语言形式化，分析型文法能更直接地对应于语言分析器的结构和语义。分析型文法体系的例子包括：